Skip to content

Instantly share code, notes, and snippets.

@maebert
Last active September 28, 2023 14:41

Revisions

  1. maebert revised this gist Feb 23, 2020. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions instagram_unshred.py
    Original file line number Diff line number Diff line change
    @@ -1,5 +1,5 @@
    # For an explanation of this code, see
    # http://portwempreludium.tumblr.com/post/13108758604/instagram-unshredding
    # Problem to be solved:
    # https://instagram-engineering.com/instagram-engineering-challenge-the-unshredder-7ef3f7323ab1

    import PIL.Image, numpy, fractions
    image = numpy.asarray(PIL.Image.open('TokyoPanoramaShredded.png').convert('L'))
  2. Manuel Ebert created this gist Nov 21, 2011.
    37 changes: 37 additions & 0 deletions instagram_unshred.py
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,37 @@
    # For an explanation of this code, see
    # http://portwempreludium.tumblr.com/post/13108758604/instagram-unshredding

    import PIL.Image, numpy, fractions
    image = numpy.asarray(PIL.Image.open('TokyoPanoramaShredded.png').convert('L'))
    diff = numpy.diff([numpy.mean(column) for column in image.transpose()])
    threshold, width = 1, 0

    def sequence(conn, start):
    seq = [start]
    while conn[seq[0]] not in seq:
    seq.insert(0, conn[seq[0]])
    return len(seq), seq

    while width < 5 and threshold < 255:
    boundaries = [index+1 for index, d in enumerate(diff) if d > threshold]
    width = reduce(lambda x, y: fractions.gcd(x, y), boundaries) if boundaries else 0
    threshold += 1

    shreds = range(image.shape[1] / width)
    bounds = [(image[:,width*shred], image[:,width*(shred+1)-1]) for shred in shreds]
    D = [[numpy.linalg.norm(bounds[s2][1] - bounds[s1][0]) if s1 != s2 else numpy.Infinity for s2 in shreds] for s1 in shreds]
    neighbours = [numpy.argmin(D[shred]) for shred in shreds]
    walks = [sequence(neighbours, start) for start in shreds]
    new_order = max(walks)[1]

    # What follows is just output.
    # From a data scientist's point of view, new_order contains the solution.

    print len(new_order), new_order
    source_im = PIL.Image.open('TokyoPanoramaShredded.png')
    unshredded = PIL.Image.new("RGBA", source_im.size)
    for target, shred in enumerate(new_order):
    source = source_im.crop((shred*width, 0, (shred+1)*width, image.shape[1]))
    destination = (target*width, 0)
    unshredded.paste(source, destination)
    unshredded.save("output.png")