Instantly share code, notes, and snippets.

# neuront/group.py Created Jul 2, 2014

Mahjong Waits Algorithm
 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
 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())
 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