My Solution to The Instagram Engineering Challenge

Instagram introduced an Engineering Challenge called the “Unshredder”. You can View the challenge on their page here.

To sum it up, they want you to create software that can take an image shredded by a paper shredder, and unshred it.

On their blog, they state that this is the way to get a job at Instagram… They also give you a free Instagram t-shirt even if you don’t want to work there. Pretty cool. (Please don’t submit my code to Instagram and try to get a job)

They want you to take any given image that’s shredded like this:

and fix it so it looks like this:

Sounds fun. This is no challenge if I’m going to do it in PHP and GD. To be honest, I’m getting real bored of PHP and I’ve been wanting to get some Python practice in. I read one and a half Python books, so I figured this would be a perfect opportunity to get more comfortable with the language. Python is actually pretty fun. I like the fact that it’s a procedural language, object-oriented language, and a functional language all in one. My solution is not elegant (as I’m still learning Python), but it works!

from PIL import Image
import ImageOps
image = Image.open("TokyoPanoramaShredded.png")
data = list(image.getdata())

width, height = image.size
NUMBER_OF_COLUMNS = 20

def get_pixel_value(x, y):
    pixel = data[y * width + x]
    return pixel

def compare_strips(column1,column2):
    dif = rdif = gdif = bdif = 0
    x1 = ((width/NUMBER_OF_COLUMNS)*column1)-1
    x2 = (width/NUMBER_OF_COLUMNS)*(column2-1)
    for y in range(0,height):
        data1 = get_pixel_value(x1,y)
        data2 = get_pixel_value(x2,y)
        rdif += abs(data1[0]-data2[0])
        gdif += abs(data1[1]-data2[1])
        bdif += abs(data1[2]-data2[2])
    return (rdif+gdif+bdif)/3

def compare_striptops(column1,column2):
    x1 = ((width/NUMBER_OF_COLUMNS)*column1)-1
    x2 = (width/NUMBER_OF_COLUMNS)*(column2-1)
    data1 = get_pixel_value(x1,0)
    data2 = get_pixel_value(x2,0)
    rdif = abs(data1[0]-data2[0])
    gdif = abs(data1[1]-data2[1])
    bdif = abs(data1[2]-data2[2])
    return (rdif+gdif+bdif)/3

# find adjacent strips
strips = []
for strip1 in range(1,NUMBER_OF_COLUMNS+1):
    strips.append((0,0,100000))
    for strip2 in range(1,NUMBER_OF_COLUMNS+1):
        if (strip1 != strip2):
            temp = strip1,strip2,compare_strips(strip1,strip2)
            if (temp[2]  seam[1]):
        seam = temp
for i in range(0,seam[0]):
    temp = sortedstrips.pop(0)
    sortedstrips.append(temp)
       
# Create a new image of the same size as the original
# and copy a region into the new image
unshredded = Image.new("RGBA", image.size)
shred_width = unshredded.size[0]/NUMBER_OF_COLUMNS
for i in range(0,NUMBER_OF_COLUMNS):
    shred_number = sortedstrips[i][0]
    x1, y1 = (shred_width * shred_number)-shred_width, 0
    x2, y2 = x1 + shred_width, height
    source_region = image.crop((x1, y1, x2, y2))
    destination_point = (i * shred_width, 0)
    unshredded.paste(source_region, destination_point)
# Output the new image
unshredded.save("unshredded.jpg", "JPEG")

Feel free to download it, modify it, improve it here.