Instagram

The engineers at Instagram put forward a challenge for coders to unshred this chopped up image. See the original post on their engineering blog : Instagram Engineering Challenge: The Unshredder.

The problem

Here are the input and target output images:

The shredded version

The unshredded version

I wrote a solution in Python that resolves the problem; here is the basic idea of the algorithm :

1. define a correlation function for two pixel columns
2. start with a random shred
3. find the shred with the maximum correlation value that would fit on the left hand side or on the right hand side of the reconstructed picture
4. iterate until all the shreds have been used

The bonus question was to guess how wide the uniform shreds are. I proceeded this way :

1. Consider all shreds width that can divide the image correctly
2. Compute the difference score between all shreds – it’s the opposite of the correlation score used before and I also include a ratio of the shred_width
3. When we are on a edge between two sherds, the difference is at its maximum. So, take the maximum of all computed difference scores.

For more details, see the code in my repository on github