史上最大のコーディングスキル判定

こんなのがあったので解いてみた。3時間で解けないんじゃないかと不安だったけど、Rubyの強力なString・Arrayのライブラリを駆使し（←）75分で解答。以下続きを読む記法にて：
以下が書いてみたコード。行数にして80行。無駄が多いとか言わない、半ば意地で解いたし。

first_tehai = "1112345678999"

if first_tehai.length < 13
  puts "shouhai!"
  exit
elsif first_tehai.length > 13
  puts "ta-hai!"
  exit
end

$result = []

def find_machi(tehai,output)
  koutsu = ["111","222","333","444","555","666","777","888","999"]
  shuntsu = ["123","234","345","456","567","678","789"]
  jiku = ["12","23","34","45","56","67","78","89"]
  atama = ["11","22","33","44","55","66","77","88","99"]
  valid_machi = jiku + atama
  has_koutsu = 0
  
  if tehai.length == 2
  	valid_machi.each do |vm|
  	  if vm == tehai
  	    $result << output + tehai
  	  end
  	end
  end
  
  if tehai.length == 1
  	$result << output + tehai
  end
  
  # check koutsu
  koutsu.each do |ko|
  	if tehai[ko]
  	  # if tehai has koutsu then deepen
  	  has_koutsu = 1
  	  find_machi(tehai.sub(ko,""),output + ko + ",")
  	end
  end
  
  # check shuntsu
  shuntsu.each do |sh|
  	sh_arr = sh.scan(/./)
    if (tehai.squeeze)[sh]
      next_tehai = tehai
      sh_arr.each do |sh_ch|
        next_tehai = next_tehai.sub(sh_ch,"")
      end
      find_machi(next_tehai,output + sh + ",")
    end
  end
  
  if tehai.length == 4 and has_koutsu == 0
    atama.each do |at|
      if tehai[at]
        find_machi(tehai.sub(at,""),output + at + ",")
      end
    end
  end
  
end

find_machi(first_tehai,"")

result = []
output = []
$result.each do |r|
  a = r.split(",")
  for i in 0..3 do
    a[i] = "(" + a[i] + ")"
  end
  a[4] = "[" + a[4] + "]"
  result << a.sort
end

result = result.uniq
result.each do |r|
  puts r.join
end

まずアイデア。手牌をベースに有効な順子・刻子・頭を削っていく探索問題。@mayahjpさんが「ISerならOCamlかPrologで解かなきゃねー」というのも納得、Prologは確かにこれに向いている。でもPrologだとどういうデータ構造使えばいいか考えるのがめんどくさい。というわけで再帰で探索を実装。再帰で探索を実装するなら関数型というので以上の意見には納得だけど、OCamlがそんなに自信もって書けない。mutableなリスト使ってできたもの放り込んでいけばいいんだろうけどね。
で、「()[]の出力順は自由ですが、順序だけが違うものは同一視してください（例：111222を刻子2つで構成するとき、(111)(222)が(222)(111)に入れ替わるだけのものは同一解答とします）」という指示を見て思ったのは、Rubyで一度Array#sortとArray#uniqを使って順序違いのものの同一視をやったことがあったので、よし、Rubyだと。というか最初からRuby使うことしか頭になかったのかもしれない。再帰呼び出しはするけど返り値を使って処理する純粋に関数型なアプローチではなくmutableなリストに放り込むようなノリでグローバル変数を使う。
あとはsubstringのマッチングとsubstringの削除を駆使して計算。枝狩りとかやってない上に内部でloop繰り返してるので相当重い。

でも原出題者の「人材獲得作戦」第４回の迷路の問題は同様に探索問題だけど探索の方針がこの問題ほど単純じゃなく、まず最初の図をパースするのが一苦労（おそらく二次配列に落とす）、実行時間の制限とか設けてある場合枝狩りしないと間に合わない、最短性のチェックは最短距離を解答の図と一緒に保管しておけば可能（それかマップ全体の移動した経路の長さを移動経路を示す文字のカウントで）とは思うが…など、多分そっちは3時間じゃ辛い。まぁどちらにせよ探索問題なのですが。