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

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

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr">Today in <a href="https://twitter.com/hashtag/ManasBlog?src=hash">#ManasBlog</a> we ask you: How many triangles can you find in this figure? by <a href="https://twitter.com/bcardiff">@bcardiff</a> <a href="https://t.co/EA3eQQxYMb">https://t.co/EA3eQQxYMb</a> <a href="https://t.co/00S3LaDRG2">pic.twitter.com/00S3LaDRG2</a></p>&mdash; Manas (@manastech) <a href="https://twitter.com/manastech/status/709428123679514624">2016年3月14日</a></blockquote>

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

```rb: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で全部っぽい？

# <i class="fa fa-file-text-o"></i> 追記（2016/03/17）

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

```rb: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}"
```

## 変更点１： `dst` の定義
`dst` は始点となる点を key として，「取り得る直線の終点のリスト」を value として保持するハッシュです。上記コード中の value は始点から取り得る直線ごとに終点のリストを配列として作り，直線の数だけ「その配列」を持つ配列（日本語にすると分かりにくいですね）として `Array(Array(Int32))` 型になっています。

当初は直線ごとにまとまってると使い道があるかなと思ったのですが，実際のところは必ず `#flatten` でフラットな１次元配列に落とし込んで使ってる状態でしたので，最初から１次元配列に定義を変更しました。

## 変更点２： `sort` を呼ぶタイミング
最終的な出力結果が番号順になって欲しくて，終点リストを `#each` で回すたびに `#sort` を呼んでいましたが，最後の出力時点で `triangles` を `#sort` すれば良いことに気づいたのでそのように変更しました。

## 変更点３： フォーマットを読みやすく
最初の `PATH` 定義を始め，行数を減らすために強引に１行に詰め込んだ部分がありましたが，そこまでして行数をへらしても読みづらいだけなので一般的な記述方式に変更しました。

ただ，出力処理については，配列の要素を `#each` で回してその中で整形したものを毎回 `puts` で書き出すのと，`#map` 後に `#join` して１回の `puts` で済ませるののどちらが処理的に軽いのかは気なるところ。