Source

instagram /

Filename Size Date modified Message
resource
source
38 B
1.6 KB
Instagram Challenge
===================

On their `blog`_ Instagram's engineering team posted a small `Python
challenge`_ to reconstruct a shredded image into it's original form.

I'm coming late to the party so no more t-shirts, but it is still an
interesting problem to tackle.

The test image they gave is:

.. image:: https://bitbucket.org/thesociable/instagram/raw/18e64688e846/resource/shredded.png

They stress simplicity over fancy algorithms and have the concession that 
the shred width does not have to be calculated.

So, with that in mind, you can run my basic solution as follows::

    $ python source/unshred.py resource/shredded.png resource/unshredded.png

That should produce the following unshredded image:

.. image:: https://bitbucket.org/thesociable/instagram/raw/9489f2ed7afb/resource/unshredded.png

The approach I took was to loop over all the shreds and for each one
find the best left neighbour shred. This was done by comparing the euclidean
distance between the left pixel column of the shred and the right pixel column
of the candidate shred.

With this neighbour registry in place I then had to work out which was the 
first shred in the image as they were randomly jumbled. To do this I walk 
over the neighbour registry trying each shred as a potential start shred. The
longest walk through the registry (before encountering a duplicate use of a 
shred) is then the best solution for ordering the shreds to get the unshredded
image.


.. _blog: http://instagram-engineering.tumblr.com/
.. _Python challenge: http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder


Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.