Elementary cellular automaton/Infinite length
The purpose of this task is to create a version of an Elementary cellular automaton whose number of cells is only limited by the memory size of the computer.
To be precise, consider the state of the automaton to be made of an infinite number of cells, but with a bounded support. In other words, to describe the state of the automaton, you need a finite number of adjacent cells, along with their individual state, and you then consider that the individual state of each of all other cells is the negation of the closest individual cell among the previously defined finite number of cells.
Examples:
1 -> ..., 0, 0, 1, 0, 0, ... 0, 1 -> ..., 1, 1, 0, 1, 0, 0, ... 1, 0, 1 -> ..., 0, 0, 1, 0, 1, 0, 0, ...
More complex methods can be imagined, provided it is possible to somehow encode the infinite sections. But for this task we will stick to this simple version.
D
<lang d>import std.stdio, std.array, std.range, std.typecons, std.string, std.conv; alias R = replicate;
void main() {
enum nLines = 25; enum notCell = (in char c) pure => (c == '1') ? "0" : "1";
foreach (immutable rule; [90, 30]) {
writeln("\nRule: ", rule);
immutable ruleBits = "%08b".format(rule).retro.text;
const neighs2next = 8.iota
.map!(n => tuple("%03b".format(n), [ruleBits[n]]))
.assocArray;
string C = "1";
foreach (immutable i; 0 .. nLines) {
writefln("%2d: %s%s", i, " ".R(nLines - i), C.tr("01", ".#"));
C = notCell(C[0]).R(2) ~ C ~ notCell(C[$ - 1]).R(2);
C = iota(1, C.length - 1)
.map!(i => neighs2next[C[i - 1 .. i + 2]])
.join;
}
}
}</lang> The output is the same as the Python entry.
Perl
The edges of a pattern is implicitly repeating. The code will try to lineup output by padding up to 40 spaces to the left, but since the cells keep expanding, that has to end somewhere. <lang perl>sub evolve { my ($rule, $_) = @_; my $offset = 0;
while (1) { my ($l, $r, $st); s/^((.)\g2*)/$2$2/ and $l = $2, $offset -= length($2); s/(.)\g1*$/$1$1/ and $r = $1;
$st = $_;
tr/01/.#/; printf "%5d| %s%s\n", $offset, ' ' x (40 + $offset), $_;
$_ = join , map(1 & ($rule>>oct "0b$_"), $l x 3, map(substr($st, $_, 3), 0 .. length($st)-3), $r x 3); } }
evolve(90, "010");</lang>
- Output:
-1| ..#.. -2| ..#.#.. -3| ..#...#.. -4| ..#.#.#.#.. -5| ..#.......#.. -6| ..#.#.....#.#.. -7| ..#...#...#...#.. -8| ..#.#.#.#.#.#.#.#.. -9| ..#...............#.. -10| ..#.#.............#.#.. -11| ..#...#...........#...#.. -12| ..#.#.#.#.........#.#.#.#.. -13| ..#.......#.......#.......#.. ---(infinite more lines snipped)---
Python
Infinite generator but only print 25 lines of each rule.
<lang python>def _notcell(c):
return '0' if c == '1' else '1'
def eca_infinite(cells, rule):
lencells = len(cells)
rulebits = '{0:08b}'.format(rule)
neighbours2next = {'{0:03b}'.format(n):rulebits[::-1][n] for n in range(8)}
c = cells
while True:
yield c
c = _notcell(c[0])*2 + c + _notcell(c[-1])*2 # Extend and pad the ends
c = .join(neighbours2next[c[i-1:i+2]] for i in range(1,len(c) - 1))
#yield c[1:-1]
if __name__ == '__main__':
lines = 25
for rule in (90, 30):
print('\nRule: %i' % rule)
for i, c in zip(range(lines), eca_infinite('1', rule)):
print('%2i: %s%s' % (i, ' '*(lines - i), c.replace('0', '.').replace('1', '#')))</lang>
- Output:
Rule: 90 0: # 1: #.# 2: #...# 3: #.#.#.# 4: #.......# 5: #.#.....#.# 6: #...#...#...# 7: #.#.#.#.#.#.#.# 8: #...............# 9: #.#.............#.# 10: #...#...........#...# 11: #.#.#.#.........#.#.#.# 12: #.......#.......#.......# 13: #.#.....#.#.....#.#.....#.# 14: #...#...#...#...#...#...#...# 15: #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# 16: #...............................# 17: #.#.............................#.# 18: #...#...........................#...# 19: #.#.#.#.........................#.#.#.# 20: #.......#.......................#.......# 21: #.#.....#.#.....................#.#.....#.# 22: #...#...#...#...................#...#...#...# 23: #.#.#.#.#.#.#.#.................#.#.#.#.#.#.#.# 24: #...............#...............#...............# Rule: 30 0: # 1: ### 2: ##..# 3: ##.#### 4: ##..#...# 5: ##.####.### 6: ##..#....#..# 7: ##.####..###### 8: ##..#...###.....# 9: ##.####.##..#...### 10: ##..#....#.####.##..# 11: ##.####..##.#....#.#### 12: ##..#...###..##..##.#...# 13: ##.####.##..###.###..##.### 14: ##..#....#.###...#..###..#..# 15: ##.####..##.#..#.#####..####### 16: ##..#...###..####.#....###......# 17: ##.####.##..###....##..##..#....### 18: ##..#....#.###..#..##.###.####..##..# 19: ##.####..##.#..######..#...#...###.#### 20: ##..#...###..####.....####.###.##...#...# 21: ##.####.##..###...#...##....#...#.#.###.### 22: ##..#....#.###..#.###.##.#..###.##.#.#...#..# 23: ##.####..##.#..###.#...#..####...#..#.##.###### 24: ##..#...###..####...##.#####...#.#####.#..#.....#
Racket
Uses solution to Elementary cellular automata saved in file "Elementary_cellular_automata.rkt"
<lang racket>#lang racket
- below is the code from the parent task
(require "Elementary_cellular_automata.rkt") (require racket/fixnum)
(define (wrap-rule-infinite v-in vl-1 offset)
(define l-bit-set? (bitwise-bit-set? (fxvector-ref v-in 0) usable-bits/fixnum-1))
(define r-bit-set? (bitwise-bit-set? (fxvector-ref v-in vl-1) 0))
;; if we need to extend left offset is reduced by 1
(define l-pad-words (if l-bit-set? 1 0))
(define r-pad-words (if r-bit-set? 1 0))
(define new-words (fx+ l-pad-words r-pad-words))
(cond
[(fx= 0 new-words) (values v-in vl-1 offset)] ; nothing changes
[else
(define offset- (if l-bit-set? (fx- offset 1) offset))
(define l-sequence (if l-bit-set? (in-value 0) (in-sequences)))
(define vl-1+ (fx+ vl-1 (fx+ l-pad-words r-pad-words)))
(define v-out
(for/fxvector
#:length (fx+ vl-1+ 1) #:fill 0 ; this provides suitable right padding
((f (in-sequences l-sequence (in-fxvector v-in)))) f))
(values v-out vl-1+ offset-)]))
(module+ main
(define ng/90/infinite (CA-next-generation 90 #:wrap-rule wrap-rule-infinite))
(for/fold ((v (fxvector #b10000000000000000000))
(o 1)) ; start by pushing output right by one
((step (in-range 40)))
(show-automaton v #:step step #:push-right o)
(newline)
(ng/90/infinite v o)))</lang>
- Output:
[ 0] ..............................000000000010000000000000000000 [ 1] ..............................000000000101000000000000000000 [ 2] ..............................000000001000100000000000000000 [ 3] ..............................000000010101010000000000000000 [ 4] ..............................000000100000001000000000000000 [ 5] ..............................000001010000010100000000000000 [ 6] ..............................000010001000100010000000000000 [ 7] ..............................000101010101010101000000000000 [ 8] ..............................001000000000000000100000000000 [ 9] ..............................010100000000000001010000000000 [ 10] ..............................100010000000000010001000000000 [ 11] 000000000000000000000000000001010101000000000101010100000000 [ 12] 000000000000000000000000000010000000100000001000000010000000 [ 13] 000000000000000000000000000101000001010000010100000101000000 [ 14] 000000000000000000000000001000100010001000100010001000100000 [ 15] 000000000000000000000000010101010101010101010101010101010000 [ 16] 000000000000000000000000100000000000000000000000000000001000 [ 17] 000000000000000000000001010000000000000000000000000000010100 [ 18] 000000000000000000000010001000000000000000000000000000100010 [ 19] 000000000000000000000101010100000000000000000000000001010101 [ 20] 000000000000000000001000000010000000000000000000000010000000100000000000000000000000000000 [ 21] 000000000000000000010100000101000000000000000000000101000001010000000000000000000000000000 [ 22] 000000000000000000100010001000100000000000000000001000100010001000000000000000000000000000 [ 23] 000000000000000001010101010101010000000000000000010101010101010100000000000000000000000000 [ 24] 000000000000000010000000000000001000000000000000100000000000000010000000000000000000000000 [ 25] 000000000000000101000000000000010100000000000001010000000000000101000000000000000000000000 [ 26] 000000000000001000100000000000100010000000000010001000000000001000100000000000000000000000 [ 27] 000000000000010101010000000001010101000000000101010100000000010101010000000000000000000000 [ 28] 000000000000100000001000000010000000100000001000000010000000100000001000000000000000000000 [ 29] 000000000001010000010100000101000001010000010100000101000001010000010100000000000000000000 [ 30] 000000000010001000100010001000100010001000100010001000100010001000100010000000000000000000 [ 31] 000000000101010101010101010101010101010101010101010101010101010101010101000000000000000000 [ 32] 000000001000000000000000000000000000000000000000000000000000000000000000100000000000000000 [ 33] 000000010100000000000000000000000000000000000000000000000000000000000001010000000000000000 [ 34] 000000100010000000000000000000000000000000000000000000000000000000000010001000000000000000 [ 35] 000001010101000000000000000000000000000000000000000000000000000000000101010100000000000000 [ 36] 000010000000100000000000000000000000000000000000000000000000000000001000000010000000000000 [ 37] 000101000001010000000000000000000000000000000000000000000000000000010100000101000000000000 [ 38] 001000100010001000000000000000000000000000000000000000000000000000100010001000100000000000 [ 39] 010101010101010100000000000000000000000000000000000000000000000001010101010101010000000000 #fx(536879104 0 33554944) 0
Ruby
<lang ruby>def notcell(c)
c.tr('01','10')
end
def eca_infinite(cells, rule)
neighbours2next = Hash[8.times.map{|i|["%03b"%i, "01"[rule[i]]]}]
c = cells
Enumerator.new do |y|
loop do
y << c
c = notcell(c[0])*2 + c + notcell(c[-1])*2 # Extend and pad the ends
c = (1..c.size-2).map{|i| neighbours2next[c[i-1..i+1]]}.join
end
end
end
if __FILE__ == $0
lines = 25
for rule in [90, 30]
puts "\nRule: %i" % rule
for i, c in (0...lines).zip(eca_infinite('1', rule))
puts '%2i: %s%s' % [i, ' '*(lines - i), c.tr('01', '.#')]
end
end
end</lang> The output is the same as the Python entry.
Tcl
<lang tcl>package require Tcl 8.6
oo::class create InfiniteElementaryAutomaton {
variable rules
# Decode the rule number to get a collection of state mapping rules.
# In effect, "compiles" the rule number
constructor {ruleNumber} {
set ins {111 110 101 100 011 010 001 000} set bits [split [string range [format %08b $ruleNumber] end-7 end] ""] foreach input {111 110 101 100 011 010 001 000} state $bits { dict set rules $input $state }
}
# Apply the rule to an automaton state to get a new automaton state.
# We wrap the edges; the state space is circular.
method evolve {left state right} {
set state [list $left {*}$state $right] set len [llength $state] for {set i -1;set j 0;set k 1} {$j < $len} {incr i;incr j;incr k} { set a [expr {$i<0 ? $left : [lindex $state $i]}] set b [lindex $state $j] set c [expr {$k==$len ? $right : [lindex $state $k]}] lappend result [dict get $rules $a$b$c] } return $result
}
method evolveEnd {endState} {
return [dict get $rules $endState$endState$endState]
}
# Simple driver method; omit the initial state to get a centred dot
method run {steps {initialState "010"}} {
set cap [string repeat "\u2026" $steps] set s [split [string map ". 0 # 1" $initialState] ""] set left [lindex $s 0] set right [lindex $s end] set s [lrange $s 1 end-1] for {set i 0} {$i < $steps} {incr i} { puts $cap[string map "0 . 1 #" $left[join $s ""]$right]$cap set s [my evolve $left $s $right] set left [my evolveEnd $left] set right [my evolveEnd $right] set cap [string range $cap 1 end] } puts $cap[string map "0 . 1 #" $left[join $s ""]$right]$cap
}
}
foreach num {90 30} {
puts "Rule ${num}:"
set rule [InfiniteElementaryAutomaton new $num]
$rule run 25
$rule destroy
}</lang>
- Output:
Rule 90: ………………………………………………………………….#.………………………………………………………………… ……………………………………………………………….#.#.……………………………………………………………… …………………………………………………………….#...#.…………………………………………………………… ………………………………………………………….#.#.#.#.………………………………………………………… ……………………………………………………….#.......#.……………………………………………………… …………………………………………………….#.#.....#.#.…………………………………………………… ………………………………………………….#...#...#...#.………………………………………………… ……………………………………………….#.#.#.#.#.#.#.#.……………………………………………… …………………………………………….#...............#.…………………………………………… ………………………………………….#.#.............#.#.………………………………………… ……………………………………….#...#...........#...#.……………………………………… …………………………………….#.#.#.#.........#.#.#.#.…………………………………… ………………………………….#.......#.......#.......#.………………………………… ……………………………….#.#.....#.#.....#.#.....#.#.……………………………… …………………………….#...#...#...#...#...#...#...#.…………………………… ………………………….#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.………………………… ……………………….#...............................#.……………………… …………………….#.#.............................#.#.…………………… ………………….#...#...........................#...#.………………… ……………….#.#.#.#.........................#.#.#.#.……………… …………….#.......#.......................#.......#.…………… ………….#.#.....#.#.....................#.#.....#.#.………… ……….#...#...#...#...................#...#...#...#.……… …….#.#.#.#.#.#.#.#.................#.#.#.#.#.#.#.#.…… ….#...............#...............#...............#.… .#.#.............#.#.............#.#.............#.#. Rule 30: ………………………………………………………………….#.………………………………………………………………… ……………………………………………………………….###.……………………………………………………………… …………………………………………………………….##..#.…………………………………………………………… ………………………………………………………….##.####.………………………………………………………… ……………………………………………………….##..#...#.……………………………………………………… …………………………………………………….##.####.###.…………………………………………………… ………………………………………………….##..#....#..#.………………………………………………… ……………………………………………….##.####..######.……………………………………………… …………………………………………….##..#...###.....#.…………………………………………… ………………………………………….##.####.##..#...###.………………………………………… ……………………………………….##..#....#.####.##..#.……………………………………… …………………………………….##.####..##.#....#.####.…………………………………… ………………………………….##..#...###..##..##.#...#.………………………………… ……………………………….##.####.##..###.###..##.###.……………………………… …………………………….##..#....#.###...#..###..#..#.…………………………… ………………………….##.####..##.#..#.#####..#######.………………………… ……………………….##..#...###..####.#....###......#.……………………… …………………….##.####.##..###....##..##..#....###.…………………… ………………….##..#....#.###..#..##.###.####..##..#.………………… ……………….##.####..##.#..######..#...#...###.####.……………… …………….##..#...###..####.....####.###.##...#...#.…………… ………….##.####.##..###...#...##....#...#.#.###.###.………… ……….##..#....#.###..#.###.##.#..###.##.#.#...#..#.……… …….##.####..##.#..###.#...#..####...#..#.##.######.…… ….##..#...###..####...##.#####...#.#####.#..#.....#.… .##.####.##..###...#.##..#....#.##.#.....#####...###.