Worth Living

• ブログのタイトル Worth Living は、生きるに値するのような意味でして、人生はみんな生きる価値があるんだよという思いを込めて付けました。
• 健康や仕事、お金などライフスタイルに関する考察、およびプログラミング学習についてのコンテンツを公開しています。 お問合せ

• # Ruby入門 ＞ アルゴリズム

麻雀の手牌に対する待ちを出力する問題をRubyで解いた

makeplex salon：あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定 (1/2) – ITmedia エンタープライズ

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

前回の迷路問題に続いて、麻雀の手待ちを求める面白そうな問題が出題されていたので、またRubyで解いてみました。

前回の問題よりも今回の問題の方が、私にとっては解きやすかったです。麻雀好きだったのが功を奏したのか？
問題には書いてなかったけど、おまけでチートイツ（七対子）の待ちも求めるようにした。

今回は、迷路問題と違って、一切アルゴリズム調べたりとかをせずに、約2時間弱で解けました。たぶん解けてるはず。
書きっぱなしで、DRY違反する部分とか多いですが、面倒くさいのでそのままで。
ループ回数もたいしたことなさそうだったので、探索を減らす努力とかしてませんが、気が向いたらリファクタリングと共にチャレンジする。
では、まず問題の全文から。

麻雀の手牌が入力として与えられたとき、「待ち」を出力するプログラムを書いてください。
* 字牌なし・萬子のみの想定、つまり、いわゆる「チンイツ」限定で結構です（プログラミングの本質的にはこの限定でまったく問題ないため）
* 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個の答えになります。
(123)[23](44)(888)(999), [1](234)(234)(888)(999), (123)(234)[4](888)(999)
1112345678999 :
「九蓮宝燈」という役です。1～9すべてが待ちになっています。これに正しく答えが出るのであれば、プログラムはほぼ正しいでしょう。

以下、書いたコード。
かなり力技な部分もあるし、もっと短く書けそうだけど、ざっと書いたら僕の技量だとこんなもん。
特に残り4牌の構成を求める部分と、順子、刻子を探索する部分はどうにかしなきゃですね。

require "pp"
TEHAI = 13
LIMIT = 3   # 槓子(同じ牌が4枚)は存在しない
 
class Majan
  attr_reader :tehais, :len, :used
  # ソート済みの手牌を渡す
  def initialize(tehais)
    @tehais = tehais
    @len = @tehais.length
    # 手牌を面子で使ったかどうかのフラグ
    @used = []
    @len.times do |i|
      @used[i] = false
    end
    @answer = []
  end
 
  # 未使用の手牌の中でインデックスnを起点にして順子を探索
  def make_shuntu(n)
    shuntu = []
    used_indexes = []
    if @used[n] == false
      shuntu.push(@tehais[n])
      @used[n] = true
      used_indexes.push(n)
    end
    (n...@len).each do |i|
      if @used[i] == false
        if @tehais[i] == @tehais[n] + 1 && !shuntu.include?(@tehais[i])
          shuntu.push(@tehais[i])
          @used[i] = true
          used_indexes.push(i)
        end
        if @tehais[i] == @tehais[n] + 2 && !shuntu.include?(@tehais[i])
          shuntu.push(@tehais[i])
          @used[i] = true
          used_indexes.push(i)
        end
        if (shuntu.length == 3)
          return "(#{shuntu.to_s})"
        end
      end
    end
    # 順子ができなかったらusedフラグをクリア
    used_indexes.each do |u|
      @used[u] = false
    end
    return false
  end
 
  # 未使用の手牌の中でインデックスnを起点にして刻子を探索
  def make_koutu(n)
    koutu = []
    used_indexes = []
    if @used[n] == false
      koutu.push(@tehais[n])
      @used[n] = true
      used_indexes.push(n)
    end
    (n...@len).each do |i|
      if @used[i] == false
        if @tehais[i] == @tehais[n]
          koutu.push(@tehais[i])
          @used[i] = true
          used_indexes.push(i)
        end
        if (koutu.length == 3)
          return "(#{koutu})"
        end
      end
    end
    # 刻子ができなかったらusedフラグをクリア
    used_indexes.each do |u|
      @used[u] = false
    end
    return false
  end
 
  # 順子・刻子が3つ出来上がった後の残り4牌の構成を調査。聴牌のケースは以下の通り。
  # 1144 / 2256 / 5688 / 3456 / 3345 / 3455 / 3445 / 1345 / 3458 / 1333 / 3338 / 2333 / 3334 
  def rest_hai
    rest = []
    (0...@len).each do |i|
      if @used[i] == false
        rest.push(@tehais[i])
      end
    end
    rest.sort!
    if rest.length != 4
      return "error: rest num is not 4"
    end
 
    a, b, c, d = rest[0], rest[1], rest[2], rest[3]
    # 1144 => [ ["(11)", "[44]"], ["[11]", "(44)"] ]
    if a == b && c == d
      return [ [mentu(a, b), mati(c, d)], [mati(a, b), mentu(c, d)] ]
    # 2256 => [ ["(22)", "[56]"] ]
    elsif a == b && b+1 < c && c+1 == d
      return [ [mentu(a, b), mati(c, d)] ]
    # 5688 => [ ["[56]", "(88)"] ]
    elsif c == d && c-1 > b && b-1 == a
      return [ [mati(a, b), mentu(c, d)] ]
    # 3456 => [ ["[3]", "(456)"], ["(345)", "[6]"] ]
    elsif a+1 == b && a+2 == c && a+3 == d
      return [ [mati(a), mentu(b, c, d)], [mentu(a, b, c), mati(d)] ]
    # 3345 => [ ["[3]", "(345)"], ["(33)", "[45]"] ]
    elsif a == b && b+1 == c && c+1 == d
      return [ [mati(a), mentu(b, c, d)], [mentu(a, b), mati(c, d)] ]
    # 3455 => [ ["[34]", "(55)"], ["(345)", "[5]"] ]
    elsif c == d && c-1 == b && b-1 == a
      return [ [mati(a, b), mentu(c, d)], [mentu(a, b, c), mati(d)] ]
    # 3445 => [ ["(345)", "[4]"] ]
    elsif b == c && a == b-1 && d == c+1
      return [ [mentu(a, b, d), mati(c)] ]
    # 1345 => [ ["[1]", "(345)"] ]
    elsif a+1 < b && b+1 == c && c+1 == d
      return [ [mati(a), mentu(b, c, d)] ]
    # 3458 => [ ["(345)", "[8]"] ]
    elsif a+1 == b && b+1 == c && c+1 < d
      return [ [mentu(a, b, c), mati(d)] ]
    # 1333 => [ ["[1]", "(333)"] ]
    elsif a+1 < b && b == c && c == d
      return [ [mati(a), mentu(b, c, d)] ]
    # 3338 => [ ["(333)", "[8]"] ]
    elsif a == b && b == c && c+1 < d
      return [ [mentu(a, b, c), mati(d)] ]
    # 2333 => [ ["[2]", "(333)"], ["[23]", "(33)"] ]
    elsif a+1 == b && b == c && c == d
      return [ [mati(a), mentu(b, c, d)], [mati(a, b), mentu(c, d)] ]
    # 3334 => [ ["(333)", "[4]"], ["(33)", "[34]"] ]
    elsif a == b && b == c && c+1 == d
      return [ [mentu(a, b, c), mati(d)], [mentu(a, b), mati(c, d)] ]
    # テンパってない
    else
      return false
    end
  end
 
  def mentu(i1=nil, i2=nil, i3=nil)
    return "(" + i1.to_s + i2.to_s + i3.to_s + ")"
  end
 
  def mati(i1=nil, i2=nil, i3=nil)
    return "[" + i1.to_s + i2.to_s + i3.to_s + "]"
  end
 
  # チートイツ判別
  def titoitu
    tenpai = []
    rest = []
    # 裸単騎待ちの牌を抜き出す
    i = nil
    (0...@len).each do |i|
      # @tehais[i]が2つ含まれなかったら、@tehais[i]がとりあえず裸単騎待ちの候補
      rest = @tehais.clone
      rest.delete_at(i)
      rest.sort!
      break unless rest.include?(@tehais[i])
    end
    tenpai.push(mati(@tehais[i]))
 
    # 裸単騎待ち候補以外が全部ペアならチートイツ聴牌、そうでないならチートイツ聴牌じゃない
    0.step(rest.length-1, 2) do |j|
      if rest[j] != rest[j+1]
        return false
      end
      tenpai.push(mentu(rest[j], rest[j+1]))
    end
 
    return sort_tenpai(tenpai).to_s
  end
 
  def sort_tenpai(arr)
    return arr.sort_by{|i| i[1..(i.length-1)]}
  end
 
  def clear_used
    # usedフラグをクリア
    (0...@len).each do |i|
      @used[i] = false
    end
  end
 
  def process_rest_hai(tenpai)
    if (rh = rest_hai) != false
      rest_hai.each do |rests|
        tenpai_tmp = tenpai.clone
        rests.each do |rest|
          tenpai_tmp.push(rest)
        end
        if tenpai_tmp.length == 5
          @answer.push(sort_tenpai(tenpai_tmp).to_s)
        end
      end
    end
  end
 
  def solve
    # チートイツ
    if (ti = titoitu) != false
      @answer.push(ti)
    end
 
    # 順子→刻子 の順で探索。面子が3個できたらbreak
    (0...@len).each do |i|
      tenpai =[]
      # make_shuntu
      hai_range = (i..@len-1).map + (0..i-1).map
      hai_range.each do |n|
        if (shuntu = make_shuntu(n)) != false 
          tenpai.push(shuntu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
      # make_koutu
      hai_range.each do |n|
        if (koutu = make_koutu(n)) != false 
          tenpai.push(koutu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
 
      clear_used
    end
 
    clear_used
 
    # 刻子→順子 の順で探索。面子が3個できたらbreak
    (0...@len).each do |i|
      tenpai =[]
      # make_koutu
      hai_range = (i..@len-1).map + (0..i-1).map
      hai_range.each do |n|
        if (koutu = make_koutu(n)) != false 
          tenpai.push(koutu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
      # make_shuntu
      hai_range.each do |n|
        if (shuntu = make_shuntu(n)) != false 
          tenpai.push(shuntu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
 
      clear_used
    end
 
    clear_used
 
    # 順子刻子と並行に調査。面子が3個できたらbreak
    (0...@len).each do |i|
      tenpai =[]
      hai_range = (i..@len-1).map + (0..i-1).map
      hai_range.each do |n|
        # make_shuntu
        if (shuntu = make_shuntu(n)) != false 
          tenpai.push(shuntu)
        end
        # make_koutu
        if (koutu = make_koutu(n)) != false 
          tenpai.push(koutu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
      clear_used
    end
 
    clear_used
 
    # 刻子順子と並行に調査。面子が3個できたらbreak
    (0...@len).each do |i|
      tenpai =[]
      hai_range = (i..@len-1).map + (0..i-1).map
      hai_range.each do |n|
        # make_koutu
        if (koutu = make_koutu(n)) != false 
          tenpai.push(koutu)
        end
        # make_shuntu
        if (shuntu = make_shuntu(n)) != false 
          tenpai.push(shuntu)
        end
        # rest
        if tenpai.length == 3
          process_rest_hai(tenpai)
          break
        end
      end
      clear_used
    end
 
    clear_used
 
    if (@answer.length > 0)
      return @answer.uniq
    else
      return "no answer"
    end
  end
 
end
 
# 手牌を13枚ランダムに配る
def random_tehai
  tehais = []
  hai_num = Hash.new(0)
  TEHAI.times do |i|
    hai = rand(9) + 1 
    hai_num[hai] += 1
    if (hai_num[hai] > LIMIT)
      while (true)
        hai = rand(9) + 1 
        hai_num[hai] += 1
        if (hai_num[hai] <= LIMIT)
          break
        end
      end
    end
    tehais.push(hai)
  end
  tehais.sort.to_s
end
 
def display_answer(tehai)
  puts "----- #{tehai} -----"
  arr = tehai.split(//).map{|i| i.to_i}
  majan = Majan.new(arr.sort)
  puts majan.solve
  puts
end
 
puts "■例題\n\n"
tehai = "1112224588899"
display_answer(tehai)
 
tehai = "1122335556799"
display_answer(tehai)
 
tehai = "1112223335559"
display_answer(tehai)
 
tehai = "1223344888999"
display_answer(tehai)
 
tehai = "1112345678999"
display_answer(tehai)
 
puts
puts "■チートイツ絡み\n\n"
# チートイツ聴牌かつ多面待ち
tehai = "3344556778899"
display_answer(tehai)
 
# チートイツ崩れノーテン
tehai = "2234456677899"
display_answer(tehai)
 
# チートイツ崩れだが聴牌
tehai = "2334456678899"
display_answer(tehai)
 
puts
puts "■ランダム手牌\n\n"
10.times do
  display_answer(random_tehai)
end

実行結果。
一応、けっこう速攻で答えが求まりました。

■例題
 
----- 1112224588899 -----
(111)(222)[45](888)(99)
 
----- 1122335556799 -----
(123)(123)(55)(567)[99]
(123)(123)[55](567)(99)
(123)(123)(555)[67](99)
 
----- 1112223335559 -----
(123)(123)(123)(555)[9]
(111)(222)(333)(555)[9]
 
----- 1223344888999 -----
(123)(234)[4](888)(999)
[1](234)(234)(888)(999)
(123)[23](44)(888)(999)
 
----- 1112345678999 -----
(11)(123)(456)(789)[99]
[11](123)(456)(789)(99)
(111)(234)(567)[8](999)
(111)[2](345)(678)(999)
(11)[12](345)(678)(999)
(11)(123)[45](678)(999)
(111)(234)[5](678)(999)
(11)(123)(456)[78](999)
(111)(234)(567)[89](99)
(111)[23](456)(789)(99)
(111)(234)[56](789)(99)
 
■チートイツ絡み
 
----- 3344556778899 -----
(33)(44)(55)[6](77)(88)(99)
(345)(345)(678)[78](99)
(345)(345)(678)(789)[9]
(345)[3](456)(789)(789)
(33)(456)[45](789)(789)
(345)(345)[6](789)(789)
 
----- 2234456677899 -----
no answer
 
----- 2334456678899 -----
(234)(345)(66)(789)[89]
 
■ランダム手牌
 
----- 1112244555689 -----
no answer
 
----- 2223356778899 -----
(222)(33)(567)(789)[89]
(222)(33)[56](789)(789)
 
----- 1222446667799 -----
no answer
 
----- 1112234567999 -----
(111)(234)[2](567)(999)
(11)[12](234)(567)(999)
(111)(22)(345)[67](999)
(111)(22)[34](567)(999)
 
----- 1112333446677 -----
no answer
 
----- 1123346677899 -----
no answer
 
----- 1222335558899 -----
no answer
 
----- 1222345567899 -----
no answer
 
----- 1233344455678 -----
(123)(345)(345)[4](678)
[1](234)(345)(345)(678)
[12](333)(444)(55)(678)
 
----- 1223344556678 -----
(123)(234)(456)[5](678)
(123)(234)(456)(567)[8]
(123)[2](345)(456)(678)

九蓮宝燈も解けてるっぽいので、まぁ良いかな・・・
アルゴリズム一切ググらずに解けたのはちょっと自信つきました。

• - 関連記事 -
• RubyでFizzBuzz問題を解いてみる
• Rubyでライフゲーム
• Rubyでエイトクイーン問題をバックトラック法で解く
• Rubyで迷路問題を解いた

• ブログ検索

• 更新情報/RSSフィード

# Ruby入門
• Rubyの基本 (14)
• オブジェクト・変数・定数 (2)
• 演算子 (3)
• 条件分岐 (3)
• 繰り返し (9)
• イテレータ (8)
• メソッド (2)
• クラス・モジュール (14)
• 例外・エラー処理 (3)
• Mix-in (2)
• コマンドラインオプション (7)
• Numericクラス（数値） (2)
• Arrayクラス（配列） (11)
• Hashクラス（ハッシュ） (5)
• Stringクラス（文字列） (5)
• Regexpクラス（正規表現） (5)
• IOクラス（入出力） (10)
• File/Dirクラス（ファイル・ディレクトリ） (10)
• Date/Timeクラス（日付・時間） (1)
• Thread/Mutexクラス（スレッド） (1)
• Ruby on Rails (8)
• Ruby tips (4)
• デザインパターン (3)
• アルゴリズム (5)
• 技術書を読む (7)

Copyright Worth Living All Rights Reserved.