Simulate Rule 110

Question

Rule 110 is a cellular automaton with some interesting properties. Your goal is to simulate a rule 110 in as few characters as possible.

For those who don't know, rule 110 is simulated line by line. Each square in a line looks at the squares above, above-left and above-right to determine what cell it should be.

current pattern  111 110 101 100 011 010 001 000
new cell          0   1   1   0   1   1   1   0

Input: numbers from 0 to 39 representing top row nth input square, separated by commas.

Example input:

38,39

Output: A 40 x 40 grid representing the automata running including the first row. You should leave 0 as blank and 1 as any character.

Example output:

                                  XX
                                 XXX
                                XX X
                               XXXXX
                              XX   X
                             XXX  XX
                            XX X XXX
                           XXXXXXX X
                          XX     XXX
                         XXX    XX X
                        XX X   XXXXX
                       XXXXX  XX   X
                      XX   X XXX  XX
                     XXX  XXXX X XXX

etc.

Note: A similar question about 1D cellular automata has already been asked, but I hope that, by using only one rule, shorter answers can be written.

Do the patterns wrap around (i.e. does the left-most cell check the right-most cell in the line above it)? — Ventero, 21 hours ago
Do we have to take input as a comma-delimited string or (if we write a function) can we take a list of numbers as input? (At least one answer does the latter.) — m.buettner, 19 hours ago
The answers may be fractionally shorter than Simulate any 1D cellular automaton because the rule is hard-coded rather than having to be parsed from the input, but other than that the answers are going to be the same. If it were a different rule then there would be potential for savings, but how on Earth would special-casing a Turing-powerful rule save anything over a general implementation? — Peter Taylor, 16 hours ago

Ventero · Answer 1 · 2014-07-14 08:07:28Z

Ruby, 113 characters

c=[0]*41
eval"[#{gets}].map{|i|c[i]=1}"+'
c=(0..39).map{|x|putc" X"[u=c[x]]
110[4*c[x-1]+2*u+c[x+1]]}<<0;puts'*40

Takes input on stdin. To use a different rule, simply replace the 110 in the last line with whatever rule you want to try.

Example:

$ ruby 110.rb <<< 38,39
                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

m.buettner · Answer 2 · 2014-07-14 08:00:06Z

Mathematica, 122 bytes

f[a_]:=Riffle[CellularAutomaton[110,Array[If[MemberQ[ToExpression["{"<>a<>"}"],#-1],1,0]&,40],39]/.0->" "/.1->"X","
"]<>""

Yes, you might view this as abusing this loophole, but a) that loophole is quite disputed, b) a Cellular Automaton question needs a Mathematica answer (especially one about Rule 110) and c) Ventero's Ruby answer is shorter anyway, so I don't think any harm is done.

Most of the characters are used for input parsing and output formatting. The actual automaton is simulated using

CellularAutomaton[110,initialGrid,39]

This uses periodic boundary conditions (so the grid wraps around).

Alex L · Answer 3 · 2014-07-14 08:31:54Z

up vote 5 down vote

Python - 141

i=input()
o=range(40)
l=''.join(' X'[c in i]for c in o)
for r in o:print l;l=''.join('X '[l[c-1:c+2]in('XXX','   ','X  ','','  ')]for c in o)

Run as e.g. python 110.py <<< 38,39

edited 20 hours ago

answered 21 hours ago

Alex L
4215

2

['X',' '] could be changed to 'X ' to save 5 characters. – Calvin's Hobbies 20 hours ago

Thanks @Calvin'sHobbies! Made the change. – Alex L 20 hours ago

add comment

slackwear · Answer 4 · 2014-07-14 08:06:12Z

up vote 4 down vote

q (67 chars)

Assumes no wrap-around:

{40{not(flip(prev;::;next)@\:x)in 3 cut 111100000b}\@[40#0b;x;not]}

answered 20 hours ago

slackwear
2,655720

add comment

Calvin's Hobbies · Answer 5 · 2014-07-14 07:02:23Z

Python, 186

def r(s,m=range(40)):
 s=[int(i in s)for i in m]
 for g in m:print''.join([' X'[i]for i in s]);s=[int(not''.join(map(str,s[i-1:i+2]if i else s[:2]))in'111 100 000 00'.split())for i in m]

Decent but probably not optimal.

You didn't specify how input is gotten so I just made a function.

Use example:

r([38,39])

Output:

                                      XX
                                     XXX
                                    XX X
                                   XXXXX
                                  XX   X
                                 XXX  XX
                                XX X XXX
                               XXXXXXX X
                              XX     XXX
                             XXX    XX X
                            XX X   XXXXX
                           XXXXX  XX   X
                          XX   X XXX  XX
                         XXX  XXXX X XXX
                        XX X XX  XXXXX X
                       XXXXXXXX XX   XXX
                      XX      XXXX  XX X
                     XXX     XX  X XXXXX
                    XX X    XXX XXXX   X
                   XXXXX   XX XXX  X  XX
                  XX   X  XXXXX X XX XXX
                 XXX  XX XX   XXXXXXXX X
                XX X XXXXXX  XX      XXX
               XXXXXXX    X XXX     XX X
              XX     X   XXXX X    XXXXX
             XXX    XX  XX  XXX   XX   X
            XX X   XXX XXX XX X  XXX  XX
           XXXXX  XX XXX XXXXXX XX X XXX
          XX   X XXXXX XXX    XXXXXXXX X
         XXX  XXXX   XXX X   XX      XXX
        XX X XX  X  XX XXX  XXX     XX X
       XXXXXXXX XX XXXXX X XX X    XXXXX
      XX      XXXXXX   XXXXXXXX   XX   X
     XXX     XX    X  XX      X  XXX  XX
    XX X    XXX   XX XXX     XX XX X XXX
   XXXXX   XX X  XXXXX X    XXXXXXXXXX X
  XX   X  XXXXX XX   XXX   XX        XXX
 XXX  XX XX   XXXX  XX X  XXX       XX X
XX X XXXXXX  XX  X XXXXX XX X      XXXXX
XXXXXX    X XXX XXXX   XXXXXX     XX   X

AndoDaan · Answer 6 · 2014-07-14 08:42:55Z

Lua - 351

Not the ideal language for golfing.

s,n,t,u=arg[1],{},table.remove,table.insert
for i=1,40 do u(n,i,'.') end
for i in s:gmatch("%d+")do u(n,i,'x');t(n)end
function a(b) c="";for i=1,40 do c=c..b[i] end;print(c);return c end
for i=1,40 do z= n[40]..a(n)..n[1];for k=2,41 do y=string.sub(z,k-1,k+1);if y=="xxx"or y=="x.." or y=="..." then u(n,k-1,'.')else u(n,k-1,'x')end;t(n)end end

alephalpha · Answer 7 · 2014-07-14 10:45:57Z

up vote 2 down vote

Mathematica, 113 chars

Another Mathematica answer using CellularAutomaton.

Print@@" "["X"][[#]]&/@CellularAutomaton[110,SparseArray[#+1->1&/@ImportString[InputString[],"CSV"][[1]],40],39];

answered 18 hours ago

alephalpha
2,891520

Interesting, how does " "["X"][[#]]& work? – m.buettner 17 hours ago

@m.buettner " "["X"][[1]] is "X". " "["X"][[0]] returns the head of " "["X"], namely " ". – alephalpha 17 hours ago

Oh, I see. So that's just generally saving a character for lists. That's really clever. I guess you could add it to codegolf.stackexchange.com/questions/12900/… – m.buettner 17 hours ago

add comment

Paul Drewett · Answer 8 · 2014-07-14 17:37:39Z

My php version 408 characters:

This was a great puzzle. I also spent ages playing with the inputs as these are fascinating things it must be said. Anyway, here is my PHP version (which is nowhere near as good as some of the answers posted but is complete. In 0th position only take above and above right, in 39th position only take above and above left, ie no wrapping. So here is my version:

<?php $a='38,39';$b='';$d=explode(',',$a);for($i=0;$i<40;++$i){$c=' ';
foreach($d as $k=>$v){if($v == $i){$c='x';}}$b.=$c;}echo $b."\n";
for($x=1;$x<50;++$x){$o='';for($i=1;$i<41;++$i){if(($i>1)AND(substr($b,$i-2,1)=='x')){
$l=1;}else{$l=0;}if((substr($b,$i-1,1))=='x'){$v=1;}else{$v=0;}if((substr($b,$i,1))=='x'){
$r=1;}else{$r=0;}if((($l+$v+$r)==2)OR(($v+$r)==1)){$o.='x';}else{$o.=' ';}}
echo $o."\n";$b=$o;}?>

You can see it and run it here: http://codepad.org/3905T8i8

Input is a input string at the start as $a='38, 39';

Output is as follows:

                                      xx
                                     xxx
                                    xx x
                                   xxxxx
                                  xx   x
                                 xxx  xx
                                xx x xxx
                               xxxxxxx x
                              xx     xxx
                             xxx    xx x
                            xx x   xxxxx
                           xxxxx  xx   x
                          xx   x xxx  xx
                         xxx  xxxx x xxx
                        xx x xx  xxxxx x
                       xxxxxxxx xx   xxx
                      xx      xxxx  xx x
                     xxx     xx  x xxxxx
                    xx x    xxx xxxx   x
                   xxxxx   xx xxx  x  xx
                  xx   x  xxxxx x xx xxx
                 xxx  xx xx   xxxxxxxx x
                xx x xxxxxx  xx      xxx
               xxxxxxx    x xxx     xx x
              xx     x   xxxx x    xxxxx
             xxx    xx  xx  xxx   xx   x
            xx x   xxx xxx xx x  xxx  xx
           xxxxx  xx xxx xxxxxx xx x xxx
          xx   x xxxxx xxx    xxxxxxxx x
         xxx  xxxx   xxx x   xx      xxx
        xx x xx  x  xx xxx  xxx     xx x
       xxxxxxxx xx xxxxx x xx x    xxxxx
      xx      xxxxxx   xxxxxxxx   xx   x
     xxx     xx    x  xx      x  xxx  xx
    xx x    xxx   xx xxx     xx xx x xxx
   xxxxx   xx x  xxxxx x    xxxxxxxxxx x
  xx   x  xxxxx xx   xxx   xx        xxx
 xxx  xx xx   xxxx  xx x  xxx       xx x
xx x xxxxxx  xx  x xxxxx xx x      xxxxx
xxxxxx    x xxx xxxx   xxxxxx     xx   x
x    x   xxxx xxx  x  xx    x    xxx  xx
x   xx  xx  xxx x xx xxx   xx   xx x xxx
x  xxx xxx xx xxxxxxxx x  xxx  xxxxxxx x
x xx xxx xxxxxx      xxx xx x xx     xxx
xxxxxx xxx    x     xx xxxxxxxxx    xx x
x    xxx x   xx    xxxxx       x   xxxxx
x   xx xxx  xxx   xx   x      xx  xx   x
x  xxxxx x xx x  xxx  xx     xxx xxx  xx
x xx   xxxxxxxx xx x xxx    xx xxx x xxx
xxxx  xx      xxxxxxxx x   xxxxx xxxxx x

Hope you like it!!!

PS I had to add a few line breaks to the code so you could see all of it and not have it stretch accross the page with a scroll bar.

Tomáš Dvořák · Answer 9 · 2014-07-14 15:41:33Z

Java, 321 characters

Input passed as argument from command line, for example java R 38,39

I have never written more obfuscated java code :-)

class R{public static void main(String[]a) {
Integer s=40;boolean[]n,o=new boolean[s];
for(String x:a[0].split(","))o[s.valueOf(x)]=s>0;
for(Object b:o){n=o.clone();
for(int j=0;j<s;j++){
boolean l=j>1&&o[j-1],r=o[j],c=j+1<s&&o[j+1];
n[j]=!(l&c&r|l&!c&!r|!(l|c|r));
System.out.print((r?"X":" ")+(j>s-2?"\n":""));
}o=n;}}}

Allbeert · Answer 10 · 2014-07-14 16:12:15Z

C - 182

This code depends on the fact that each row in a matrix is stored in contiguous memory. Also, it does not print the first row, but it prints the next 40 ones, since the rules only specified a 40x40 grid.

Indented for readability only, the byte count only includes necessary code.

a[41][42],i,j,*t;
main(){
    while(scanf("%d,",&j)>0)
        a[i][j]=1;
    for(;i<40;i++,puts(""))
        for(j=0;++j<40;)
            t=&a[i][j],
            printf("%c",(*(t+42)=1&(110>>(*(t+1)?1:0)+(*t?2:0)+(*(t-1)?4:0)))?88:32);
}

asked	today
viewed	2133 times
active	today

current community

your communities

more stack exchange communities

Simulate Rule 110

10 Answers

Ruby, 113 characters

Mathematica, 122 bytes

Python - 141

q (67 chars)

Python, 186

Lua - 351

Mathematica, 113 chars

Java, 321 characters

C - 182

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf cellular-automata or ask your own question.

Linked

Hot Network Questions

current community

your communities

more stack exchange communities

Simulate Rule 110

10 Answers

Ruby, 113 characters

Did you find this question interesting? Try our newsletter

Mathematica, 122 bytes

Python - 141

q (67 chars)

Python, 186

Lua - 351

Mathematica, 113 chars

Java, 321 characters

C - 182

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf cellular-automata or ask your own question.

Linked

Related

Hot Network Questions