Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment