My solution to the Unshredder problem posted by Instagram.

Motivation

Free tshirt.

Usage

The project contains two scripts

unshred.py - unshreds a shredded image.

./unshred.py source dest [strip_width=32]

source - the source image that has been stripped into equal
         columns of strip_width pixels.

dest - the file under which to save the unshredded image.

stript_width - the width of each stripped column.  This is an
               optional parameter and is assumed to be 32 pixels
               if not provided.

shred.py - shreds an image. Takes some care to order the strips so that adjacent strips do not end up adjacent to each other.

./shred.py source dest [strip_width=32]

source - the source image to strip into equal columns of width
         strip_width.

dest - the file under which to save the shredded image.

stript_width - the width of each stripped column.  This is an
               optional parameter and is taken as 32 pixels by
               default.

How it works

The program works by generating as many strips from the image as needed and comparing the edges of all strips. Given two strips s1, s2 it computes the color differences between all pixels on the right edge of s1 and left edge of s2, and color differences between all pixels on the left edge of s1 and right edge of s2.

Strips are ordered by minimal color differences between them. Since many such orderings are possible (depending upon the starting strip), all orderings are computed. The cheapest ordering is taken as the correct path.

After finding the optimal ordering, we have to find the first and last strips. This is done by computing the differences between adjacent strips in the ideal order. The highest difference indicates maximal difference between two strips. So, if a pair, (si, sj) has the greatest difference, si is made the last strip and sj the first.

Caveats

1. My day job involves programming in Java. Unlike most of proggit and HackerNews, I actually like the Java programming language. I used Python in this program because I've used PIL in the past (circa 2007) and felt it would be easier than playing with some Java libray I've never used. The code may not be canonical Python.

2. Unshredding doesn't work under all circumstances. Specifically, it doesn't perform well when many strips are similar to each other.

3. The program is not written for speed. I have made exactly one improvement for the sake of speed: a wrapper class around PIL.Image to speed up pixel access. The program was around 1.5 times faster after that adjustment.