自分の無能さを晒す 2 Google Dev Fest 2010 の Quiz パッチワーク版

まずは，6時間かかったバージョン。

#!/opt/local/bin/ruby

# read file and create array.
$basearea = []
$hascheckedarea = []
$max_x_size = 0
$max_y_size = 0

open(ARGV[0]) do |file|
  while l = file.gets
    $max_y_size += 1
    l.chomp!
    add_array = []
    add_check_array = []
    for i in 0 .. l.size - 1
      add_array += [l[i].chr]
      add_check_array += [false]
    end
    $basearea << add_array
    if ($max_x_size < add_array.size) 
      $max_x_size = add_array.size
    end
    $hascheckedarea << add_check_array
  end
end


# main routine

def clear_has_checked_array
  for x in 0 .. ($hascheckedarea.size - 1)
    for y in 0 .. $hascheckedarea[x].size - 1
      $hascheckedarea[x][y] = false
    end
  end
end

def is_equal_char_forpoint(compare_char, point_x, point_y)
  # debug_str = "checking (x, y) = (" + point_x.to_s + ", " + point_y.to_s + ")"
  if point_x < 0 || point_y < 0 || point_x >= $max_x_size || point_y >= $max_y_size
    return false
  end
  # p debug_str
  retvalue = false 
  if $basearea[point_x][point_y]
    if $hascheckedarea[point_x][point_y] == true
      # debug_str += (" has been checked ") 
    else
      $hascheckedarea[point_x][point_y] = true
      # debug_str += (" is " + $basearea[point_x][point_y])
      if compare_char == $basearea[point_x][point_y]
        retvalue = true
      else
        retvalue = false
      end
      # debug_str += (retvalue == true) ? "result is true" : "result is false"
    end
  end
  # debug_str += " for ( " + point_x.to_s + ", " +  point_y.to_s + ")"
  # p debug_str
  retvalue
end

def measure_continuous_area(base_char, start_point_x, start_point_y)
  # debug_str = "searching (" + (start_point_x).to_s + ", " + (start_point_y).to_s + ")"
  # p debug_str
  retvalue = 1
  $hascheckedarea[start_point_x][start_point_y] = true
  if is_equal_char_forpoint(base_char, start_point_x - 1, start_point_y)
    retvalue += measure_continuous_area(base_char, 
                                        start_point_x - 1, start_point_y)
  end
  if is_equal_char_forpoint(base_char, start_point_x, start_point_y - 1)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x, start_point_y -1)
  end

  if is_equal_char_forpoint(base_char, start_point_x + 1, start_point_y)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x + 1, start_point_y)
  end

  if is_equal_char_forpoint(base_char, start_point_x, start_point_y + 1)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x, start_point_y + 1)
  end
  retvalue
end

x_axis = 0
y_axis = 0
conarea_size =[]
for x_axis in 0 .. $basearea.size - 1
  line_size = []
  for y_axis in 0 .. $basearea[x_axis].size - 1
    #p $basearea[x_axis][y_axis]
    clear_has_checked_array()
    line_size += [measure_continuous_area($basearea[x_axis][y_axis], x_axis, y_axis)]
  end
  conarea_size << line_size;
end

$basearea.each do |array|
  p array
end

#conarea_size.each do |array|
#  p array
#end

max_area_size = 0

conarea_size.each do |x_array|
  p x_array
  x_array.each do |value|
    if max_area_size < value
      max_area_size = value
    end
  end
end

#debug_str = "max area size " + max_area_size.to_s
#p debug_str

conarea_size.each do |x_array|
  count = 0
  x_array.each do |value|
    if max_area_size == value
      count += 1
    end
  end
  p count
end

何がまずいか。

• 各点ごとに最大連結エリアサイズを求めようとしている。
• エリアサイズを求める際に，境界を記録しておく配列 $hascheckedarea (サイズ 600×600)を用意していたが，各点のエリア計算時にクリアしている。

各点ごとに計算しているので，例えば

AAB
BAA
BBA

を例にしたとき，A全ての点でおいて最大連結エリアサイズを求めている。この場合，点(0,0)のAの最大連結エリアサイズが判れば，他の点で計算する必要はない。しかも，$hascheckedarea を各点の計算毎にクリアしているので，とんでもない無駄な計算をしてしまった。

回答終了後，DevFest Quizパッチワーク問題の回答 CommonJS編 (電脳戦士ハラキリ -SE道とは死ぬ事と見つけたり)を見て，最大連結エリアを構成する部分集合のうちの1点だけを記録して，最後に答となる点から連結するエリアを塗りつぶせばいいということと(リンク先の配列 maxScoreCells[]と関数 fill()に注目)，チェックした領域を1点ごとにクリアしてはいけない ($hascheckedareaを利用しない。そのかわり，$scoreMapで記録する。このscoreMapは全ての点において正しい最大連結エリアの値を保存しているとは限らない) ということを理解して，改訂しました。

#!/opt/local/bin/ruby

# read file and create array.
$basearea = []
$scoreMap = []

$max_x_size = 0
$max_y_size = 0

# 問題ファイルを読みこみ，元となる配列 $basearea を作成
open(ARGV[0]) do |file|
  while l = file.gets
    $max_y_size += 1
    l.chomp!
    add_array = []
    add_check_array = []
    for i in 0 .. l.size - 1
      add_array += [l[i].chr]
      add_check_array += [-1]
    end
    $basearea << add_array
    if ($max_x_size < add_array.size) 
      $max_x_size = add_array.size
    end
    $scoreMap << add_check_array
  end
end


def is_equal_char_forpoint(compare_char, point_x, point_y)
  # debug_str = "checking (x, y) = (" + point_x.to_s + ", " + point_y.to_s + ")"
  if point_x < 0 || point_y < 0 || point_x >= $max_x_size || point_y >= $max_y_size
    return false
  end

  if $scoreMap[point_x][point_y] != -1
    return false # this point has been already checked
  end
  # p debug_str
  retvalue = false
  if $basearea[point_x][point_y]
    if compare_char == $basearea[point_x][point_y]
      retvalue = true
    else
      retvalue = false
    end
  end
  # debug_str += " for ( " + point_x.to_s + ", " +  point_y.to_s + ")"
  # p debug_str
  retvalue
end

def measure_continuous_area(base_char, start_point_x, start_point_y)
  # debug_str = "searching (" + (start_point_x).to_s + ", " + (start_point_y).to_s + ")"
  # p debug_str
  if $scoreMap[start_point_x][start_point_y] != -1
    retvalue = 0 # チェック済みなので計算させない
  end

  $scoreMap[start_point_x][start_point_y] = 0 # この作業で点 (start_point_x, start_point_y) はチェック済みであることを表す。

  if (base_char == $basearea[start_point_x][start_point_y])
    retvalue = 1
  end

  if is_equal_char_forpoint(base_char, start_point_x - 1, start_point_y)
    retvalue += measure_continuous_area(base_char, 
                                        start_point_x - 1, start_point_y)
  end
  if is_equal_char_forpoint(base_char, start_point_x, start_point_y - 1)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x, start_point_y -1)
  end

  if is_equal_char_forpoint(base_char, start_point_x + 1, start_point_y)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x + 1, start_point_y)
  end

  if is_equal_char_forpoint(base_char, start_point_x, start_point_y + 1)
    retvalue += measure_continuous_area(base_char,
                                        start_point_x, start_point_y + 1)
  end
  retvalue
end

x_axis = 0
y_axis = 0
maxScore = 0
maxScorePoint = []

for x in 0 .. $basearea.size - 1
  for y in 0 .. $basearea[x_axis].size - 1
    #p $basearea[x_axis][y_axis]
    # clear_has_checked_array()
    score = measure_continuous_area($basearea[x][y], x, y)
    if (maxScore < score)  
      maxScore = score
      maxScorePoint = [[x, y]]
    elsif (maxScore == score)
        maxScorePoint += [[x, y]]
    end
  end
end

$basearea.each do |array|
  p array
end

def fill(x, y, chr)
  if ($basearea[x][y] != chr)
    return
  end

  $basearea[x][y] = '_'
  fill(x+1, y, chr)
  fill(x, y+1, chr)
  fill(x-1, y, chr)
  fill(x, y-1, chr)

end

maxScorePoint.each do |point|
  x = point[0]
  y = point[1]
  fill(x, y, $basearea[x][y])
end

$basearea.each do |array|
  p array
end

$basearea.each do |array|
  cnt = 0
  array.each do |chr|
    if chr == '_'
      cnt += 1
    end
  end
  p cnt
end

結果，10秒程度で実行完了。自分の無能さを実感した日でした。