Instagram Engineering Challenge: The Unshredder
"Your challenge, if you choose to accept it, is to write a simple script that
takes a shredded image in as input and outputs an unshredded and reconstituted image."
So here's the sample image:
We're given the information that the slices are 32 pixels wide each, so I don't actually
address finding slices.
My Solution Process
Disclaimer: I've never really worked with images before and have little to no
knowledge of the research and techniques often used in this area.
The challenge appears to be figure out the best way to put pieces back together.
My first thought was I can sample X pixels from each edge of a slice, grab the RGB
value of each pixel and compare the difference.
The reasoning behind this was RGB is the easiest way I can think of to compare
differences in colors between pixels. Sampling would hopefully make it faster.
I made one critical mistake, instead of comparing pixel to pixel, I calculated
total R,G,B on an edge and compared the sum of an edge instead of a difference.
I didn't understand why that was wrong until the example of a checkerboard was
given. If you had a slice on a checkerboard they would actually be equal on
average but very different on a pixel to pixel comparison.
So, I had to revise my solution to compare pixel to pixel on each slice against
its opposing slices. So left side of slice 1 was compared against right side of
all the other slices in the image. The logic being that the slices with the
least amount of difference between them probably fit together.
Almost. Something is wrong here. The striped building seems to throwing it off.
The striped building has the highest difference value of any left-right pairs.
So my algorithm kept putting it on the side.
How can I make the striped building fit together? I tried cheating and seeded the
proper right end image (slice 10) and the image constructed itself perfectly.
Well, the only solution I came up with was somewhat brute force in nature. What
if I try compiling the image with every slice as an edge and see what the total
computed difference of the image is?
Voila! The only way I could think to overcome this was proving the whole image turned
out better despite the high difference pair.
My code is publicly available on Github
I apologize if you actually read the code, it's a mess, there is a lot of testing going on, commented out code and things that aren't used in the final version. I thought it would be a good way to learn about ImageMagick and PHP's Imagick class (which is the worst documented thing I've seen on PHP.NET)
