Download

← Examples

rule110

Rule 110, a one-dimensional cellular automaton, one row per generation.

examples/rule110 in the repository.

// Rule 110: a one-dimensional cellular automaton famously proven to be
// Turing-complete. Each cell's next state is a fixed function of its own
// state and its two neighbours' states ; the lookup table for those eight
// (left, mid, right) bit-patterns is the binary encoding of 110 (0b01101110).
//
// Boundaries wrap around so the row stays a closed loop ; the initial
// generation has a single live cell on the right end, which is the seed
// classically used to display the rule's drift to the left.

module "main"

import "std/io"
import "std/string_builder"

GENERATIONS :: 100
WIDTH       :: GENERATIONS

// Rule 110, as a bit pattern. `next_cell(l, m, r)` reads bit `(l<<2 | m<<1 | r)`
// out of this byte to decide the centre cell's next state.
RULE :: 110

next_cell :: fn(left: i32, mid: i32, right: i32) -> i32 {
    pattern :: (left << 0b10) | (mid << 0b01) | right << 0b00
    return (RULE >> pattern) & 1
}

// The next row, built fresh from `row`.
step :: fn(row: i32[]) -> i32[] {
    n :: row.len()
    next: i32[]: []
    for i in 0..<n {
        // Wrap-around so the row is a closed loop.
        left  :: row[(i - 1 + n) % n]
        mid   :: row[i]
        right :: row[(i + 1) % n]
        next.push(next_cell(left, mid, right))
    }
    return next
}

format_row :: fn(row: i32[]) -> string {
    sb :: StringBuilder {}
    for cell in row {
        if cell == 1 {
            sb.append_char('#')
        } else {
            sb.append_char(' ')
        }
    }
    return sb.to_string()
}

main :: fn() -> i32 {
    row: i32[] = []
    for i in 0..<WIDTH {
        // Seed: a single live cell on the right end.
        row.push(if i == WIDTH - 1 { 1 } else { 0 })
    }

    for 0..<GENERATIONS {
        println(format_row(row))
        row = step(row)
    }
    return 0
}