Elementary cellular automaton: Difference between revisions
Content added Content deleted
m (→{{header|Racket}}: stub added) |
(→{{header|Racket}}: actual implementation added) |
||
| Line 890: | Line 890: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
This is the base code for the three elementary CA tasks. The "wrap" code is a little over-complicated for the simple cases of wrapping on word boundaries and for CA's with a narrower word. However, it will be used unmodified for [Elementary |
This is the base code for the three elementary CA tasks. The "wrap" code is a little over-complicated for the simple cases of wrapping on word boundaries and for CA's with a narrower word. However, it will be used unmodified for [[Elementary cellular automaton/Infinite length]]. |
||
<lang racket> |
<lang racket>#lang racket |
||
(require racket/fixnum) |
|||
</lang> |
|||
(provide usable-bits/fixnum usable-bits/fixnum-1 CA-next-generation show-automaton) |
|||
(define usable-bits/fixnum 30) |
|||
(define usable-bits/fixnum-1 (sub1 usable-bits/fixnum)) |
|||
(define usable-bits/mask (fx- (fxlshift 1 usable-bits/fixnum) 1)) |
|||
(define 2^u-b-1 (fxlshift 1 usable-bits/fixnum-1)) |
|||
(define (shift-right-1-bit-with-lsb-L L n) |
|||
(fxior (if (bitwise-bit-set? L 0) 2^u-b-1 0) (fxrshift n 1))) |
|||
(define (shift-left-1-bit-with-msb-R n R) |
|||
(fxior (fxand usable-bits/mask (fxlshift n 1)) (if (bitwise-bit-set? R usable-bits/fixnum-1) 1 0))) |
|||
(define ((CA-next-bit-state rule) L n R) |
|||
(for/fold ((n+ 0)) |
|||
((b (in-range usable-bits/fixnum-1 -1 -1))) |
|||
(define bit.2 (if (bitwise-bit-set? (shift-right-1-bit-with-lsb-L L n) b) 4 0)) |
|||
(define bit.1 (if (bitwise-bit-set? n b) 2 0)) |
|||
(define bit.0 (if (bitwise-bit-set? (shift-left-1-bit-with-msb-R n R) b) 1 0)) |
|||
(define rule-bit (fxior bit.2 (fxior bit.1 bit.0))) |
|||
(values (fxior (fxlshift n+ 1) (if (bitwise-bit-set? rule rule-bit) 1 0))))) |
|||
;; CA-next-generation generates a function which takes: |
|||
;; v-in : an fxvector representing the CA's current state as a bit field. This may be mutated |
|||
;; offset : the offset of the leftmost element of v-in; this is used in infinite CA to allow the CA |
|||
;; to occupy negative indices |
|||
;; wrap-rule : provided for automata that are not an integer number of usable-bits/fixnum bits wide |
|||
;; wrap-rule = #f - v-in and offset are unchanged |
|||
;; wrap-rule : (v-in vl-1 offset) -> (values v-out vl-1+ offset-) |
|||
;; v-in as passed into CA-next-generation |
|||
;; vl-1=(sub1 (length v-in)), since its precomputed vaule is needed |
|||
;; offset as passed into CA-next-generation |
|||
;; v-out: either a new copy of v-in, or v-in itself (which might be mutated) |
|||
;; vl-1+: (sub1 (length v-out)) |
|||
;; offset- : a new value for offset (it will have decreased since the CA grows to the left |
|||
;; with offset, and to the right with (length v-out) |
|||
(define (CA-next-generation rule #:wrap-rule (wrap-rule #f)) |
|||
(define next-state (CA-next-bit-state rule)) |
|||
(lambda (v-in offset) |
|||
(define vl-1 (fx- (fxvector-length v-in) 1)) |
|||
(define-values (v+ v+l-1 offset-) ((or wrap-rule values) v-in vl-1 offset)) |
|||
(define rv |
|||
(for/fxvector |
|||
((l (in-sequences (in-value (fxvector-ref v+ v+l-1)) (in-fxvector v+))) |
|||
(n (in-fxvector v+)) |
|||
(r (in-sequences (in-fxvector v+ 1) (in-value (fxvector-ref v+ 0))))) |
|||
(next-state l n r))) |
|||
(values rv offset-))) |
|||
;; CA-next-generation with the default (non) wrap rule wraps the MSB of the left-hand word (L) and the |
|||
;; LSB of the right-hand word (R) in the CA. If the CA is not a multiple of usable-bits/fixnum wide, |
|||
;; then we use this function to put these bits where they can be used... i.e. the actual MSB is copied |
|||
;; to the word's MSB and the LSB is copied to the bit that is to the left of the actual MSB. |
|||
(define (wrap-rule-truncate-left-word sig-bits) |
|||
(define wlb-mask (fx- (fxlshift 1 sig-bits) 1)) |
|||
(unless (fx< sig-bits (fx- usable-bits/fixnum 1)) |
|||
(error "we need at least 2 bits in the top of the word to do this safely")) |
|||
(lambda (v-in vl-1 offset) |
|||
(define v0 (fxvector-ref v-in 0)) |
|||
;; this must wrap to wlb of the first word |
|||
(define last-bit (fxlshift (fxand 1 (fxvector-ref v-in vl-1)) sig-bits)) |
|||
;; this must wrap to the extreme left of the first word |
|||
(define first-bit (if (bitwise-bit-set? v0 (fx- sig-bits 1)) 2^u-b-1 0)) |
|||
(fxvector-set! v-in 0 (fxior (fxior last-bit first-bit) (fxand v0 wlb-mask))) |
|||
(values v-in vl-1 offset))) |
|||
;; This displays a state of the CA |
|||
(define (show-automaton v #:step (step #f) #:sig-bits (sig-bits #f) #:push-right (push-right #f)) |
|||
(when step (printf "[~a] " (~a #:align 'right #:width 10 step))) |
|||
(when push-right (display (make-string (* usable-bits/fixnum push-right) #\.))) |
|||
(when (number? sig-bits) |
|||
(display (~a #:width sig-bits #:align 'right #:pad-string "0" |
|||
(number->string (fxvector-ref v 0) 2)))) |
|||
(for ((n (in-fxvector v (if sig-bits 1 0)))) |
|||
(display (~a #:width usable-bits/fixnum #:align 'right #:pad-string "0" (number->string n 2))))) |
|||
(module+ main |
|||
(define ng/122/19-bits (CA-next-generation 122 #:wrap-rule (wrap-rule-truncate-left-word 19))) |
|||
(for/fold ((v (fxvector #b1000000000)) (o 0)) ((step (in-range 40))) |
|||
(show-automaton v #:step step #:sig-bits 19) |
|||
(newline) |
|||
(ng/122/19-bits v o)))</lang> |
|||
{{out}} |
{{out}} |
||
<pre>[ 0] 0000000001000000000 |
|||
<pre> |
|||
[ 1] 0000000010100000000 |
|||
</pre> |
|||
[ 2] 0000000101010000000 |
|||
[ 3] 0000001010101000000 |
|||
[ 4] 0000010101010100000 |
|||
[ 5] 0000101010101010000 |
|||
[ 6] 0001010101010101000 |
|||
[ 7] 0010101010101010100 |
|||
[ 8] 0101010101010101010 |
|||
[ 9] 1010101010101010101 |
|||
[ 10] 1100000001111010101 |
|||
[ 11] 1100000001101101010 |
|||
[ 12] 1111010101010101111 |
|||
[ 13] 1100000001100011010 |
|||
[ 14] 0011110101010111100 |
|||
[ 15] 0110011010101100110 |
|||
[ 16] 1111111101011111111 |
|||
[ 17] 1100000001100000001 |
|||
[ 18] 0000001111111000000 |
|||
[ 19] 0000011000001100000 |
|||
[ 20] 0000111100011110000 |
|||
[ 21] 0001100110110011000 |
|||
[ 22] 0011111111111111100 |
|||
[ 23] 0110000000000000110 |
|||
[ 24] 1111000000000001111 |
|||
[ 25] 1100000001100011000 |
|||
[ 26] 0011110000000111100 |
|||
[ 27] 0110011000001100110 |
|||
[ 28] 1111111100011111111 |
|||
[ 29] 1100000001100000001 |
|||
[ 30] 0000001111111000000 |
|||
[ 31] 0000011000001100000 |
|||
[ 32] 0000111100011110000 |
|||
[ 33] 0001100110110011000 |
|||
[ 34] 0011111111111111100 |
|||
[ 35] 0110000000000000110 |
|||
[ 36] 1111000000000001111 |
|||
[ 37] 1100000001100011000 |
|||
[ 38] 0011110000000111100 |
|||
[ 39] 0110011000001100110 |
|||
#fx(522495) |
|||
0</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Revision as of 19:18, 12 January 2015
Elementary cellular automaton is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
An elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states (labeled 0 and 1) and the rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors. Those three values can be encoded with three bits.
The rules of evolution are then encoded with eight bits indicating the outcome of each of the eight possibilities 111, 110, 101, 100, 011, 010, 001 and 000 in this order. Thus for instance the rule 13 means that a state is updated to 1 only in the cases 011, 010 and 000, since 13 in binary is 0b00001101.
The purpose of this task is to create a subroutine, program or function that allows to create and visualize the evolution of any of the 256 possible elementary cellular automaton of arbitrary space length and for any given initial state. You can demonstrate your solution with any automaton of your choice.
The space state should wrap: this means that the left-most cell should be considered as the right neighbor of the right-most cell, and reciprocally.
This task is basically a generalization of one-dimensional cellular automaton.
AutoHotkey
<lang AutoHotkey>state := StrSplit("0000000001000000000") rule := 90 output := "Rule: " rule Loop, 10 { output .= "`n" A_Index "`t" PrintState(state) state := NextState(state, rule) } Gui, Font,, Courier New Gui, Add, Text,, % output Gui, Show return
GuiClose: ExitApp
- Returns the next state based on the current state and rule.
NextState(state, rule) { r := ByteDigits(rule) result := {} for i, val in state { if (i = 1) ; The leftmost cell result.Insert(r[state[state.MaxIndex()] state.1 state.2]) else if (i = state.MaxIndex()) ; The rightmost cell result.Insert(r[state[i-1] val state.1]) else ; All cells between leftmost and rightmost result.Insert(r[state[i - 1] val state[i + 1]]) } return result }
- Returns an array with each three digit sequence as a key corresponding to a value
- of true or false depending on the rule.
ByteDigits(rule) { res := {} for i, val in ["000", "001", "010", "011", "100", "101", "110", "111"] { res[val] := Mod(rule, 2) rule >>= 1 } return res }
- Converts 0 and 1 to . and # respectively and returns a string representing the state
PrintState(state) { for i, val in state result .= val = 1 ? "#" : "." return result }</lang>
- Output:
Rule: 90 1 .........#......... 2 ........#.#........ 3 .......#...#....... 4 ......#.#.#.#...... 5 .....#.......#..... 6 ....#.#.....#.#.... 7 ...#...#...#...#... 8 ..#.#.#.#.#.#.#.#.. 9 .#...............#. 10 #.#.............#.#
C
64 cells, edges are cyclic. <lang c>#include <stdio.h>
- include <limits.h>
typedef unsigned long long ull;
- define N (sizeof(ull) * CHAR_BIT)
- define B(x) (1ULL << (x))
void evolve(ull state, int rule) { int i; ull st;
printf("Rule %d:\n", rule); do { st = state; for (i = N; i--; ) putchar(st & B(i) ? '#' : '.'); putchar('\n');
for (state = i = 0; i < N; i++) if (rule & B(7 & (st>>(i-1) | st<<(N+1-i)))) state |= B(i); } while (st != state); }
int main(int argc, char **argv) { evolve(B(N/2), 90); evolve(B(N/4)|B(N - N/4), 30); // well, enjoy the fireworks
return 0; }</lang>
- Output:
Rule 90:
................................#...............................
...............................#.#..............................
..............................#...#.............................
.............................#.#.#.#............................
............................#.......#...........................
...........................#.#.....#.#..........................
..........................#...#...#...#.........................
.........................#.#.#.#.#.#.#.#........................
........................#...............#.......................
---(output snipped)---
C++
<lang cpp>#include <bitset>
- include <stdio.h>
- define SIZE 80
- define RULE 30
- define RULE_TEST(x) (RULE & 1 << (7 & (x)))
void evolve(std::bitset<SIZE> &s) {
int i; std::bitset<SIZE> t(0); t[SIZE-1] = RULE_TEST( s[0] << 2 | s[SIZE-1] << 1 | s[SIZE-2] ); t[ 0] = RULE_TEST( s[1] << 2 | s[ 0] << 1 | s[SIZE-1] ); for (i = 1; i < SIZE-1; i++)
t[i] = RULE_TEST( s[i+1] << 2 | s[i] << 1 | s[i-1] );
for (i = 0; i < SIZE; i++) s[i] = t[i];
} void show(std::bitset<SIZE> s) {
int i;
for (i = SIZE; --i; ) printf("%c", s[i] ? '#' : ' ');
printf("\n");
} int main() {
int i;
std::bitset<SIZE> state(1);
state <<= SIZE / 2;
for (i=0; i<10; i++) {
show(state); evolve(state);
} return 0;
}</lang>
- Output:
# |
### |
## # |
## #### |
## # # |
## #### ### |
## # # # |
## #### ###### |
## # ### # |
## #### ## # ### |
C#
<lang csharp> using System; using System.Collections; namespace ElementaryCellularAutomaton {
class Automata
{
BitArray cells, ncells;
const int MAX_CELLS = 19;
public void run()
{
cells = new BitArray(MAX_CELLS);
ncells = new BitArray(MAX_CELLS);
while (true)
{
Console.Clear();
Console.WriteLine("What Rule do you want to visualize");
doRule(int.Parse(Console.ReadLine()));
Console.WriteLine("Press any key to continue...");
Console.ReadKey();
}
}
private byte getCells(int index)
{
byte b;
int i1 = index - 1,
i2 = index,
i3 = index + 1;
if (i1 < 0) i1 = MAX_CELLS - 1;
if (i3 >= MAX_CELLS) i3 -= MAX_CELLS;
b = Convert.ToByte(
4 * Convert.ToByte(cells.Get(i1)) +
2 * Convert.ToByte(cells.Get(i2)) +
Convert.ToByte(cells.Get(i3)));
return b;
}
private string getBase2(int i)
{
string s = Convert.ToString(i, 2);
while (s.Length < 8)
{ s = "0" + s; }
return s;
}
private void doRule(int rule)
{
Console.Clear();
string rl = getBase2(rule);
cells.SetAll(false);
ncells.SetAll(false);
cells.Set(MAX_CELLS / 2, true);
Console.WriteLine("Rule: " + rule + "\n----------\n");
for (int gen = 0; gen < 51; gen++)
{
Console.Write("{0, 4}", gen + ": ");
foreach (bool b in cells)
Console.Write(b ? "#" : ".");
Console.WriteLine("");
int i = 0;
while (true)
{
byte b = getCells(i);
ncells[i] = '1' == rl[7 - b] ? true : false;
if (++i == MAX_CELLS) break;
}
i = 0;
foreach (bool b in ncells)
cells[i++] = b;
}
Console.WriteLine("");
}
};
class Program
{
static void Main(string[] args)
{
Automata t = new Automata();
t.run();
}
}
} </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: .#..#.........#..#. 25: #.##.#.......#.##.# 26: #.##..#.....#..##.# 27: #.####.#...#.####.# 28: #.#..#..#.#..#..#.# 29: #..##.##...##.##..# 30: #####.###.###.##### 31: ....#.#.#.#.#.#.... 32: ...#...........#... 33: ..#.#.........#.#.. 34: .#...#.......#...#. 35: #.#.#.#.....#.#.#.# 36: #......#...#......# 37: ##....#.#.#.#....## 38: .##..#.......#..##. 39: #####.#.....#.##### 40: ....#..#...#..#.... 41: ...#.##.#.#.##.#... 42: ..#..##.....##..#.. 43: .#.#####...#####.#. 44: #..#...##.##...#..# 45: ###.#.###.###.#.### 46: ..#...#.#.#.#...#.. 47: .#.#.#.......#.#.#. 48: #.....#.....#.....# 49: ##...#.#...#.#...## 50: .##.#...#.#...#.##.
Common Lisp
<lang lisp>(defun automaton (init rule &optional (stop 10))
(labels ((next-gen (cells)
(mapcar #'new-cell
(cons (car (last cells)) cells)
cells
(append (cdr cells) (list (car cells)))))
(new-cell (left current right)
(let ((shift (+ (* left 4) (* current 2) right)))
(if (logtest rule (ash 1 shift)) 1 0)))
(pretty-print (cells)
(format T "~{~a~}~%"
(mapcar (lambda (x) (if (zerop x) #\. #\#))
cells))))
(loop for cells = init then (next-gen cells)
for i below stop
do (pretty-print cells))))
(automaton '(0 0 0 0 0 0 1 0 0 0 0 0 0) 90)</lang>
- Output:
......#...... .....#.#..... ....#...#.... ...#.#.#.#... ..#.......#.. .#.#.....#.#. #...#...#...# ##.#.#.#.#.## .#.........#. #.#.......#.#
D
<lang d>import std.stdio, std.string, std.conv, std.range;
enum mod = (in int n, in int m) pure nothrow @nogc => ((n % m) + m) % m;
struct ECAwrap {
public string front; public enum bool empty = false; private immutable(char)[string] next;
this(in string cells_, in uint rule) {
this.front = cells_;
immutable ruleBits = "%08b".format(rule).retro.text;
next = 8.iota.map!(n => tuple("%03b".format(n), ruleBits[n])).assocArray;
}
void popFront() {
alias c = front;
c = iota(c.length)
.map!(i => next[[c[(i - 1).mod(c.length)], c[i], c[(i + 1) % c.length]]])
.text;
}
}
void main() {
enum nLines = 50;
immutable string start = "0000000001000000000";
immutable uint[] rules = [90, 30, 122];
writeln("Rules: ", rules);
auto ecas = rules.map!(rule => ECAwrap(start, rule)).array;
foreach (immutable i; 0 .. nLines) {
writefln("%2d: %-(%s %)", i, ecas.map!(eca => eca.front.tr("01", ".#")));
foreach (ref eca; ecas)
eca.popFront;
}
}</lang>
- Output:
Rules: [90, 30, 122] 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: .#..#.........#..#. ..#.##....#.####..# ####...........#### 25: #.##.#.......#.##.# ###.#.#..##.#...### ...##.........##... 26: #.##..#.....#..##.# ....#.####..##.##.. ..####.......####.. 27: #.####.#...#.####.# ...##.#...###..#.#. .##..##.....##..##. 28: #.#..#..#.#..#..#.# ..##..##.##..###.## ########...######## 29: #..##.##...##.##..# ###.###..#.###...#. .......##.##....... 30: #####.###.###.##### #...#..###.#..#.##. ......#######...... 31: ....#.#.#.#.#.#.... ##.#####...####.#.. .....##.....##..... 32: ...#...........#... #..#....#.##....### ....####...####.... 33: ..#.#.........#.#.. .####..##.#.#..##.. ...##..##.##..##... 34: .#...#.......#...#. ##...###..#.####.#. ..###############.. 35: #.#.#.#.....#.#.#.# #.#.##..###.#....#. .##.............##. 36: #......#...#......# #.#.#.###...##..##. ####...........#### 37: ##....#.#.#.#....## #.#.#.#..#.##.###.. ...##.........##... 38: .##..#.......#..##. #.#.#.####.#..#..## ..####.......####.. 39: #####.#.....#.##### ..#.#.#....#######. .##..##.....##..##. 40: ....#..#...#..#.... .##.#.##..##......# ########...######## 41: ...#.##.#.#.##.#... .#..#.#.###.#....## .......##.##....... 42: ..#..##.....##..#.. .####.#.#...##..##. ......#######...... 43: .#.#####...#####.#. ##....#.##.##.###.# .....##.....##..... 44: #..#...##.##...#..# ..#..##.#..#..#...# ....####...####.... 45: ###.#.###.###.#.### ######..########.## ...##..##.##..##... 46: ..#...#.#.#.#...#.. ......###........#. ..###############.. 47: .#.#.#.......#.#.#. .....##..#......### .##.............##. 48: #.....#.....#.....# #...##.####....##.. ####...........#### 49: ##...#.#...#.#...## ##.##..#...#..##.## ...##.........##...
J
We'll define a state transition mechanism, and then rely on the language for iteration and display:
<lang J> next=: ((8$2) #: [) {~ 2 #. 1 - [: |: |.~"1 0&_1 0 1@]
' *'{~90 next^:(i.9) 0 0 0 0 0 0 1 0 0 0 0 0
*
* *
* *
* * * *
* *
* * * *
* *
* * * *
* * </lang>
Go
<lang go>package main
import (
"fmt" "math/big" "math/rand" "strings"
)
func main() {
const cells = 20
const generations = 9
fmt.Println("Single 1, rule 90:")
a := big.NewInt(1)
a.Lsh(a, cells/2)
elem(90, cells, generations, a)
fmt.Println("Random intial state, rule 30:")
a = big.NewInt(1)
a.Rand(rand.New(rand.NewSource(3)), a.Lsh(a, cells))
elem(30, cells, generations, a)
}
func elem(rule uint, cells, generations int, a *big.Int) {
output := func() {
fmt.Println(strings.Replace(strings.Replace(
fmt.Sprintf("%0*b", cells, a), "0", " ", -1), "1", "#", -1))
}
output()
a1 := new(big.Int)
set := func(cell int, k uint) {
a1.SetBit(a1, cell, rule>>k&1)
}
last := cells - 1
for r := 0; r < generations; r++ {
k := a.Bit(last) | a.Bit(0)<<1 | a.Bit(1)<<2
set(0, k)
for c := 1; c < last; c++ {
k = k>>1 | a.Bit(c+1)<<2
set(c, k)
}
set(last, k>>1|a.Bit(0)<<2)
a, a1 = a1, a
output()
}
}</lang>
- Output:
Single 1, rule 90:
#
# #
# #
# # # #
# #
# # # #
# # # #
# # # # # # # #
# #
# # # #
Random intial state, rule 30:
# # # #### #
## ## #### # ##
# # # # ### ##
######### ## # # #
# ## ## #
# ##### # #
# ## ######
## ## # ##
## # ## #### #
# #### ### ## #
Perl
<lang perl>use strict; use warnings;
package Automaton {
sub new {
my $class = shift; my $rule = [ reverse split //, sprintf "%08b", shift ]; return bless { rule => $rule, cells => [ @_ ] }, $class;
}
sub next {
my $this = shift; my @previous = @{$this->{cells}}; $this->{cells} = [ @{$this->{rule}}[ map { 4*$previous[($_ - 1) % @previous] + 2*$previous[$_] + $previous[($_ + 1) % @previous] } 0 .. @previous - 1 ] ]; return $this;
}
use overload
q{""} => sub {
my $this = shift; join , map { $_ ? '#' : ' ' } @{$this->{cells}}
};
}
my @a = map 0, 1 .. 91; $a[45] = 1; my $a = Automaton->new(90, @a);
for (1..40) {
print "|$a|\n"; $a->next;
}</lang>
- Output:
| # | | # # | | # # | | # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # # # # # # # # # | | # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | | # # | | # # # # | | # # # # | | # # # # # # # # | | # # # # | | # # # # # # # # | | # # # # # # # # | | # # # # # # # # # # # # # # # # |
Perl 6
<lang perl6>class Automaton {
has ($.rule, @.cells);
method gist { <| |>.join: @!cells.map({$_ ?? '#' !! ' '}).join }
method code { $!rule.fmt("%08b").flip.comb }
method succ {
self.new: :$!rule, :cells(
self.code[
(4 X* @!cells.rotate(-1))
Z+ (2 X* @!cells)
Z+ @!cells.rotate(1)
]
)
}
}
my $size = 10; my Automaton $a .= new:
:rule(30), :cells( 0 xx $size, 1, 0 xx $size );
say $a++ for ^$size;</lang>
- Output:
| # | | ### | | ## # | | ## #### | | ## # # | | ## #### ### | | ## # # # | | ## #### ###### | | ## # ### # | | ## #### ## # ### |
Unfortunately that version is somewhat slow due to the (as yet) unoptimized vector operations, as well as rebuilding the code every iteration. The following version runs about ten times faster and produces the same output: <lang perl6>class Automaton {
has $.rule; has @.cells; has @.code;
method new (|args) { self.bless(|args).init }
method init { @!code ||= $!rule.fmt("%08b").flip.comb».Int; self; }
method gist { <| |>.join: @!cells.map({$_ ?? '#' !! ' '}).join }
method succ {
my \size = +@!cells;
self.new: :$!rule, :@!code, :cells(
@!code[
for ^size -> \i {
4 * @!cells[(i - 1) % size] +
2 * @!cells[i] +
@!cells[(i+1) % size];
}
]
);
}
}
my $size = 10; my Automaton $a .= new:
:rule(30), :cells( 0 xx $size, 1, 0 xx $size );
say $a++ for ^$size;</lang>
Python
Python: Zero padded
Note: This only fitted the original task description that read:
- You can deal with the limit conditions (what happens on the borders of the space) in any way you please.
<lang python>def eca(cells, rule):
lencells = len(cells)
c = "0" + cells + "0" # Zero pad the ends
rulebits = '{0:08b}'.format(rule)
neighbours2next = {'{0:03b}'.format(n):rulebits[::-1][n] for n in range(8)}
yield c[1:-1]
while True:
c = .join(['0',
.join(neighbours2next[c[i-1:i+2]]
for i in range(1,lencells+1)),
'0'])
yield c[1:-1]
if __name__ == '__main__':
lines, start, rules = 50, '0000000001000000000', (90, 30, 122)
zipped = [range(lines)] + [eca(start, rule) for rule in rules]
print('\n Rules: %r' % (rules,))
for data in zip(*zipped):
i = data[0]
cells = data[1:]
print('%2i: %s' % (i, ' '.join(cells).replace('0', '.').replace('1', '#')))</lang>
- Output:
(Note how Rule 30 does not look random).
Rules: (90, 30, 122) 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: .#...#.......#...#. #.#.#...#.##.#.#.#. .#.#.#.#.#.#.#.#.#. 25: #.#.#.#.....#.#.#.# #.#.##.##.#..#.#.## #.#.#.#.#.#.#.#.#.# 26: .......#...#....... #.#.#..#..####.#.#. .#.#.#.#.#.#.#.#.#. 27: ......#.#.#.#...... #.#.#######....#.## #.#.#.#.#.#.#.#.#.# 28: .....#.......#..... #.#.#......#..##.#. .#.#.#.#.#.#.#.#.#. 29: ....#.#.....#.#.... #.#.##....#####..## #.#.#.#.#.#.#.#.#.# 30: ...#...#...#...#... #.#.#.#..##....###. .#.#.#.#.#.#.#.#.#. 31: ..#.#.#.#.#.#.#.#.. #.#.#.####.#..##..# #.#.#.#.#.#.#.#.#.# 32: .#...............#. #.#.#.#....####.### .#.#.#.#.#.#.#.#.#. 33: #.#.............#.# #.#.#.##..##....#.. #.#.#.#.#.#.#.#.#.# 34: ...#...........#... #.#.#.#.###.#..###. .#.#.#.#.#.#.#.#.#. 35: ..#.#.........#.#.. #.#.#.#.#...####..# #.#.#.#.#.#.#.#.#.# 36: .#...#.......#...#. #.#.#.#.##.##...### .#.#.#.#.#.#.#.#.#. 37: #.#.#.#.....#.#.#.# #.#.#.#.#..#.#.##.. #.#.#.#.#.#.#.#.#.# 38: .......#...#....... #.#.#.#.####.#.#.#. .#.#.#.#.#.#.#.#.#. 39: ......#.#.#.#...... #.#.#.#.#....#.#.## #.#.#.#.#.#.#.#.#.# 40: .....#.......#..... #.#.#.#.##..##.#.#. .#.#.#.#.#.#.#.#.#. 41: ....#.#.....#.#.... #.#.#.#.#.###..#.## #.#.#.#.#.#.#.#.#.# 42: ...#...#...#...#... #.#.#.#.#.#..###.#. .#.#.#.#.#.#.#.#.#. 43: ..#.#.#.#.#.#.#.#.. #.#.#.#.#.####...## #.#.#.#.#.#.#.#.#.# 44: .#...............#. #.#.#.#.#.#...#.##. .#.#.#.#.#.#.#.#.#. 45: #.#.............#.# #.#.#.#.#.##.##.#.# #.#.#.#.#.#.#.#.#.# 46: ...#...........#... #.#.#.#.#.#..#..#.# .#.#.#.#.#.#.#.#.#. 47: ..#.#.........#.#.. #.#.#.#.#.#######.# #.#.#.#.#.#.#.#.#.# 48: .#...#.......#...#. #.#.#.#.#.#.......# .#.#.#.#.#.#.#.#.#. 49: #.#.#.#.....#.#.#.# #.#.#.#.#.##.....## #.#.#.#.#.#.#.#.#.#
Python: wrap
The ends of the cells wrap-around. <lang python>def eca_wrap(cells, rule):
lencells = len(cells)
rulebits = '{0:08b}'.format(rule)
neighbours2next = {tuple('{0:03b}'.format(n)):rulebits[::-1][n] for n in range(8)}
c = cells
while True:
yield c
c = .join(neighbours2next[(c[i-1], c[i], c[(i+1) % lencells])] for i in range(lencells))
if __name__ == '__main__':
lines, start, rules = 50, '0000000001000000000', (90, 30, 122)
zipped = [range(lines)] + [eca_wrap(start, rule) for rule in rules]
print('\n Rules: %r' % (rules,))
for data in zip(*zipped):
i = data[0]
cells = data[1:]
print('%2i: %s' % (i, ' '.join(cells).replace('0', '.').replace('1', '#')))
</lang>
- Output:
Rules: (90, 30, 122) 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: .#..#.........#..#. ..#.##....#.####..# ####...........#### 25: #.##.#.......#.##.# ###.#.#..##.#...### ...##.........##... 26: #.##..#.....#..##.# ....#.####..##.##.. ..####.......####.. 27: #.####.#...#.####.# ...##.#...###..#.#. .##..##.....##..##. 28: #.#..#..#.#..#..#.# ..##..##.##..###.## ########...######## 29: #..##.##...##.##..# ###.###..#.###...#. .......##.##....... 30: #####.###.###.##### #...#..###.#..#.##. ......#######...... 31: ....#.#.#.#.#.#.... ##.#####...####.#.. .....##.....##..... 32: ...#...........#... #..#....#.##....### ....####...####.... 33: ..#.#.........#.#.. .####..##.#.#..##.. ...##..##.##..##... 34: .#...#.......#...#. ##...###..#.####.#. ..###############.. 35: #.#.#.#.....#.#.#.# #.#.##..###.#....#. .##.............##. 36: #......#...#......# #.#.#.###...##..##. ####...........#### 37: ##....#.#.#.#....## #.#.#.#..#.##.###.. ...##.........##... 38: .##..#.......#..##. #.#.#.####.#..#..## ..####.......####.. 39: #####.#.....#.##### ..#.#.#....#######. .##..##.....##..##. 40: ....#..#...#..#.... .##.#.##..##......# ########...######## 41: ...#.##.#.#.##.#... .#..#.#.###.#....## .......##.##....... 42: ..#..##.....##..#.. .####.#.#...##..##. ......#######...... 43: .#.#####...#####.#. ##....#.##.##.###.# .....##.....##..... 44: #..#...##.##...#..# ..#..##.#..#..#...# ....####...####.... 45: ###.#.###.###.#.### ######..########.## ...##..##.##..##... 46: ..#...#.#.#.#...#.. ......###........#. ..###############.. 47: .#.#.#.......#.#.#. .....##..#......### .##.............##. 48: #.....#.....#.....# #...##.####....##.. ####...........#### 49: ##...#.#...#.#...## ##.##..#...#..##.## ...##.........##...
Python: Infinite
Note: This only fitted the original task description that read:
- You can deal with the limit conditions (what happens on the borders of the space) in any way you please.
Pad and extend with inverse of end cells on each iteration. <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, start, rules = 20, '1', (90, 30, 122)
zipped = [range(lines)] + [eca_infinite(start, rule) for rule in rules]
print('\n Rules: %r' % (rules,))
for data in zip(*zipped):
i = data[0]
cells = ['%s%s%s' % (' '*(lines - i), c, ' '*(lines - i)) for c in data[1:]]
print('%2i: %s' % (i, ' '.join(cells).replace('0', '.').replace('1', '#')))</lang>
- Output:
Rules: (90, 30, 122) 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
This is the base code for the three elementary CA tasks. The "wrap" code is a little over-complicated for the simple cases of wrapping on word boundaries and for CA's with a narrower word. However, it will be used unmodified for Elementary cellular automaton/Infinite length.
<lang racket>#lang racket (require racket/fixnum) (provide usable-bits/fixnum usable-bits/fixnum-1 CA-next-generation show-automaton)
(define usable-bits/fixnum 30) (define usable-bits/fixnum-1 (sub1 usable-bits/fixnum)) (define usable-bits/mask (fx- (fxlshift 1 usable-bits/fixnum) 1)) (define 2^u-b-1 (fxlshift 1 usable-bits/fixnum-1))
(define (shift-right-1-bit-with-lsb-L L n)
(fxior (if (bitwise-bit-set? L 0) 2^u-b-1 0) (fxrshift n 1)))
(define (shift-left-1-bit-with-msb-R n R)
(fxior (fxand usable-bits/mask (fxlshift n 1)) (if (bitwise-bit-set? R usable-bits/fixnum-1) 1 0)))
(define ((CA-next-bit-state rule) L n R)
(for/fold ((n+ 0)) ((b (in-range usable-bits/fixnum-1 -1 -1))) (define bit.2 (if (bitwise-bit-set? (shift-right-1-bit-with-lsb-L L n) b) 4 0)) (define bit.1 (if (bitwise-bit-set? n b) 2 0)) (define bit.0 (if (bitwise-bit-set? (shift-left-1-bit-with-msb-R n R) b) 1 0)) (define rule-bit (fxior bit.2 (fxior bit.1 bit.0))) (values (fxior (fxlshift n+ 1) (if (bitwise-bit-set? rule rule-bit) 1 0)))))
- CA-next-generation generates a function which takes
- v-in
- an fxvector representing the CA's current state as a bit field. This may be mutated
- offset
- the offset of the leftmost element of v-in; this is used in infinite CA to allow the CA
- to occupy negative indices
- wrap-rule
- provided for automata that are not an integer number of usable-bits/fixnum bits wide
- wrap-rule = #f - v-in and offset are unchanged
- wrap-rule
- (v-in vl-1 offset) -> (values v-out vl-1+ offset-)
- v-in as passed into CA-next-generation
- vl-1=(sub1 (length v-in)), since its precomputed vaule is needed
- offset as passed into CA-next-generation
- v-out
- either a new copy of v-in, or v-in itself (which might be mutated)
- vl-1+
- (sub1 (length v-out))
- offset-
- a new value for offset (it will have decreased since the CA grows to the left
- with offset, and to the right with (length v-out)
(define (CA-next-generation rule #:wrap-rule (wrap-rule #f))
(define next-state (CA-next-bit-state rule))
(lambda (v-in offset)
(define vl-1 (fx- (fxvector-length v-in) 1))
(define-values (v+ v+l-1 offset-) ((or wrap-rule values) v-in vl-1 offset))
(define rv
(for/fxvector
((l (in-sequences (in-value (fxvector-ref v+ v+l-1)) (in-fxvector v+)))
(n (in-fxvector v+))
(r (in-sequences (in-fxvector v+ 1) (in-value (fxvector-ref v+ 0)))))
(next-state l n r)))
(values rv offset-)))
- CA-next-generation with the default (non) wrap rule wraps the MSB of the left-hand word (L) and the
- LSB of the right-hand word (R) in the CA. If the CA is not a multiple of usable-bits/fixnum wide,
- then we use this function to put these bits where they can be used... i.e. the actual MSB is copied
- to the word's MSB and the LSB is copied to the bit that is to the left of the actual MSB.
(define (wrap-rule-truncate-left-word sig-bits)
(define wlb-mask (fx- (fxlshift 1 sig-bits) 1)) (unless (fx< sig-bits (fx- usable-bits/fixnum 1)) (error "we need at least 2 bits in the top of the word to do this safely")) (lambda (v-in vl-1 offset) (define v0 (fxvector-ref v-in 0)) ;; this must wrap to wlb of the first word (define last-bit (fxlshift (fxand 1 (fxvector-ref v-in vl-1)) sig-bits)) ;; this must wrap to the extreme left of the first word (define first-bit (if (bitwise-bit-set? v0 (fx- sig-bits 1)) 2^u-b-1 0)) (fxvector-set! v-in 0 (fxior (fxior last-bit first-bit) (fxand v0 wlb-mask))) (values v-in vl-1 offset)))
- This displays a state of the CA
(define (show-automaton v #:step (step #f) #:sig-bits (sig-bits #f) #:push-right (push-right #f))
(when step (printf "[~a] " (~a #:align 'right #:width 10 step)))
(when push-right (display (make-string (* usable-bits/fixnum push-right) #\.)))
(when (number? sig-bits)
(display (~a #:width sig-bits #:align 'right #:pad-string "0"
(number->string (fxvector-ref v 0) 2))))
(for ((n (in-fxvector v (if sig-bits 1 0))))
(display (~a #:width usable-bits/fixnum #:align 'right #:pad-string "0" (number->string n 2)))))
(module+ main
(define ng/122/19-bits (CA-next-generation 122 #:wrap-rule (wrap-rule-truncate-left-word 19))) (for/fold ((v (fxvector #b1000000000)) (o 0)) ((step (in-range 40))) (show-automaton v #:step step #:sig-bits 19) (newline) (ng/122/19-bits v o)))</lang>
- Output:
[ 0] 0000000001000000000 [ 1] 0000000010100000000 [ 2] 0000000101010000000 [ 3] 0000001010101000000 [ 4] 0000010101010100000 [ 5] 0000101010101010000 [ 6] 0001010101010101000 [ 7] 0010101010101010100 [ 8] 0101010101010101010 [ 9] 1010101010101010101 [ 10] 1100000001111010101 [ 11] 1100000001101101010 [ 12] 1111010101010101111 [ 13] 1100000001100011010 [ 14] 0011110101010111100 [ 15] 0110011010101100110 [ 16] 1111111101011111111 [ 17] 1100000001100000001 [ 18] 0000001111111000000 [ 19] 0000011000001100000 [ 20] 0000111100011110000 [ 21] 0001100110110011000 [ 22] 0011111111111111100 [ 23] 0110000000000000110 [ 24] 1111000000000001111 [ 25] 1100000001100011000 [ 26] 0011110000000111100 [ 27] 0110011000001100110 [ 28] 1111111100011111111 [ 29] 1100000001100000001 [ 30] 0000001111111000000 [ 31] 0000011000001100000 [ 32] 0000111100011110000 [ 33] 0001100110110011000 [ 34] 0011111111111111100 [ 35] 0110000000000000110 [ 36] 1111000000000001111 [ 37] 1100000001100011000 [ 38] 0011110000000111100 [ 39] 0110011000001100110 #fx(522495) 0
Ruby
<lang ruby>class ElemCellAutomat
include Enumerable
def initialize (start_str, rule, disp=false)
@cur = start_str
@patterns = Hash[8.times.map{|i|["%03b"%i, "01"[rule[i]]]}]
puts "Rule (#{rule}) : #@patterns" if disp
end
def each
return to_enum unless block_given?
loop do
yield @cur
str = @cur[-1] + @cur + @cur[0]
@cur = @cur.size.times.map {|i| @patterns[str[i,3]]}.join
end
end
end
eca = ElemCellAutomat.new('1'.center(39, "0"), 18, true) eca.take(30).each{|line| puts line.tr("01", ".#")}</lang>
- Output:
Rule (18) : {"000"=>"0", "001"=>"1", "010"=>"0", "011"=>"0", "100"=>"1", "101"=>"0", "110"=>"0", "111"=>"0"}
...................#...................
..................#.#..................
.................#...#.................
................#.#.#.#................
...............#.......#...............
..............#.#.....#.#..............
.............#...#...#...#.............
............#.#.#.#.#.#.#.#............
...........#...............#...........
..........#.#.............#.#..........
.........#...#...........#...#.........
........#.#.#.#.........#.#.#.#........
.......#.......#.......#.......#.......
......#.#.....#.#.....#.#.....#.#......
.....#...#...#...#...#...#...#...#.....
....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....
...#...............................#...
..#.#.............................#.#..
.#...#...........................#...#.
#.#.#.#.........................#.#.#.#
.......#.......................#.......
......#.#.....................#.#......
.....#...#...................#...#.....
....#.#.#.#.................#.#.#.#....
...#.......#...............#.......#...
..#.#.....#.#.............#.#.....#.#..
.#...#...#...#...........#...#...#...#.
#.#.#.#.#.#.#.#.........#.#.#.#.#.#.#.#
...............#.......#...............
..............#.#.....#.#..............
Scheme
<lang scheme>
- uses SRFI-1 library http://srfi.schemers.org/srfi-1/srfi-1.html
(define (evolve ls r)
(unfold
(lambda (x) (null? (cddr x)))
(lambda (x)
(vector-ref r (+ (* 4 (first x)) (* 2 (second x)) (third x))))
cdr
(cons (last ls) (append ls (list (car ls))))))
(define (automaton s r n)
(define (*automaton s0 rv n)
(for-each (lambda (x) (display (if (zero? x) #\. #\#))) s0)
(newline)
(if (not (zero? n))
(let ((s1 (evolve s0 rv)))
(*automaton s1 rv (- n 1)))))
(display "Rule ")
(display r)
(newline)
(*automaton
s
(list->vector
(append
(int->bin r) (make-list (- 7 (floor (/ (log r) (log 2)))) 0)))
n))
(automaton '(0 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 1) 30 20) </lang>
- Output:
Rule 30 .#...#.#..####.....# .##.##.####...#...## .#..#..#...#.###.##. #########.##.#...#.# ..........#..##.##.# #........#####..#..# .#......##....###### .##....##.#..##..... ##.#..##..####.#.... #..####.###....##..# .###....#..#..##.### .#..#..########..#.. ########.......####. #.......#.....##.... ##.....###...##.#..# ..#...##..#.##..#### ####.##.###.#.###... #....#..#...#.#..#.# .#..######.##.####.# .####......#..#....# .#...#....######..##
Tcl
<lang tcl>package require Tcl 8.6
oo::class create ElementaryAutomaton {
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 {state} {
set len [llength $state] for {set i 0} {$i < $len} {incr i} { lappend result [dict get $rules [ lindex $state [expr {($i-1)%$len}]][ lindex $state $i][ lindex $state [expr {($i+1)%$len}]]] } return $result
}
# Simple driver method; omit the initial state to get a centred dot
method run {steps {initialState ""}} {
if {[llength [info level 0]] < 4} { set initialState "[string repeat . $steps]1[string repeat . $steps]" } set s [split [string map ". 0 # 1" $initialState] ""] for {set i 0} {$i < $steps} {incr i} { puts [string map "0 . 1 #" [join $s ""]] set s [my evolve $s] } puts [string map "0 . 1 #" [join $s ""]]
}
}</lang> Demonstrating: <lang tcl>puts "Rule 90 (with default state):" ElementaryAutomaton create rule90 90 rule90 run 20 puts "\nRule 122:" [ElementaryAutomaton new 122] run 25 "..........#......…."</lang>
- Output:
Rule 90 (with default state): ....................#.................... ...................#.#................... ..................#...#.................. .................#.#.#.#................. ................#.......#................ ...............#.#.....#.#............... ..............#...#...#...#.............. .............#.#.#.#.#.#.#.#............. ............#...............#............ ...........#.#.............#.#........... ..........#...#...........#...#.......... .........#.#.#.#.........#.#.#.#......... ........#.......#.......#.......#........ .......#.#.....#.#.....#.#.....#.#....... ......#...#...#...#...#...#...#...#...... .....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#..... ....#...............................#.... ...#.#.............................#.#... ..#...#...........................#...#.. .#.#.#.#.........................#.#.#.#. #.......#.......................#.......# Rule 122: ..........#.......... .........#.#......... ........#.#.#........ .......#.#.#.#....... ......#.#.#.#.#...... .....#.#.#.#.#.#..... ....#.#.#.#.#.#.#.... ...#.#.#.#.#.#.#.#... ..#.#.#.#.#.#.#.#.#.. .#.#.#.#.#.#.#.#.#.#. #.#.#.#.#.#.#.#.#.#.# ##.#.#.#.#.#.#.#.#.## .##.#.#.#.#.#.#.#.##. ####.#.#.#.#.#.#.#### ...##.#.#.#.#.#.##... ..####.#.#.#.#.####.. .##..##.#.#.#.##..##. ########.#.#.######## .......##.#.##....... ......####.####...... .....##..###..##..... ....######.######.... ...##....###....##... ..####..##.##..####.. .##..###########..##. ######.........######