飯は食えるらしい
ここに課題があったので、試しにといてみた。
http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.html
問題
麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。
- 字牌なし・萬子のみの想定、つまり、いわゆる「チンイツ」限定で結構です(プログラミングの本質的にはこの限定でまったく問題ないため)
- 1〜9の数字13個からなる文字列を受け取り、できている順子・刻子・アタマを()、待ちの部分を[]でくくって出力してください
- 面前かつ槓子は存在しない前提でOKです
- ()[]の出力順は自由ですが、順序だけが違うものは同一視してください(例:111222を刻子2つで構成するとき、(111)(222)が (222)(111)に入れ替わるだけのものは同一解答とします)
- 多面待ちのときも含めすべての待ちを出力してください
- 待ちがないときは何も出力しないでください
コメント
無駄な探索をできるだけしないための工夫、デバッグを効率化するための工夫などがあればソースコードにコメントとして記入してください。
出力例
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}]"
だけ追加。