On their blog Instagram's engineering team recently posted a small Python challenge to win a T-Shirt.
Inspired by their in-office paper shredder, the team came up with the problem of reconstructing the shredded image (below) into it's original form.
On their blog, they post advice about using Python's Imaging Library, PIL to solve the problem as well as a few other guidelines and tips.
So, I had a go at solving this particular problem, and this GitHub repository contains the source code I came up with. Unfortunately, so far I have failed - this is the closest I can get to an unshredded image:
Although all the strips or shreds are correctly sorted, the resulting image is wrapped and so is incorrect. Answers on a postcard! It should of course look like this:
Since posting this, a number of other people have hit the same problem. Others (such as Fatty Beagle) have got around this by sampling surrounding pixel data rather than using absolute values of the outer most strips; by using a graph traversal to more reliably establish the outer most strips (as demonstrated by The Sociable), or through a combination of techniques involving changing colour spaces and introducing thresholds (Shatter Mediocrity). Some have even solved it using HTML5.
I have decided not to update my code and leave it as-is, because having now seen these alternative approaches I'm not up for plagiarism.
Want more? DARPA in the U.S. have posted a challenge to reconstruct shredded text based documents for intelligence purposes. Solved in 33 days by a team of 3 developers, the bounty of $50k was slightly more than the t-shirt offered by the Instagram guys.