5 ms·
Like y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python. I too
by jepler 5y ago
Like y'all, I wanted to see how I could do. Of course, I didn't get all the way to tested code on a gameboy. But it does compress & decompress in Python.
I took the central idea of encoding deltas (or actually delta less 1, since the delta is always at least one; I'll just say delta below), but did it on the full five letter word. The largest delta was still less than 2*18 but bigger than 2*17. (I'm not sure why the blog mentions 20 bits as the biggest delta; I used the dataset from https://github.com/alex1770/wordle/commit/62520406365ca58a1a30d398a2bfad8666f6c3c4 https://github.com/alex1770/wordle/commit/62520406365ca58a1a...)
I decided I wanted a variable length code in bits. Manually, I found the best break-points that I could:
breaks = [16, 128, 512, 2**12, 2**18]
bitprefixes = ['0', '10', '110', '1110', '1111']
So deltas 0..15 are encoded as '0' plus a 4-bit number, deltas 16..271(=16+256-1) as '10' plus a 7-bit number, etc.
Compressed like that, my dictionary runs to 14840 bytes.
1111000000000001010110 // aahed 4839 = 4839- 0
1110100001101100 // aalii 2813 = 7652- 4839
1110110100010010 // aargh 4003 = 11655- 7652
110011000010 // aarti 339 = 11994- 11655
1111000000001101110001 // abaca 5634 = 17628- 11994
00111 // abaci 8 = 17636- 17628
00001 // aback 2 = 17638- 17636
00111 // abacs 8 = 17646- 17638
100111110 // abaft 79 = 17725- 17646
...
However, a non byte aligned code isn't ideal, especially on the gameboy's CPU which doesn't have variable bit shifts as far as I recall. Still, over 3000 bytes beckoning to be re-used for some other purpose. Did they put in a soundtrack yet?
Compressor & decompressor: https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32a0c https://gist.github.com/jepler/d502965b57fd52df0838a6def2d32...
- quicktwo 5y agoI like your trick of subtracting the prior node size if it's too small, it gets a number of offsets into the lower bucket to save some bits. I took this technique and made a few changes. Firstly, I effectively did variable length integer encoding in chunks of 3, this mildly outperformed your hand crafted prefixes. self.breaksv = [2**3, 2**6, 2**9, 2**12, 2**15, 2**18, 2**21] self.prefixesv = [ ['0'], ['1', '0'], ['1', '1', '0'], ['1', '1', '1', '0'], ['1', '1', '1', '1', '0'], ['1', '1', '1', '1', '1', '0'], ['1', '1', '1', '1', '1', '1', '0']] Secondly, I made my offsets relative to the overall solution space of 26*5, ordering the words sorting from their ends, and with a little bit of twiddling the order of the alphabet to put common letters near the start: alpha1 = "aeioustrbcdfghjklmnpqvwxyz" alpha2 = "aeioustrbcdfghjklmnpqvwxyz" alpha3 = "aeioustrbcdfghjklmnpqvwxyz" alpha4 = "aeioustrbcdfghjklmnpqvwxyz" alpha5 = "aeioustrybcdfghjklmnpqvwxz" bitmap = [] for ia, a in enumerate(alpha1): for ib, b in enumerate(alpha2): for ic, c in enumerate(alpha3): for id, d in enumerate(alpha4): for ie, e in enumerate(alpha5): bitmap.append(e+d+c+b+a in words) Doing this, and then doing the variable length encoding I got the file down to 13,181 bytes (it was 13,180 bytes, but I needed to add a 7 bit termination string so that you can properly decode the file after you write it to disk, otherwise when the file rounds to the nearest byte you have random 0s that get decoded). I'm sure with some twiddling of the alphabets some more you could save a few more bytes, but this does better than both Brotli on a ASCII trie and the Huffman Trie by almost 1KB (https://github.com/adamcw/wordle-trie-packing#all-words https://github.com/adamcw/wordle-trie-packing#all-words), so I'm very happy.