tag:blogger.com,1999:blog-1806360094658697411.post39495923321889634..comments2018-08-07T04:52:02.281-04:00Comments on The Lowly Programmer: The Game of Life, part 2: HashLifeEric Burnetthttps://plus.google.com/103760168651162106315noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-1806360094658697411.post-35702906679891806092014-09-02T22:33:54.087-04:002014-09-02T22:33:54.087-04:00I am a beginner here. I am not able to understand ...I am a beginner here. I am not able to understand the below point..Is there any proof for this to work.. Do you have any link of that, I am not able to see how this works(tried) doing this manually in paper too(cumbersome)..Can you please explain why you are considering only the center core part and neglecting the corners?<br />" in the Game of Life a square of (n)x(n) points fully dictates the inner (n-2)x(n-2) core one generation forward, the inner (n/2)x(n/2) core n/4 generations forward,"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-68604754521708655402013-06-06T09:45:13.674-04:002013-06-06T09:45:13.674-04:00A node - as in the specific points it represents -...A node - as in the specific points it represents - is uniquely defined by the four sub-nodes it's composed of. Canonical versions of each node are put into a hash table. The cached _next is not part of the key (only the addresses of the sub-nodes are) but is still stored on the node. So when looking one up to find the canonical version, you'll find the stored node's cached _next at the same time. Similarly, if you calculate the inner core of a node, you store it as _next in the canonical node in the hash table, to be easily found later.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-57145579754386331552013-06-06T03:30:10.062-04:002013-06-06T03:30:10.062-04:00If the stored one already has a cached_next,how do...If the stored one already has a cached_next,how do we come to know about it,i.e how does the hash table help us in searching for it? Dr.Dobb's say" Canonicalizing the nodes requires a simple hash set with the usual recurrence on trees, so the hash function of a node can be as simple as some mixing of the addresses of the four sub-nodes".I couldn't interpret these lines at all.<br />Parikshit Khannohttps://www.blogger.com/profile/12953083405737499517noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-11950377332022740112013-06-05T09:29:51.184-04:002013-06-05T09:29:51.184-04:00Yes, the center should be stored whenever it's...Yes, the center should be stored whenever it's calculated. That's _next in my implementation.<br /><br />For searching, that's where the bottom-up and immutable restrictions come into play. When you make a new node of size 2^n, it's built out of four smaller nodes of size 2^n-1. We know these nodes will be unique already, so to check if we've just made a duplicate (of size 2^n), we need to check if there is already a node stored with the same four components (nw, ne, sw, se). If there isn't, add the new node you just created to the hash table. If there is, throw away the one you made and use the stored one instead. And if that stored one already has a cached _next, great - you now have the recursive center for free.Eric Burnetthttps://www.blogger.com/profile/10741882872804697111noreply@blogger.comtag:blogger.com,1999:blog-1806360094658697411.post-88343850641326354332013-06-05T08:29:24.051-04:002013-06-05T08:29:24.051-04:00I was told that while evaluating the result,i.e th...I was told that while evaluating the result,i.e the center(by recursion) for each node(of whatever size),I should store it, and use it for further evaluations(as in the fibonacci example at Dr. Dobbâ€™s).However searching if the present node has already been encountered or not requires searching.How can this searching be avoided with the help of hash-table,i.e constant time?Parikshit Khannohttps://www.blogger.com/profile/12953083405737499517noreply@blogger.com