麻雀の「待ち」を出力する その3

雑記 Ruby

さらに前回の続き。

  • メソッドを再帰呼び出しすることで、ループ（再帰呼び出し）回数はかなり節約できた。
  • しかし、puts @outs.uniqに頼っている現状では、まだ無駄な検索をしていることになる。
  • 順序違いの組み合わせは、最初から無視すれば、一石二鳥だ。
    • 無駄なループ処理を節約できる。
    • 重複を取り除く処理も不要になる。
  • uniqで誤摩化すということは、自分で書いたコードのアルゴリズムを読み切れていない証拠だ。
  • 処理の流れを徹底的に理解して、無駄な処理を排除してみる。
class Tehai
  def initialize(input)
    @in_text = input
    @outs = []
    @count = 0
  end
  
  # 対子を取り出す
  def toitsu(loc, n, rest, pick, head)
    new_rest = rest.sub(/#{n}#{n}/, '')
    generals(loc, new_rest, pick + ["(#{$&})"], head+1) if $&
  end
  
  # 刻子を取り出す
  def koutsu(loc, n, rest, pick, head)
    new_rest = rest.sub(/#{n}#{n}#{n}/, '')
    generals(loc, new_rest, pick + ["(#{$&})"], head) if $&
  end
  
  # 順子を取り出す
  def juntsu(loc, n, rest, pick, head)
    new_rest = rest.sub(/#{n}#{n+1}(#{n+1}*)#{n+2}/,'\1')
    generals(loc, new_rest, pick + ["(#{n}#{n+1}#{n+2})"], head, rest[loc]!=new_rest[loc]) if $&
  end
  
  # テンパイしているかどうか？
  def tenpai?(rest, head)
    case rest.size
    when 1
      true if head == 0 || head == 6
    when 2
      d = rest[1] - rest[0]
      true if head == 1 && d <= 2
    end
  end
  
  # 次に注目する牌の位置を返す
  def next_loc(loc, rest)
    while !rest[loc, 1].nil? && rest[loc, 1] == rest[loc+1, 1]
      loc += 1
    end
    loc + 1
  end
  
  # 待ちを出力する
  def machi
    generals
    p @in_text
    puts @outs, "ループ回数: " + @count.to_s, ''
  end
  
  # 一般的なテンパイを検索（七対子含む）
  def generals(loc=0, rest=@in_text, pick=[], head=0, first_check=true)
    @count += 1
    if tenpai?(rest, head)
      @outs << (pick << "[#{rest}]").to_s
    else
      n = rest[loc, 1].to_i
      toitsu(loc, n, rest, pick, head) if first_check
      koutsu(loc, n, rest, pick, head) if first_check && head < 2
      juntsu(loc, n, rest, pick, head) if                head < 2
      loc = next_loc(loc, rest)
      generals(loc, rest, pick, head) if (head < 2 && loc <= 2) || (head >= 2 && loc <= 1)
    end
  end
end

# テスト
require 'benchmark'
Benchmark.bm do |x|
x.report {
Tehai.new('1112224588899').machi
Tehai.new('1122335556799').machi
Tehai.new('1112223335559').machi
Tehai.new('1223344888999').machi
Tehai.new('1112345678999').machi # 九蓮宝燈
Tehai.new('1112223334699').machi # 嵌張待ち（[46]）
Tehai.new('1122334455667').machi # 七対子
Tehai.new('1112223334445').machi # 多面待ち
Tehai.new('1112223334567').machi # ノベタン
Tehai.new('1111234566669').machi # 検索順序
}
end
  • if first_check
    • 例：1112344666999に対しての重複を排除する。
      • 対子・順子の検索のみ実行する。(11)(123)(44)(666)(999)
      • 順子・対子の検索は実行しない。(123)(11)(44)(666)(999)
    • 但し、一律に順子→対子の検索順序を無視してしまうと、例：(123)(33)(44)(666)(999) のパターンが認識できなくなる。
    • そこで、juntsuメソッドから再帰呼び出しする時に、rest[loc]!=new_rest[loc] の真偽値を付加して、first_checkで利用している。
    • 順子の先頭数字と、取り出して残った牌の先頭数字が、違っていればtrue。同じならfalse。
    • これで、(123)(11)のパターンは無視され、(123)(33)のパターンは有効になった。
    • 同様に、刻子・順子と、順子・刻子の順序違いも考慮する。
      • 有効：(111)(123)(456)(666)(9)
      • 無視：(123)(111)(456)(666)(9)
  • if head < 2
    • 刻子・順子が存在する場合、頭の対子が2つ以上はあり得ないのだ。
  • if (head < 2 && loc <= 2) || (head >= 2 && loc <= 1)
    • 一般役と七対子の場合に分けて、再帰呼び出しを続けるかどうかを判定する。
    • 一般役なら2牌以上の保留はあり得ないのだ。(head < 2 && loc <= 2)
    • 七対子なら1牌以上の保留はあり得ないのだ。(head >= 2 && loc <= 1)

実行してみた。

$ ruby /Users/bebe/Desktop/mahjong/marjon.rb 
      user     system      total        real
"1112224588899"
(111)(222)(888)(99)[45]
ループ回数: 16

"1122335556799"
(123)(123)(55)(567)[99]
(123)(123)(555)(99)[67]
(123)(123)(567)(99)[55]
ループ回数: 28

"1112223335559"
(111)(222)(333)(555)[9]
(123)(123)(123)(555)[9]
ループ回数: 50

"1223344888999"
(123)(234)(888)(999)[4]
(123)(44)(888)(999)[23]
(234)(234)(888)(999)[1]
ループ回数: 35

"1112345678999"
(11)(123)(456)(789)[99]
(11)(123)(456)(999)[78]
(11)(123)(678)(999)[45]
(11)(345)(678)(999)[12]
(111)(234)(567)(99)[89]
(111)(234)(567)(999)[8]
(111)(234)(678)(999)[5]
(111)(234)(789)(99)[56]
(111)(345)(678)(999)[2]
(111)(456)(789)(99)[23]
(123)(456)(789)(99)[11]
ループ回数: 65

"1112223334699"
(111)(222)(333)(99)[46]
(123)(123)(123)(99)[46]
ループ回数: 55

"1122334455667"
(11)(22)(33)(44)(55)(66)[7]
(11)(234)(234)(567)[56]
(11)(234)(456)(567)[23]
(123)(123)(44)(567)[56]
(123)(123)(456)(456)[7]
(123)(123)(456)(567)[4]
(123)(234)(456)(567)[1]
ループ回数: 76

"1112223334445"
(11)(123)(234)(234)[45]
(11)(123)(234)(345)[24]
(11)(234)(234)(345)[12]
(111)(22)(234)(345)[34]
(111)(222)(33)(345)[44]
(111)(222)(33)(444)[35]
(111)(222)(333)(44)[45]
(111)(222)(333)(444)[5]
(111)(222)(345)(44)[33]
(111)(234)(234)(234)[5]
(111)(234)(234)(345)[2]
(123)(123)(123)(44)[45]
(123)(123)(123)(444)[5]
(123)(123)(345)(44)[12]
ループ回数: 89

"1112223334567"
(11)(123)(234)(567)[23]
(111)(22)(234)(567)[33]
(111)(22)(333)(567)[24]
(111)(222)(33)(345)[67]
(111)(222)(33)(567)[34]
(111)(222)(333)(456)[7]
(111)(222)(333)(567)[4]
(111)(234)(33)(567)[22]
(123)(123)(123)(456)[7]
(123)(123)(123)(567)[4]
(123)(123)(234)(567)[1]
ループ回数: 76

"1111234566669"
(111)(123)(456)(666)[9]
ループ回数: 37

  0.020000   0.000000   0.020000 (  0.021025)

七対子を含めた判定を一つのメソッドで処理しても、ループ回数はほとんど増えていない！sortやuniqの処理も不要になった！