「あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定」をやってみた
麻雀の「待ち」を出力する問題
http://headlines.yahoo.co.jp/hl?a=20100404-00000003-zdn_ep-sci の問題をやってみた。
制限時間は3時間とのことだけど、
- 作った(5時間)→考え方が間違っていて失敗
- 修正(2時間)→やっぱりダメ
- また作った(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]
最後のやつだけは合ってるのかわからない…。
プログラムの解説
その前に用語解説。適当に調べたもの。
- チンイツ:1種類の牌で役を完成すること。
- 順子(ジュンツ):同じ種類で連続する牌を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.