ぷよぷよの連鎖状況を表示するプログラム

puyo.rb

#!/usr/bin/ruby

# ぷよぷよの連鎖状況を表示するプログラム by H.Hiro main@hhiro.net
# 出題: http://okajima.air-nifty.com/b/2011/01/2011-ffac.html
# Ruby1.8, 1.9両対応です。
# 
# 当の記事に
# 「書くのにかかった時間も自己申告してください。
#   目安として、２時間以上かかった人は採用は難しいでしょう。
#   僕が自分で書いてみたら30分でした。」
# とあったので、解く時間を重視して解いたところ、私は45分で解けました
# （一応動くようになったまでの時間。プログラムについてのコメントを
#   追加した時間も加えると60分）。
# またそのため、プログラムはかなり汚いです。

data =<<EOS
  GYRR
RYYGYG
GYGYRR
RYGYRG
YGYRYG
GYRYRG
YGYRYR
YGYRYR
YRRGRG
RYGYGG
GRYGYR
GRYGYR
GRYGYR
EOS
data.chomp!

# from http://jbbs.livedoor.jp/bbs/read.cgi/game/45949/1237508784/28
# ( via http://d.hatena.ne.jp/heisseswasser/20110223/1298429883 )
data =<<EOS
7745564556755676
5574456445677677
5574566456675566
4456745674567457
7557755775577556
4466446644664466
7456745674567457
7567456745674576
7466446644664477
4557755775577556
4567456745674576
7756745674567456
4557755775577557
7766446644664477
4756745674567456
4567456745674567
4766446644664466
7557755775577557
7567456745674567
4456745674567457
7557755775577556
4466446644664466
7456745674567457
7567456745674567
7466446644664466
4557755775577557
4567456745674567
EOS
data.chomp!

class Object
  def deep_dup
    Marshal.load(Marshal.dump(self))
  end
end

class PuyoField
  # 読み込み
  def initialize(obj)
    if obj.kind_of?(PuyoField)
      @data = obj.data.deep_dup
      @xsize = obj.xsize
      @ysize = obj.ysize
    else
      @data = obj.split(/\r\n?|\n/)
      @xsize = @data.first.length
      @ysize = @data.length
    end
  end
  
  attr_reader :data, :xsize, :ysize
  
  # 座標を指定し、何のぷよがあるかを返す。
  # 座標が範囲外ならnilを返す。
  def [](x, y)
    if x < 0 || x >= @xsize || y < 0 || y >= @ysize
      return nil
    end
    
    @data[y][x]
  end
  
  # 座標を指定し、その場所にあるぷよを変更する。
  def []=(x, y, new_value)
    @data[y][x] = new_value
  end
  
  # フィールドを全部空白にする。
  def clean
    for y in 0...@ysize
      for x in 0...@xsize
        @data[y][x] = ' '[0] # Ruby1.8でも1.9でも動くように
      end
    end
  end
  
  # フィールドの各位置について、ぷよの種類と座標を得ながら繰り返す。
  def each_with_coord
    for y in 0...@ysize
      for x in 0...@xsize
        yield @data[y][x], x, y
      end
    end
  end
  
  def to_s
    @data.join("\n")
  end
  
  # ぷよが消える場所の一覧を得る。
  # ぷよを1つも消せない場合はnilを返す。
  def find_cleaned_areas
    erased = nil
    
    checked = PuyoField.new(self) # 消える場所かの判定が済んでいる場合「*」そうでない場合空白
    checked.clean
    cleaned = PuyoField.new(checked) # 消える場所であることが確定した場合「*」そうでない場合空白
    
    self.each_with_coord do |color, x, y|
	  # ぷよのない場所、既にチェック済みの場所は除外する
      next if color == " "[0] || checked[x, y] != " "[0]
	  
      # スタックを使って、色が繋がっている座標の一覧を再帰的に列挙する。
	  # cleaned_coord_candidate_currentが座標を格納するスタック、
	  # cleaned_coord_candidate_allが列挙済みの座標である。
      cleaned_coord_candidate_current = [[x, y]]
      cleaned_coord_candidate_all = []
      cleaned_coord_result = []
      until cleaned_coord_candidate_current.empty?
        cand = cleaned_coord_candidate_current.pop
        
        next if self[*cand] != color
        next if cleaned_coord_candidate_all.include?(cand)
        
        checked[*cand] = "*"[0]
        cleaned_coord_result << cand
        cleaned_coord_candidate_all << cand
        
        # 左隣
        cand_next = cand.dup
        cand_next[0] -= 1
        cleaned_coord_candidate_current << cand_next
        
        # 右隣
        cand_next = cand.dup
        cand_next[0] += 1
        cleaned_coord_candidate_current << cand_next
        
        # 上隣
        cand_next = cand.dup
        cand_next[1] -= 1
        cleaned_coord_candidate_current << cand_next
        
        # 下隣
        cand_next = cand.dup
        cand_next[1] += 1
        cleaned_coord_candidate_current << cand_next
      end
      
      if cleaned_coord_result.size >= 4 # 4つ繋がっている場合
        cleaned_coord_result.each do |coord|
          cleaned[*coord] = "*"[0]
        end
        erased = true
      end
    end
    
    erased ? cleaned : nil
  end
  
  # ぷよを消して、落下処理を行う
  def clean_and_fall
    cleaned_areas = self.find_cleaned_areas
    return nil unless cleaned_areas
    
    cleaned_areas.each_with_coord do |color, x, y|
      if color == "*"[0]
		# 消えるべき場所のぷよを消す
        self[x, y] = " "[0]
        
		# 落とす
        fall_dest_height = y
        while fall_dest_height > 0 && self[x, fall_dest_height] == " "[0]
          self[x, fall_dest_height] = self[x, fall_dest_height-1]
          self[x, fall_dest_height-1] = " "[0]
          fall_dest_height -= 1
        end
      end
    end
    
    self
  end
end

field = PuyoField.new(data)
count = 0

while true
  puts "------ #{count}"
  puts field
  
  field = field.clean_and_fall
  break unless field
  count += 1
end