3 ms·
It is definitely possible to win this challenge though. Consider an arbitrary long series of integers. Somewhere within this series of integers, there will be
by RyanZAG 14y ago
It is definitely possible to win this challenge though.
Consider an arbitrary long series of integers. Somewhere within this series of integers, there will be some kind of randomly created pattern, since this is a property of an infinite set. eg. somewhere within the data set, there could be the values [1, 2, 3, ... 10] or [1, 3, 9, .. 27] or [1, 2, 4, 16, 32] - it does not matter which of these patterns, exist, only that there does exist some mathematical pattern in the data.
The chances of there being no pattern in a big enough set of random data is impossible as there is a finite number of possible data combinations for bytes [1..256][1..256] etc. I guess a data set of 256^256 bytes would guarantee a pattern, but I'm sure there is a far smaller number that would give 99% confidence.
Once you find a pattern in the data, you can remove that pattern and replace it with code that will recreate the pattern using a data offset. ie. you remove the pattern from the data completely, and replace it with a smaller piece of code to recreate that pattern exactly and insert it into the correct position.
The key here is that once the data has been generated, it is no longer 'random data', but a fixed input. eg, you cannot compress a random unknown string of bytes, but you can compress the string [1,2,4,16..]
The output data would have all possible mathematical patterns removed from it, and the decompression code would be just a list of mathematical functions and data offset points.
- lifthrasiir 14y agoYou are recreating Kolmogorov complexity there. Kolmogorov complexity is defined as the minimal amount of program (for some programming language) to recreate the given string. By the definition, your strategy will compress the data no better than its Kolmogorov complexity. In this aspect, Kolmogorov complexity measures the data's true randomness. If the random data has been generated correctly its complexity should be near its length, however, so your strategy won't work. (And there is enough evidence that this was the case.) It does not matter whether the data is already known or not; it is the data's inherent randomness prohibiting you to compress it. To be sure, of course, Patrick Craig did not compress it in the pure information theoretic sense. Mike Goldman failed to equate the goal to that information theoretic compression however.
- RyanZAG 14y agoIf you pipe a random process into an image viewer, eventually you will get an image that can be compressed with PNG compression. If you let the random process run, you will eventually get enough of these images compressible by PNG that will allow you to save enough bytes to fit in a PNG decompression library. This may only occur after a ridiculous amount of bytes, but it is guaranteed to eventually occur following the properties of randomness. So the method will work, but it may take a very large amount of data before it does. If the method does not work, it implies that a random process cannot generate an image that can be compressed with PNG - and that is definitely false.
- jgeralnik 14y agoBut you also have to store the index at which the image occurs, and the index is bigger than the gains from the compression. This is similar to the argument that since pi is (probably) normal, any sequence of characters appears in it and we can simply use indexes into pi instead of storing numbers. The problem is that given a file of size X, that sequence of X bytes probably only occurs at more than 2^X places into pi.