Programming 5: Algorithm

Put your programming skills to the test in these challenges.

Programming 5: Algorithm

Post by SuperHacker01 on Wed Apr 20, 2016 11:24 am
([msg=92173]see Programming 5: Algorithm[/msg])

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
New User
 
Posts: 4
Joined: Wed Oct 07, 2015 3:24 pm
Blog: View Blog (0)


Re: Programming 5: Algorithm

Post by cyberdrain on Mon Apr 25, 2016 5:54 pm
([msg=92211]see Re: Programming 5: Algorithm[/msg])

Did you read through this thread?
Free your mind / Think clearly
User avatar
cyberdrain
Expert
Expert
 
Posts: 2160
Joined: Sun Nov 27, 2011 1:58 pm
Blog: View Blog (0)


Re: Programming 5: Algorithm

Post by SuperHacker01 on Sun Nov 13, 2016 4:21 pm
([msg=93095]see Re: Programming 5: Algorithm[/msg])

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
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