Instagram Engineering Challengeを解いてみた

Instagram Engineering Challenge: The Unshredder - Instagram Engineering

以下のように寸断された画像を並び替えて元の画像に戻すという問題。

整列前

整列後

Rubyの勉強がてらにやってみました。
画像の分割数を自力で求めるとボーナスがつきますが、今回はとりあえず自明な値（20）としました。
Rubyのバージョンは1.9.2、画像の読み書きはRMagickを使ってます。

普段はJavaかC++で、Rubyは馴染みがないです。
まともなコードになってるか不安です。

require 'RMagick'

# 短冊（寸断された画像の一片）を表すクラス
class Strip
  def initialize(srcImage, left, right)
      @srcImage = srcImage
      @left = left
      @right = right
      @estimatedLeftStrip = nil
  end
  attr_accessor :left, :right, :estimatedLeftStrip

  private
  def pixelL(y)
      return @srcImage.pixel_color(@left, y)
  end

  public 
  def pixelR(y)
      return @srcImage.pixel_color(@right, y)
  end
  
  private
  def calc_diff(pixel1, pixel2)
      diff = 0
      diff += (pixel1.red - pixel2.red).abs
      diff += (pixel1.green - pixel2.green).abs
      diff += (pixel1.blue - pixel2.blue).abs
      diff += (pixel1.opacity - pixel2.opacity).abs
  end
  
  # 自短冊の左端と他短冊の右端の類似度を計算する（値が小さいほど類似度高）
  private
  def calc_similarity(other)
      diff = 0
      (0...@srcImage.rows).each do |y|
          diff += calc_diff(pixelL(y), other.pixelR(y))
      end
      return diff
  end

  # 自短冊の左端と他短冊の右端を比較し、類似度が高いものを左側の短冊候補とする
  public
  def estimate_left_strip(strips)
      similarities = []
      strips.each do |other|
          next if other == self
          similarities.push({"strip" => other, 
             "degree_of_similarity" => calc_similarity(other)})
      end
      @estimatedLeftStrip = similarities.min{|item1, item2| 
          item1["degree_of_similarity"] <=> 
          item2["degree_of_similarity"]}
  end

  # 自短冊の右に来る短冊を探す
  public
  def find_right_strip(strips)
      candidate = []
      strips.each do |other|
          if other.estimatedLeftStrip["strip"] == self
              candidate.push(other)
          end
      end

      if candidate.empty?
          # 候補なし（右端の短冊）
          return nil
      end

      # 候補が複数ある場合、最も類似度が高いものを採用する
      return candidate.min{|item1, item2| 
          item1.estimatedLeftStrip["degree_of_similarity"] <=> 
          item2.estimatedLeftStrip["degree_of_similarity"]}
  end
end 

# 短冊インスタンスの作成
def create_strips(srcImage, stripWidth, numOfStrips)
    strips = []
    (0...numOfStrips).each do |i|
        stripLeft = i * stripWidth
        stripRight = (i + 1) * stripWidth - 1
        strips[i] = Strip.new(srcImage, stripLeft, stripRight)
    end

    strips.each do |strip|
        strip.estimate_left_strip(strips)
    end

    return strips
end

# 短冊をソート
def sort(strips)
    sorted = []

    strips.each do |strip|    
        next if sorted.include?(strip)

        tmpArray = [strip]        
        while strip != nil || sorted[0] != strip do
            rightStrip = strip.find_right_strip(strips)
            if rightStrip == nil
                # 右端
                sorted.push(tmpArray).flatten!
                break
            end
            if !sorted.empty? && sorted[0] == rightStrip
                sorted.insert(0, tmpArray).flatten!
                break
            else
                tmpArray.push(rightStrip)            
                strip = rightStrip
            end
        end
    end
    
    return sorted
end

# main
NUM_OF_STRIPS = 20
srcImage = Magick::ImageList.new("TokyoPanoramaShredded.png")
stripWidth = srcImage.columns / NUM_OF_STRIPS
strips = create_strips(srcImage, stripWidth, NUM_OF_STRIPS)
sortedStrips = sort(strips)

# 整列後の短冊から画像を作成する
dstImage = Magick::Image.new(srcImage.columns, srcImage.rows)
sortedStrips.each_with_index do |strip, i|
    (strip.left..strip.right).each_with_index do |srcx, dstx|
        (0...srcImage.rows).each do |y|
            dstImage.pixel_color(i * stripWidth + dstx, y, 
                srcImage.pixel_color(srcx, y))
        end
    end    
end

dstImage.write("TokyoPanoramaShredded_sorted.png")