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

前回の続き。前回は他人のコードを一切参考にせずに書いて、試行錯誤してようやく出来上がった。見直してみると無駄が多い。

• ループ回数は節約したと言っても、常に2100回も繰り返されてしまう。どんな単純な「待ち」であっても。
• 問題は、手牌の状態に関係なく、1から9までの対子・順子・刻子をチェックしているところ。本来は手牌に無ければ、チェックの必要がないのに。

• 自分がテンパイを認識する時は、頭・刻子・順子を、手牌の先頭から順に当てはめて、可能な限りの組み合わせを探していると思う。
• 手牌に存在しない組み合わせは、当たり前だが全くチェックしていない。
• 自分の思考と同じ仕組みでチェックすれば良いのだが、それをコードとしてどうやって実現すれば良いのか、結構悩ましい。
• すでに多数の、麻雀の「待ち」を出力するプログラム、が発表されているので、そこからヒントを探すことにした。
  • http://b.hatena.ne.jp/entry/www.itmedia.co.jp/enterprise/articles/1004/03/news002.html

• いろいろ見てみると、やはり再帰を利用した方法が、コードも短くなり、ループ（再帰呼び出し）回数も少なくなって良さそう。
• 参考にしたのは以下のページ。（感謝です！）
  • 史上最大のコーディングスキル判定 - yuyarinの日記

再帰を利用して書いてみた。

• • • 以下コード中の半角￥は、半角＼に置き換える必要あり。

class Tehai
  def initialize(input)
    @in_text = input
    @outs = []
    @count = 0
  end
  
  # 対子を取り出す
  def toitsu(n, s, rest, pick)
    new_rest = rest.sub(/#{s}#{s}/, '')
    chitoitsu(n, new_rest, pick + ["(#{$&})"]) if $&
  end
  
  # 頭を取り出す
  def atama(n, s, rest, pick, head)
    new_rest = rest.sub(/#{s}#{s}/, '')
    generals(n, new_rest, pick + ["(#{$&})"], true) if $&
  end
  
  # 刻子を取り出す
  def koutsu(n, s, rest, pick, head)
    new_rest = rest.sub(/#{s}#{s}#{s}/, '')
    generals(n, new_rest, pick + ["(#{$&})"], head) if $&
  end
  
  # 順子を取り出す
  def juntsu(n, s, rest, pick, head)
    new_rest = rest.sub(/#{s}#{s+1}(#{s+1}*)#{s+2}/,'\1')
    generals(n, new_rest, pick + ["(#{s}#{s+1}#{s+2})"], head) if $&
  end
  
  # テンパイしているかどうか？
  def tenpai?(rest)
    case rest.size
    when 1
      true
    when 2
      d = rest[1] - rest[0]
      true if d <= 2
    end
  end
  
  # 待ちを出力する
  def machi
    generals(0, @in_text, [], false)
    chitoitsu(0, @in_text, [])
    p @in_text
    puts @outs.uniq, "ループ回数: " + @count.to_s, ''
  end
  
  # 一般的なテンパイを検索
  def generals(n, rest, pick, head)
    @count += 1
    if tenpai?(rest)
      @outs << (pick.sort << "[#{rest}]").to_s
    else
      s = rest[n, 1].to_i
      atama(n, s, rest, pick, head) unless head
      koutsu(n, s, rest, pick, head)
      juntsu(n, s, rest, pick, head)
      while rest[n, 1] == rest[n+1, 1]; n += 1; end
      generals(n+1, rest, pick, head) if n < 2
    end
  end
  
  # 七対子のテンパイを検索
  def chitoitsu(n, rest, pick)
    @count += 1
    if tenpai?(rest)
      @outs << (pick.sort << "[#{rest}]").to_s
    else
      s = rest[n, 1]
      toitsu(n, s, rest, pick)
      while rest[n, 1] == rest[n+1, 1]; n += 1; end
      chitoitsu(n+1, rest, pick) if n < 1
    end
  end
end

# テスト
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 # ノベタン

実行してみる

$ ruby ~/Desktop/marjon.rb
"1112224588899"
(111)(222)(888)(99)[45]
ループ回数: 19

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

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

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

"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]
ループ回数: 75

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

"1122334455667"
(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]
(11)(22)(33)(44)(55)(66)[7]
ループ回数: 56

"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]
ループ回数: 85

"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]
ループ回数: 81

• ループ回数は劇的に減った！

• でも、七対子を検索するために、似たような処理を繰り返しているのは無駄なところ。
• 頭・対子・順子・刻子を照合を、メソッドに分ける必要もなさそうな気がしてきた...。
• メソッドに渡す引数ばかり増えて、かえって分かり難い気がする。

以上の対策を考えて、修正してみた。

• • • 以下コード中の半角￥は、半角＼に置き換える必要あり。

class Tehai
  def initialize(input)
    @in_text = input
    @outs = []
    @count = 0
  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 machi
    generals(0, @in_text, [], 0)
    p @in_text
    puts @outs.uniq, "ループ回数: " + @count.to_s, ''
  end
  
  # 一般的なテンパイを検索
  def generals(n, rest, pick, head)
    @count += 1
    if tenpai?(rest, head)
      @outs << (pick.sort << "[#{rest}]").to_s
    else
      s = rest[n, 1].to_i
      new_rest = rest.sub(/#{s}#{s}/, '')                   # 対子
      generals(n, new_rest, pick + ["(#{$&})"], head+1) if $&
      new_rest = rest.sub(/#{s}#{s}#{s}/, '')               # 刻子
      generals(n, new_rest, pick + ["(#{$&})"], head)   if $&
      new_rest = rest.sub(/#{s}#{s+1}(#{s+1}*)#{s+2}/,'\1') # 順子
      generals(n, new_rest, pick + ["(#{s}#{s+1}#{s+2})"], head) if $&
      while !rest[n, 1].nil? && rest[n, 1] == rest[n+1, 1]; n += 1; end
      generals(n+1, rest, pick, head) if n < 2
    end
  end
end

# テスト
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 # ノベタン

実行してみる。

$ ruby /Users/bebe/Desktop/marjon6.rb 
"1112224588899"
(111)(222)(888)(99)[45]
ループ回数: 17

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

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

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

"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]
ループ回数: 81

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

"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]
ループ回数: 122

"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]
ループ回数: 184

"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]
ループ回数: 155

• コードは短くなり、かなり凝縮された。
• その分、所々に条件判定が増えて、見通しは悪くなった。
• ループ回数は少し増えた。

所感

• 自分にとって、再帰呼び出しは難解だ。コードの見通しが悪くなる。
• 分かり易さでは、最初の2100回ループするコードが一番読み易かった。

• それにしても、実に様々な発想のコードがあるものだ。
  • http://b.hatena.ne.jp/entry/www.itmedia.co.jp/enterprise/articles/1004/03/news002.html
• 中には、たった300バイトのワンライナーで実現してしまうコードもあった。すごい！

x=256,y=65793;char*t,s[99];f(i,p,j,k){int*m=t=s+x+(k=i%x),*q=s+p;s[p-1]=41,j=i/x-3,i>768?!j&*t>21-p|j>0&p>19&*t&t[j]?*q=91+k*y-k+j*x,s[23]=93,puts(s+1):0:*m-(j=i<x?y:1-j)&y*8||(*m-=j,*q=40+k*y*x+(i<x)*258*x,f(i>>9?768:i,p+5-i/512),*m+=j);i-x*6&&f(i+1,p);}main(){for(t=gets(s);*t;s[x+*t++]++);f(0,1);}

kusano_prog

• コンパイルして、実行してみた。

$ gcc -m32 ~/Desktop/marjon.c
~/Desktop/marjon.c:1: warning: data definition has no type or storage class
~/Desktop/marjon.c: In function ‘f’:
~/Desktop/marjon.c:1: warning: initialization from incompatible pointer type
~/Desktop/marjon.c:1: warning: initialization from incompatible pointer type
~/Desktop/marjon.c: In function ‘main’:
~/Desktop/marjon.c:1: warning: assignment makes pointer from integer without a cast

$ ./a.out
warning: this program uses gets(), which is unsafe.
1112345678999
(321)(654)(987)(11)[99]
(321)(654)(987)(99)[11]
(321)(654)(999)(11)[87]
(321)(876)(999)(11)[54]
(432)(765)(111)(999)[8]
(432)(765)(111)(99)[98]
(432)(876)(111)(999)[5]
(432)(987)(111)(99)[65]
(543)(876)(111)(999)[2]
(543)(876)(999)(11)[21]
(654)(987)(111)(99)[32]

• いろいろ警告されるけど、ちゃんと待ち判定してくれた。すごい！

• • • さらに次回に続く