## Programming 5: Algorithm

Put your programming skills to the test in these challenges.

### Programming 5: Algorithm

Hello,

I'm trying to understand how to solve programming 5. It's a corrupted bz2 file transferred via FTP. Now the problem is to fix that file and uncompress it to get the png file inside.

Here is what I have been trying to do:

It appears that some particular items may have been added to the file. I know all about those items and can remove all of them with ease. It also appears that there may be some items missing from the file. I'm not sure if those will or will not matter. Some decompression that I know of (LZMA) ignore extra stuff, but I'm not so sure about missing parts of the file.

Let's assume that I have to remove all of the items added to the file. They are indistinguishable from other bytes in the file that may be of the same value. This problem then boils down to an "n choose k" math problem by iterating through each and every possibility. It's actually going to be 2^n iterations. That can be a lot computationally and take too much time.

I feel like I'm missing something else about how this bz2 compression works. Any good hints?

Thanks!
SuperHacker01
New User

Posts: 4
Joined: Wed Oct 07, 2015 3:24 pm
Blog: View Blog (0)

### Re: Programming 5: Algorithm

Did you read through this thread?
Free your mind / Think clearly

cyberdrain
Expert

Posts: 2160
Joined: Sun Nov 27, 2011 1:58 pm
Blog: View Blog (0)

### Re: Programming 5: Algorithm

I took a break from this one and have come back to it. I've made a lot of progress. I think I have the brute force algorithm down. I'm just trying to understand what I can do to limit the search space. I get what the program is supposed to do, but the example file I have contains around 37 additional items. This is an n choose k problem and therefore there are 2^37 combinations. That is 137 billion--far too many. The problem is how do I limit that? I tried dissecting the bz2 file and looking for various components of the file, but I have not been able to get through the entirety of that. It seems that the file I have is incomplete--there is no magic eos. I see PI and various values. I've looked through the file specifications to see if I could actually pick this thing apart in more detail. Any ideas on what I might look for?
SuperHacker01
New User

Posts: 4
Joined: Wed Oct 07, 2015 3:24 pm
Blog: View Blog (0)

Return to Programming

### Who is online

Users browsing this forum: No registered users and 0 guests