Hacker News Reader

Comment by nine_k | Hacker News Reader

13 possible states, because the empty state is important, too. But they fit nicely into 4 bits.

It would be mildly interesting to super-package the state into the theoretically smallest possible amount of bits: 13 * 16 = 665416609183179841 possible states, which is approximately 2 * 59.2, so 60 bits would be enough, with some margin. A whole hex digit shorter!

View on HN

That's what the code already does. It packs 16 fields into a base 12 representation that takes up 57.36 bits and uses the remaining 6.64 bits to store a random seed between 0 and 99 (exclusive).

I included empty in my count.

Is that really the theoretically smallest?

I think you can prove that some states representable by your proposal are unreachable. E.g. a board with 16 2s. So there might be another bit to spare.

Although at that point, your attempts to cut the state will probably resemble a look-up table enumerating every valid board state, which obviously balloons the executable size by a large amount.

yes but there could conceivably be better tricks to discover

It ought to be possible to generate valid states ordered by total value and lexicographical order or something.

But whether that is practical is a different matter. It does allow you to unambiguously define state #5546335 with the lowest number of bits

It's not quite literally the smallest, but the interesting question is what fraction of all states represent such unreachable states.

Reply on news.ycombinator.com