飯は食えるらしい

ここに課題があったので、試しにといてみた。
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

問題

麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。

1. 字牌なし・萬子のみの想定、つまり、いわゆる「チンイツ」限定で結構です（プログラミングの本質的にはこの限定でまったく問題ないため）
2. 1〜9の数字13個からなる文字列を受け取り、できている順子・刻子・アタマを()、待ちの部分を[]でくくって出力してください
3. 面前かつ槓子は存在しない前提でOKです
4. ()[]の出力順は自由ですが、順序だけが違うものは同一視してください（例：111222を刻子2つで構成するとき、(111)(222)が (222)(111)に入れ替わるだけのものは同一解答とします）
5. 多面待ちのときも含めすべての待ちを出力してください
6. 待ちがないときは何も出力しないでください

コメント

無駄な探索をできるだけしないための工夫、デバッグを効率化するための工夫などがあればソースコードにコメントとして記入してください。

出力例

1112224588899 :

単純なケースです。45を軸にする両面の待ちなので、(111)(222)(888)(99)[45]になります。

1122335556799 :
“99”をアタマの両面か“55”“99”のシャボであるので、(123)(123)(555)(99)[67]、(123)(123)(55)(567) [99]、(123)(123)(99)(567)[55]が正解です。

1112223335559 :
待ちは“9”単騎ですが、(123)(123)(123)(555)[9]と(111)(222)(333)(555)[9]の2つあります。

1223344888999 :
1-4の“ノベタン”待ちですが、4をアタマにしての[23]待ちと、1単騎、4単騎で3個の答えになります。

1112345678999 :
「九蓮宝燈」という役です。1〜9すべてが待ちになっています。これに正しく答えが出るのであれば、プログラムはほぼ正しいでしょう。

* 麻雀を知らない人は、順子・刻子・アタマ・待ちといった用語の意味だけ調べてから解答に取りかかってください。これを調べる時間は計算外とします。

とりあえずといてみた。
twitterで確認してみたところ8:39に解き始めて10:20で終わってるので、100分で一応解けたみたい。
ただしコードは雑。

# 手牌が空かどうか
def end_check_tehai(tehai)
  tehai.each do | key, value |
    return tehai if value > 0
  end
  return nil
end

def get_juntu(hai, tehai)
  if tehai[hai].to_i > 0 && tehai[hai + 1].to_i > 0 && tehai[hai + 2].to_i > 0
    (0..2).each do | i |
      tehai[hai + i] -= 1
    end
    return [(0..2).map{|i|hai + i},  end_check_tehai( tehai )]
  end
  return false
end

#頭チェックも兼ねる。 
def get_kotu(hai, tehai, idx = 3)
  if tehai[hai].to_i >= idx
    tehai[hai] -= idx
    return [[hai]*idx, end_check_tehai( tehai )]
  end
  return false
end

def check_loop_inner(data, return_array)
  if data[1]
    data_2 = check_loop(data[1])
    if data_2.empty?
      return_array << [data[0]]
    else
      data_2.each do | d |
        return_array << [data[0]] + d
      end
    end
  else
    return_array << [data[0]]
  end
end

#取り敢えず、ジャンツとかコーツとか頭とか、取れるケースを全部あげる。
def check_loop(tehai)
  return_array = Array.new
  (1..9).each do | i |
    if data = get_juntu(i, tehai.dup)
      check_loop_inner(data, return_array)
    end
    if data = get_kotu(i, tehai.dup)
      check_loop_inner(data, return_array)
    end
    if data = get_kotu(i, tehai.dup, 2)
      check_loop_inner(data, return_array)
    end
  end
  return return_array
end

#あげたケースが、ちゃんと成り立つかチェック
def answer_check(answer, tehai)
  atama = Array.new
  nomal = Array.new
  answer.each do | a |
    if a.size == 2
      atama << a
    else
      nomal << a
    end
    a.each do | i |
      tehai[i] = tehai[i] - 1
    end
  end
  amari = []
  tehai.each do | t , v|
    v.times do
      amari << t
    end
  end
  atama_count = atama.size
  tehai_count = amari.size

  if atama_count == 0 && tehai_count == 1
    amari = amari.sort.join
    return nomal.map{|n| "(#{n.to_s})" } << "[#{amari}]"
  elsif atama_count == 1 && tehai_count == 2
    if ( amari[0] - amari [1]).abs < 3
      return answer.map{|n| "(#{n.to_s})" } << "[#{amari}]"
    else
      return nil
    end
  elsif atama_count  == 2 && tehai_count == 0
    return [ (nomal + [atama[0]]).map{|n| "(#{n.to_s})" } << "[#{atama[1].to_s}]" ,
             (nomal + [atama[1]]).map{|n| "(#{n.to_s})" } << "[#{atama[0].to_s}]" ]
  elsif atama_count  == 6 && tehai_count == 1
      return answer.map{|n| "(#{n.to_s})" } << "[#{amari}]"
  end
  return nil
end

def get_machi(tehai_string)
  tehai = Hash.new
  input_strings = tehai_string.split(//).delete_if{|c| !( c =~ /^\d$/) }

  input_strings.each do|c|
    tehai[c.to_i] = (tehai[c.to_i] || 0) + 1
  end

  answers = []
  nocheck_answers =  check_loop(tehai.dup)
  nocheck_answers.each do | answer |
    answer_check_return = answer_check(answer, tehai.dup)
   if answer_check_return.class == Array && answer_check_return.size == 2
     answer_check_return.each do | a |
       answers << a.sort
     end
   elsif answer_check_return
     answers << answer_check_return.sort
   end
  end
  puts "check #{tehai_string}"
  puts answers.uniq.map{|a| a.to_s}.join("\n")
end

get_machi("1112224588899")
get_machi("1122335556799")
get_machi("1112223335559")
get_machi("1223344888999")
get_machi("1112345678999")
get_machi("1444477888999")  # => 待ち無しのテスト

出力結果は

ruby majan.rb
check 1112224588899
(111)(222)(888)(99)[54]
check 1122335556799
(123)(123)(55)(567)[99]
(123)(123)(567)(99)[55]
(123)(123)(555)(99)[67]
check 1112223335559
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]
check 1223344888999
(123)(234)(888)(999)[4]
(123)(44)(888)(999)[23]
(234)(234)(888)(999)[1]
check 1112345678999
(11)(123)(456)(789)[99]
(123)(456)(789)(99)[11]
(11)(123)(456)(999)[78]
(11)(123)(678)(999)[54]
(111)(234)(567)(999)[8]
(111)(234)(567)(99)[89]
(111)(234)(678)(999)[5]
(111)(234)(789)(99)[56]
(111)(345)(678)(999)[2]
(111)(456)(789)(99)[23]
(11)(345)(678)(999)[12]
check 1444477888999

こんな感じ
全然アルゴリズム考えた事がなかったので、ちょっと楽しかった。

10:53 チートイツにも対応した。

  elsif atama_count  == 6 && tehai_count == 1
      return answer.map{|n| "(#{n.to_s})" } << "[#{amari}]"

だけ追加。