Last active
September 28, 2023 14:41
Revisions
-
maebert revised this gist
Feb 23, 2020 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,5 +1,5 @@ # 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')) -
Manuel Ebert created this gist
Nov 21, 2011 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal 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")