「中学入試から：図形と場合の数」の 解説・解題

CodeIQ に「中学入試から：図形と場合の数」という問題
https://codeiq.jp/ace/nabetani_takenori/q1188
を出した。

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

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

で。
まずは問題

問題

■問題の概要
中学入試算数の範囲で、以下の様な問題を作ることが出来ます。

円周上を7等分する点を考え、順に点Aから点Gとします。
これらの頂点のうち A,C,E,G から3点を選び、この3点を頂点とする三角形を考えます。
作ることのできる三角形は、何種類あるでしょうか。
ただし、裏返さずに回転してぴったり重ねられる三角形は、同じ種類とします。

この問題を

円周上を【あ】等分する点を考え、点の名前を点A, 点B, ... と順につけます。
これらの頂点のうち【い】から3点を選び、この3点を頂点とする三角形を考えます。
作ることのできる三角形は、何種類あるでしょうか。
ただし、裏返さずに回転してぴったり重ねられる三角形は、同じ種類とします。

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

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

■補足
・データIDがTで始まるデータは、すべて正しい答えになっています。テストにお使い下さい。
・不正な入力に対処する必要はありません。
・辺の長さが 3, 4, 5 の三角形と 5, 4, 3 の三角形は裏返さないと重ねられれないので同種とみなしません。
・間違いの数は、5件より多く、20件より少なくなっています。

■資料
http://nabetani.sakura.ne.jp/codeiq/q1138.zip
上記リンク先の zip ファイルの中には、以下のファイル含まれています

・ data.txt
　→ 調査対象およびテストデータです。

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

こんな感じ。

出題の背景と意図とか

今回もかなりリアルな中学入試問題になっている。
「裏返して重なるものは同じとみなす」という問題が多いんだけど、今回は裏返さないと重ならないものを別とみなすというひねりを入れてみた。
このひねりがないと簡単すぎると思ったからなんだけど、それでも十分簡単だったと思う。
簡単だったでしょ？

実装戦略と例

三角形の列挙は、ruby なら combination(3) が使えるので、それで。
そういう関数がない C や Java の場合は三重ループを書くのが良いと思う。
私の場合、こういう場合は YAGNI の精神で必要最低限のものを書く方が良いように感じている。

次に。
列挙した三角形を数えるんだけど、
a) 正規化する
b) 発見済みのものとの比較
というふたつの戦略がある。自然に正規化に思考が向かわなかった人は、たぶんちょっと反省したほうがいいと思う。

正規化は、[a,b,c], [b,c,a], [c,a,b] の三通りのうち辞書順で一番先頭になるもの。というのが書きやすくて良いと思う。
最小の辺を先頭に……いや二等辺三角形の場合は……というような感じで場合分けをするよりも簡単になる。

で。ruby による実装例。

def solve_impl( total, corners )
  corners.combination(3).each_with_object({}){ |c,h|
    lens=3.times.map{ |x|(c[x]-c[x-1]+total)%total }
    key=3.times.map{ |x| lens.rotate(x) }.min
    h[key]=true
  }.size
end

def solve( total, corners )
  solve_impl(total.to_i, corners.split(",").map{ |x| x.ord-?A.ord } )
end

File.open( "data.txt" ) do |f|
  wrongs = f.flat_map{ |line|
    id, total, corners, expected = line.split("\t")
    actual = solve( total, corners )
    actual==expected.to_i ? [] : [id]
  }
  puts wrongs.join(",")
end

ruby なので、rotate があったり、配列と配列の大小関係が使えたり、便利この上ない。
ひとつ注意をしておくと。この実装では、Hash のキーに配列を使ってしまっている。
この実装のように、メソッドの外に出ないような使い方は問題無いと思うけど、一般的にはお勧めできない。
まずいことが起こるのは、下記のような例：

h={[1,2] => 3 } # 配列をキーにする。
p h #=> {[1, 2]=>3}
p h[ [ 1, 2 ] ] #=> 3。当たり前。
h.keys.first.reverse! # キーの配列に破壊的変更を加える
p h #=> {[2, 1]=>3}。当たり前。
p h[ [ 2, 1 ] ] # => nil。見つからない。
h.rehash
p h[ [ 2, 1 ] ] # => 3。rehash すると見つかるようになる。

rehash なんて忘れるに決まっているので、キーがひとり歩きしうる状況では配列のような変更しやすい感じのオブジェクトはキーにしないほうがいいと思う。
そういう意味では、ruby の場合は文字列もあまりよろしくない。シンボルや数値がよい。

感想など

今回もほぼ全員が正解だった。
おめでとう！

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

今回はちょっと時間が取れなくて締切後の私の動きが にぶく なっているけどご容赦下さい。
実装例リンク集は明日辺りに。

次の問題は、当初とっくに公開済みの予定だったんだけど、難航していて12月中に出せるかどうか。
無理かもしれないけど まだ諦めてはいない。