Re:Game Boy Wordle clone: How to compress 12972 five-letter ...
by ProjectBarks on Sunday February 20, 2022 @02:08AM
(#30403852)
I think you are thinking of a trie
[ Parent
| on HN ]
Re:Game Boy Wordle clone: How to compress 12972 five-letter ...
by hinkley on Sunday February 20, 2022 @02:17AM
(#30403882)
No, not a trie.
After throwing more words at the Google Wall, it finally allowed that what I'm thinking of is the Shortest Superstring Problem.
Re:Game Boy Wordle clone: How to compress 12972 five-letter ...
by hinkley on Sunday February 20, 2022 @09:50PM
(#30411426)
Nerd sniping indeed.
This morning without putting a whole lot of effort into this, I was able to winnow it down to 27.32 bits per word without any other trickery like 5bit packing. You need at most 1 bit per word to identify the real words, so that's 27.32+1 bits without the bitpacking. Doing 6 bits per letter drops that by 25%.
Now having put too much effort in, I'm around 21.6 + 1 bits per word, (17 bit packed) just by using SSP.