Crystal の開発元である Manas社のTwitterアカウントで,以下のようなつぶやきを見かけまして。
Today in #ManasBlog we ask you: How many triangles can you find in this figure? by @bcardiff https://t.co/EA3eQQxYMb pic.twitter.com/00S3LaDRG2
— Manas (@manastech) 2016年3月14日
とりあえず,手作業で47個までは見つけたのですが,他にもないのか機械的に探索するコードを Crystal で書いてみたのがこんな感じ。
PATH = [ [1, 2, 3], [1, 4, 6, 9], [1, 7, 10], [2, 1], [2, 3], [2, 4, 7], [2, 6, 8, 10], [2, 5, 9], [3, 2, 1], [3, 5, 6, 7], [3, 9, 10], [4, 1], [4, 2], [4, 6, 9], [4, 7], [5, 2], [5, 3], [5, 6, 7], [5, 9], [6, 2], [6, 4, 1], [6, 5, 3], [6, 7], [6, 8, 10], [6, 9], [7, 1], [7, 4, 2], [7, 6, 5, 3], [7, 8, 9], [7, 10], [8, 6, 2], [8, 7], [8, 9], [8, 10], [9, 3], [9, 5, 2], [9, 6, 4, 1], [9, 8, 7], [9, 10], [10, 7, 1], [10, 8, 6, 2], [10, 9, 3] ]
def straight?(p1, p2, p3)
PATH.each { |path| return true if path.includes?(p1) && path.includes?(p2) && path.includes?(p3) }
return false
end
dst = Hash(Int32, Array(Array(Int32))).new { |h,k| h[k] = Array(Array(Int32)).new }
triangles = Array(Array(Int32)).new
PATH.each { |path| dst[path.first] << path[1..-1] }
dst.each_key do |p1|
dst[p1].flatten.sort.each do |p2|
dst[p2].flatten.sort.each do |p3|
next if !dst[p3].flatten.includes?(p1) || straight?(p1, p2, p3)
triangle = [p1, p2, p3].sort
triangles << triangle unless triangles.includes?(triangle)
end
end
end
puts triangles.map{|t| t.join("-") + "\n"}.join() + "total: #{triangles.size}"
でもって,その出力がこちら。
1-2-4
1-2-6
1-2-7
1-2-9
1-2-10
1-3-6
1-3-7
1-3-9
1-3-10
1-4-7
1-6-7
1-6-10
1-7-9
1-9-10
2-3-5
2-3-6
2-3-7
2-3-9
2-3-10
2-4-6
2-4-9
2-5-6
2-5-7
2-6-7
2-6-9
2-7-8
2-7-9
2-7-10
2-8-9
2-9-10
3-5-9
3-6-9
3-6-10
3-7-9
3-7-10
4-6-7
4-7-9
5-6-9
5-7-9
6-7-8
6-7-9
6-7-10
6-8-9
6-9-10
7-8-10
7-9-10
8-9-10
total: 47
どうやら47で全部っぽい?
追記(2016/03/17)
上記がとりあえず動く事優先で無駄な動きがあったので手直しをば。
PATH = [ [1, 2, 3], [1, 4, 6, 9], [1, 7, 10],
[2, 1], [2, 3], [2, 4, 7], [2, 6, 8, 10], [2, 5, 9],
[3, 2, 1], [3, 5, 6, 7], [3, 9, 10], [4, 1],
[4, 2], [4, 6, 9], [4, 7],
[5, 2], [5, 3], [5, 6, 7], [5, 9],
[6, 2], [6, 4, 1], [6, 5, 3], [6, 7], [6, 8, 10], [6, 9],
[7, 1], [7, 4, 2], [7, 6, 5, 3], [7, 8, 9], [7, 10],
[8, 6, 2], [8, 7], [8, 9], [8, 10],
[9, 3], [9, 5, 2], [9, 6, 4, 1], [9, 8, 7], [9, 10],
[10, 7, 1], [10, 8, 6, 2], [10, 9, 3] ]
def on_a_path?(p1, p2, p3)
PATH.each do |path|
return true if path.includes?(p1) && path.includes?(p2) && path.includes?(p3)
end
return false
end
dst = Hash(Int32, Array(Int32)).new { |h,k| h[k] = Array(Int32).new }
triangles = Array(Array(Int32)).new
PATH.each do |path|
dst[path.first] += path[1..-1]
end
dst.each_key do |p1|
dst[p1].each do |p2|
dst[p2].each do |p3|
next if !dst[p3].includes?(p1) || on_a_path?(p1, p2, p3)
triangle = [p1, p2, p3].sort
triangles << triangle unless triangles.includes?(triangle)
end
end
end
triangles.sort.each do |triangle|
puts triangle.join("-")
end
puts "total: #{triangles.size}"
変更点1: dst
の定義
dst
は始点となる点を key として,「取り得る直線の終点のリスト」を value として保持するハッシュです。上記コード中の value は始点から取り得る直線ごとに終点のリストを配列として作り,直線の数だけ「その配列」を持つ配列(日本語にすると分かりにくいですね)として Array(Array(Int32))
型になっています。
当初は直線ごとにまとまってると使い道があるかなと思ったのですが,実際のところは必ず #flatten
でフラットな1次元配列に落とし込んで使ってる状態でしたので,最初から1次元配列に定義を変更しました。
変更点2: sort
を呼ぶタイミング
最終的な出力結果が番号順になって欲しくて,終点リストを #each
で回すたびに #sort
を呼んでいましたが,最後の出力時点で triangles
を #sort
すれば良いことに気づいたのでそのように変更しました。
変更点3: フォーマットを読みやすく
最初の PATH
定義を始め,行数を減らすために強引に1行に詰め込んだ部分がありましたが,そこまでして行数をへらしても読みづらいだけなので一般的な記述方式に変更しました。
ただ,出力処理については,配列の要素を #each
で回してその中で整形したものを毎回 puts
で書き出すのと,#map
後に #join
して1回の puts
で済ませるののどちらが処理的に軽いのかは気なるところ。