Golfing the Game of Life (and its variations)
October 2016
We golfed the Game of Life many times in the past few years, in many different forms:
First, when 140byt.es still existed, we golfed the algorithm alone in less than 140 bytes (135b by aemkei and 126b by me);
Subzey joined us to golf miniGameOfLife, a complete Game of Life simulation in ASCII in 238b, which used the mouse and the keyboard to set the initial state and evolve;
Aemkei golfed a pure HTML version in 176b and he presented many... obfuscated... versions... on stage;
We made MiniGameOfBraille in 389b;
And finally, we ended up golfing a super tiny version on a 100x100px canvas inspired by aemkei's talks, in just 221b, featuring ES6 and a pseudo-random initial state.
<canvas id=a><svg onload=z=a.getContext`2d`;s=!setInterval`p=a;a=[];for(i=1e4;a[i]=s?3==k|p[i]&2==k:3<i%9,k=0,i--;)for((j)of[1,97,v,99])k+=p[i+j]+p[i-j];for(s=1e4;s--;)z[a[s]?'fillRect':'clearRect'](s%v,s/v|0,1${v=98}1)`>
During months, we really thought we couldn't do better than that. We even included this version in our js13kgames entry 26-games-in-1.
We also golfed other cellular automata like miniLangtonAnt, miniLangtonLoops and cellularandom.
This week, we discovered a new, intriguing variation of the Game of Life, that produced a Serpinski triangle fractal while it evolved from a vertical line.
So I tried to reproduce it and golf it from scratch with @sqaxomonophonen @subzey @nderscore and @veubeke. The result is HERE, and it fits in just 188b!
Here are the different steps of this quite epic golfing session, just after we realized that the rules of this game were the same as Game of Life's, except that cells live with 0 or 3 live neighbours instead of 2 or 3 live neighbours:
The commented source code can be found HERE.
// Just minified, not golfed yet.
<canvas id=a><script>d=[];k=0;setInterval(function(){a.width^=0;e=[];for(i=0;i<98*98;i++){if(!k){d[i]=((i%98)==49)?1:0;}else{n=0;for(j of[1,97,98,99])n+=!!d[i+j]+!!d[i-j];if(e[i]=[x=d[i],,x,!x][n])a.getContext`2d`.fillRect(i%98,~~(i/98),1,1);}}if(k)d=e;k++;},9)</script>
// Move k (a flag telling if the game has started or not) into d (an array representing all cells' state). Pass a string to setInterval. Move the rest of the code to remove some curly braces.
<canvas id=a><script>d=[k=0];setInterval(`a.width^=0;e=[];for(i=0;i<98*98;i++){n=0;if(k)for(j of[1,97,98,99])n+=!!d[i+j]+!!d[i-j];else d[i]=e[i]=((i%98)==49)?1:0;if(e[i]=[x=d[i],,x,!x][n])a.getContext("2d").fillRect(i%98,~~(i/98),1,1);}d=e;k++`,9)</script>
// Move some code inside e (an array representing the new state of the grid). Use .map() to iterate on the set of neighbours offsets.
<canvas id=a><script>d=[k=0];setInterval(`for(e=[a.width^=i=0];i<98*98;i++)n=0,k?[1,97,98,99].map(j=>n+=!!d[i+j]+!!d[i-j]):d[i]=e[i]=i%98-49?0:1,(e[i]=[x=d[i],,x,!x][n])&&a.getContext("2d").fillRect(i%98,~~(i/98),1,1);d=e;k++`,9)</script>
// Reverse the loop (from 10000 to 0) to iterate on all the cells. Move n reset at the end.
<canvas id=a><script>d=[k=0];setInterval(`e=[a.width^=0];for(i=1e4;i--;k?[1,97,98,99].map(j=>n+=!!d[i+j]+!!d[i-j]):d[i]=e[i]=i%98-49?0:1,(e[i]=[x=d[i],,x,!x][n])&&a.getContext("2d").fillRect(i%98,~~(i/98),1,1))n=0;d=e;k++`,9)</script>
// Instead of incrementing k at each loop, just set it to the value of e after the first iteration
<canvas id=a><script> d=[k=0];setInterval(`e=[a.width^=0];for(i=1e4;i--;k?[1,97,98,99].map(j=>n+=!!d[i+j]+!!d[i-j]):d[i]=e[i]=i%98-49?0:1,(e[i]=[x=d[i],,x,!x][n])&&a.getContext("2d").fillRect(i%98,~~(i/98),1,1))n=0;k=d=e`,9)</script>
// Place all the JS code in an svg onload. Reorder the code a little, and simplify the game's rules (e[i]=!(d[i]?n^2&n:n^3) instead of e[i]=[x=d[i],,x,!x][n])
<canvas id=a><svg onload="d=[k=0];setInterval('e=[a.width^=0];for(i=1e4;i--;k?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98|0,1,1):e[i]=i%98==49)n=0;k=d=e',9)">
// Set d to zero and use it as the second parameter of setInterval (it's not useful as an array at the beginning ant it's set to the value of e after each iteration)
<canvas id=a><svg onload="setInterval('e=[a.width^=0];for(i=1e4;i--;d?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98|0,1,1):e[i]=i%98==49)n=0;k=d=e',d=0)">
// k is not needed anymore, the truthiness of d is enough to choose between "initiate the grid" (when d=0) and "iterate" (when d=e)
<canvas id=a><svg onload="setInterval('e=[a.width^=0];for(i=1e4;i--;d?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98|0,1,1):e[i]=i%98==49)n=0;d=e',d=0)">
// Do not floor the y position of each pixel (at this scale, it's almost not noticeable)
<canvas id=a><svg onload="setInterval('e=[a.width^=0];for(i=1e4;i--;d?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98,1,1):e[i]=i%98==49)n=0;d=e',d=0)">
// Try to use a boolean in d... but it doesn't work on Firefox (Fx needs an integer as second param of setInterval)
<canvas id=a><svg onload="d=!setInterval('e=[a.width^=0];for(i=1e4;i--;d?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98,1,1):e[i]=i%98==49)n=0;d=e')">
// Rollback
<canvas id=a><svg onload="setInterval('e=[a.width^=0];for(i=1e4;i--;d?[1,97,98,99].map(j=>n+=d[i+j]+d[i-j])|(e[i]=!(d[i]?n^2&n:n^3))&&a.getContext`2d`.fillRect(i%98,i/98,1,1):e[i]=i%98==49)n=0;d=e',d=0)">
// Move some code inside e[i]=xxx (e[yyy,i]=xxx is valid in JS!)
<canvas id=a><svg onload="setInterval('e=[a.width^=0];for(i=1e4;i--;e[[1,97,98,99].map(j=>n+=d[i+j]+d[i-j]),i]=d?(d[i]?n^2&n:n^3)?0:!a.getContext`2d`.fillRect(i%98,i/98,1,1):i%98==49)n=0;d=e',d=0)">
// Move some code (declaration of e and reset of a.width) inside the for loop and mix it with "i=1e4". Also, save the number 98 in a variable (k) to reuse it many times.
<canvas id=a><svg onload="setInterval('for(a.width|=e=[i=1e4];i--;e[[1,97,k=98,99].map(j=>n+=d[i+j]+d[i-j]),i]=d?(d[i]?n^2&n:n^3)?0:!a.getContext`2d`.fillRect(i%k,i/k,1,1):i%k==49)n=0;d=e',d=0)">
// Simplify the rules with a global "n xor"
<canvas id=a><svg onload="setInterval('for(a.width|=e=[i=1e4];i--;e[[1,97,k=98,99].map(j=>n+=d[i+j]+d[i-j]),i]=d?n^(d[i]?2&n:3)?0:!a.getContext`2d`.fillRect(i%k,i/k,1,1):i%k==49)n=0;d=e',d=0)">
// Moved rules inside of height argument of fillRect.
<canvas id=a><svg onload="setInterval('for(a.width&=e=[i=1e4];i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=d?!(d[i]?n^2&n:n^3):i%k==49))[1,97,k=98,99].map(j=>n+=d[i+j]+d[i-j],n=0);d=e',d=0)">
// Simplify the rules again (reuse the global "n xor" trick) and simplify "i%k==49" into "i%k^49".
<canvas id=a><svg onload="setInterval('for(a.width&=e=[i=1e4];i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=!(d?n^(d[i]?2&n:3):i%k^49)))[1,97,k=98,99].map(j=>n+=d[i+j]+d[i-j],n=0);d=e',d=0)">
// Remove the quotes of the svg onload attribute, and replace the map() with "for(j of[...])". The space is replaced with a vertical tab character (considered as a space in JS but not in HTML)
<canvas id=a><svg onload=setInterval('for(a.width&=e=[i=1e4];i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=!(d?n^(d[i]?2&n:3):i%k^49))){n=0;for(jof[1,97,k=98,99])n+=d[i+j]+d[i-j]}d=e',d=0)>
// Move n=0 at the beginning of the loop to get rid of two more curly braces.
<canvas id=a><svg onload=setInterval('for(a.width&=e=[i=1e4];n=0,i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=!(d?n^(d[i]?2&n:3):i%k^49)))for(jof[1,97,k=98,99])n+=d[i+j]+d[i-j];d=e',d=0)>
With this extremely small code, we tried to re-golf miniGameOfLife with the same principle, and got it down from 221b to 183b! The result is HERE!
<canvas id=a><svg onload=setInterval('for(a.width&=e=[i=1e4];i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=d?d[i]+n==4||n==4:3<i%9))for(jof[n=1,97,k=98,99])n+=d[i+j]+d[i-j];d=e',d=0)>
New mini projects!
— xem (@MaximeEuziere) 28 octobre 2016
MiniconwaySerpinski golfed in 188b - https://t.co/B3a6iAlIy8
and miniGameOfLife2 golfed in 184b - https://t.co/WAI1CdvRO9 pic.twitter.com/AVdS64MCzK
(to save one extra byte, Subzey also had the idea to rewrite the rule "e[i]=(d[i]&&n==2)||n==3" into "e[i]=d?d[i]+n==4||n==4")
To conclude, I'd like to show that this model can actually be used as a bootstrap for any Game of Life variation, not only these two:
<canvas id=a><svg onload=setInterval('for(a.width&=e=[i=1e4];i--;a.getContext`2d`.fillRect(i%k,i/k,1,e[i]=d?[RULES]:[INITIAL STATE]))for(jof[n=1,97,k=98,99])n+=d[i+j]+d[i-j];d=e',d=0)>
Replace [RULES] with the conditions that make e[i] (the current cell) alive based on d[i] (the previous state of the current cell) and n (the number of live neighbours);
and replace [INITIAL STATE] with the code that defines the initial state of the grid, based on i (the cell counter).
For example, if you use the rules of Life without Death, you can get something like this:
Cheers,
the Team