中学入試から：単位のある計算」の解説・解題

CodeIQ に「中学入試から：単位のある計算」という問題
https://codeiq.jp/ace/nabetani_takenori/q1058
を出した。

中学入試算数問題第二弾。

挑戦の募集はすでに締めきっている。
というわけで、解説・解題。

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題が出ることがあります。
以下の式の□にあてはまる数を求めなさい。
　3m20cm-3m10cm-□mm=5mm
この問題を
以下の式の□にあてはまる数を求めなさい。
　【　A　】
と考え、A を入力文字列として与えます。
問題の答えを計算するプログラムを書いて下さい。
■具体的な課題
下記リンクの zip 内に data.utf8.txt および data.sjis.txt というファイルがあります。
これらのファイルの各行は
　「データID、空欄Aの内容(1)、空欄Aの内容(2)」
を TAB区切りでならべたものです。
ほとんどのデータは「空欄Aの内容(1)」と「空欄Aの内容(2)」の答えが同じになっています。
「空欄Aの内容(1)」と「空欄Aの内容(2)」の答えが異なるデータが数件あります。それらのデータの ID を答えて下さい。
data.utf8.txt と data.sjis.txt は、文字コードが異なるだけで内容はまったく同じです。
お好きな方をお使い下さい。
■補足
・データIDがTで始まるデータは、すべて (1) と (2) の答えが同じになっています。
テストにお使い下さい。
・(1) と (2) で答えが異なるデータの ID は全て数字になっています。間違い数は5件より多く、20件より少なくなっています。
・不正な入力（「4cm=□□=□宇宙ノット」など）に対処する必要はありません。
・長さ・重さ・時間しかありません。また、加算と減算しかありません。
・□には必ず負ではない整数が入ります。
■資料
http://nabetani.sakura.ne.jp/codeiq/q1058.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています
・ data.utf8.txt
　→ 調査対象およびテストデータです。文字コードは UTF-8 になっています。
・ data.sjis.txt
　→ 調査対象およびテストデータです。文字コードは Shift_JIS になっています。
■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

当初は、上記の補足にある「負ではない整数」の部分が「正の整数」になっているという出題ミスがあった。
すいません。＞中の人と挑戦していただいた方々

出題の背景と意図とか

中学入試算数をシリーズ化しようということになったので、問題集を購入。
眺めていて、これにしようと思った次第。
難易度や手かずもちょうど良さそう。

実装戦略と例

小学生にとっては単位の計算と空欄の値の逆算が難しいわけだけど、ソースコードを書く身としては字句解析が難しい。

入力は、問題にある通り

3m20cm-3m10cm-□mm=5mm

のようになっている。
BNFっぽく（っぽいだけ）書くと

入力は、2つの式を「=」でつないだもの
式は、項を「+」か「-」でつないだもの
項は、値を区切り記号なしでつないだもの
値は、数値と単位を区切り記号なしでつないだもの
数値は、10進数または「□」
単位は、「秒」「mg」「km」などいろいろ

という感じ。

これを素直に実装するのが良いと思う。

というわけで、私の実装例を示しておく。

私の実装例 ( ruby )

# ruby  2.1.3p242
UNIT_VALUES = [
  { 'mm' => 1r / 1000, 'cm' => 1r / 100, 'm' => 1r, 'km' => 1000r, },
  { 'mg' => 1r / 1000, 'cg' => 1r / 100, 'g' => 1r, 'kg' => 1000r, },
  { '秒' => 1r, '分' => 60r, '時間' => 60 * 60r, '日' => 60 * 60 * 24r, },
]

# "3分20秒" のような文字列を 200 に変換する(1秒、1m、1g が 1 になる)
# @note "□km" のような文字列は 0 になる
def term_value(t, units)
  t.scan(/([\d□]+)([^\d□]+)/).reduce(0){ |acc, (digit, unit)|
    acc  +  digit.to_i * units[unit].tap{ |v|
      raise "#{unit} is not in #{units.keys.join(",")}" unless v
    } # "□".to_i==0 を利用している
  }
end

# "3分20秒+30秒-1分" のような文字列を 170 に変換する(1秒、1m、1g が 1 になる)
# @note "□km" のような文字列は 0 になる
def expr_value(e, units)
  e.scan(/([+-]?)([^+-]+)/).reduce(0){ |acc, (sign, term)|
    acc + ( sign == '-' ? -1 : 1) * term_value(term, units)
  }
end

# "3m20cm-3m10cm-□mm=5mm" のような問題を解く
# @note 答えが負にならないことに依存している
def solve(x)
  unit = /□([^\+\-\=]+)/.match(x)[1]
  units = UNIT_VALUES.find{ |u| u.keys.include?( unit ) }
  raise "#{unit} is not in units" unless units
  left, right = x.split('=').map { |e| expr_value(e, units) }
  (left - right).abs / units[unit]
end

# data.utf8.txt を読み、右の問題と左の問題の答えが合わないものを出力する。
open('data.utf8.txt', 'r:utf-8') do |f|
  ids = f.flat_map{ |line|
    id, *q = line.strip.split(/\t/)
    answers = q.map { |x| solve(x) }
    answers.uniq.size == 1 ? [] : [id]
  }
  puts '%d件 : %s' % [ids.size, ids.join(',')]
end

右辺と左辺を別々に処理した方がいいので、入力から式を得るためには「=」で分割するのが良い。
分割された文字列は
「3m20cm-3m10cm-□mm」のような形をしているんだけど、これを
「3m20cm」「-3m10cm」「-□mm」のよう分割する。これは、「-3m10cm」のような部分で、「-」は「3m」にも「10cm」にも影響をあたえるから。
あとは「-3m10cm」のようになるので、数値＋単位で scan してから「cm」のような単位を評価してから合計し、符号に応じて +1 か -1 を乗じれば良い。
「□」は、"□".to_i がゼロになるのでゼロになるに任せた。

方程式を解く部分はちょっとズルくて、右辺と左辺の差の絶対値という計算をしている。
負の値は出てこないことを利用している。
もうちょっとずるくすると、右辺の項はどれもひとつだけになっているので「=」を「-」に読み替えるという手もある。
最後に「□」についてる単位に応じて調整して終了。

時間があったら perl6 の grammar を使ったものや、求解を2分探索で行うものも実装したい。

感想など

今回も、テストせずに提出するのはほぼ無理という形で出題したのが功を奏し、ほぼ全員が正解だった。
おめでとう！

真剣なパーサーで対応してくださった方もいらっしゃったんだけど、この文法は再帰していないのでそこまでは不要。
上記の例のように淡々と切っていくのが良いと思う。
perl6 や Haskell のような、パーサーを書くのが簡単な言語なら真剣なパーサも悪くない選択だとは思うけどね。

いつも通り、締切後はコード公開大歓迎。
コードを公開したら、 twitter などで知らせてくれると見つけやすくて助かります。

最後に

次の問題は、もう CodeIQ の中の人に渡してあるので近日中に公開されると思う。

それと。
第26回オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/events/15316 ) やります。
10月4日(土) 横浜。

お暇とご興味のある方は是非。

CodeIQ との違いは下表の通り。

	CodeIQ	オフラインリアルタイムどう書く
場	オンライン	オフライン
締め切り	3週間とか	1時間ぐらい
問題	いろいろ	1時間で解ける人が半分ぐらいの問題
他人のコード	見られないこともある	見られる
自分のコード	見せなくてもいい	見せる
懇親会	なし	あり
転職	役に立つ	たぶん役に立たない
雰囲気	？？	ぬるい

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

中学入試から：単位のある計算」の解説・解題

問題

出題の背景と意図とか

実装戦略と例

私の実装例 ( ruby )

感想など

最後に