Instagram challenge solution

gistfile1.coffee

unshred = (shreddedImage, shredWidth) ->
  {width, height} = shreddedImage
  shreds = split shreddedImage, shredWidth

  weights = cross shreds, (x, y) ->
    if x == y
      0
    else
      mean zipWith unzip(rightEdge(x)), unzip(leftEdge(y)), correlate

  invertNormalize = (row) -> invert normalize row
  path = optimalPath range(shreds.length), map weights, invertNormalize
  unshreddedImage = element 'canvas', {width, height}
  map path, (p, i) -> draw unshreddedImage, shreds[p], i * shredWidth, 0
  unshreddedImage

optimalPath = (nodes, weights) ->
  best = path: [], weight: Number.MAX_VALUE

  walk = (nodes, current={path: [], weight: 0}) ->
    return best = current if nodes.length == 0
    weight = (node) -> current.weight + (weights[last current.path]?[node] ? 0)
    weightCmp = (x, y) -> weight(x) - weight(y)
    for node in sort nodes, weightCmp
      return if best.weight <  weight node
      walk remove(node, nodes),
        path: append(node, current.path)
        weight: weight node

  walk nodes
  best.path

cross = (xs, fn) ->
  (fn(x1, x2) for x2 in xs for x1 in xs)

correlate = (xs, ys) ->
  covariance(xs, ys) / (stdDev(xs) * stdDev(ys))

covariance = (xs, ys) ->
  [mx, my] = [mean(xs), mean(ys)]
  mean zipWith xs, ys, (x, y) -> (x - mx) * (y - my)

normalize = (xs) ->
  [mn, mx] = [min(xs), max(xs)]
  map xs, (x) -> (x - mn) / (mx - mn)

invert = (xs) ->
  map xs, (x) -> 1 - x

element = (type, options) ->
  el = document.createElement type
  for key, val of options
    el[key] = val
  el

draw = (target, source, args...) ->
  target.getContext('2d').drawImage source, args...
  target

loadImage = (src, callback) ->
  image = new Image()
  image.src = src
  image.onload = ->
    canvas = element 'canvas', width: image.width, height: image.height
    draw canvas, image, 0, 0
    callback canvas

split = (canvas, width) ->
  height = canvas.height
  for x in range(0, canvas.width, width)
    slice = element 'canvas', width: width, height: height
    draw slice, canvas, x, 0, width, height, 0, 0, width, height

pixelColumn = (canvas, index) ->
  context = canvas.getContext('2d')
  data = (i for i in context.getImageData(index, 0, 1, canvas.height).data)
  rgb = ((data[(4 * i) + j] for j in range(3)) for i in range(canvas.height))

rightEdge = (canvas) ->
  pixelColumn canvas, canvas.width - 1

leftEdge = (canvas) ->
  pixelColumn canvas, 0

The above code with annotations: http://krenzel.org/files/docs/insta.html