無印吉澤（※新エントリはhatenablogに掲載中） - Google DevFest 2010 Japan Quizの問題とその答えの一例（Rubyで解きました）

2010/03/02

■[programming]Google DevFest 2010 Japan Quizの問題とその答えの一例（Rubyで解きました）

これまでのあらすじ：
3/18(木)に開催されるGoogle DevFest 2010の募集がかけられた。参加したらNexus Oneがただで貰えるのではないかと見込んだ（僕みたいな）応募者が殺到したせいかどうかは知らないが、参加希望者は定員の400名をオーバーしていた。そこで、参加希望者を上位400名に絞り込むためのプログラミングクイズがGoogleから参加希望者に送りつけられ、Nexus Oneに釣られた参加希望者はそれを嬉々として解いてしまうのだった。Nexus Oneなんて配られないとも知らずに……。

----

そんなDevFest Quizも終わり、採点結果が参加希望者に送られたようなので、せっかくだから僕の答えも公開してみます。まあ、基本的に問題文通りの処理をベタ書きしただけですけど。

DevFest Quizは全部で10問出題され、プログラミングの問題は以下の3題でした。androidzaurusさんによる以下のまとめを見ると、みんな思い思いの言語で解いたみたいですね。僕はRubyで解きました。

みんなの回答のまとめ：はてなブックマーク - 安藤恐竜のブックマーク - DevFestQuiz

----

■ 暗号通信（配点：4.0点）

あなたの登録したメールアドレスを、このクイズサーバーに転送して下さい。ただし、次のような暗号化をしてください。

A → L

B → M

C → N

D → O

E → P

中略 → 中略

Z → K

a → l

b → m

c → n

中略 → 中略

z → k

@ → @

1 → 1

変換したメールアドレスと、次のキーワード : "（省略）" とを一緒に、http://devquiz.appspot.com/personalpost までpostしてください。二つのデータは以下のようにjson形式にして、POSTの本文に text/plain 形式で入れてください。
{
  "key": キーワード
  "pass": 変換されたメールアドレス
}

この問題は、自分のメールアドレスを変換するところまではRubyでプログラムを書いたのですが、データをpostするところはFirefoxアドオンのRestTestで送りつけて済ませちゃいました。

メールアドレスの変換処理は以下のようにベタに書いたんですが、他の人の答えを見てると、Rubyだったらtrっていうメソッドを使うと楽に解けたみたいです。なんでみんなそんなの知ってるの……と思ったらPerl由来なんだそうで。なるほど。

email = "メールアドレス"

BEFORE = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz@.1234567890"
AFTER  = "LMNOPQRSTUVWXYZABCDEFGHIJKlmnopqrstuvwxyzabcdefghijk@.1234567890"

converted_email = ""

email.split("").each do |str|
  regex = Regexp.new(Regexp.escape(str))
  idx = (BEFORE =~ regex)
  converted_email += AFTER[idx, 1]
end

print converted_email

----

■ パッチワーク（配点：5.0点）

ここ（実際はテキストファイルへのリンク）に "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。

まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。

そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。

以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。

例1:
入力
ABAAB
BABAA
BAABB
ABABB
BABAA
塗りつぶしたところ.
AB__B
B_B__
B____
AB___
BABAA
答え
2
3
4
3
0
例2:
入力
AAABABAAAA
ABBBBBABAA
BAABAAABAA
BBAABABABA
BAABBAAABA
AABABAABAB
ABAABBABAB
BABBBABABB
BABABBAABB
BBBABABAAA
塗りつぶしたところ.
AAABAB____
ABBBBB_B__
BAAB___B__
BBAAB_B_B_
BAABB___B_
AABAB__BAB
ABAABB_BAB
BABBBABABB
BABABBAABB
BBBABABAAA
答え
4
3
5
3
4
2
1
0
0
0

これは、最初なにかエレガントな解決方法があるんじゃないかと色々試したんですが、処理にやたら時間がかかったり、結局正解が出なかったりしました……。なので、結局以下のようにいちいち探索する処理を書いて解きました。

それぞれの動作は、ソースコード中のコメントの通りです。読んでもわかりにくいところとしては、check_groupメソッドがインスタンス変数@input_arrayやら@checked_arrayを参照してるところでしょうか。上から順に処理を書いていったらこうなったんですが、正直かなり汚いコードですね、こりゃ。

# 問題の読み込み
@input = []
open("patchworkinput.txt") {|file|
  while line = file.gets
    @input << line.chomp
  end
}

# 幅と高さ（これは不要だったかも）
@width = @input.first.size
@height = @input.size

# 読み込んだ値を入れる二次元配列
# Aなら0、Bなら1とする
@input_array = []
A = 0
B = 1

# それぞれの値をチェック済みか記録する二次元配列
# チェック前なら0、チェック済みなら1とする
@checked_array = []
UNCHECKED = 0
CHECKED = 1

# 二次元配列に初期値を設定
@input.each_with_index do |line, y|
  line.split("").each_with_index do |c, x|
    @input_array[y] ||= []
    @input_array[y][x] = (c == "A" ? A : B)

    @checked_array[y] ||= []
    @checked_array[y][x] = UNCHECKED
  end
end

# 個々の点を始点として、再帰的に値をチェックするための関数
# 返り値として、マッチした文字の数を返す
# xは横軸、yは縦軸の座標（いずれも0開始）、valueはマッチすべき値（AまたはB）
def check_group(x, y, value)
  # 座標が枠外なら0を返す
  return 0 if x < 0 or y < 0 or x >= @width or y >= @height

  # その枠が既にチェックされていたら0を返す
  return 0 if @checked_array[y][x] == CHECKED

  # その枠の値がvalueと違ったら0を返す
  return 0 unless @input_array[y][x] == value

  # その枠の値がvalueと同じだったら、チェックを入れる
  @checked_array[y][x] = CHECKED

  # 上下左右を再帰的にチェックする
  1 + check_group(x - 1, y, value) + check_group(x + 1, y, value) +
    check_group(x, y - 1, value) + check_group(x, y + 1, value)
end

# [ チェックに使った始点x軸, 始点y軸, 値, 一致した要素の数 ] の配列を格納する変数
results = []

@input_array.each_with_index do |line, y|
  line.each_with_index do |value, x|
    # その枠が既にチェックされていたらパス
    next if @checked_array[y][x] == CHECKED
    results << [ x, y, value, check_group(x, y, value) ]
  end
end

# 一致した要素の数の最大値を計算
max_num = 0
results.each do |res|
  max_num = res[3] if max_num < res[3]
end

# 一致した要素の数が最大のものだけを選択
max_results = results.select{|res| max_num == res[3] }

# 二次元配列をすべてリセット
@input_array = []
@checked_array = []
@input.each_with_index do |line, y|
  next if y >= @height

  line.split("").each_with_index do |c, x|
    next if x >= @width

    @input_array[y] ||= []
    @input_array[y][x] = (c == "A" ? A : B)

    @checked_array[y] ||= []
    @checked_array[y][x] = UNCHECKED
  end
end

# 今度は、正解部分だけをチェックする
max_results.each do |res|
  check_group(res[0], res[1], res[2])
end

# 各行の正解数を数えて、ファイルに書き込む
open("result.txt", "w") do |f|
  @checked_array.each do |line|
    f.puts line.select{|l| l == CHECKED }.size
  end
end

----

■ 漢字変換サーバ（配点：7.0点）

数字を漢数字に変換するアプリケーションを作ってください。

http://[あなたのアプリケーションのURL]?n=[数字] にアクセスすると、 text/plain でその数字を漢数字に変換した結果を返すウェブサーバを作ってください。ただし、漢字はすべて以下の表の通りにアルファベットに変換して出力してください。

零 → K

一 → E

二 → Y

三 → M

四 → B

五 → H

六 → P

七 → Z

八 → N

九 → J

十 → X

百 → G

千 → F

万 → U

億 → T

兆 → L

注意:

「千万」「千億」「千兆」の前に「一」がつかないようにしてください。

入力は負でない整数で、大きさは高々9999兆9999億9999万9999までです。

標準のポート番号80番のみ扱えます。

僕が問題を解いたときは「一」に関する注意書きがなかったような気がするんですが、ミスする人が多かったんですかね。気持ちは分かります。

それで回答の方針ですが、僕は数字を漢数字に変換するKanjiクラスを作って、それを呼び出す形にしました。テストケースを書きたかったというのもあって、変換処理は独立したクラスとして実装しています。

まず、Kanjiクラスを呼び出すnk_application.rb。このファイルに実行権を与えて公開します。

#!/usr/bin/env ruby
require "cgi-lib"
require "kanji"

input = CGI.new

print "Content-type: text/plain\n\n"

str = Kanji.num2kanji(input["n"])
print str if str

次に、Kanjiクラスを実装したkanji.rb。かなりベタベタにかいてます。

class Kanji
  def self.num2kanji(number)
    # 数字以外は無視
    unless number =~ /^\d+$/
      return nil
    end

    # 京に達してたら無視
    if number.size > 16
      return nil
    end

    # 値が0の時は、零 → K を返す
    if number.to_i == 0
      return "K"
    end

    # 数字を後ろから4個ずつの固まり（チャンク）に区切る
    numbers = []

    # 部分文字列を作るためのインデックスと長さ
    index = number.size
    length = 4

    while index > 0
      if index < 4
        length = index
        index = 0
      else
        index = index - 4
      end

      numbers << number[index, length]
    end

    # 下の位から取っているので、順序を入れ替える
    numbers.reverse!

    # 返り値
    kanji = ""

    numbers.each_with_index do |fournum, i|
      # 数値に変換してゼロだったら何もしない
      next if fournum.to_i == 0

      kanji += fournum2kanji(fournum)
      case numbers.size - i
      when 4
        # 兆 → L
        kanji += "L"
      when 3
        # 億 → T
        kanji += "T"
      when 2
        # 万 → U
        kanji += "U"
      end

    end

    kanji
  end

  # 零が出てくるのは0のときだけと思われるので、それは無視する
  # （0だけは例外として、もっと手前で扱う）
  BEFORE = "123456789"
  AFTER  = "EYMBHPZNJ"

  # 4文字の数字を、何千何百何十何、まで変換して返します。
  def self.fournum2kanji(fournum)
    kanji = ""

    fournum.split("").each_with_index do |num, i|
      regex = Regexp.new(Regexp.escape(num))
      idx = (BEFORE =~ regex)

      if idx
        case fournum.size - i
        when 4
          # 千 → F
          # 1だけ特別扱い（一千、とは言わない）
          kanji += AFTER[idx, 1] unless num == "1"
          kanji += "F"
        when 3
          # 百 → G
          # 1だけ特別扱い（一百、とは言わない）
          kanji += AFTER[idx, 1] unless num == "1"
          kanji += "G"
        when 2
          # 十 → X
          # 1だけ特別扱い（一十、とは言わない）
          kanji += AFTER[idx, 1] unless num == "1"
          kanji += "X"
        when 1
          kanji += AFTER[idx, 1]
        end
      end
    end

    kanji
  end
end

で、最後に「一千」とかの扱いに不安があったので、このKanjiクラスをテストするkanji_test.rbも書きました。

require 'test/unit'
require 'kanji'

class TestKanji < Test::Unit::TestCase

  def setup
  end

  def teardown
  end


  def test_num2kanji
    # 零 → K
    # 一 → E
    # 二 → Y
    # 三 → M
    # 四 → B
    # 五 → H
    # 六 → P
    # 七 → Z
    # 八 → N
    # 九 → J
    # 十 → X
    assert_equal("K", Kanji.num2kanji("0"))
    assert_equal("E", Kanji.num2kanji("1"))
    assert_equal("Y", Kanji.num2kanji("2"))
    assert_equal("M", Kanji.num2kanji("3"))
    assert_equal("B", Kanji.num2kanji("4"))
    assert_equal("H", Kanji.num2kanji("5"))
    assert_equal("P", Kanji.num2kanji("6"))
    assert_equal("Z", Kanji.num2kanji("7"))
    assert_equal("N", Kanji.num2kanji("8"))
    assert_equal("J", Kanji.num2kanji("9"))
    assert_equal("X", Kanji.num2kanji("10"))

    # 九十九
    assert_equal("JXJ", Kanji.num2kanji("99"))

    # 百 → G
    assert_equal("G", Kanji.num2kanji("100"))

    # 百一
    assert_equal("GE", Kanji.num2kanji("101"))

    # 九百九十九
    assert_equal("JGJXJ", Kanji.num2kanji("999"))

    # 千 → F
    # 1000 は 千
    assert_equal("F", Kanji.num2kanji("1000"))
    
    # 千一
    assert_equal("FE", Kanji.num2kanji("1001"))

    # 千十
    assert_equal("FX", Kanji.num2kanji("1010"))

    # 万 → U
    # 1万 は 一万
    assert_equal("EU", Kanji.num2kanji("10000"))

    # 億 → T
    # 1億 は 一億
    assert_equal("ET", Kanji.num2kanji("100000000"))

    # 兆 → L
    # 1兆 は 一兆
    assert_equal("EL", Kanji.num2kanji("1000000000000"))

    # 9999兆9999億9999万9999
    assert_equal("JFJGJXJLJFJGJXJTJFJGJXJUJFJGJXJ", Kanji.num2kanji("9999999999999999"))

    # この範囲を超えたらエラー
    assert_equal(nil, Kanji.num2kanji("10000000000000000"))
  end

end

動作中のサンプルはこちら：http://muziyoshiz.jp/archives/devfest2010/nk_application.rb

----

僕の答えはこんな感じだったのですが、いかがでしたでしょうか。何か（物笑いとか）のネタになれば幸いです。

[ツッコミを入れる]

[]

«前の日記(2010/01/04) 最新次の日記(2015/03/15)»

2004|06|07|09|11|12|