4 ms·
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
by nine_k 1y ago
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!
- eurleif 1y agoI included empty in my count.
- sltkr 1y agoThat'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).
- dmurray 1y agoIs 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.
- YurgenJurgensen 1y agoAlthough 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.
- whereismyacc 1y agoyes but there could conceivably be better tricks to discover
- shiandow 1y agoIt 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
- sltkr 1y agoIt's not quite literally the smallest, but the interesting question is what fraction of all states represent such unreachable states.