6 ms·

I feel like if the FAQ requires not using filename shenanigans then the slight of hand was illegal the whole way.

by l33t7332273 2y ago

spott 2y ago
The FAQ was not part of the challenge statement. It was part of the newsgroup I believe.
stavros 2y ago
He didn't use filenames, he used files, and if that were illegal, Mike shouldn't have accepted it.
- anamexis 2y ago
  He does use the filenames. If you change the filenames randomly (such that the files sort differently), it does not work.
  - Dylan16807 2y ago
    > such that the files sort differently But if you change them without making them sort differently, everything is fine. He depends on the order, not the filenames. You could even remove the filenames entirely, as long as you patch the code to account for such a strange environment.
    - mafuy 2y ago
      Not really a good point. If the order of bytes does not matter, then I can compress any file of your liking to O(log n) size :P
      - Dylan16807 2y ago
        Wait, whose point are you saying is not good? I'm saying order does matter and it's the only thing that matters about the separate files using this code.
        anamexis 2y ago
        I think the question is, if you remove the filenames entirely, how do you keep the parts ordered? (Someone else suggested sorting them by file size.)
        Dylan16807 2y ago
        You have to be storing them outside a traditional filesystem to not have filenames, so the way you keep them ordered depends on what your storage mechanism is. For example, you could store them in a Set object in many programming languages, one that preserves insertion order. Or you could be extracting them one by one from a tar file that has blank filenames stored in it.
        anamexis 2y ago
        For the Set example, where would the insertion order come from? For the tar file, the tar file would be larger than the input file it's supposed to be "compressing".
        Dylan16807 2y ago
        > For the Set example, where would the insertion order come from? It would come from however the files were transferred from competitor computer to verifier computer. > For the tar file, the tar file would be larger than the input file it's supposed to be "compressing". It sure would be! I don't see how that's relevant to the filename discussion though?
        anamexis 2y ago
        The whole point of the filename discussion is that it's a trick to "compress" the data, such that the sum of the file size of the input files is smaller than the file size of the decompressed output file. Neither of your ideas work with this. In terms of just transferring the files in order, then you need to delineate the start and end of each file, which will take more space than the byte you are removing. Same with the tar file.
  - hombre_fatal 2y ago
    Not in any significant way. The decompressor could be changed to require you to feed the files into it in the correct order or expect some other sorting. What you're saying is like saying that you encoded info in filenames because decompress.sh expects a file "compressed.dat" to exist. It's not describing any meaningful part of the scheme.
    - anamexis 2y ago
      The filenames contain information that you need in some way for the scheme to work. You are combining different parts and inserting a missing byte every time you combine the files. You need to combine the parts in the correct order, and the order is part of the information that makes this work. If the ordering isn't coming from filenames, it needs to come from somewhere else.
      - mhandley 2y ago
        You could do the same spitting trick but only split at progressively increasing file lengths at the character '5'. The "compression" would be worse, so you'd need a larger starting file, but you could still satisfy the requirements this way and be independent of the filenames. The decompressor would just sort the files by increasing length before merging.
        anamexis 2y ago
        That's a neat idea.
        gus_massa 2y ago
        Nice idea, but doesn't this require a linear increase of the length of the partial files and a quadratic size of the original file? If the length of a file is X, then in the next file you must skip the first X characters and look for a "5" that in average is in the X+128 position. So the average length of the Nth file is 128*N and if you want to reduce C bytes the size of the original file should be ~128C^2/2 (instead of the linear 128*C in the article).

I feel like if the FAQ requires not using filename shenanigans then the slight of hand was illegal the whole way.

spott 2y ago

The FAQ was not part of the challenge statement. It was part of the newsgroup I believe.

stavros 2y ago

He didn't use filenames, he used files, and if that were illegal, Mike shouldn't have accepted it.

anamexis 2y ago
He does use the filenames. If you change the filenames randomly (such that the files sort differently), it does not work.
- Dylan16807 2y ago
  > such that the files sort differently But if you change them without making them sort differently, everything is fine. He depends on the order, not the filenames. You could even remove the filenames entirely, as long as you patch the code to account for such a strange environment.
  - mafuy 2y ago
    Not really a good point. If the order of bytes does not matter, then I can compress any file of your liking to O(log n) size :P
    - Dylan16807 2y ago
      Wait, whose point are you saying is not good? I'm saying order does matter and it's the only thing that matters about the separate files using this code.
      - anamexis 2y ago
        I think the question is, if you remove the filenames entirely, how do you keep the parts ordered? (Someone else suggested sorting them by file size.)
        Dylan16807 2y ago
        You have to be storing them outside a traditional filesystem to not have filenames, so the way you keep them ordered depends on what your storage mechanism is. For example, you could store them in a Set object in many programming languages, one that preserves insertion order. Or you could be extracting them one by one from a tar file that has blank filenames stored in it.
        anamexis 2y ago
        For the Set example, where would the insertion order come from? For the tar file, the tar file would be larger than the input file it's supposed to be "compressing".
        Dylan16807 2y ago
        > For the Set example, where would the insertion order come from? It would come from however the files were transferred from competitor computer to verifier computer. > For the tar file, the tar file would be larger than the input file it's supposed to be "compressing". It sure would be! I don't see how that's relevant to the filename discussion though?
        anamexis 2y ago
        The whole point of the filename discussion is that it's a trick to "compress" the data, such that the sum of the file size of the input files is smaller than the file size of the decompressed output file. Neither of your ideas work with this. In terms of just transferring the files in order, then you need to delineate the start and end of each file, which will take more space than the byte you are removing. Same with the tar file.
- hombre_fatal 2y ago
  Not in any significant way. The decompressor could be changed to require you to feed the files into it in the correct order or expect some other sorting. What you're saying is like saying that you encoded info in filenames because decompress.sh expects a file "compressed.dat" to exist. It's not describing any meaningful part of the scheme.
  - anamexis 2y ago
    The filenames contain information that you need in some way for the scheme to work. You are combining different parts and inserting a missing byte every time you combine the files. You need to combine the parts in the correct order, and the order is part of the information that makes this work. If the ordering isn't coming from filenames, it needs to come from somewhere else.
    - mhandley 2y ago
      You could do the same spitting trick but only split at progressively increasing file lengths at the character '5'. The "compression" would be worse, so you'd need a larger starting file, but you could still satisfy the requirements this way and be independent of the filenames. The decompressor would just sort the files by increasing length before merging.
      - anamexis 2y ago
        That's a neat idea.
      - gus_massa 2y ago
        Nice idea, but doesn't this require a linear increase of the length of the partial files and a quadratic size of the original file? If the length of a file is X, then in the next file you must skip the first X characters and look for a "5" that in average is in the X+128 position. So the average length of the Nth file is 128*N and if you want to reduce C bytes the size of the original file should be ~128C^2/2 (instead of the linear 128*C in the article).