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

11–20 of 170 posts

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

#11

Post by they4kman »

rchrch wrote: post #5

Did you compare this to compression with a trie?

I imagine only having to store 5 bits for the differences accounts for a large swath of the savings. With the first letter bucketing the rest of the words in a sort of trie-like behaviour, I wonder if there's enough duplication of successive characters for a full trie to be worth it. After all, there would need to be extra bits used to store leaf/node identity, as well as whether there are _more_ nodes past the current leaf. I suppose instead of using markers to denote ends, the parent node could store a count, but that might be wasteful for buckets at the fourth character.

I'm very curious about this.

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

#13

Post by glandium »

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?

I read it as "I don't know how fast a Game Boy runs, so I optimized for speed rather than minimal size"

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

#14

Post by willis936 »

>The Answers could be stored as a bitmap of length 12972, which would be 1622 bytes. But this would make the code for generating a random word more complicated and slower.

You could run RLE on that as well for a decent storage savings.

Another thought: you could order the list of words such that the first 1622 words are answers. That way you don't need to store the answer list and checking is as fast as comparing the value of a memory address. This would probably hurt the differential coding performance though.

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

#15

Post by noduerme »

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.

Even though it's domain specific, it's a pretty clever idea that could carry over to other things. I wonder if you couldn't cleverly reorder any text document in chunks and get the maximum word differences per chunk, keep a map of word order and compress it this way. With a 2 bit minimum per word, maybe you could take all replica words in two bits.

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

#17

Post by davidjohnstone »

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 + "le")). In theory a compression algorithm could handle this automatically, but in practice this gives better compression.

This is conceptually similar to what OP does by storing the (numerical) difference between the words. Also, if you have a list of numbers that aren't random, they generally compress better if you turn it into a list of the differences between the numbers.

A simple compression algorithm (miniLZO is apparently 6KB compiled) might be small enough and save enough bytes with compression to make it worth it for OP.

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

#19

Post by nerfhammer »

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.

It's similar to the compression techniques you might use in column store

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

#20

Post by throwanem »

indigodaddy wrote: post #18

Bug? See screenshot. My 5th guess shouldn’t have gone down like that for a conventional Wordle clone. https://ibb.co/93CdVWv

Looks like maybe a bug in highlighting multiple occurrences of a letter in the same word, yeah.
Post reply on HN