Matthewの備忘録

忘れたときはここを見ろ。何か書いてある。

俺のスキルで飯は食えるか？

　飯は食えてたが…いや、なんでもない。
　次の記事があったので自分なりにコーディングしてみた。
あなたのスキルで飯は食えるか？　史上最大のコーディングスキル判定
　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で実装するには骨が折れそうな気がするが、簡単に実装できそうな気がする。
　記事中に最短４０分で実装を終えたとあるが、私の場合、Python環境を整えるのと、態々不慣れなPythonを選んだのとで、数時間かかってしまった（汗）。
　バックトラックで実装すりゃ良かったなぁ。バックトラック版も書いてみよう。

参考：