141–150 of 175 posts
I am actually surprised that Patrick did not compress the original data to 0 bytes by keeping all the data in filenames. That would be the ultimate troll ;)
I disagree. You could legitimately say he just stored the data in the metadata fields. But files have a size, even as a stream, completely regardless of metadata. I think this is a more clever hack.
I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it.…
> If you design an impossible game, the only possible thing for anyone to do is to break it. Which is the Kobayashi Maru in a nutshell. In that fictional case, Kirk was disqualified but also received a commendation.
I don't know if the novel is canon, but it ought to be.
Kirk beat it by cheating, Scotty beat it legitimately, then proved that what he did only worked in the simulation.
Earlier quoted context omitted.
Note that he never guaranteed to leave the files with the same file names, and without that, Patrick's trick wouldn't have worked. Given the fact that Patrick made the rules concerning multiple files, and that they were intentionally tricky, I think it's fair to interpret them in that spirit - as a trick. Notably, even without the ordering there is still some information leakage purely in terms of file sizes, but tha…
He could have ordered the files by size pretty easily. Trick still would have worked. No fancy requirements needed. Just making the files available in any manner. And yes there needs to be a way to know which file(s) are the compressed data, that loophole would disqualify any entry.
Another scheme: chop it up into files of increasing length, the difference being 1..256, encoding a byte (ignore the last difference).
EDIT more efficient to increase in length by 1 or 2, encoding a bit.
Earlier quoted context omitted.
If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? There is no such thing as random file . Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". It can be random looking, you can run some statistic analysis on the byte sequence and say "It's probably generated by some good random algorithm", but even h…
> Randomness is not a property of a single file. You can't look at a byte sequence and say that "it's random". Interestingly, this is less true than you might think. The mathematics of Kolmogorov complexity[1] formalizes the idea that a given finite fixed string is "random". In this framework, you can have a byte sequence that definitely is random. (However, your second sentence I quoted is still technically true her…
I read into the wiki article and this approach is certainly interesting. However this complexity depends on the description language so there is no unique way to determine if a string is random.
I didn't see anything that mentions run-time in the challenge. I think a good compression challenge should mention about run-time. Theoretically, it would be possible to hash parts of the file and then brute force the hash in the decompressor. This would take a lot of time but would work.
Except if the hash is smaller than the source data, then with a good hash, there will be multiple source datasets that hash to the same result, which makes your decompression program unreliable. You could well bruteforce the wrong answer.
I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it.…
I feel the same way when casinos bust card counters. You use math to take money from suckers. When other people use your rules and better math to take money from you, that's suddenly deeply immoral.
Why wouldn't binary run length encoding work here? E.g. "compressing" 11100110 to 30020 for example?
Compression relies on entropy. There's not enough entropy in the random file your your run-length encoding to work. I think the data is available so you can always try to beat the bet.
A binary string of all ones followed by all zeroes has very low entropy, while a purely random binary string has high entropy. (I think. I'm skimming the Wikipedia article on entropy now)
In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes. It's just a shame that the heat death of the universe will probably occur before your program finishes.
Earlier quoted context omitted.
Compression relies on entropy. There's not enough entropy in the random file your your run-length encoding to work. I think the data is available so you can always try to beat the bet.
I may be completely misinformed, but I think you meant to say there's too much entropy. A binary string of all ones followed by all zeroes has very low entropy, while a purely random binary string has high entropy. (I think. I'm skimming the Wikipedia article on entropy now)
http://www.si.com/vault/1972/10/09/618832/soundings-from-tit...
(The risk being that half of it is made up, but he definitely had a reputation for this sort of thing.)
"You might wonder why, if I was the best golfer in the world, like I say I was, I didn't turn pro and win all the championships? Well, you were liable to win a golf bag if you won a tournament in those days. A top pro wouldn't win as much in a year as I would in a week as a hustler. People would get to know a pro, and I wanted to keep my skill a secret as far as possible. I didn't care about championships. I wanted the cash."