私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「自然言語で計算できるAIを作ろう」（CodeIQ）を参照してください。
あなたはとあるスマートフォンOSの開発者で、AppleのSiriのような自然言語で対話できるAIの開発を任されました。
AIと聞いて、まずディープラーニングや分散表現といった先端技術を駆使したシステムを夢想してしまったかもしれませんが、最初の目標として掲げられたのは、”まず電卓の代わりになる”こと… はい、まずは"隗より始めよ"ということで、ルールベースのシンプルな言語解析プログラムの開発から始めましょう。
求められるプログラムの前提条件は、以下の通りとなります。
標準入力から、小文字の英字およびスペースのみで構成された英文が送られる。文字列の長さは80以下とする
英文は二項演算の代数式を示しており、"one plus one"というように数も英単語として表現される
英文は、以下に示す加減乗除の二項演算のいずれかで表現されており、例外はないものとする
代数式に含まれる数は0以上10000以下の整数であり、結果は必ず整数となる
そのため、計算の過程で桁あふれや0除算は考慮しなくともよい
代数式の結果を、入力が"one plus one"なら"2"というように、数字で標準出力に返すこと
結果は整数であることが前提となるため、小数点以下は切り捨てること
以下、英文と代数式の対応となります。
表中のxおよびyは変数を示しており、実際には英単語で表現された数が入ります。
足し算 add x to y x+y x added to y y+x x plus y x+y 引き算 subtract x from y y-x x minus y x-y 掛け算 x times y x*y x multiplied by y x*y twice x 2*x 割り算 divide x by y x/y x divides y y/x half of x x/2
また、代数式の数は下記いずれかの英単語で表現されるものとします。
0,1..., 19 "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine","ten","eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" 20, 30 ... 90 "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" 100 "hundred" 1,000 "thousand" 1,000,000 "million" "and"
以下、入力と出力例になります。英文は、2200+22 を意味しています。
【入出力サンプル】
標準入力
add two thousand and two hundred to twenty two
標準出力
2222
たかが計算といっても、数字が英単語に置き換わるだけで、処理が一気に複雑になることがわかりますね。
しかも、本当に大変なのは音声認識ですから、改めて人間の脳の処理能力には驚かされます。
それでは是非、ロボットになった気分で（？）挑戦してみてくださいね。
【問題】
標準入力から、二項演算の代数式を表す英文の文字列が送られます。
文字列は、数も含めてスペース区切りの英単語のみで構成されています。
この英文の代数式を解釈し、その結果を数値で標準出力に返してください。
Rubyで解答しています。
#!/usr/bin/ruby
# 演算の種類を調べる
def checkOperator(line)
ops = {
"added to"=>"+", "add"=>"+", "plus"=>"+",
"subtract"=>"-", "minus"=>"-",
"times"=>"*", "multiplied by"=>"*", "twice"=>"*",
"divides"=>"/", "divide"=>"/", "half of"=>"/",
}
op = ""
ops.each{|key, val|
if line.include?(key) then
op = val
break
end
}
return op
end
# 文字列から数値にすべき部分を文字列で取り出す
def splitLine(line)
ret = []
if line.include?("twice") then
ret << "two"
ret << line.sub("twice", "").strip
elsif line.include?("half of") then
ret << line.sub("half of", "").strip
ret << "two"
else
ops = {
# 検索文字列 => ["削除文字列", "分割文字列"]
"added to"=>[nil, "added to"],
"add"=>["add", "to"],
"plus"=>[nil, "plus"],
"subtract"=>["subtract", "from"],
"minus"=>[nil, "minus"],
"times"=>[nil, "times"],
"multiplied by"=>[nil, "multiplied by"],
"divides"=>[nil, "divides"],
"divide"=>["divide", "by"],
}
removes = ""
splitter = ""
swap = false
ops.each{|key, val|
if line.include?(key) then
if key == "divides" then swap=true end
removes = val[0]
splitter = val[1]
break
end
}
# 削除文字列を消す
l = line
if removes != nil then
l = l.sub(removes, "").strip
end
# 分割する
ret = l.split(splitter).map{|a| a.strip}
if swap then
return [ret[1], ret[0]]
else
return ret
end
end
end
# 数値に変換可能な文字列を数値に直す
def toNum(line)
nums = {
"zero"=>0, "one"=>1, "two"=>2, "three"=>3, "four"=>4, "five"=>5,
"six"=>6, "seven"=>7, "eight"=>8, "nine"=>9, "ten"=>10,
"eleven"=>11, "twelve"=>12, "thirteen"=>13, "fourteen"=>14, "fifteen"=>15,
"sixteen"=>16, "seventeen"=>17, "eighteen"=>18, "nineteen"=>19,
}
tys ={
"twenty"=>20, "thirty"=>30, "forty"=>40, "fifty"=>50,
"sixty"=>60, "seventy"=>70, "eighty"=>80, "ninety"=>90,
}
bigs={
"hundred"=>100, "thousand"=>1000, # 10000以下なのでmillionは無い
}
# andを除いて分割
s = line.sub(" and ", " ").split
ret = 0
while !s.empty?
w = s.shift
v = 0
# 0〜19の場合
if nums[w] != nil then
v = nums[w]
# 20〜90の場合
elsif tys[w] != nil then
v = tys[w]
# 次の単語が0〜9なら加算する
if nums[s[0]] != nil then
x = s.shift
v += nums[x]
end
end
# 次の単語が1000か100なら掛ける
if bigs[s[0]] != nil then
x = s.shift
v = bigs[x]*v
end
ret += v
end
return ret
end
# 計算する
def calc(op, v1, v2)
case op
when "+" then
return v1 + v2
when "-" then
return v1 - v2
when "*" then
return v1 * v2
when "/"
return v1 / v2
end
end
# 問題を解く
def solve(line)
op = checkOperator(line)
vals = splitLine(line)
nums = []
for v in vals
nums << toNum(v)
end
return calc(op, nums[0], nums[1])
end
# main
while line = gets
line.strip!
if line.empty? then next end
p solve(line)
end
難しくはありません。頑張れば正解のプログラムを作れます。
ただ、面倒くさいです。
問題文には1,000,000が英語表記として記載されていますが、最大が10,000なので最大が1,000,000に比べるとずっと簡単です。
最大のポイントは数値部分を取り出して、数値に直す部分です。それさえできればプログラムはできたも同然です。「twice x」と「harf of x」いうのがありますがこれらだけ特殊な扱いをする必要があります。
入力力演算の種類を判断します。
問題文の入力は足し算、引き算、掛け算、割り算それぞれユニークな文字列があるのでそれでチェックしてヒットしたものを演算子の文字列として返します。
「add」と「added to」、「divede」と「devides」は一方が他方の部分文字列になっているので問題文とは順番を入れ替え、別々にヒットするようにしていますが、「added to」、「devides」は省いてしまっても正しく動作します。
文字列から数値に変換する部分（x,y）を取り出します。
まず、「twice x」と「harf of x」が特殊なので別個に処理します（25〜27行目、28〜30行目）。この処理のちょっとしたポイントは入力値にはXしかありませんが「twice x」の場合は["two", "x"]、「half of x」は["x", "two"]と[x,y]の形式にして返却値を返すことです。フォーマットが統一されるので後の処理が楽になります。
それ以外の場合ですが、正規表現を使ってできそうですが、正規表現を考えるのが面倒だったので部分文字列を引っ掛けてチェックしています。opsの各要素は「検索文字列 => ["削除文字列", "分割文字列"]」の形式になっていて、入力値に検索文字列が見つかったら（48〜55行目）削除文字列を消し（58〜61行目）、分割文字列で分割する（64行目）という処理になっています。
1点ひっかけがあって「x divides y」は数式にすると「y/x」とx,yを入れ替えなければなりません。それをswap変数をフラグとして使用し、swap=trueなら返却値を入れ替えます。
数値を表す文字列を数値に変換します。
ちなみに、この関数は仕様に対して少しオーバースペックになっていて、99,999までは正しく数値に変換できます。
numsはzero〜nineteenまで、tysはtwenty〜ninetyの10の位、bigsはhundredとthousandをチェックするための定数です。twenty〜ninetyは次にone〜nineが続く場合に足し合わせる必要があり、hundredとthousandはそれまでに数値変換した値を100倍、1000倍する必要があるので分けておきます。
まず、andは邪魔なので除いて単語に分割しておきます（93行目）。テストケースにはなかったのですが「two thousand two hundred」でも正しい様に思えたため、この様な入力パターンも考慮してのことです。この様な入力を考慮するなら最初からandを除いてフォーマットを統一した方が楽です。
分割した単語を1語ずつ先頭から処理して数値にします（96〜121行目）。
まず、単語がzero〜nineteenかtwenty〜ninetyかをチェックします（101、104行目）。
単語がzero〜nineteenまでなら相当する数値にして一時変数vに保持します（102行目）。
twenty〜ninetyなら次の単語をチェックし、one〜nineなら取り出して加算してvに保持します（105〜111行目）。つまり、「twenty one」の様に2桁の数の場合、10の位→1の位の順で記述されるのでその処理をします。
更に、「twenty one thousand」や「two hundred」の様な場合、続けて100や1000を表す単語が来るのでチェックしてvに掛けてやります（115〜118行目）。
これまでの処理で「twenty one thousand three hundred forty five」の様な入力を1回ループを回るごとに「twenty one thousand」、「three hundred」、「forty five」として分割しながら数値に変換できるので返却値retにループごとに作った値を加算して行けば数値変換が完了します。
これまで説明した各関数で作成したx,y、演算子を引数にして結果を計算します。
checkOperator()で演算子を判定し、splitLine()で数値を表す部分の文字列["x", "y"]を取り出し、toNum()でx,yを数値として取得し、calc()で計算します。
入力される最大の値が10000なので数値変換がそれほどでもありませんが、999,999,999までなら相当ややこしくなります。逆に、999,999,999まで処理できる（まともな）プログラムを作れれば、それ以上になっても対応は容易です。
ちなみに、この問題のテストケースは3パターンしかありませんでした。さすがに少なすぎると思います。
この問題をやりながら、英語よりも日本語の方が数字の数え方は秩序立っているなと思いました。でも、確かフランス語はもっといかれた数え方になるんじゃなかったっけ？