「あなたのスキルで飯は食えるか？ 史上最大のコーディングスキル判定」をやってみた

麻雀の「待ち」を出力する問題

http://headlines.yahoo.co.jp/hl?a=20100404-00000003-zdn_ep-sci の問題をやってみた。

制限時間は3時間とのことだけど、

1. 作った（5時間）→考え方が間違っていて失敗
2. 修正（2時間）→やっぱりダメ
3. また作った（3時間）→たぶん成功

と、全部で10時間くらいかかった。自分はプログラマに向いていないのかも知れない orz...

ソース

プログラムはRubyで作った。メインルーチンが1つとクラスが3つ、それぞれ別のソースに分けた。

chin_itsu.rb：

#!ruby

require 'te.rb'
require 'mentsu.rb'
require 'result.rb'

def main
  puts machi_of(ARGV[0]).join("\n")
end

# get machi of specified haipai string.
# ex. '1223344888999' -> ['(123)(234)(888)(999)[4]',
#       '(123)(44)(888)(999)[23]', '(234)(234)(888)(999)[1]']
#
def machi_of(str)
  te = Te.new(str)
  (tanki_machi(te) + hi_tanki_machi(te)).sort.uniq
end

# tanki_machi: find all te of tanki machi.
# ex. Te('1223344888999') ->
#       ['(123)(234)(888)(999)[4]', '(234)(234)(888)(999)[1]']
#
def tanki_machi(te)
  te.digits.inject(Result.new) { |result, tanki|
    find_all_mentsu(te.clone.exclude(tanki),
      Mentsu.new.include_machi(tanki), result) }.to_a
end

# find all mentsu combination in specified te.
#
def find_all_mentsu(te, mentsu, result)
  if result.include?(mentsu)
    result
  elsif te.empty?
    result.found(mentsu)
  else
    te.available_mentsu.inject(result) { |result, current_mentsu|
      find_all_mentsu(te.clone.exclude(current_mentsu),
        mentsu.clone.include(current_mentsu), result) }.not_found(mentsu)
  end
end

# hi_tanki_machi: find all mentsu combination in specified te without tanki.
# ex. Te('1223344888999') -> ['(123)(44)(888)(999)[23]']
#
def hi_tanki_machi(te)
  te.available_toitsu.inject(Result.new) { |result, current_toitsu|
    find_machi(te.clone.exclude(current_toitsu),
      Mentsu.new.include(current_toitsu), result) }.to_a
end

# find_machi: find all mentsu and machi in specified te.
#
def find_machi(te, mentsu, result)
  if result.include?(mentsu)
    result
  elsif te.part_of_mentsu?
    mentsu.include_machi(te.to_s)
    result.found(mentsu)
  else
    te.available_mentsu.inject(result) { |result, current_mentsu|
      find_machi(te.clone.exclude(current_mentsu),
        mentsu.clone.include(current_mentsu), result) }.not_found(mentsu)
  end
end

main

te.rb：

#!ruby

class Te
  def initialize(str)
    @te = str.split(//).sort.join
  end
  
  def empty?
    @te.empty?
  end
  
  def clone
    Te.new(@te.dup)
  end
  
  def to_s
    @te
  end
  
  def digits
    @te.split(//).sort.uniq
  end
  
  def exclude(mentsu)
    mentsu.split(//).each { |c| delete_first_found(c) }
    self
  end
  
  def delete_first_found(c)
    p = @te.index(c)
    @te[p] = '' if p
  end
  
  def available_mentsu
    available_kohtsu + available_juntsu
  end
  
  def available_kohtsu
    digits.map { |c| c * 3 }.select { |kohtsu| @te.include?(kohtsu) }
  end
  
  def available_juntsu
    digits.map { |c| c + c.next + c.next.next }.select { |juntsu|
      digits.join.include?(juntsu) }
  end
  
  def available_toitsu
    digits.map { |c| c * 2  }.select { |toitsu| @te.include?(toitsu) }
  end
  
  def part_of_mentsu?
    (@te.length == 2) and (part_of_kohtsu? or part_of_juntsu?)
  end
  
  def part_of_kohtsu?
    @te[0] == @te[1]
  end
  
  def part_of_juntsu?
    (@te[0].next == @te[1]) or (@te[0].next.next == @te[1])
  end
end

mentsu.rb：

#!ruby

class Mentsu
  def initialize(init = [])
    @mentsu = init
  end
  
  def clone
    Mentsu.new(@mentsu.dup)
  end
  
  def include(mentsu)
    @mentsu << "(#{mentsu})"
    self
  end
  
  def include_machi(mentsu)
    @mentsu << "[#{mentsu}]"
    self
  end
  
  def to_s
    @mentsu.sort.join
  end
end

result.rb：

#!ruby

class Result
  def initialize
    @result = Hash.new
  end
  
  def include?(mentsu)
    @result.include?(mentsu.to_s)
  end
  
  def found(mentsu)
    @result[mentsu.to_s] = true
    self
  end
  
  def not_found(mentsu)
    @result[mentsu.to_s] = false
    self
  end
  
  def to_a
    @result.keys.select { |key| @result[key] }
  end
end

実行結果

上記のページに出力例として書いてあったものをやってみた。

> ruby chin_itsu.rb 1112224588899
(111)(222)(888)(99)[45]

> ruby chin_itsu.rb 1122335556799
(123)(123)(55)(567)[99]
(123)(123)(555)(99)[67]
(123)(123)(567)(99)[55]

> ruby chin_itsu.rb 1112223335559
(111)(222)(333)(555)[9]
(123)(123)(123)(555)[9]

> ruby chin_itsu.rb 1223344888999
(123)(234)(888)(999)[4]
(123)(44)(888)(999)[23]
(234)(234)(888)(999)[1]

> ruby chin_itsu.rb 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]

最後のやつだけは合ってるのかわからない…。

プログラムの解説

その前に用語解説。適当に調べたもの。

• チンイツ：１種類の牌で役を完成すること。
• 順子（ジュンツ）：同じ種類で連続する牌を3つ並べたもの。1,2,3など。
• 刻子（コーツ）：同じ牌を3つ並べたもの。1,1,1など。
• 対子（トイツ）：同じ牌を2つ並べたもの。1,1など。
• 単騎：アタマ以外はすべて揃い、アタマの片方を待っている状態。
• 順子、刻子などを合わせて面子（メンツ）という。基本的には4つの面子と1つの対子で役が完成する。

私は麻雀をやらないので、正しい言葉を使っていないかも知れません。

chin_itsu.rb

machi_of(str)：文字列を渡すと、面子＋待ちを文字列の配列で返す。結果は単騎待ち＋非単騎待ちの処理結果を足したもの。

tanki_machi(te)：手札で作れる単騎待ちを返す。手札に含まれる数字を1つずつ単騎の頭とみなし、手札からそれを除いたものがすべて面子に分解できるかどうかを調べる。分解できれば単騎待ちになる。

find_all_mentsu(te, mentsu, result)：手札を面子に分解しながら再帰し、すべて分解できるかどうかを調べる。すでに調べた手（resultに含まれるもの）は調べない。分解された面子はmentsu、残った手札はteに格納される。結果はresultに格納される。

hi_tanki_machi(te)：手札で作れる非単騎待ちを返す。手札に含まれる対子を頭とみなし、手札からそれを除いたものを面子に分解する。分解後、残ったものが面子の部分（あと1つで面子になる）かどうかを調べる。部分なら、それが待ちになる。

find_machi(te, mentsu, result)：手札を面子に分解しながら再帰し、残ったものが面子の部分かどうかを調べる。すでに調べた手（resultに含まれるもの）は調べない。分解された面子はmentsu、残った手札はteに格納される。結果はresultに格納される。

te.rb

手札を表すクラスTeを定義している。

initialize(str)：コンストラクタ。与えられた文字列を初期値として、数字の昇順に並べ替えて内部に格納する。

empty?：手札が無い場合にtrueを返す。

clone：同じ手札を持つ新しいオブジェクトを作成して返す。

to_s：手札を文字列形式で返す。

digits：手札に含まれる数字を重複なしで返す。

exclude(mentsu)：手札から指定された面子を除外（削除）する。自分自身を返す。

delete_first_found(c)：手札に最初に現れる文字cを削除する。excludeから使われる。

available_mentsu：手札から取り得る面子を配列で返す。面子＝刻子＋順子。

available_kohtsu：手札から取り得る刻子を配列で返す。

available_juntsu：手札から取り得る順子を配列で返す。

available_toitsu：手札から取り得る対子を配列で返す。

part_of_mentsu?：手札が面子の部分（あと1つで面子になる）かどうかを返す。

part_of_kohtsu?：手札が刻子の部分かどうかを返す。

part_of_juntsu?：手札が順子の部分かどうかを返す。

mentsu.rb

手札を分解した面子を表すクラスMentsuを定義している。

initialize(init = )：コンストラクタ。与えられた配列を初期値として内部に格納する。

clone：同じ面子を持つ新しいオブジェクトを作成して返す。

include(mentsu)：面子を非待ちとして追加する。“()”でくくられて追加される。自分自身を返す。

include_machi(mentsu)：面子を待ちとして追加する。“”でくくられて追加される。自分自身を返す。

to_s：面子を文字列として返す。

result.rb

結果を格納するクラスResultを定義している。Resultには面子と、それが面子＋待ちになっているかどうかを格納する。

initialize：コンストラクタ。内部ハッシュを初期化している。

include?(mentsu)：与えられた面子が記録されているかを返す。

found(mentsu)：与えられた面子が面子＋待ちに分解できるとして記録する。自分自身を返す。

not_found(mentsu)：与えられた面子が面子＋待ちに分解できないとして記録する。自分自身を返す。

to_a：記録されている面子の組み合わせのうち、面子＋待ちに分解できるもののみを配列として返す。

＜追記＞

この記事をアップしてからググったら、みんなエレガントな解き方で短いコードになっていて素晴らしかった。自分の頭が悪いのがよくわかった orz. orz.