Skip to content

My Solution to The Instagram Engineering Challenge

November 18, 2011
instagramchallengeunshredder

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.

About these ads

From → Hacks

One Comment
  1. Somebody essentially assist to make significantly articles I might state.
    This is the very first time I frequented your web page and so
    far? I surprised with the research you made to create this particular publish incredible.
    Fantastic task!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,487 other followers

%d bloggers like this: