←back to thread

The $5000 Compression Challenge (2001)

(www.patrickcraig.co.uk)
181 points ekiauhce | 1 comments | 23 Nov 24 21:10 UTC | HN request time: 0.207s | source
Show context
johnfn ◴[23 Nov 24 23:42 UTC] No.42224779[source]▶
This is hilarious, but Mike’s behavior boils my blood. To switch the rules when fairly beaten is just so scummy!

Of course Patrick’s solution occurred to me immediately once he started talking about splitting up the file. :)

Then I got to wondering if it would be possible to compress a large enough file and save a few bytes, in the spirit of what Mike actually wanted. For instance, if you tried encrypting with a bunch of random keys, you’ll find some such that the result ends with n 0s (say), so then your result could be something like encrypted + key + n. Typically you’d expect to find that the length of the encryption key would be roughly the length of the number of 0s, so you wouldn’t actually net any savings. But I think if you searched long enough, you might “get lucky” and find a key that generated more 0s then the length of the key, so you could theoretically win the challenge. Of course you’d have to somehow embed a program which could decrypt and reassemble everything in a tiny amount of space, but it still doesn’t seem impossible like Mike seems to suggest. Perhaps just requires an intractable amount of computing power. :)

I’m not sure if any of that made sense. I think I’m using the wrong terms for things.

replies(1): >>42230945 #
1. crazygringo ◴[24 Nov 24 21:51 UTC] No.42230945[source]▶
I remember reading from a previous thread how yes you can do something like that (or lots of other techniques) but they will only work on a small percentage of files.

That sometimes the smallest decompressor (including the key, in your example) will result in overall less space, but usually it will result in more (because the smallest key that generates 10 zeros happens to be 14 digits long, etc.).

And so ultimately the more interesting question becomes about those probabilities, and therefore what is the right entry price for the bet to be even?