undefined | Better HN

0 pointstromp9y ago0 comments

I can't say, because I didn't enumerate them. I only counted them. See

http://tromp.github.io/go/legal.html

for the method used, which is a form of dynamic programming.

0 comments

Though if it is dynamic programming, then it should be possible for you to answer dogecoinbase's question using not much more computational power than you used to count them in the first place, right?

If you think of dynamic programming as counting the number of paths in a directed graph (in this case, from skimming the paper, the nodes correspond to border states), then given a path number, you can trace the path backwards through the graph, as long as you remember the number of paths ending in every vertex.

trompOP9y ago

Yes, you could if you preserved all intermediate counts. But the graph I used has 362 layers each of which can have up to 363 billion nodes, so I had to recycle the space used for the counts (4TB per layer). Also, I didn't even compute with full counts. I reconstructed them using the Chinese Remaineder theorem from 9 separate modular counts. So, yes it's possible, but highly impractical...

j / k navigate · click thread line to collapse