There's a famous anecdote about human unshredding: when the Iranian revolutionary took over the US embassy in 1979, they captured the shredded remains of secret documents. They took those shredding to the carpet weavers Iran is so famous of, who manually rewoven the shreds into the original documents (See <a href="http://en.wikisource.org/wiki/Documents_seized_from_the_U.S._Embassy_in_Tehran/Shredded_Documents" rel="nofollow">http://en.wikisource.org/wiki/Documents_seized_from_the_U.S....</a>)
Interestingly enough, DARPA is running a similar challenge (their prize is a lot better): <a href="http://www.darpa.mil/shredder_splash.aspx#Splash" rel="nofollow">http://www.darpa.mil/shredder_splash.aspx#Splash</a>
I thought it would be a fun thing to do tonight until I saw all the tips given at the end of the article. They basically give the solution, it's not funny anymore :(.
Warning, spoiler?<p>My first take on it was the following:
Take the average of the differences between each pixel and the pixel adjacent to it over each column and store that as, say, X[].
Find some maximum number such that the sum of every nth column of X - the sum of all other rows of X is maximised. That's the column width.
Split into a series of columns, use stable matching to match columns based on the sum of differences between rightmost male pixel and leftmost female pixel over all rows.
Use stable marrage to give you a partial ordering, turn into a complete ordering and unscramble the image.<p>Any better/more elegant solutions?
I find it strange that they don't provide an interface that the desired program should implement. For example, "provide the input image as a command line parameter to the script / binary, write the output to out.jpg"<p>Because of this, is someone going to actually take the time to understand what assumptions people make to run the program? If there was an interface, they could just run a script to test submissions...
The tips seem to be just a crude pixel matcher. Seems much more elegant to transfer the image into the frequency domain via FFT and find edges that way.
Isn't this extremely obvious? Couldn't you just take the first slice, calculate the total color difference between its right edge pixels and the corresponding left edge pixels of each of the other slices, and stick it next to the one with least difference, then repeat?<p>I mean, you'd need to specify some threshold to handle slices on the ends, and maybe use sum of (difference^2) instead of just the sum, but it shouldn't be hard at all. Am I missing something?
Interesting. A 90 degree phase change makes a huge difference<p>> For maximum security, documents should be shredded so that the words of the document go through the shredder horizontally (i.e. perpendicular to the blades). Many of the documents in the Enron Accounting scandals were fed through the shredder the wrong way, making them easier to reassemble.
For anyone who's thinking of using Ruby I recommend OilyPNG instead of RMagick. It's a c extension to ChunkyPNG and is much faster if you don't need all of the fancy filters that come with ImageMagick.<p><a href="https://github.com/wvanbergen/oily_png" rel="nofollow">https://github.com/wvanbergen/oily_png</a>
Looks like I was able to do it. I'm not sure if they will be happy to get a result in C#, though.<p>Also, not as easy as I thought it would be. A friend had to give me some help with the math to match the stripes.<p>Edit: How long did you guys take to figure this out? I took nearly 4 hours.
You know you're done if you understand what this image means (and how it was made): <a href="http://i.imgur.com/Kn7Za.png" rel="nofollow">http://i.imgur.com/Kn7Za.png</a>
Although Instagram promised a brand-spankin’ new Instagram shirt if you complete the challenge correctly, they are only sending out stickers.<p>I hope they are not another Zynga :).