Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

alexanderpruss.blogspot.com

Post reply on HN
Print view View original

101–110 of 170 posts

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#101

Post by [deleted] »

HALtheWise wrote: post #58
davidjohnstone wrote: post #17

Earlier quoted context omitted.

To improve compression of a sorted list of words you can replace the (initial) letters repeated from the word above with spaces before compression and add them back as an extra step after decompression. For example, if the previous word was "apple", the next entry will be " y" ("apply", edit: HN removes extra spaces, so this should be four spaces + "y") ("apple" will probably already be entered as " le" (three spaces…

Because all the words are five letters here, you should be fine to elide leading spaces in this case.

[deleted]

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#102

Post by [deleted] »

iforgotpassword wrote: post #83
justinlloyd wrote: post #71

I love little compression hacks like the one given in the article. I created a word search game way back in late 1978/early 1979 4KB of RAM. I had about 2KB for storing the word database. And I recall I had about 2,500 words. Which I had to type in by hand. I used the 26 tables of words trick too, to drop the first letter. I also treated each word being made up of 32 symbols. I called them letters, but they didn't re…

Man, at 11 my programs mainly consisted of INPUT, PRINT and GOTO, which I wrote on my uncle's brand new IBM XT.

[deleted]

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#103

Post by creatonez »

davidjohnstone wrote: post #17
jagged-chisel wrote: post #3

And far better than gzip compression. Nice work. My takeaway is that context matters - this is not General Purpose Compression, but compression made specifically for this case. Good Stuff.

To improve compression of a sorted list of words you can replace the (initial) letters repeated from the word above with spaces before compression and add them back as an extra step after decompression. For example, if the previous word was "apple", the next entry will be " y" ("apply", edit: HN removes extra spaces, so this should be four spaces + "y") ("apple" will probably already be entered as " le" (three spaces…

Testing this with zstd -19

29.44% - Original sorted list just compressed with zstd

22.45% - Matching prefix characters from previous word replaced with space

19.38% - Matching prefix characters from previous word removed

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#105

Post by notpushkin »

quicktwo wrote: post #56

You can get down to 15,559 bytes by combining a trie with Huffman coding: https://github.com/adamcw/wordle-trie-packing However, this doesn't beat general Brotli encoding of a ASCII trie representation, which gets down to 14,180 bytes (but needs an experience decoder), but goes to show general purpose compression is still really really good these days.

Huffman coding was the first thing that jumped into my mind, too. Reminds me of the time we implemented a subset of bzip2 on a CS class in highschool.

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#106

Post by Closi »

anon_123g987 wrote: post #2

> I don’t have a good feel for how fast the Game Boy runs, so I did a bit of speed optimization. This sounds like a very wrong approach to optimization. I mean, if you don't know exactly what and how to optimize, or if there's a need for optimization at all, then what are you doing?

The idea of 'don't optimize if you don't have to' probably doesn't apply as much when developing a game for a 8-bit processor that runs at 4mhz with 8kb of working RAM, and when you are building a program which is inherently aiming to push the capabilities of the hardware with clever coding tricks (I mean the whole project is basically an exercise in optimization).

I think OP was saying they weren't sure if the original algorithm would be too slow to run under these conditions, and didn't have the ability to test it at the time, so they wrote it in a way which increased the chances of it running quickly considering the system limitations.

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#107

Post by tragomaskhalos »

There was a pretty decent Scrabble available for the ZX Spectrum - around 41k for vocab + code. I always imagined that must have used a fairly ingenious compression mechanism for its dictionary, especially given the types of fairly open searching it would need to do.

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#108

Post by [deleted] »

hinkley wrote: post #78
habibur wrote: post #64

Earlier quoted context omitted.

> This example above is the entire dict file, not the wordle fil only 5 letter words from the dict, not the entire one. check the grep command at the beginning.

Right, but it's still many times larger and compresses better.

[deleted]

Re: Game Boy Wordle clone: How to compress 12972 five-letter words to 17871 bytes

#110

Post by Someone »

jhgb wrote: post #90
Someone wrote: post #60

My first thought would be “DAWG”. That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. https://www.cs.cmu.edu/afs/cs/academic/class/15451-s06/www/l... compresses a 780k word list into 175k. That’s about 22% of the size. This accomplishes 27%. This list is a lot shorter, so there will be fewer opportunities for savings. On the other hand, all words are five letters, so the ‘i…

> That’s a smart way to represent a trie, with identical ‘tail’ ends of the trie merged into one. That sounds like a DAG-shaped FSM to me...? At least I can't spot the difference.

That’s correct. https://en.wikipedia.org/wiki/Directed_acyclic_word_graph links it to Deterministic acyclic finite state automaton (https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_s...)

I guess a strategy for compressing a word set could be to compile a regular expression recognizing it using a good regex engine and to then construct a compact representation of the resulting automaton.

Post reply on HN