# Quickly Solving the “Instagram Engineering Challenge: The Unshredder”

Today I have read about the Instagram Engineering Challenge: The Unshredder, and decided to give it a try. The task is simple to explain: Create a program that can unshred this image (do not try the challenge on this image, try the original PNG source instead!):

I have postet here that I think I can solve it in 2 hours, and got some downvotes for that; so I have decided to really give it a try. Long story short, it took me about 2 hours and 35 minutes.

Before I started developing, I made some quick assumptions to simplify things:

• I want to code it in Ruby, this is the language where I am most productive.
• I can assume the size of the stripes is well known, and I have hardcoded this size.
• The image can be converted to RAW with an external tool, and written into RAW.
While coding I timed myself, and created a little timeline of my trials and errors. Since I wanted to finish as quickly as possible, the code is very ugly: no tests, some hardcoded constants, etc.

# Code

Without further ado, I give you the code:

# Result

Here is the result I got with this code:

# Algorithm

In hindsight, the algorithm combines two ideas: Hierarchical Agglomerative Clustering, and a quick and dirty novel distance-metric that defines how “good” a pairing is.

The hierarchical agglomerative clustering is a bit difficult to code, because there are a lot of corner cases when you are allowed to combine pairings and when not. I am not sure if my code is correctly, this should be recoded without time pressure.

The first version of the distance metric was very simple: calculate the sum of the quadratic differences between the two neighboring pixels when two slices are put together. Unfortunately this does not work for the slices with skyscraper that has black-white stripes: here lots of pixels are white on the left side, but black on the right side since the building is just slightly tilt. After realizing this problem, the solution is simple: for each pixel, find the best matching pixel of the other slice within a certain range. Through trial and error I have chosen +-15 pixels, and finally got the correct image.

Happy hacking,
Martin

5 Comments on "Quickly Solving the “Instagram Engineering Challenge: The Unshredder”"

Notify of
Guest

whoops, me and my big mouth!
honestly, i would’nt have thought of using ruby. but i code like an old man, too…

greets

Guest

funny challenge! I cant refrain from doing some promotion for matlab: with a few matrix operations I could do it in 30 lines…

Guest

@wpalfi: Alright, if you can do it in 30 lines of Matlab code, it must be possible in 15 lines of Python! ðŸ˜‰ http://portwempreludium.tumblr.com/post/13108758604/instagram-unshredding