Explorations in Go: solving the Instagram engineering challenge

The good folks at Instagram posted a fun challenge on their engineering blog recently:

"Your challenge, if you choose to accept it, is to write a simple script that takes a shredded image in as input and outputs an unshredded and reconstituted image. That is, imagine if you took an image, divided it into an even number of columns and shuffled those columns randomly to produce a shredded image. Then, take that image into the script and output the original image."

(The original post is here: Instagram Engineering Challenge: The Unshredder).

This struck me as a great opportunity to hack out some code in Go (rev 60.1) as part of my continuing exploration of the language and its packages.

The problem

Here are the input and target output images:

The shredded version

The unshredded version

They offer the following tips:

1. Don’t overthink it. Use of really complex algorithms isn’t needed. Our solution WITH the bonus exercise comes in at just over 150 lines of python.
2. Think about how you would quantify whether or not two shreds ‘fit’ together by using pixel data
3. Assume you’re using the source image, or other normal photographs without edge-case patterns.
4. There are edge cases where the script we wrote with our approach will not work because of repeating patterns. This is OK in your script as well. Don’t worry about special cases – focus on making the sample images work that we’ve provided.

Great. The simplest approach that occurred to me was this:

1. Assume the left-most shred is in the right place.
2. Search the other shreds, find the one that fits best to the right of the first one, then stick it there.
3. Repeat until you run out of shreds.
4. Figure which shred is actually the left-most one, then reorder to that configuration by rotating the ring of shreds.

As it turns out, this works. My solution is on Github here: https://github.com/joncooper/instashred. They've run out of t-shirts, though :P, so no soup for me.

Here's a quick tour of the standard library's packages that I used:

image

The image.Image interface from the image package provides what the docs describe in their typically awesome and laconic manner as "a finite rectangular grid of Colors drawn from a ColorModel."

Basically, the image.Image interface defines a read-only grid of pixels expressed as image.Color, upon which you can call RGBA() to get out a tuple containing alpha-premultiplied channel intensities.

At first the read-only nature of image.Image made me scratch my head a bit. But it ends up being pretty neat. You can do things like create a procedural image which can then be sampled, like this:

The standard library also implements image.Tiled, which acts like an infinitely (okay, just extremely large) large tiling of a source image. See the source here--it's just pretty.

image/png

Image file support is minimal but useful at the moment. There are image subpackages that implement decoding/encoding for JPEG and PNG, and decode only for BMP, GIF and TIFF.

Here's an example for how you write an image.Image to a PNG file:

image/draw

This package implements image compositing functions and little else. In particular, it doesn't implement vector art staples like line, circle, rectangle, etc.

It's deals solely with compositing images by copying image.Color pixels from one image.Image and pasting them into a draw.Image, optionally using a mask and a Porter-Duff compositing operator.

See the golang blog's post on this package here: The Go image/draw package.

The primary operation I used is image.Draw, which has the following function signature:

func Draw(dst Image, r image.Rectangle, src image.Image, sp image.Point, op Op)

This copies a region the size of r from src into dst with the top left corner at sp.

Here's an example combining tying the last three together:

An aside on Go interfaces

The relationship between image.Image and draw.Image is extremely representative of idiomatic Go. In Go, a type doesn't declare that it implements an interface, it just does so, and it gets checked statically at compile time.

A draw.Image is just like an image.Image, but you can draw into it. The interface requirements are a superset of those defined in image.Image. Taking a look at the source to draw.Image reveals the neat way that interface inheritance happens in Go:

Wrap

This implementation was enjoyable; I am really warming up to Go.

So far, the standard libraries are uniformly sensible and in many cases beautiful. It's clearly an opinionated language and set of packages, but so far, I seem to agree with those opinions. :)

Cheers,
Jon