Hacker News Reader

Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.

lim (k -> 0) (n^k / (k!)) is actually 0. k! grows faster than n^k for any constant n.

I should have been a bit more careful I suppose, but in practice you can't increase k indefinitely without also increasing n anyway. In particular n >= k, so at worst it would be something like k^k / k!.

Really not sure why the state space would only grow as n^k / k!. As well as what n and k are in this case. Adding more tiles or more actors would both dramatically increase the size of the state space for that input.

That question should go to the parent comment. I only corrected the assumption.

On your comment though, I don't think there's much of "drama" in increasing the state space. Really it is just under 2 bits per cell by width by height. I would say it grows exponentially to the size of the board.

Reply on news.ycombinator.com