Quickly Solving the "Instagram Engineering Challenge: The Unshredder"

class Img
  attr_reader :w, :h, :slices
  def initialize
    # unpack as 8bit unsigned chars
    @d = IO.binread("TokyoPanoramaShredded.raw").unpack("C*")
    @w = 640
    @h = 359
    @slices = 20
    @sw = @w / @slices
  end
  
  def write(sorted)
    data = @d.dup
    source_slice = 0
    sorted.each do |target_slice|
      # copy one slice
      @sw.times do |w|
        @h.times do |h|
          target_idx = idx(w + @sw * source_slice, h)
          source_idx = idx(w + @sw * target_slice, h)
          data[target_idx] = @d[source_idx]
          data[target_idx+1] = @d[source_idx+1]
          data[target_idx+2] = @d[source_idx+2]
        end
      end
      source_slice += 1
    end
    
    File.open("out.raw", "wb") do |f|
      f.write data.pack("C*")
    end
  end

  def idx(x, y)
    (y * @w + x) * 3
  end
  
  # top left is 0, 0
  def rgb(x, y)
    i = idx(x, y)    
    [@d[i], @d[i+1], @d[i+2]]
  end  
  
  # calculate sum of difference between r, g, b of two columns
  def difference(x1, x2)
    diff = 0
    @h.times do |y|    
      # find best in range. This is required because otherwise the black syscraper fucks things up.
      lower = y - 15
      lower = 0 if (lower < 0)
      
      upper = y + 15
      upper = @h-1 if upper >= @h
      
      best = 1e100
      lower.upto(upper) do |r|
        v = 0
        rgb1 = rgb(x1, r)
        rgb2 = rgb(x2, r)
        
        d = rgb1[0] - rgb2[0]
        v += d*d
        d = rgb1[1] - rgb2[1]
        v += d*d
        d = rgb1[2] - rgb2[2]
        v += d*d
        
        best = v if (v < best)
      end
      diff += best
    end
    diff
  end
  
  def slice_start_idx(s)
    @sw * s
  end
  
  def slice_end_idx(s)
    @sw * s + @sw - 1
  end
end

# calculate
img = Img.new

# create ALL pairings.
slices = 20
pairs = []
slices.times do |s1|
  slices.times do |s2|
    next if s1 == s2
    
    pairs.push [img.difference(img.slice_end_idx(s1), img.slice_start_idx(s2)), [s1, s2] ]
  end
end

def add_to_group(combined, new_group)
  # create array of fixed numbers
  taken_numbers = {}
  taken_left = {}
  taken_right = {}
  combined.each do |group|
    group[1..-2].each do |x|
      taken_numbers[x] = true
    end
    taken_left[group.last] = true
    taken_right[group.first] = true
  end
  
  was_found = false
  combined.each do |group|
    next if was_found
    if (group.last == new_group.first)    
      # insert at back
      was_found = true
      new_group.delete_at(0)
      if taken_numbers[new_group.last] || taken_left[new_group.last] || new_group.last == group.first
        return
      end
      new_group.each do |x|
        group.push x
      end
    elsif (group.first == new_group.last)
      # insert at front
      was_found = true
      new_group.pop
      if taken_numbers[new_group.first] || taken_right[new_group.first] || new_group.first == group.last
        return
      end
      new_group.reverse.each do |x|
        group.insert(0, x)
      end
    end
  end
  if !was_found    
    cf = combined.flatten
    new_group.each do |x|
      was_found = was_found || cf.index(x)
    end
    if !was_found
      combined.push new_group
    end
  end
end

# sort, lowest first
pairs.sort!

# create combinations.
# combined has an array of all correspondences.
combined = []
pairs.each do |diff, new_group|
  
  # insert new group
  add_to_group(combined, new_group)
  
  # try to recombine everything, until nothing changes any more
  was_recombined = true
  while was_recombined
    new_combined = []  
    combined.each do |group|
      add_to_group(new_combined, group)
    end
    was_recombined = combined.size != new_combined.size
    combined = new_combined
  end
  
  if (combined.size == 1 && combined[0].size == img.slices)
    # we got everything! Write output image.
    img.write(combined[0])
    exit
  end
end