Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

The Challenge

You are to write a complete program that takes seven numbers from STDIN, and prints the two dimensional history of the cellular automaton (CA) to STDOUT. This is code golf.

Input Formatting The input will be seven integers/strings separated by commas. The first number is the number of the rule according to Wolfram code (the standard name for each rule). The second is the initial starting configuration. The third and fourth describe what pattern and how many times it should be appended to the left of the starting config. as padding. The fifth and sixth do the same for the right side. The last number is the number of generations to run the simulation.

So, an example of input is 90,11,0,4,0,4,5. This should tell your program that you are running rule 90. It should also tell the program that you want the initial configuration to be 11 with the string 0 appended 4 times to both ends, so the actual starting pattern is 0000110000. It also tells your program to run this simulation for 5 generations.

Output Your program should print the entire array of cells each generation (separated by newlines), so that the output is the space-time diagram of the CA. For each generation, the state of each cell is determined by its state and the states of the cells to the immediate left and right, in accordance to the rule provided as input. The simulation should wrap around the edges. The first thing printed should be the starting array as gen. 0.

The input 90,11,0,4,0,4,5 should result in the following output as exactly as possible.

0000110000
0001111000
0011001100
0111111110
1100000011
0110000110

Notice that the starting state is not included in the five generations. Also notice that the simulation wraps around the edges.

More Examples

input:

184,1100,01,2,01,1,4

output:

0101110001
1011101000
0111010100
0110101010
0101010101

input:

0,1011,1,0,0,1,2

output:

10110
00000
00000

More information on how 1D CA's work and how they are numbered

share|improve this question
    
Well done for including rule 0 as a test case. –  Peter Taylor Dec 17 '11 at 22:15
    
I'm fascinated that rule 90 is a Sierpinski Gasket. Especially since that was part of the testing I did for another Codegolf project. –  JoeFish Dec 13 '12 at 14:54
    
@JoeFish It was your image that led me to try this one out. I wanted to make an 8086 answer -- kill 2 birds -- but it would probably need string operations, so my emulator wouldn't be able to run it (yet). –  luser droog Dec 13 '12 at 23:18
    
Somebody did it already: pouet.net/prod.php?which=60478 –  luser droog Dec 18 '12 at 9:59
add comment

5 Answers

Golfscript, 77 73 70 chars

','/)~\(~:?;~~*@@~*@+\+{1&}/]({[.,{.[3<?256+]{2base}/\~=\(+}*])n@)\+}*

Thanks to @Howard, who pointed out how to save 4 chars.

share|improve this answer
    
You can save an obvious one 48- -> 1& and I think also three more. You may omit ) before the block (not increase the counter) and therefore also save the last two pops. –  Howard Dec 18 '11 at 10:10
    
@Howard, thanks. Those pops at the end were useful in an earlier iteration but you're right that eliminating them makes sense now. –  Peter Taylor Dec 18 '11 at 13:17
add comment

Ruby, 165 159 characters

a=gets.split ?,
b=a.map &:to_i
c=(x=a[2]*b[3]+a[1]+a[4]*b[5]).chars.map &:hex
(0..b[6]).map{puts c*''
c=(1..w=x.size).map{|i|b[0]>>c[i-1]*2+c[i%w]+c[i-2]*4&1}}

Edit: I found some places for small enhancements.

Example run:

> 30,1,0,20,0,20,20
00000000000000000000100000000000000000000
00000000000000000001110000000000000000000
00000000000000000011001000000000000000000
00000000000000000110111100000000000000000
00000000000000001100100010000000000000000
00000000000000011011110111000000000000000
00000000000000110010000100100000000000000
00000000000001101111001111110000000000000
00000000000011001000111000001000000000000
00000000000110111101100100011100000000000
00000000001100100001011110110010000000000
00000000011011110011010000101111000000000
00000000110010001110011001101000100000000
00000001101111011001110111001101110000000
00000011001000010111000100111001001000000
00000110111100110100101111100111111100000
00001100100011100111101000011100000010000
00011011110110011100001100110010000111000
00110010000101110010011011101111001100100
01101111001101001111110010001000111011110
11001000111001111000001111011101100010001
share|improve this answer
add comment

APL (153 characters)

∇ cellularautomaton
  i               ← ⍞
  s               ← (i=',') / ⍳ ⍴i
  (b a x c)       ← {i[s[⍵]↓⍳s[⍵+1]-1]} ¨ ⍳4
  (z x x l x r n) ← ⍎i
  y               ← ⍎ ¨ ⊃ ,/ (l / ⊂a) , b , r / ⊂c
  (n+1) (⊃⍴,y) ⍴ '01'[1+⊃ ,/ y,{({(z ⊤⍨ 8/2)[8 - 2⊥¨ 3 ,/ (⊃⌽⍵),⍵,⊃⍵]}⍣⍵)y} ¨ ⍳n]
∇

And in less readable, slightly shorter form:

i←⍞⋄s←(i=',')/⍳⍴i⋄b a x c←{i[s[⍵]↓⍳s[⍵+1]-1]}¨⍳4⋄z x x l x r n←⍎i⋄y←⍎¨⊃,/(l/⊂a),b,r/⊂c⋄'01'[1+⊃,/y,{({(z⊤⍨8/2)[8-2⊥¨3,/(⊃⌽⍵),⍵,⊃⍵]}⍣⍵)y}¨⍳n]⍴⍨(1+n),⊃⍴,y

Example:

      cellularautomaton
26,00110,01,4,10,6,7
0101010100110101010101010
1000000011100000000000001
0100000110010000000000011
0010001101101000000000110
0101011001000100000001101
0000010110101010000011000
0000100100000001000110100
0001011010000010101100010

I'm certain there is room for improvement (I even found a few changes while writing this post!), but some of it could involve fundamental changes, and I can't stand staring at APL any longer. The variant of APL used here is Dyalog APL.

share|improve this answer
add comment

C, 303 305 301 294 292

305 Edit: oops. Forgot that calloc() takes two args. It was blowing up on larger input.

301 Edit: Ah HA! Used my calloc() boo-boo to save 2 more bytes by upping the block size of the requested memory.

294 Edit: Broke 300! Eliminated one of the strcat()s and tweaked a few loops. Got to use maximal munch, which is as much fun to say as use.

292 Edit: Didn't need the +2 in memory allocation.

I used luser droog's answer as the base idea, but changed up the wrapping algorithm, as well as a lot of tweaking and factoring out of constants.

r,A,C,n,j;main(){char*s,*p,*t,a[9],b[9],c[9];scanf("%d,%[01],%[01],%d,%[01],%d,%d",&r,b,a,&A,c,&C,&n);for(s=calloc(A+++C,9);A--;)strcat(s,A?a:b);for(;C--;)strcat(s,c);p=strdup(s);for(C=strlen(s);A++<n;puts(s),t=p,p=s,s=t)for(j=C;j--;)p[j]=(1<<(s[j?j-1:C-1]*4+s[j]*2+s[(j+1)%C])-336)&r?49:48;}

r,A,C,n,j;
main(){
    char*s,*p,*t,a[9],b[9],c[9];
    scanf("%d,%[01],%[01],%d,%[01],%d,%d",&r,b,a,&A,c,&C,&n);
    for(s=calloc(A+++C,9);A--;)
        strcat(s,A?a:b);
    for(;C--;)
        strcat(s,c);
    p=strdup(s);
    for(C=strlen(s);A++<n;puts(s),t=p,p=s,s=t)
        for(j=C;j--;)
            p[j]=(1<<(s[j?j-1:C-1]*4+s[j]*2+s[(j+1)%C])-336)&r?49:48;
}

screenshot1

screenshot2

share|improve this answer
1  
You forgot to make it start C,A,! :) –  luser droog Dec 15 '12 at 12:52
    
for loads of memory, what about brk()? then p=s+C+1; somewhere. –  luser droog Jan 25 '13 at 12:39
    
+1 again for using +++! –  luser droog Mar 2 '13 at 6:42
add comment

C (487 484 418 with spaces removed)

*Dropped 66 with help from JoeFish*

C,A,r,n,j;main(){char*s,*p,*t,a[9],b[9],c[9];
    scanf("%d,%[01],%[01],%d,%[01],%d,%d",&r,b,a,&A,c,&C,&n);
    s=malloc(strlen(a)*A+strlen(b)+strlen(c)*C+3);*s=0;
    strcat(s,"0");
    for(;A--;)strcat(s,a);
    strcat(s,b);
    for(;C--;)strcat(s,c);
    strcat(s,"0");
    p=malloc((C=strlen(s)-1)+2);
    for(;n--;){
    *s=s[C-1];
    s[C]=0;
    puts(s+1);
    s[C]=s[1];
    for(j=1;s[j+1];j++)
        p[j]=(1<<(s[j-1]-48)*4+(s[j]-48)*2+s[j+1]-48)&r?49:48;
    t=p;p=s;s=t;
    }
    s[C]=0;
    puts(s+1);
}

typescript

josh@Z1 ~
$ !m
make ca
cc     ca.c   -o ca
ca.c:1:1: warning: data definition has no type or storage class
ca.c: In function ‘main’:
ca.c:2:5: warning: incompatible implicit declaration of built-in function ‘scanf’
ca.c:3:7: warning: incompatible implicit declaration of built-in function ‘malloc’
ca.c:3:14: warning: incompatible implicit declaration of built-in function ‘strlen’
ca.c:4:5: warning: incompatible implicit declaration of built-in function ‘strcat’

josh@Z1 ~
$ echo 90,11,0,4,0,4,5 | ca
-bash: ca: command not found

josh@Z1 ~
$ echo 90,11,0,4,0,4,5 | ./ca
0000110000
0001111000
0011001100
0111111110
1100000011
0110000110

share|improve this answer
    
Nice. You can shave quite a few bytes by making your int variables global and removing the #include: r,A,B,C,n,i,j; main(){char *s... –  JoeFish Dec 13 '12 at 15:19
    
Save a bunch in your for loops: for(;A--;)strcat(s,a); –  JoeFish Dec 13 '12 at 15:23
    
And re-use A and C later so you don't have to declare i or B at all. p=malloc((C=strlen(s))+1); --C; strcpy(p,s); for(A=0;A<n;A++){ Sorry, I'll stop now :) –  JoeFish Dec 13 '12 at 15:25
    
Ok, I lied, one more. Get rid of 2 byes by eliminating --C;: p=malloc((C=strlen(s)-1)+2);. I think golfing code is more fun than coming up with it in the first place! –  JoeFish Dec 13 '12 at 15:28
    
I wasn't sure about removing the #include since scanf is variadic. But it's probably ok since it's only called once. ... My old machine died yesterday, and I'm still installing Cygwin. I'll incorporate those changes as soon as I can test it. Thanks! –  luser droog Dec 13 '12 at 23:05
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.