LoginSignup
1

More than 5 years have passed since last update.

[Crystal] 3角形はいくつあるの問題

Last updated at Posted at 2016-03-16

Crystal の開発元である Manas社のTwitterアカウントで,以下のようなつぶやきを見かけまして。

とりあえず,手作業で47個までは見つけたのですが,他にもないのか機械的に探索するコードを Crystal で書いてみたのがこんな感じ。

triangles.cr
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)

上記がとりあえず動く事優先で無駄な動きがあったので手直しをば。

triangles2.cr
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 で済ませるののどちらが処理的に軽いのかは気なるところ。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1