読者です 読者をやめる 読者になる 読者になる

Matthewの備忘録

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

lambda式利用版

 先日のバックトラック版をlambda式をつかって、アルゴリズム構造を関数化してみた。
 なんとなく、内部関数を再帰呼び出しのたびに定義するのってスタックと時間の無駄な気がする。もうちょっと詳しく調べておく必要があるな。

#-------------------------------------------------------------------------------
# Name:        Ready Hand Judgement
# Purpose:     To judge wheather a hand in mahjong is ready or not
#
# Author:      Matthew
#
# Version:     0.3
# Created:     19/04/2010
# Copyright:   (c) Matthew 2010
# Licence:     GPL Ver. 3
#-------------------------------------------------------------------------------
#!/usr/bin/env python

import sys
from datetime import datetime, date, time

def check_ready(hand):
    hand = sorted(list(hand))

    def _check_ready(comparison, waiting, removement):
        bfr = []
        for i in hand:
            j = int(i)
            if comparison(j, hand):
                if waiting(j) in bfr: continue
                rest = hand[:]
                rest.remove(i)
                removement(j, rest)
                search(rest, waiting(j), [])
                bfr.append(waiting(j))

    # waiting for the only tile for a pair
    comparison = lambda i, h: True
    waiting = lambda i: '[%1d]'%(i)
    removement = lambda i, r: True
    _check_ready(comparison, waiting, removement)

    # waiting for the middle in a sequence
    comparison = lambda i, h: str(i + 2) in h
    waiting = lambda i: '[%1d%1d]'%(i, i + 2)
    removement = lambda i, r: r.remove(str(i + 2))
    _check_ready(comparison, waiting, removement)

    # waiting for either of two gates and
    # waiting for three or seven the tile
    comparison = lambda i, h: str(i + 1) in h
    waiting = lambda i: '[%1d%1d]'%(i, i + 1)
    removement = lambda i, r: r.remove(str(i + 1))
    _check_ready(comparison, waiting, removement)

    # waiting for a triplet
    comparison = lambda i, h: h.count(str(i)) > 1
    waiting = lambda i: '[%1d%1d]'%(i, i)
    removement = lambda i, r: r.remove(str(i))
    _check_ready(comparison, waiting, removement)

def show_ready(elements, waiting):
    for i in elements:
        sys.stdout.write(i)
    sys.stdout.write(waiting)
    sys.stdout.write('\n')

def search(rest, waiting, elements):

    def _search(comparison, element, removement1, removement2):
        r, t = rest[:], rest[0]
        if comparison(r, t):
            elements.append(element(t))
            r.remove(t)
            removement1(r, t)
            removement2(r, t)
            search(r, waiting, elements)
            elements.pop()

    # show ready hands
    if not rest:
        if len(elements) == 4 or len(elements) == 6:
            show_ready(elements, waiting)
        return

    # head or pair(included in elements)
    comparison = lambda r, t: r.count(t) == 2
    element = lambda t: '(%1s%1s)'%(t, t)
    removement1 = lambda r, t: r.remove(t)
    removement2 = lambda r, t: True
    _search(comparison, element, removement1, removement2)

    # triplet
    comparison = lambda r, t: r.count(t) > 2
    element = lambda t: '(%1s%1s%1s)'%(t, t, t)
    removement1 = lambda r, t: r.remove(t)
    _search(comparison, element, removement1, removement1)

    # sequence
    comparison = lambda r, t: str(int(t) + 1) in r and str(int(t) + 2) in r
    element = lambda t: '(%1s%1s%1s)'%(t, str(int(t) + 1), str(int(t) + 2))
    removement1 = lambda r, t: r.remove(str(int(t) + 1))
    removement2 = lambda r, t: r.remove(str(int(t) + 2))
    _search(comparison, element, removement1, removement2)

# a kind of homogeneous product generator
def hp(list, counter, n):
    if n == 0: return [[]]
    tuples = []
    for i, x in enumerate(list):
        if counter[i] > 0:
            counter[i] -= 1
            tuples.extend([[x] + l for l in hp(list[i:], counter[i:], n - 1)])
    return tuples

def main():
    pass

if __name__ == '__main__':
    main()

check_ready('1112345678999')
exit()

### data coverage test
##print datetime.now()
##c = hp([1, 2, 3, 4, 5, 6, 7, 8, 9], [4, 4, 4, 4, 4, 4, 4, 4, 4], 13)
##for i in c:
##    check_ready("".join(map(str, i)))
##print datetime.now()