<div dir="auto">Hi Vanessa!</div><div dir="auto"> Yeah thank you for the explanation, pretty clear.</div><div dir="auto"> I understood the algorithm after reading the article and looking at it with a co-worker</div><div dir="auto"> He did some refactorings that will share for sure</div><div dir="auto"><br></div><div dir="auto">Hernan</div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, 22 Jan 2023 at 19:56 Vanessa Freudenberg <<a href="mailto:vanessa@codefrau.net">vanessa@codefrau.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> <div><div><div><div><div><div>On Sat, Jan 21, 2023 at 00:48 Stéphane Rollandin <<a href="mailto:lecteur@zogotounga.net" target="_blank">lecteur@zogotounga.net</a>> wrote:<br></div></div><div><div><div class="gmail_quote"></div></div></div><div><div><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)"> <br>
> I can not map <br>
> that implementation to the rules of the game... Can someone explain to <br>
> me or point me to a paper/description of why that implementation works?<br>
<br>
There is the Byte paper, around<br>
<a href="https://archive.org/details/byte-magazine-1981-08/page/n205/mode/2up?view=theater" rel="noreferrer" target="_blank">https://archive.org/details/byte-magazine-1981-08/page/n205/mode/2up?view=theater</a><br>
<br>
The figure there shows how ancilliary forms are used to count, in <br>
parallel, the number of neighbors for each point in the pattern.<br>
<br>
For each direction in the Moore neighborood, the pattern is shifted and <br>
these eight shifted grids are combined together.<br>
<br>
This is an addition in base two, and we need to count up to eight, so <br>
the algorithm uses three forms (nbr1, nbr2 and nbr4) to store the <br>
corresponding bits, and two other forms (carry2 and carry4) to store the <br>
bits carried from one bit to the next (so here from nbr1 to nbr2, and <br>
from nbr2 to nbr4), just as you need to do when performing an addition <br>
by hand.<br>
<br>
The last step (the last four lines in #nextLifeGeneration from the Byte <br>
paper) generates the next pattern from nbr1, nbr2 and nbr4. The rules of <br>
the Game of Life are encoded here in the successive combination rules, <br>
in a nifty and quite obfuscated way that I did not even tried to <br>
comprehend.<br>
<br>
Stef</blockquote><div dir="auto"><br></div><div dir="auto"><br></div></div></div></div></div></div></div></div><div><div><div><div><div><div><div class="gmail_quote"><div dir="auto">Right. You basically need to understand how binary counting works at a logic-gate level, to be able to comprehend the neighbor counting code. </div><div dir="auto"><br></div><div dir="auto">Typically that logic is invisible. I love this mechanical version:</div><div dir="auto"><br></div><div dir="auto"><div><a href="https://youtu.be/zELAfmp3fXY" target="_blank">https://youtu.be/zELAfmp3fXY</a></div><br></div><div dir="auto">You can see the bits (the big 0s and 1s). The carry is the little latch sticking out to the left, and it gets set whenever a bit flips from 1 to 0, which means the next bit has to flip. </div><div dir="auto"><br></div><div dir="auto">The “bit + carry” logic is called a “half adder”, you can google that, but basically it generates the next bit and carry from the previous bit and carry using two logic operations, an XOR for the bit and an AND for the carry. </div><div dir="auto"><br></div><div dir="auto">With that understanding, Dan’s explanation in the Byte article might make more sense – it does the XOR and AND for all pixels at the same time. <br></div><div dir="auto"><br></div><div dir="auto">The 3 bit result count is then used to determine if a cell should be born, survive, or die. Again, logic ops do that for all pixels at once. </div><div dir="auto"><br></div><div dir="auto">The Life rule is that cells with 2 or 3 neighbors survive, any with fewer or more neighbors die, and any empty cell with 3 neighbors is born. </div><div dir="auto"><br></div><div dir="auto">To implement that rule with minimal logic, we restructure it a bit</div><div dir="auto"><br></div><div dir="auto">A live cell will be there in the next generation if</div><div dir="auto">(1) the cell is alive AND has 2 neighbors</div><div dir="auto">(2) OR has 3 neighbors (independent of itself being alive or not)</div><div dir="auto">(3) BUT it must not have 4 or more neighbors </div><div dir="auto"><br></div><div dir="auto">(1) is implemented as “self AND 2s” because the 2s bit is only set for 2, 6 and 7 neighbors (010, 110 and 111 in binary), and we deal with the >= 4 neighbors case in (3)</div><div dir="auto">(2) is implemented as “self OR (1s AND 2s)” because those bits are only set together for 3 and 7 neighbors (011 and 111 in binary), and we <span style="color:rgb(0,0,0)">deal with the 7 neighbors case in (3)</span></div><div dir="auto">(3) is implemented as “self AND NOT 4s” which kills any remaining 6 and 7 neighbor cells (4, 5, and 8 neighbor cells wouldn’t have made it to this step anyways because their lower bits look like 0 and 1 neighbors: 100, 101, and 000)</div><div dir="auto"><br></div><div dir="auto">This also explains why we don’t need to count to 8. With 3 bits we can only count to 7, if we add one more to 7 we get 0. But in Life this is fine because both cells with 8 and 0 neighbors have the same result. </div><div dir="auto"><br></div><div dir="auto">Hope that helps,</div><div dir="auto">Vanessa</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding-left:1ex;border-left-color:rgb(204,204,204)" dir="auto"><br>
</blockquote></div></div>
</div>
</div>
</div>
</div>
</div>
</blockquote></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div style="font-size:small"><div dir="ltr"><div dir="ltr"><div style="font-size:12.8px"><span style="font-family:tahoma,sans-serif;font-size:xx-small;border-collapse:collapse"><strong><span style="font-size:8pt"><span style="font-size:small"><font size="2"><span style="font-weight:normal"><span style="font-weight:bold">Hernán Wilkinson</span><br>Agile Software Development, Teaching & Coaching</span></font></span></span></strong></span></div><div style="font-size:12.8px"><span style="font-family:tahoma,sans-serif;font-size:xx-small;border-collapse:collapse"><strong><span style="font-size:8pt"><span style="font-size:small"><font size="2"><span style="font-weight:normal">Phone: +54-011</span></font></span></span></strong></span><font face="tahoma, sans-serif" size="2">-4893-2057</font></div><div style="font-size:12.8px"><strong style="font-family:tahoma,sans-serif;font-size:xx-small"><span style="font-size:8pt"><span style="font-size:small"><font size="2"><span style="font-weight:normal">Twitter: @HernanWilkinson</span></font></span></span></strong></div><div style="font-size:12.8px"><span style="font-family:tahoma,sans-serif;font-size:xx-small;border-collapse:collapse"><strong><span style="font-size:8pt"><span style="font-size:small"><font size="2"><span style="font-weight:normal">site: <a href="http://www.10pines.com/" style="color:rgb(17,65,112)" target="_blank">http://www.10Pines.com</a></span></font></span></span></strong></span></div><div style="font-size:12.8px"><font face="tahoma, sans-serif"><span style="border-collapse:collapse">Address: Alem 896</span></font>, Floor 6, Buenos Aires, Argentina</div></div></div></div></div></div></div></div>