俺のスキルで飯は食えるか?
飯は食えてたが…いや、なんでもない。
次の記事があったので自分なりにコーディングしてみた。
あなたのスキルで飯は食えるか? 史上最大のコーディングスキル判定
Windows XP上のPyScripter 1.9.9.7 環境で作成し、Python 2.6.5上で動作確認した。
#------------------------------------------------------------------------------- # Name: Ready Hand Judgement # Purpose: To judge wheather a hand in mahjong is ready or not # # Author: Matthew # # Version: 0.1 # Created: 14/04/2010 # Copyright: (c) Matthew 2010 # Licence: GPL Ver. 3 #------------------------------------------------------------------------------- #!/usr/bin/env python import sys def homogeneous_product(list, n): if n == 0: return [[]] tuples = [] for i, x in enumerate(list): tuples.extend([[x] + l for l in homogeneous_product(list[i:], n - 1)]) return tuples # input a hand inputed_hand = raw_input('Input a hand: ') if len(inputed_hand) != 13: print 'You need to type 13 number characters.' exit() for c in inputed_hand: if ord(c) < 49 or 57 < ord(c): print 'You need to type number characters between 1 to 9.' exit() # inputed hand arrangement given_hand = [0, 0, 0, 0, 0, 0, 0, 0, 0] for i in inputed_hand: given_hand[int(i) - 1] += 1 # possible sequences reduction possible_sequences = [] possible_sequences += homogeneous_product([0, 1, 2, 3, 4, 5, 6], 0) possible_sequences += homogeneous_product([0, 1, 2, 3, 4, 5, 6], 1) possible_sequences += homogeneous_product([0, 1, 2, 3, 4, 5, 6], 2) possible_sequences += homogeneous_product([0, 1, 2, 3, 4, 5, 6], 3) possible_sequences += homogeneous_product([0, 1, 2, 3, 4, 5, 6], 4) # searching and judgement ready_hands = [] # head for i in range(-1, 9): heads = [] hand = list(given_hand) if i != -1: if hand[i] < 2: continue heads.append('(%1d%1d)'%(i + 1, i + 1)) hand[i] -= 2 # sequence hand_clone = list(hand) for j in possible_sequences: sequences = [] nominated_flag = True hand = list(hand_clone) for k in j: if hand[k] > 0 and hand[k + 1] > 0 and hand[k + 2] > 0: for l in range(3): hand[k + l] -= 1 sequences.append('(%1d%1d%1d)'%(k + 1, k + 2, k + 3)) else: nominated_flag = False break if not nominated_flag: continue # triplet triplets = [] for k in range(9): if hand[k] > 2: hand[k] -= 3 triplets.append('(%1d%1d%1d)'%(k + 1, k + 1, k + 1)) # judgement of waiting waitings = [] sum = 0 for k in hand: sum += k if sum < 3: # waiting for the only tile for a pair if sum < 2: for l in range(9): if hand[l] == 1: waitings.append('[%1d]'%(l + 1)) break # waiting for the middle in a sequence for l in range(7): if hand[l] == 1 and hand[l + 2] == 1: waitings.append('[%1d%1d]'%(l + 1, l + 3)) break # waiting for either of two gates and # waiting for three or seven the tile for l in range(8): if hand[l] == 1 and hand[l + 1] == 1: waitings.append('[%1d%1d]'%(l + 1, l + 2)) break # waiting for a triplet for l in range(9): if hand[l] == 2: waitings.append('[%1d%1d]'%(l + 1, l + 1)) break if not waitings: continue ready_hands.append(heads + sequences + triplets + waitings) # judgement of seven pairs heads = [] hand = list(given_hand) for i in range(9): if hand[i] > 1: heads.append('(%1d%1d)'%(i + 1, i + 1)) hand[i] -= 2 if len(heads) > 5: for i in range(9): if hand[i] == 1: ready_hands.append(heads + ['[%1d]'%(i + 1)]) break # show ready hands for i in ready_hands: for j in i: sys.stdout.write(j) sys.stdout.write('\n')
細かいことは気にしない(笑)。単純にアルゴリズムがどうあるべきかを問うているだけであるから、入出力部分は気にしない(笑)。怪しい英語も気にしない(笑)。
"possible sequences reduction"と書いているのに、順子の重複組合せ数を一つも削減できなかったのは自分のスキル不足を痛感させる。時間があればつくれそうではある。どことなく富豪感覚で作られているっぽい。こんなプログラムでは遅い気がする。
もっと賢く、メモリやプロセッサ時間を使わない方法があると思うが、模範解答を待ってみる。
上記のプログラムはLisp/SchemeやRuby、JavaScriptにも恐らく移植しやすいでしょう。Cで実装するには骨が折れそうな気がするが、簡単に実装できそうな気がする。
記事中に最短40分で実装を終えたとあるが、私の場合、Python環境を整えるのと、態々不慣れなPythonを選んだのとで、数時間かかってしまった(汗)。
バックトラックで実装すりゃ良かったなぁ。バックトラック版も書いてみよう。
参考:
- アルゴリズム
- Ruby1.9のCombinationとPermutationをPythonでも
- 重複組合せ計算のために、ソースの一部を利用させてもらいました。
- これってMathの中に入ってないのかな?
- Ruby1.9のCombinationとPermutationをPythonでも
- 麻雀英語