I feel people often miss opportunities to map between (potentially complex, high entropy) state spaces into simple linear sequences of possible states and then either use those sequences to store the complex state data as a simple number or use the state of a system to encode data of some kind.
Like, if you use a limited 7-bit character set encoding for text and map that to a number in a sequence of possible orderings of a deck of 52 cards, you can store 32 characters (conveniently sized for passwords you might not want people to know are passwords).
Since 15^16 < 2^64, you can still use a 64 bit state to reach 2^15=32768, which does not seem to be reachable in practice (the previous state would fill the whole board!)
edit: Explanation of the 131072 cap: https://puzzling.stackexchange.com/questions/48/what-is-the-...
Also, in one of the answers there someone claims to have achieved 65536 in practice
The state in this implementation also stores a random seed (between 0 and 99, exclusive), so using 16^16 for the state would leave nothing for the random seed.
Using this representation is great: it lets me pack a whole gameboard into a single machine register, which makes it super efficient. In this case I see that you’re able to pack in a seed value to enable replayability - neat!
Now log_2(11^16)=55.34, thus 56 bits are sufficient. That's tight!
There is 18 states. The final possible board state is 16 increasing power of 2s starting at 4, since it's possible for a tile to spawn in as 4. Then you also need states for 2 and empty making for a total of 18.
Usually you can encode special states in a more compact form because the type of specialness is additional information meaning the single special bit is all you need to grow by.
A bloated form for the final state would be a bit to indicate specialness, 7 bits for specialness mode. End state mode is encoded as the turn before plus direction. So adding 10 bits in all, there's almost certainly enough in the knowledge that it is an end state to encode the board in 10 bits fewer, eliminating all expansion except for the specialness bit.
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!
w) squish ;;
a) rot; squish; rot; rot; rot ;;
s) rot; rot; squish; rot; rot ;;
d) rot; rot; rot; squish; rot ;; curl -fsSL https://raw.githubusercontent.com/izabera/bitwise-challenge-2048/develop/2048.bash -o "$HOME/bin/2048" && chmod +x "$HOME/bin/2048" && 2048 curl -fsSL https://raw.githubusercontent.com/izabera/bitwise-challenge-2048/413abf35be0f47c4947a5ebd6d581355383041e1/2048.bash -o "$HOME/bin/2048" && chmod +x "$HOME/bin/2048" && 2048
meta-level•5h ago
JoeOfTexas•5h ago