31–40 of 170 posts
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' > from sys import stdin > from os import write > N = 26 ** 5 > data = bytearray((N+7)//8) > for l in stdin: > b = 0 > for c in l.strip(): > b *= 26 > b += ord(c)-ord("a") > data[b//8] |= 1 write(1, data) > ' | gzip | wc -c 12126 decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' > from sys import stdin > from os import write > N = 26 ** 5 > data = bytearray((N+7)//8) > for l in stdin: > b = 0 > for c in l.strip(): > b *= 26 > b += ord(c)-ord("a") > data[b//8] |= 1 write(1, data) > ' | gzip | wc -c 12126 decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
The memory requirements for inflate are (in bytes) 1 Any time you are tasks with crushing the living daylights out of an unordered list, always, always look at suffix sorting as an option. It might not work out as useful, but it's frequently worth the cost of checking.
I will say that given that a delta encoding was settled on, bitpacking the words first is probably a mistake, and multiplication should have been used instead. For instance using multiplication you can store the words in 24 bits without chopping off the first character and using pointers to them. That may seem a small difference but it makes the deltas he's looking at narrower. So instead of choosing 8 words in 8 bytes versus 10 words in 8 bytes, it could be 8 vs 11, possibly 12.
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' > from sys import stdin > from os import write > N = 26 ** 5 > data = bytearray((N+7)//8) > for l in stdin: > b = 0 > for c in l.strip(): > b *= 26 > b += ord(c)-ord("a") > data[b//8] |= 1 write(1, data) > ' | gzip | wc -c 12126 decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
Zlib's implementation, at least, requires more working RAM (~40 KB) than the Game Boy has (8 KB). https://github.com/madler/zlib/blob/master/zconf.h The memory requirements for inflate are (in bytes) 1
I'd have to check the version history, but while 15 bits is the default it's also the maximum, and you can go down to 8. Hardware has gotten a lot faster.
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.
Is task specific compression a thing in real life practical software engineering? As far as reducing data loads go I only came across the keyword "SQL optimization".
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' > from sys import stdin > from os import write > N = 26 ** 5 > data = bytearray((N+7)//8) > for l in stdin: > b = 0 > for c in l.strip(): > b *= 26 > b += ord(c)-ord("a") > data[b//8] |= 1 write(1, data) > ' | gzip | wc -c 12126 decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
$ grep '^[a-z]\{5\}$' /usr/share/dict/words | python -c ' > from sys import stdin > from os import write > N = 26 ** 5 > data = bytearray((N+7)//8) > for l in stdin: > b = 0 > for c in l.strip(): > b *= 26 > b += ord(c)-ord("a") > data[b//8] |= 1 write(1, data) > ' | gzip | wc -c 12126 decompression code costs extra. Though I imagine someone has a small gunzip implementation somewhere.
Green usually signifies something is correct. You should have used yellow for misplaced letters instead.
I had CRAN? in the second row, but I lost the game, because it was RANCH.
Over on http://golf.horse/ there are leaderboards for finding the smallest Javascript programs that output various word lists, including the Wordle list. I've found it to be a fun and educational challenge. I would be excited to see more submissions!
Golf.horse is measuring the payload plus the compressor, which I don't believe the author is doing, and is important when trying to be objective about the relative strength of solutions. Otherwise you can store the entire file out of band in the compressor, emit 1 bit in the output file, and then the compressor just returns the expected value on 1 and throws an error on 0 saying the file was corrupt.