自分の無能さを晒す 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秒程度で実行完了。自分の無能さを実感した日でした。

自分の無能さを晒す 1 Google Dev Fest 2010 の Quiz 漢字変換サーバ版

あー，自分でWebサーバ持っていないし，GAEにアプリ登録したこともないから，この問題にはチャレンジできないなと思っていましたが，回答締切6時間前に，別に自分で簡易ウェブサーバ立ちあげればいいんじゃないと思い，急遽やってみました。
幸いなことに，EmacsをChrome上で利用するためにWEBrickを利用したHTTPサーバのスクリプトを読んだこと（ChromeとEmacsを愛するもの達へ 【編集あり】）を思いだしたのが幸いでした。

方針は，

• 特殊ケース 0 の場合は 零(H) を返す
• 兆の位の4桁，億の位の4桁，万の位の4桁，一の位？の4桁を抽出して，漢数字に変換する。0や1千の扱い時に注意する。

です。

def trans_4digit_kansuzi(num)
  digit_1st_array = ['', 'G', 'B', 'S', 'A', 'Q', 'Z', 'P', 'C', 'Y'] # 零 一 二 三 四 五 六 七 八 九
  digit_other_array = ['', '', 'B', 'S', 'A', 'Q', 'Z', 'P', 'C', 'Y'] # 零 一 二 三 四 五 六 七 八 九
  unit_array = ['N', 'M', 'J', ''] # 千 百 十 零

  is_top_digit_zero = true
  ret_str = ""
  for i in 0 .. unit_array.size - 1
    tmp_num = (num % (10 ** (unit_array.size - i))) / (10 ** (unit_array.size - 1 -i))
    if tmp_num > 0 || is_top_digit_zero == false
      is_top_digit_zero = false
      if tmp_num != 0
        if i == (unit_array.size - 1)
          ret_str += (digit_1st_array[tmp_num] + unit_array[i])
        else
          ret_str += (digit_other_array[tmp_num] + unit_array[i])
        end
      end
    end
  end

  return ret_str
end

def trans_kansuzi(num)
  if num == 0
    return 'H' # 零
  end

  unit_array = ['T', 'D', 'K', ''] # 兆 億 万 零 

  ret_str = ""
  is_top_digit_zero = true
  for i in 0 .. unit_array.size - 1
    tmp_num = (num % (10000 ** (unit_array.size - i))) / (10000 ** (unit_array.size - 1 - i))
    debug_str = i.to_s + " " + tmp_num.to_s
    p debug_str
    if tmp_num > 0 || is_top_digit_zero == false
      is_top_digit_zero = false
      if tmp_num != 0
        ret_str += (trans_4digit_kansuzi(tmp_num) + unit_array[i])
      end
    end
  end
  return ret_str
end

p trans_kansuzi(ARGV[0].to_i)

本当は

tmp_num = (num % (10000 ** (unit_array.size - i))) / (10000 ** (unit_array.size - 1 - i))

のように上位桁から検証してしまったが，

tmp_num = num % 10000 # 下4桁の値を得る
# tmp_num 文字列生成処理
num = num / (10000 ** i) # 右4桁移動する。

のように，下位桁から検証した方が綺麗。(テストはしていない)

Google Dev Fest 2010 Japan の Quiz 暗号通信版

パッチワークの問題の解き方があまりにも恥しかったので，自分への懲戒のため自分の回答を晒します。(Google Dev Fest 2010 の Quiz) まずは，暗号通信から。 楽に，手を抜くために慣れたRubyで実装しました。

シーザー暗号なんだなと思ったけど，tr コマンドの使い方を理解していなかったことが発覚。なので，地味に書きました。手を抜くために，gemのJSONライブラリ，JSON implementation for Rubyを利用しました。

#!/opt/local/bin/ruby

require "json"
require "net/http"

target_host = "devquiz.appspot.com"
target_file = "/personalpost"
key = "(snip)"

plain_text="my email address"
pass_text=""

for i in 0 .. plain_text.size - 1
  ch = plain_text[i]
  if (ch >= 'a'[0] && ch <= 'z'[0] )    # 小文字の変換
    tmp = (ch - 'a'[0] + 4) % 26
    pass_text += ('a'[0] + tmp).chr
  elsif (ch >= 'A'[0] && ch <= 'Z'[0] ) # 大文字の変換
    tmp = (ch - 'A'[0] + 4) % 26
    pass_text += ('A'[0] + tmp).chr
  else                                  # その他の文字はそのまま通過 
    pass_text += plain_text[i].chr
  end
end

json = {"key" => key, "pass" => pass_text}.to_json
#p json

Net::HTTP.start(target_host, 80 )  do |http|
  # response = http.get('/')
  response = http.post( target_file, json )
  p response
end

tr を用いた別解
DevFestクイズ答案: 暗号通信