Moderator: Moderators
Oh, yeah, you can't escape it.orion70 wrote: ↑Tue Feb 01, 2022 2:08 am Seems like this game is very popular...
https://nypost.com/2022/01/31/new-york- ... n-figures/
chysn wrote: ↑Tue Feb 01, 2022 8:52 am You can't just try to jam 8938 x 5 bytes into memory. First, I'm storing each letter in five bits instead of 8, so letters need to be stored across byte boundaries. But this wasn't enough, because (9K x 5 letters x 5 bits)/8 bits is still almost exactly as much a +24K VIC has. So the words are alphabetized, with only the last four letters stored in three bytes, and there's a 52-byte table that keeps track of the starting offset of each letter. This gets a 9000-entry word list down to just over 26K.
One bit of each 3-byte packet is used as a starting letter boundary, an easy way to stop the search. Another bit is used to mark the 3000 most-common words, which can be selected as the puzzle.
Interesting, this seems like a simplified version of Deterministic acyclic finite state automatonchysn wrote: ↑Tue Feb 01, 2022 8:52 am You can't just try to jam 8938 x 5 bytes into memory. First, I'm storing each letter in five bits instead of 8, so letters need to be stored across byte boundaries. But this wasn't enough, because (9K x 5 letters x 5 bits)/8 bits is still almost exactly as much a +24K VIC has. So the words are alphabetized, with only the last four letters stored in three bytes, and there's a 52-byte table that keeps track of the starting offset of each letter. This gets a 9000-entry word list down to just over 26K.
One bit of each 3-byte packet is used as a starting letter boundary, an easy way to stop the search. Another bit is used to mark the 3000 most-common words, which can be selected as the puzzle.
That looks like a cool thing, thanks for the link! I'll check that out in detail later today.beamrider wrote: ↑Wed Feb 02, 2022 4:19 am Interesting, this seems like a simplified version of Deterministic acyclic finite state automaton
I think I might have had some memory savings doing a tree for the first two characters, certainly not more than that. If the letter table isn't complete (that is, 26 two-byte offsets), then a third byte per letter must be used to identify the letter. This eats up the savings of the letter being implicit in the index. But a second-level index would use 1352 bytes, plus 9000 x 2 (2 bytes to store three letters), so a significant savings over a one-letter index. The code complexity would have gone up a bit, though. If I had needed to store an extra, say, 3000 words, I would have had to do this.I guess you could reduce it even further by building a full tree, but in this case you didn't need the additional lookup complexity?
)
