←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.205s | source
Show context
Panzer04 ◴[25 Nov 24 00:19 UTC] No.42231889[source]▶
I would have expected it to be possible to compress a single arbitrary random file with a small program. I would have thought an RNG could generate a file with some weakness that allows you to compress it, although said compressor would be worse at other inputs.

Likewise this challenge would have been stronger if the requirement was to compress two provided arbitrary files :P

replies(3): >>42232185 #>>42233044 #>>42235780 #
1. codazoda ◴[25 Nov 24 12:40 UTC] No.42235780[source]▶
I expected this too, so I asked an LLM to write a quick Go program that would tell me how many bytes repeated. I created a 1.44MB file from /dev/random and then ran it through the program. Here are the bytes that repeat the most.

  Top 10 repeated byte patterns and their counts:
  Bytes: 7eda16, Count: 3
  Bytes: 65b1a4, Count: 3
  Bytes: 71d745, Count: 3
  Bytes: b72808, Count: 2
  Bytes: 60e3ee, Count: 2
  Bytes: 6e9152, Count: 2
  Bytes: 26446b, Count: 2
  Bytes: e4a05a, Count: 2
  Bytes: 67f86a, Count: 2
  Bytes: 92c487, Count: 2
Since the most common three byte sequence only appears 3 times, it seems like a non-starter. No longer byte sequences appeared more than twice either.

I generated the random digits with this:

  dd if=/dev/random of=random.bin bs=1024 count=1440