はしがき

コードゴルフ（Code Golf）というゲームがあることを最近知りました。

トータルの打数をできるだけ少なくすることを目指すスポーツのゴルフに対して，コードゴルフではソースコードをできるだけ短くすることを目指すそうです。

面白そうなので先日書いた「３角形はいくつあるの問題」を題材にチャレンジしてみることにしました。ベースとなるコードはこちら（何をしてるのかは上記リンク先を参照してくださいませ）。

元ファイル（triangle.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}"

ファイルサイズ

$ ls -l triangle.cr
-rw-r--r--  1 arcage  staff  1197  3 18 13:06 triangle.cr

正式なコードゴルフのルールは（そんなものが存在するのかも含めて）わかりませんが，今回はこれを

最終的に検出した３角形の合計数が出せればよし（３角形のリストは出さない）
読みやすさは考えない
処理効率も気にしない
本来のメソッドの使い方とかスルー
潜在的なバグの危険性とかも考慮しない
とにかくソースファイルのサイズ最小化を目指す

という方針で，現時点で思いつく限りの手を尽くしてみました。

やったことリスト

変数名を１文字に変更
省略できる空白/改行は削除（インデントもしない）
配列リテラルの代わりに文字列をString#split
"10" を "a" に
長い型名に１文字のエイリアスを用意
do ... end の代わりに {}
Array#includes?(obj)の代わりにArray#count(obj)>0
Array の代わりに Set を使うと重複チェックが要らない
１度しか呼ばないメソッドは処理をベタ書き
可能であれば == の代わりに > や < で判定
true の代わりに 1，false の代わりに nil
出力するのが数値なら puts も p も結果は同じ

その結果

こうなりました。（注：横に長いです。要スクロール）
基本的に，解決に向けたアプローチは上のコードと変わりません。（最後に p r とかしてやると，検出した３角形の一覧も見られます）

縮小版（triangles_golf.cr）

alias A=Array(String)
L="123|1469|17a|21|23|247|268a|259|321|3567|39a|41|42|469|47|52|53|567|59|62|641|653|67|68a|69|71|742|7653|789|7a|862|87|89|8a|93|952|9641|987|9a|a71|a862|a93".split("|").map(&.split(""))
d=Hash(String,A).new(A.new)
r=Set(A).new
L.each{|l|d[l[0]]+=l[1..-1]}
d.each_key{|a|d[a].each{|b|d[b].each{|c|t=[a,b,c]
f=1
L.each{|l|f=nil if t.map{|o|l.count(o)}.sum>2}
r<<t.sort if d[c].count(a)>0&&f}}}
p r.size

実行結果

$ crystal triangle_golf.cr
47

ファイルサイズ

$ ls -l triangle_golf.cr
-rw-r--r--  1 arcage  staff  425  3 18 17:58 triangle_golf.cr

今回出題された問題だけ解ければ良いのであればもう２バイトほど削減できそうですが，今の自分ではこの辺りが限界のようです。

おそらく，１年後に見たら自分でも何してるか分からないと思います。

[Crystal] 「３角形はいくつあるの問題」でコードゴルフ

はしがき

やったことリスト

その結果