### **[Mahjong Series](/collections/mahjong)**

**Mahjong** is based on draw-and-discard card games that were popular in 18th and 19th century China and some are still popular today.

In each deck, there are three different suits numbered `1` to `9`, which are called **Simple tiles**. To simplify the problem, we talk about only one suit of *simple tiles* in this kata (and that's what the term **Pure Hand** means). Note that there are **EXACTLY** 4 identical copies of each kind of tiles in a deck.

In each of Mahjong games, each of the 4 players around the table has 13 tiles. They take turns drawing a tile from the tile walls and then discarding one of the tiles from their hands. One wins the game if that player holds a combination of tiles as defined below:

A regular winning hand consists of 4 *Melds* and 1 *Pair*. Each *meld* of tiles can be 3 identical or consecutive tiles of a suit, *e.g.* `222` or `456`.



![t2](https://upload.wikimedia.org/wikipedia/commons/6/61/MJt2.png)
![t2](https://upload.wikimedia.org/wikipedia/commons/6/61/MJt2.png)
![t2](https://upload.wikimedia.org/wikipedia/commons/6/61/MJt2.png)


![t4](https://upload.wikimedia.org/wikipedia/commons/7/72/MJt4.png)
![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)
![t6](https://upload.wikimedia.org/wikipedia/commons/7/72/MJt6.png)


Now let's consider a hand of `1113335557779`.



![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t9](https://upload.wikimedia.org/wikipedia/commons/a/a1/MJt9.png)


In this hand, there are already 4 *melds* (each of 3 identical tiles), leaving a `9` alone. So we need another `9` to form a *pair*.




![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)


![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)


![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)


![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)


![t9](https://upload.wikimedia.org/wikipedia/commons/a/a1/MJt9.png)![t9](https://upload.wikimedia.org/wikipedia/commons/a/a1/MJt9.png)


Additionally, there is another option. Regardless of the 3 *melds* ahead (`111`, `333`, `555`), drawing an `8` produces `77789`, which gives a *pair* of `7`'s and a *meld* (`789`). Therefore, the required tiles to win with `1113335557779` are `8` and `9`.




![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)![t1](https://upload.wikimedia.org/wikipedia/commons/4/4a/MJt1.png)


![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)![t3](https://upload.wikimedia.org/wikipedia/commons/a/a4/MJt3.png)


![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)![t5](https://upload.wikimedia.org/wikipedia/commons/5/5c/MJt5.png)


![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)


![t7](https://upload.wikimedia.org/wikipedia/commons/6/6f/MJt7.png)![t8](https://upload.wikimedia.org/wikipedia/commons/1/18/MJt8.png)![t9](https://upload.wikimedia.org/wikipedia/commons/a/a1/MJt9.png)


Now Sakura wonders which tiles will form a hand with 13 tiles of the same suit (**Pure Hand**). Can you help her?

### **Task**
Complete a function to work out all the optional tiles to form a regular winning hand with the given tiles.

- **Input**
  - A string of 13 non-zero digits in non-decreasing order, denoting different tiles of a suit.


- **Output**
  - A string of unique non-zero digits in ascending order.

### **Examples**

```
"1335556789999" => ""
  (None of the tiles in a deck makes up a winning hand)
"1113335557779" => "89"
  ("8" => "111 333 555 77 789",
   "9" => "111 333 555 777 99")
"1223334455678" => "258"
  ("2" => "123 22 345 345 678",
   "5" => "123 234 345 55 678",
   "8" => "123 234 345 678 88")
```

Difficulty: MEDIUM_HARD
Tags: Game theory

Starter code:
def solution(tiles):
	

Solutions:
from collections import Counter

def solution(tiles):
	return ''.join((tile for tile in '123456789' if tiles.count(tile) < 4 and list(meld(meld(meld(meld(pair(Counter(map(int, tiles + tile))))))))))

def pair(c):
	yield from (c - Counter([t, t]) for t in c if c[t] > 1)

def meld(C):
	yield from (c - m for c in C for t in [min(c.keys())] for m in (Counter((t, t + d, t + d + d)) for d in (0, 1)) if c & m == m)


from re import findall

def solution(tiles):
	res = ''
	for tile in range(1, 10):
		hand = ''.join(sorted(tiles + str(tile)))
		if any((hand.count(c) > 4 for c in set(hand))):
			continue
		for pair in findall('((\\d)\\2)', hand):
			rest = hand.replace(pair[0], '', 1)
			while rest:
				char = rest[0]
				triplet = char * 3
				if triplet in rest:
					rest = rest.replace(triplet, '')
				else:
					i = int(char)
					(second, third) = (str(i + 1), str(i + 2))
					if char in rest and second in rest and (third in rest):
						rest = rest.replace(char, '', 1).replace(second, '', 1).replace(third, '', 1)
					else:
						break
			if not rest:
				res += str(tile)
				break
	return res


from collections import Counter
from copy import *

def solution(tiles):
	valid = ''
	for i in range(1, 10):
		x = tiles + str(i)
		c = Counter(x)
		if c.most_common(1)[0][1] < 5 and is_valid(Counter(x)):
			valid += str(i)
	return valid

def is_valid(hand, melds=0, pair=0):
	hand = {k: v for (k, v) in hand.items() if v}
	ordered_hand = sorted(hand, key=int)
	if melds > 5 or pair > 1:
		return False
	if len(hand) == 0:
		return True
	if hand[ordered_hand[0]] > 1:
		new_hand = deepcopy(hand)
		new_hand[ordered_hand[0]] -= 2
		if is_valid(new_hand, melds, pair + 1):
			return True
	if hand[ordered_hand[0]] > 2:
		new_hand = deepcopy(hand)
		new_hand[ordered_hand[0]] -= 3
		if is_valid(new_hand, melds + 1, pair):
			return True
	if len(ordered_hand) > 2 and int(ordered_hand[0]) + 2 == int(ordered_hand[1]) + 1 == int(ordered_hand[2]):
		new_hand = deepcopy(hand)
		new_hand[ordered_hand[0]] -= 1
		new_hand[ordered_hand[1]] -= 1
		new_hand[ordered_hand[2]] -= 1
		if is_valid(new_hand, melds + 1, pair):
			return True
	return False


from collections import Counter

def solution(tiles):

	def candidate(d):
		game[d] += 1
		isGood = dfs()
		game[d] -= 1
		return isGood

	def dfs(hasPair=False):
		(isGood, dig) = (False, min((k for (k, v) in game.items() if v)))
		for (iPair, config) in enumerate([(3,), (1, 1, 1)] + [(2,)] * (not hasPair)):
			cMeld = Counter({dig + i: v for (i, v) in enumerate(config)})
			if sum((game & cMeld).values()) == sum(config):
				game.__isub__(cMeld)
				isGood |= sum(game.values()) == 0 or dfs(hasPair or iPair == 2)
				game.__iadd__(cMeld)
				if isGood:
					break
		return isGood
	game = Counter(map(int, tiles))
	return ''.join((str(d) for d in range(1, 10) if game[d] < 4 and candidate(d)))


from collections import Counter

class SubCounter(Counter):

	def __le__(self, other):
		return all((value <= other[key] for (key, value) in self.items()))
MELDS = [SubCounter({str(n): 3}) for n in range(1, 10)]
MELDS.extend([SubCounter([str(n), str(n + 1), str(n + 2)]) for n in range(1, 8)])

def solution(tiles):

	def remove(cnt):
		if sum(cnt.values()) == 4:
			for (k, v) in cnt.items():
				if v >= 2:
					p = SubCounter(cnt)
					p[k] -= 2
					for m in MELDS:
						if p <= m:
							winning.update((m - p).keys())
		if sum(cnt.values()) == 1:
			winning.update(cnt.keys())
		else:
			for m in MELDS:
				if m <= cnt:
					remove(cnt - m)
	(winning, cnt) = (set(), SubCounter(tiles))
	forbidden = {k for (k, v) in cnt.items() if v >= 4}
	return remove(cnt) or ''.join(sorted(winning - forbidden))


deck = set('123456789')

def group(tiles, start, pair=None):
	if len(tiles) == 1:
		return [tiles]
	if len(tiles) == 2:
		if tiles[0] == tiles[1]:
			return [pair, tiles[0]]
		else:
			(a, b) = (ord(max(tiles[0], tiles[1])), ord(min(tiles[0], tiles[1])))
			if a - b == 1:
				r = []
				if chr(a + 1) in deck:
					r.append(chr(a + 1))
				if chr(b - 1) in deck:
					r.append(chr(b - 1))
				return r
			elif a - b == 2:
				return [chr(b + 1)]
		return []
	tiles_set = set(tiles)
	ret = []
	for tile in tiles_set:
		if tile < start:
			continue
		if len(tiles) % 3 == 1 and tiles.count(tile) > 1:
			ret.extend(group(tiles.replace(tile, '', 2), tile, tile))
		if tiles.count(tile) > 2:
			ret.extend(group(tiles.replace(tile, '', 3), tile, pair))
		(a, b) = (chr(ord(tile) + 1), chr(ord(tile) + 2))
		if a in tiles_set and b in tiles_set:
			ret.extend(group(tiles.replace(tile, '', 1).replace(a, '', 1).replace(b, '', 1), tile, pair))
	return ret

def solution(tiles):
	return ''.join(sorted([x for x in set(group(tiles, tiles[0])) if tiles.count(x) < 4]))


from collections import Counter

def solution(tiles):
	print(tiles)
	cnts = {}
	for i in range(1, 10):
		if str(i) in tiles:
			cnts[i] = tiles.count(str(i))
		else:
			cnts[i] = 0
	print(cnts)
	res = ''
	for i in range(1, 10):
		winset = []
		if cnts[i] < 4:
			cnts[i] += 1
			if win(cnts, 0, winset):
				res += str(i)
			cnts[i] -= 1
	return res

def win(cnts, pair, winset):
	if sum(cnts.values()) == 0:
		return True
	seqdic = {1: [(2, 3)], 2: [(1, 3), (3, 4)], 3: [(1, 2), (2, 4), (4, 5)], 4: [(2, 3), (3, 5), (5, 6)], 5: [(3, 4), (4, 6), (6, 7)], 6: [(4, 5), (5, 7), (7, 8)], 7: [(5, 6), (5, 8), (8, 9)], 8: [(6, 7), (7, 9)], 9: [(7, 8)]}
	tiles = [i for i in cnts.keys() if cnts[i] > 0]
	i = tiles[0]
	if cnts[i] == 1:
		for j in seqdic[i]:
			if cnts[j[0]] > 0 and cnts[j[1]] > 0:
				cnts_c = cnts.copy()
				cnts_c[j[0]] -= 1
				cnts_c[j[1]] -= 1
				cnts_c[i] -= 1
				if win(cnts_c, pair, winset):
					winset.append((j[0], j[1], i))
					return True
		return False
	if cnts[i] == 2:
		if not pair:
			cnts_c = cnts.copy()
			cnts_c[i] -= 2
			if win(cnts_c, 1, winset):
				winset.append((i, i))
				return True
		for j in seqdic[i]:
			if cnts[j[0]] > 1 and cnts[j[1]] > 1:
				cnts_c = cnts.copy()
				cnts_c[j[0]] -= 2
				cnts_c[j[1]] -= 2
				cnts_c[i] -= 2
				if win(cnts_c, pair, winset):
					winset += [(j[0], j[1], i)] * 2
					return True
		return False
	if cnts[i] == 3:
		if not pair:
			cnts_c = cnts.copy()
			cnts_c[i] -= 2
			if win(cnts_c, 1, winset):
				winset.append((i, i))
				return True
		cnts_c = cnts.copy()
		cnts_c[i] -= 3
		if win(cnts_c, pair, winset):
			winset.append((i, i, i))
			return True
		for j in seqdic[i]:
			if cnts[j[0]] > 2 and cnts[j[1]] > 2:
				cnts_c = cnts.copy()
				cnts_c[j[0]] -= 3
				cnts_c[j[1]] -= 3
				cnts_c[i] -= 3
				if win(cnts_c, pair, winset):
					winset += [(j[0], j[1], i)] * 3
					return True
		return False
	if cnts[i] == 4:
		if not pair:
			cnts_c = cnts.copy()
			cnts_c[i] -= 2
			if win(cnts_c, 1, winset):
				winset.append((i, i))
				return True
		cnts_c = cnts.copy()
		cnts_c[i] -= 3
		if win(cnts_c, pair, winset):
			winset.append((i, i, i))
			return True
		for j in seqdic[i]:
			if cnts[j[0]] > 3 and cnts[j[1]] > 3:
				cnts_c = cnts.copy()
				cnts_c[j[0]] -= 4
				cnts_c[j[1]] -= 4
				cnts_c[i] -= 4
				if win(cnts_c, pair, winset):
					winset += [(j[0], j[1], i)] * 4
					return True
		return False


def validate(tiles, used_pair=False):
	tiles = sorted(tiles)
	if not tiles:
		return True
	current_tile = tiles.pop(0)
	if tiles.count(current_tile) > 1:
		tiles.remove(current_tile)
		tiles.remove(current_tile)
		ok = validate(tiles, used_pair)
		if ok:
			return True
		tiles.append(current_tile)
		tiles.append(current_tile)
		tiles = list(sorted(tiles))
	if tiles.count(current_tile + 1) > 0 and tiles.count(current_tile + 2) > 0:
		tiles.remove(current_tile + 1)
		tiles.remove(current_tile + 2)
		ok = validate(tiles, used_pair)
		if ok:
			return True
		tiles.append(current_tile + 1)
		tiles.append(current_tile + 2)
		tiles = list(sorted(tiles))
	if not used_pair and tiles.count(current_tile) > 0:
		tiles.remove(current_tile)
		ok = validate(tiles, True)
		if ok:
			return True
		tiles.append(current_tile)
		tiles = list(sorted(tiles))
	tiles.append(current_tile)
	return False

def solution(tiles):
	result = ''
	for i in range(1, 10):
		if tiles.count(str(i)) > 3:
			continue
		tiles_with_new_tile = [int(n) for n in sorted(tiles + str(i))]
		if validate(tiles_with_new_tile):
			result += str(i)
	return result


from collections import Counter

def is_valid(hand):
	if any((hand.count(str(i)) > 4 for i in range(1, 10))):
		return False
	stack = [[Counter((int(h) for h in hand)), True, len(hand)]]
	while stack:
		(status, has_pair, r) = stack.pop()
		if r == 0:
			return True
		else:
			x = min((k for (k, v) in status.items() if v > 0))
			if status[x] >= 3:
				stack.append([status - Counter([x, x, x]), has_pair, r - 3])
			if status[x + 1] >= 1 and status[x + 2] >= 1:
				stack.append([status - Counter([x, x + 1, x + 2]), has_pair, r - 3])
			if has_pair and status[x] >= 2:
				stack.append([status - Counter([x, x]), False, r - 2])
	return False

def solution(tiles):
	return ''.join((n for n in '123456789' if is_valid(tiles + n)))