「中学入試から：正三角形？二等辺？」の、解説・解題

CodeIQ に「中学入試から：正三角形？二等辺？」という問題
https://codeiq.jp/ace/nabetani_takenori/q1097
を出した。

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

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

で。
まずは問題

問題

■問題の概要
中学入試の問題に、以下の様な問題が出ることがあります。

三角形ABCがあります。
角C=30度,BA=2cm,CA=2cm です。
この三角形の性質について正しく述べているものを下記のあ〜うからひとつ選んで下さい。
　あ）正三角形である。
　い）二等辺三角形である。（ただし、正三角形であるとはいえない。）
　う）二等辺三角形ではない。または、二等辺三角形かどうかわからない。

ABとACが等しいので、二等辺三角形。つまり、「い」が正解です。

この問題を

三角形ABCがあります。
【　A　】 です。
この三角形の性質について正しく述べているものを下記のあ〜うからひとつ選んで下さい。
　あ）正三角形である。
　い）二等辺三角形である。（ただし、正三角形であるとはいえない。）
　う）二等辺三角形ではない。または、二等辺三角形かどうかわからない。

と考え、A を入力として与えます。問題の答えを計算するプログラムを書いて下さい。

■具体的な課題
下記リンクの zip 内に data.utf8.txt および data.sjis.txt というファイルがあります。
これらのファイルの各行は
　「データID、空欄Aの内容、空欄Aの内容に対応した答え」
を TAB区切りでならべたものです。
ほとんどのデータは正しい答えになっています。
答えが間違っているデータが数件あります。それらのデータの ID を答えて下さい。

data.utf8.txt と data.sjis.txt は、文字コードが異なるだけで内容はまったく同じです。
お好きな方をお使い下さい。

■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・間違いの数は、5件より多く、20件より少なくなっています。
・空欄Aに入る内容は、長さまたは角度について記述されたものをコンマ区切りでならべたものです。
・長さについては「AB=3cm」のような形式です。長さの単位はすべて cm です。
・角度については「角A=30度」のような形式です。頭に「角」があり、単位は「度」です。

■資料
http://nabetani.sakura.ne.jp/codeiq/q1097.zip

上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.utf8.txt
　→ 調査対象およびテストデータです。文字コードは UTF-8 になっています。

・ data.sjis.txt
　→ 調査対象およびテストデータです。文字コードは Shift_JIS になっています。

■解答形式
「【解答】」の行に続いて解答をお書き下さい。
「【感想・工夫した点など】」の行に続いて、感想、引っかかった点、工夫した点、問題が曖昧だと感じた場合はそこをどう解釈したか、などをお書き下さい。
「【言語と処理系】」の行に続いて、言語名、処理系のバージョン、コマンドラインオプションなどをお書き下さい。
「【ソースコード】」の行に続いて、ソースコードをお書き下さい。ソースコードが複数になるようでしたら、その旨がわかるようにお願いします。

こんな感じ。

で。
今回も若干の出題ミスのようなものがあった。
三角形が成立しないデータが含まれていた。すいません。
作図可能なものについてはきちんと調べたんだが、作図するには情報が不足しているものについてのチェックが足りていなかった。

すいません。

出題の背景と意図とか

当初は平行四辺形とか菱形にしようと思っていたんだけど、条件の量が多くなるので三角形にしてみた。
簡単だったでしょ？

実装戦略と例

出題者（私）の意図通り、完全に小学生の算数の範囲で解くことにして、入力データのバリデーションを一切しないのであれば、すごく簡単になる。

バリデーションなしの実装 ( ruby )

def solve(q)
  terms = q.split(",")
  kv=terms.each_with_object(Hash.new(0)){ |t,h|
    h[ /(\d+(?:cm|度))/.match( t )[1] ] += 1
  }
  angles=kv.flat_map{ |k,v| /(\d+)度/===k ? [$1.to_i]*v : [] }
  kv["#{180-angles.inject(&:+)}度"]+=1 if angles.size==2 # 2角がわかっているので、残り1つもわかる。
  case kv.values.max
  when 0, 1 then "う"# 重複なし
  when 2 then 0<kv["60度"] ? "あ" : "い" # 二辺または二角が等しい
  when 3 then "あ" # 三辺または三角が等しい
  else raise "unexpected : #{q}"
  end
end

open( "../package/data.utf8.txt", "r:utf-8" ) do |f|
  f.flat_map{ |line|
    line.strip!
    id, q, ans = line.split(/\t+/ )
    actual = solve(q)
    ok = ans==actual
    puts [line, id, q, ans, actual ].join(" / ") unless ok
    ok ? [] : [id]
  }.join(",").tap{ |s| puts s }
end

レビューコメントで字句解析部と判定部を分けるべきだと書いているのでちょっと申し訳ないような気持ちもあるんだけど、あんまり短いのでひとつのメソッドにしてしまっている。
すいません。

実装戦略はまあ見ての通りなんだけど、一応解説しておくと。

• 「60度」のような文字列をキーにして、それの文字列の出現回数を値にする Hash を作る。
• Hash の値の最大値を見る。 → 3 なら 正三角形、など

というもの。

たぶんポイントは、角の名前や辺の名前を一切無視してよいという点にあると思う。

バリデーションありの実装 ( ruby )

挑戦いただいた方の中には、入力データのバリデーションをやってくださった方がいた。
それはまあ意図しないことではあったんだけど、全部バリデーションするとこれぐらいになるよ、というのも書いておく。

Equilateral="あ" # 正三角形
Isosceles="い" # 二等辺三角形
Common="う" # 普通の三角形
Impossible = "う!" # 三角形が作れない

# 内角の和で角度を補完する
def complete_by_interior_angles( a0 )
  angles = a0.dup
  missings = "ABC".chars - angles.keys
  if missings.size==1
    angles[missings[0]]=angles.values.inject( 180 ){ |acc, val| acc-val }
  end
  angles
end

# 角度の値が不正なら真を返す
def invalid_interior_angles( angles )
  return true if angles.values.any?{ |x| x<=0 || 180<=x }
  angles.size==3 && angles.values.inject(&:+)!=180
end

# 浮動小数点の誤差をごまかす等号
def almost_eq( a, b )
  (a-b).abs < 1e-5
end

# 浮動小数点の誤差をごまかしつつ uniq する
def almost_uniq(v0)
  v=v0.sort
  v.inject([]){ |acc, e|
    if acc.empty? || !almost_eq( acc.last, e )
      acc+[e]
    else
      acc
    end
  }
end

# 等しい物の数を数えるだけで判断する
def solve_simple( h )
  v = h.values
  return Impossible if v.min<=0
  m=v.max
  values = (v + [m+1, m+2] ).take(3)
  case almost_uniq(values).size
  when 1; Equilateral
  when 2; Isosceles
  when 3; Common
  else
    raise "logic error"
  end
end

# 弧度法を使った三角関数と逆三角関数
def sina(angle); Math.sin( angle*Math::PI/180 ); end
def cosa(angle); Math.cos( angle*Math::PI/180 ); end
def acosa(r); Math.acos(r)*180/Math::PI; end
def asina(r); Math.asin(r)*180/Math::PI; end

# 正弦定理を使って辺を求めて解く
def solve_by_sin( a, e )
  raise "logic error" unless a.size==3  && 0<e.size
  n=e.keys.first
  r=sina(a[n]) / e[n]
  a.keys.each do |m|
    expected = sina(a[m]) / r
    return Impossible if expected<=0
    if e[m]
      return Impossible unless almost_eq( e[m], expected )
    else
      e[m] = expected
    end
  end
  solve_simple( a )
end

# 二辺挟角なので余弦定理で辺を求めて解く
def solve_by_cos2(a, e)
  x=a.keys.first
  y,z=e.values
  expected2 = y*y+z*z-2*y*z*cosa(a.values.first)
  return Impossible unless 0<expected2
  e[x]=expected2**0.5
  solve_simple(e)
end

# 二辺と、挟角ではない角
def solve_by_sin2(a, e)
  x=a.keys.first
  y,=e.keys - [x]
  sin_y=sina(a[x]) * e[y] / e[x]
  return Impossible unless 0<sin_y && sin_y<=1
  ay0 = asina(sin_y)
  ay1 = 180-ay0
  [ay0, ay1].map{ |ay|
    solve_simple( complete_by_interior_angles(a.merge( y=>ay )) )
  }.select{ |r| r.size==1 }.max || Impossible # 文字コードがあいうの順になっていることに依存
end

# 余弦定理を使って角度を求めて解く
def solve_by_cos( a, e )
  raise "logic error" unless e.size==3
  3.times do |rot|
    names = %w(A B C).rotate(rot)
    ea, eb, ec = names.map{ |n| e[n] }
    expected = acosa( (eb*eb+ec*ec-ea*ea)/(2.0*eb*ec) )
    n=names.first
    if a[n]
      return Impossible unless almost_eq( a[n], expected )
    else
      a[n]=expected
    end
  end
  solve_simple( e )
end

# 字句解析。定義の重複についてはエラーを出す
def parse_problem( src )
  src.split(",").each_with_object( Array.new(2){{}} ) do |item,o|
    case item
    when /\A角([ABC])\=(\d+)度\z/
      raise "duplicate angle #{$1} in #{item}" if o[0][$1]
      o[0][$1]=$2.to_i
    when /\A([ABC]+)\=(\d+)cm\z/
      key = ( %w(A B C ) - $1.chars ).first
      raise "duplicate edge #{$1} in #{item}" if o[1][key]
      o[1][key]=$2.to_i
    else
      raise "unexpected item : #{item}"
    end
  end
end

# 三辺の長さとしてあり得るなら真
def acceptable_edges(e)
  raise "logic error" unless e.size==3
  a,b,c=e.values.sort
  return c<a+b
end

#問題を解く、主要部分
def solve_core( angles, edges )
  case [angles.size, edges.size].join
  when /[01][01]/; Common # 情報不足
  when /30/; solve_simple( angles )
  when /03/; 
    if acceptable_edges( edges )
      solve_simple( edges )
    else
      Impossible
    end
  when /3[123]/; solve_by_sin(angles, edges)
  when /[0123]3/; solve_by_cos(angles, edges)
  when /12/;
    if %w(A B C)==[angles.keys, edges.keys].flatten.sort
      solve_by_cos2(angles, edges)
    else
      solve_by_sin2(angles, edges)
    end
  when /02/;
    solve_simple( edges )
  else
    raise "logic error : #{[angles.size, edges.size]}"
  end
end

#問題を解く
def solve(src)
  angles, edges = parse_problem(src)
  angles = complete_by_interior_angles( angles )
  return Impossible if  invalid_interior_angles( angles )
  solve_core( angles, edges )
end

if __FILE__==$0
  File.open( "../../../package/data.utf8.txt", "r:utf-8" ) do |f|
    inco=[]
    imp=[]
    f.each do |line|
      id, src, expected = line.strip.split(/\t+/)
      actual = solve(src)
      inco<<id if actual[0,1] != expected
      imp<<id if 1<actual.size
    end
    puts "wrong answers : "+inco.join(",")
    puts "impossible triangles : "+imp.join(",")
  end
end

とまあ、200行弱。

バリデーションがあると、角や辺の名前を捨てる訳にはいかない。
実装戦略は

• 既知の角/辺 の数と配置によって分岐。
• 分岐先で、余弦定理や正弦定理を使って残りの角や辺を求めたりバリデーションしたり。
• 最終的には、何かが 3個あったら正三角形、2個あったら二等辺、というようなところに落ちる。
• 等値性は、浮動小数点なので適当に誤差を許して比較する。

実はこのバリデーションを一生懸命している長い実装のほうがよろしくない。
浮動小数点を使っている関係で、厳密に等しいかどうかの判定ができないからだ。

具体的には「BC=33379cm,AC=96111cm,角C=80度」のような入力で間違える。
この入力は二辺と挟まれる角なので、余弦定理で AB を求めることができて、AB=96110.999998cm ぐらいになる。
AC と ほぼ 同じなので二等辺三角形だと思い込んで「い」を返すんだけど、AB と AC は厳密に等しいわけではない。
今回の課題に含まれるデータには小さな整数しか入っていないので問題ないんだけど、三角関数で不足している辺や角を求めてしまった方は、この問題に意識的であるべきだと思う。

数学的に厳密に

実は。
「3辺が整数で、3つの角も弧度法表示で整数になる三角形は、正三角形である」
という定理があるので、数学的に厳密な実装という観点では三角関数は不要ということがわかっている。

三角形のバリデーションをするのには必要だと思うけど。

感想など

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

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

そうそう。
解答の数字は円周率。円周率だけだと間がひろく空いてしまう場所があったので、ゾロ目も混ぜてみた。

最後に

次の問題は準備中。今回よりさらに簡単になる予定。

それと。
第27回 オフラインリアルタイムどう書く( http://yhpg.doorkeeper.jp/events/16017 ) やります。
11月7日(金) 横浜。

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