mahjong.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
#
# Ruby 1.9以降必須。Array#combinationとか便利だし
# Ken Nishimura 2010/4/5
#
# (方針）
#
# 単騎待ちとそれ以外を分けて考える。再帰で3つずつ区切って幅優先探索。順
# 子、コーツ以外はその場で探索打ち切り。もう少し重複を刈り取れるけど、
# これで十分速い。完成してから改めて考えてみたら、単騎待ちとそれ以外で
# 分けるより、(...)(...)(...)[....]とパイを分けてから、最後に残った4枚
# で場合分けするほうがコードがすっきりしそう。

$machi = []         # 両面やシャンポン待ち
$tanki_machi = []   # 単騎待ち

# $visitedに探索済みの状態を入れていって無駄な探索を削るために、
# (123)(234) と (234)(123)を同一視しようとか思ったけど、すでに十分速い

# $visited = {}

class Array
 def delete_a_pie(n)
   self.delete_at(self.index(n))
 end
end

def kotsu?(pies)
 pies.uniq.size == 1
end

def shuntsu?(pies)
 pies[2] - pies[1] == 1 && pies[1] - pies[0] == 1
end

def set?(pies)
 kotsu?(pies) || shuntsu?(pies)
end

# 頭を除外して3枚セットでピックアップしていく。
# 幅優先探索だけど、順子、コーツになってない枝はそこでストップ
# 残った2枚が待ちの状態であれば、それが正解の1つ

def pick3(rest, picked, head)
 rest.combination(3).to_a.uniq.each do |pies|
  next unless set?(pies)   # 順子、コーツ以外の枝は全部無視
# if $visited? then next else $visited <- (this state)
  new_rest = rest.dup
  new_picked = picked.dup
  pies.each{|n| new_rest.delete_a_pie(n)}
  new_picked << pies

  if new_rest.size == 2 &&    # 残り2枚が待ちとして成立しているか
        (new_rest[0] == new_rest[1] || new_rest[1] - new_rest[0] == 1 ||
        new_rest[1] - new_rest[0] == 2) then
    $machi << [head, new_picked.sort, new_rest]
  else
    pick3(new_rest, new_picked, head)
  end
 end
end

# 単騎待ちのケースを探る。3枚セットでピックアップしていき、
# 最後に1枚残るか調べる。

def pick3_tanki(rest, picked)
 rest.combination(3).to_a.uniq.each do |pies|
  next unless set?(pies)
# if $visited? then next else $visited <- (this state)
  new_rest = rest.dup
  new_picked = picked.dup
  pies.each{|n| new_rest.delete_a_pie(n)}
  new_picked << pies

  if new_rest.size == 1 then
    $tanki_machi << [new_picked.sort, new_rest]
  else
    pick3_tanki(new_rest, new_picked)
  end
 end
end

# main

# コマンドラインから引数でパイの状態を受け取る。
pie = ARGV[0].to_s.split(//).map{|i|i.to_i}.sort

# 単騎待ちを調べる
full = pie.dup
pick3_tanki(full, [])

# 1から9について頭となることを仮定してシャンポンと両面待ちを調べる
(1..9).each do |n|
 if (pie - [n]).size <= 11 then # nは頭になれる（2枚以上ある）か？
  new_pie = pie.dup
  2.times {new_pie.delete_a_pie(n)}
  pick3(new_pie, [], [n, n])
 end
end

# それぞれ適当にフォーマットして出力。汚いけど。
# ここで(111)(222)[33]と(222)(111)[33]はuniqを取ってる。これは
# 探索のときに刈り取るのもありだけど速度的にはこれで十分だし、
# 富豪バンザイ的な感じで
$machi.uniq.each do |m|
 print "(" + m[0].join + ")"
 print m[1].map{|pie| "(" + pie.join + ")"}.join
 print "[" + m[2].join + "]"
 print "\n"
end

$tanki_machi.uniq.each do |m|
 print m[0].map{|pie| "(" + pie.join + ")"}.join
 print "[" + m[1].join + "]"
 print "\n"
end

# 1:30経過、とりあえずできた
# bugってる。なおした +10
# たんきまち対応しないと
# ムスメが昼寝から起きた(中断）
# たんき対応した +5
# たんきバグってたの直した +5
# と思ったら今度は両面待ちが出なくなった。
# バグなおした +5
# 完成 約2時間(途中に中断あり）

実行例：
% ruby mahjong.rb 1123451867999   チューレン、入力はソートしてなくてもOK
(11)(123)(456)(789)[99]
(11)(123)(456)(999)[78]
(11)(123)(678)(999)[45]
(11)(345)(678)(999)[12]
(99)(111)(234)(567)[89]
(99)(111)(234)(789)[56]
(99)(111)(456)(789)[23]
(99)(123)(456)(789)[11]
(111)(234)(567)(999)[8]
(111)(234)(678)(999)[5]
(111)(345)(678)(999)[2]
% ruby mahjong.rb 1223344888999
(44)(123)(888)(999)[23]
(123)(234)(888)(999)[4]
(234)(234)(888)(999)[1]
% ruby mahjong.rb 1112223335559
(111)(222)(333)(555)[9]
(123)(123)(123)(555)[9]
% ruby mahjong.rb 1112224588899
(99)(111)(222)(888)[45]
% ./mahjong.rb 1122334455667
(11)(234)(234)(567)[56]
(11)(234)(456)(567)[23]
(44)(123)(123)(567)[56]
(123)(123)(456)(456)[7]
(123)(123)(456)(567)[4]
(123)(234)(456)(567)[1]