3 ms·
WARNING: This is wrong! 3^2 = 9, so we can't encode it in 8 different symbols, but left here for history. The 15 bit encoding could be visualized in a differen
by antirez 3y ago
WARNING: This is wrong! 3^2 = 9, so we can't encode it in 8 different symbols, but left here for history.
The 15 bit encoding could be visualized in a different way, too, that is using 3 bits to represent two successive cells state:
000 "__"
001 "X_"
010 "_X"
011 "XX"
100 "XO"
101 "OX"
110 "O_"
111 "_O"
There are 5 successive cells (4.5 actually, 9/2, but we need to be discrete here, and discard the last), so 5*3 = 15.
However this encoding shows that if you want to represent multiple boards one after the other you are actually just using 13.5 bits for each board, as it should be in theory.
Because to represent 18 total cells (two boards) you need 9*3 bits = 27/2 = 13.5 bits per board.
- occamrazor 3y agoIt doesn't work. There is no encoding for "OO".
- antirez 3y agoYou are right! Sorry totally overlooked this :) Thanks.
- AgentOrange1234 3y agoWow good eye?
- thequux 3y agoIndeed, this is wrong. However, 3^3 is 27, which is less than 32, so you can easily encode each row in 5 bits. The encoding into those 5 bits is precisely the base-3 encoding from the article, so I'll leave it as an exercise for the reader.
- antirez 3y agoGood observation! Always useful to see things from a different angle, that was indeed what I was trying to say in the original post (even if it was wrong).