Mahjong Waits Algorithm

group.py

class Group(object):
    pass


class Sequence(Group):
    def __init__(self, suit, starting_rank):
        self.suit = suit
        self.starting_rank = starting_rank


class Triplet(Group):
    def __init__(self, suit, rank):
        self.suit = suit
        self.rank = rank


class NoGroup(object):
    def value(self):
        return None

    def __add__(self, rhs):
        return self

    def append_group(self, group):
        return self


class Groups(list, NoGroup):
    def __init__(self, value=None):
        list.__init__(self, value or [])

    def value(self):
        return self

    def __add__(self, rhs):
        if type(rhs) is NoGroup:
            return NoGroup()
        return Groups(list.__add__(self, rhs))

    def append_group(self, group):
        self.append(group)
        return self

tile.py

class Tile(object):
    def __init__(self, suit, rank):
        self.suit = suit
        self.rank = rank

    def __eq__(self, rhs):
        return self.suit == rhs.suit and self.rank == rhs.rank

    def __hash__(self):
        return hash(self.suit) * hash(self.rank)

    def __repr__(self):
        return (self.suit, self.rank + 1).__repr__()


class TilesSuite(object):
    def __init__(self, count, suit):
        self.rank_count = [0] * count
        self.suit = suit

    def count(self, rank):
        return self.rank_count[rank]

    def add_rank(self, rank):
        self.rank_count[rank] += 1

    def copy_rank(self):
        return self.rank_count[:]

    def list_tiles(self):
        return [(Tile(self.suit, i), e)
                for i, e in enumerate(self.rank_count) if e != 0]

    def total(self):
        return sum(self.rank_count)

WIND_SUIT = 3
DRAGON_SUIT = 4


class HandTiles(object):
    def __init__(self):
        self.numerics = [TilesSuite(9, i) for i in xrange(3)]
        self.wind = TilesSuite(4, WIND_SUIT)
        self.dragon = TilesSuite(3, DRAGON_SUIT)

    def total(self):
        return (sum([self.numerics[i].total() for i in xrange(3)]) +
                self.wind.total() + self.dragon.total())

    def list_tiles(self):
        return (sum([self.numerics[i].list_tiles() for i in xrange(3)], []) +
                self.wind.list_tiles() + self.dragon.list_tiles())

waits.py

import tile
import group


def waits(tiles):
    return set(_waits_13(tiles) + _waits_7pairs(tiles) + _waits_4groups(tiles))

_13_ORPHANS_WAITS = (
    [tile.Tile(0, 0), tile.Tile(0, 8), tile.Tile(1, 0), tile.Tile(1, 8),
     tile.Tile(2, 0), tile.Tile(2, 8)] +
    [tile.Tile(tile.WIND_SUIT, i) for i in xrange(4)] +
    [tile.Tile(tile.DRAGON_SUIT, i) for i in xrange(3)])


def _waits_13(tiles):
    if tiles.total() != 13:
        return []
    orphans = sorted(
        [(tile.Tile(s, 0), s.count(0)) for s in tiles.numerics] +
        [(tile.Tile(s, 8), s.count(8)) for s in tiles.numerics] +
        [(tile.Tile(tile.WIND_SUIT, i), tiles.wind.count(i))
         for i in xrange(4)] +
        [(tile.Tile(tile.DRAGON_SUIT, i), tiles.dragon.count(i))
         for i in xrange(3)], key=lambda k: k[1])
    if orphans[1][1] == 0:
        return []
    if orphans[0][1] == 1:
        return _13_ORPHANS_WAITS
    return [orphans[0][0]]


def _waits_7pairs(tiles):
    if tiles.total() != 13:
        return []
    tiles_list = tiles.list_tiles()
    # NOTE: Japanese Mahjong doesn't allow two same pairs in 7-pairs
    #       in that case the predicate should be
    #  7 != len(tiles_list)
    if 7 < len(tiles_list):
        return []
    odds = [t[0] for t in tiles_list if t[1] % 2 == 1]
    return odds if len(odds) == 1 else []


def _waits_4groups(tiles):
    triplets, pairs, singles = _wind_dragon_groups(tiles)
    if pairs and singles:
        return []
    if 1 == len(singles):
        groups = _detect_completed_numeric_groups(tiles)
        return [] if groups is None else [singles[0][0]]
    if 2 == len(pairs):
        groups = _detect_completed_numeric_groups(tiles)
        return [] if groups is None else [pairs[0][0], pairs[1][0]]
    if 1 == len(pairs):
        waits, pair_wait = _detect_numeric_suit_with_two_more(tiles)
        if len(waits) == 0:
            return []
        if pair_wait:
            waits.append(pairs[0][0])
        return waits
    return (_detect_numeric_suit_with_one_more(tiles) +
            _detect_2_numeric_suits_with_2_more(tiles))


def _wind_dragon_groups(tiles):
    tiles_list = tiles.wind.list_tiles() + tiles.dragon.list_tiles()
    if len(tiles_list) == 0:
        return [], [], []
    singles = [t for t in tiles_list if t[1] == 1]
    pairs = [t for t in tiles_list if t[1] == 2]
    triplets = [t for t in tiles_list if t[1] == 3]
    quads = [t for t in tiles_list if t[1] == 4]
    return triplets + quads, pairs, singles + quads


def _detect_completed_numeric_groups(tiles):
    for i in xrange(3):
        if tiles.numerics[i].total() % 3 != 0:
            return None
    return sum([_completed_numeric_groups(i, tiles.numerics[i].copy_rank())
                for i in xrange(3)], group.Groups()).value()


def _detect_numeric_suit_with_one_more(tiles):
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 1 or mod_numerics[1][1] != 0:
        return []
    suit_one_more = mod_numerics[0][0]
    group_suit_a, group_suit_b = mod_numerics[1][0], mod_numerics[2][0]
    completed_groups = (
        _completed_numeric_groups(
            group_suit_a, tiles.numerics[group_suit_a].copy_rank()) +
        _completed_numeric_groups(
            group_suit_b, tiles.numerics[group_suit_b].copy_rank())
    ).value()

    if completed_groups is None:
        return []

    tiles = tiles.numerics[suit_one_more].copy_rank()
    result = []
    for i, c in enumerate(tiles):
        if c != 0:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 1
            groups = _completed_numeric_groups(suit_one_more, copy_tiles)
            if groups.value() is not None:
                result.append(tile.Tile(suit_one_more, i))

        if c >= 2:
            copy_tiles = tiles[:]
            copy_tiles[i] -= 2
            result.extend(_numeric_suit_with_two_more(
                suit_one_more, copy_tiles)[0])

    return result


def _detect_numeric_suit_with_two_more(tiles):
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 0:
        return [], False
    group_suit_a, group_suit_b = mod_numerics[1][0], mod_numerics[2][0]
    completed_groups = (
        _completed_numeric_groups(
            group_suit_a, tiles.numerics[group_suit_a].copy_rank()) +
        _completed_numeric_groups(
            group_suit_b, tiles.numerics[group_suit_b].copy_rank())
    ).value()

    if completed_groups is None:
        return [], False

    suit_two_more = mod_numerics[0][0]
    return _numeric_suit_with_two_more(
        suit_two_more, tiles.numerics[suit_two_more].copy_rank())


def _detect_2_numeric_suits_with_2_more(tiles):
    mod_numerics = sorted([(i, tiles.numerics[i].total() % 3)
                           for i in xrange(3)], key=lambda k: -k[1])
    if mod_numerics[0][1] != 2 or mod_numerics[1][1] != 2:
        return []

    group_suit = mod_numerics[2][0]
    completed_groups = _completed_numeric_groups(
        group_suit, tiles.numerics[group_suit].copy_rank()).value()

    if completed_groups is None:
        return []

    suit_2more_a, suit_2more_b = mod_numerics[0][0], mod_numerics[1][0]
    waits_a, flag_pair_a = _numeric_suit_with_two_more(
        suit_2more_a, tiles.numerics[suit_2more_a].copy_rank())
    waits_b, flag_pair_b = _numeric_suit_with_two_more(
        suit_2more_b, tiles.numerics[suit_2more_b].copy_rank())

    result = []
    if flag_pair_a:
        result.extend(waits_b)
    if flag_pair_b:
        result.extend(waits_a)
    return result


def _numeric_suit_with_two_more(suit, tiles):
    result = [tile.Tile(suit, pair_rank) for pair_rank, groups in
              _numeric_groups_with_pair(suit, tiles[:])]
    flag_pair = len(result) != 0

    for starting_rank, groups in _numeric_groups_with_side_waits(
            suit, tiles[:]):
        if starting_rank != 0:
            result.append(tile.Tile(suit, starting_rank - 1))
        if starting_rank != 7:
            result.append(tile.Tile(suit, starting_rank + 2))

    result.extend([
        tile.Tile(suit, staring_rank + 1)
        for staring_rank, groups in _numeric_groups_with_middle_waits(
            suit, tiles[:])])

    return result, flag_pair


def _numeric_groups_with_pair(suit, suit_tiles):
    result = []
    for i, c in enumerate(suit_tiles):
        if c >= 2:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 2
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result


def _numeric_groups_with_side_waits(suit, suit_tiles):
    result = []
    for i in xrange(8):
        if suit_tiles[i] and suit_tiles[i + 1]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 1] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result


def _numeric_groups_with_middle_waits(suit, suit_tiles):
    result = []
    for i in xrange(7):
        if suit_tiles[i] and suit_tiles[i + 2]:
            copy_tiles = suit_tiles[:]
            copy_tiles[i] -= 1
            copy_tiles[i + 2] -= 1
            groups = _completed_numeric_groups(suit, copy_tiles)
            if groups.value() is not None:
                result.append((i, groups))
    return result


def _completed_numeric_groups(suit, suit_tiles):
    for i, c in enumerate(suit_tiles):
        if c != 0:
            first_rank = i
            break
    else:
        return group.Groups()

    if suit_tiles[first_rank] >= 3:
        tri = group.Triplet(suit, first_rank)
        suit_tiles[first_rank] -= 3
        return _completed_numeric_groups(suit, suit_tiles).append_group(tri)

    if (first_rank > 6 or suit_tiles[first_rank] > suit_tiles[first_rank + 1]
            or suit_tiles[first_rank] > suit_tiles[first_rank + 2]):
        return group.NoGroup()
    seqs = [group.Sequence(suit, first_rank)
            for _ in xrange(suit_tiles[first_rank])]
    suit_tiles[first_rank + 1] -= suit_tiles[first_rank]
    suit_tiles[first_rank + 2] -= suit_tiles[first_rank]
    suit_tiles[first_rank] = 0
    return _completed_numeric_groups(suit, suit_tiles) + seqs