### **[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: interview

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(r'((\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 *
##only works for first case
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: # Meld
            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: # Pair
            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):
#         print(f'try {i}\n=============================')
        winset = []
        if cnts[i] < 4:
            cnts[i] += 1
            if win(cnts, 0, winset):
                res += str(i)
            cnts[i] -= 1
#         print(f'res = {res}, winset = {winset}')
            
    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]
#     print(i, cnts)
    if cnts[i] == 1: # sequence * 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: # pair or sequence * 2
        # pair
        if not pair:
            cnts_c = cnts.copy()
            cnts_c[i] -= 2
            if win(cnts_c, 1, winset):
                winset.append((i, i))
                return True
        # sequence * 2
        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: # pair and sequence, triplet, or sequence * 3
        # pair and sequence
        if not pair:
            cnts_c = cnts.copy()
            cnts_c[i] -= 2
            if win(cnts_c, 1, winset):
                winset.append((i, i))
                return True
        # triplet
        cnts_c = cnts.copy()
        cnts_c[i] -= 3
        if win(cnts_c, pair, winset):
            winset.append((i, i, i))
            return True
        # sequence * 3
        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: # pair and sequence * 2, triplet and sequence, or sequence * 4
        # pair and sequence * 2
        if not pair:
            cnts_c = cnts.copy()
            cnts_c[i] -= 2
            if win(cnts_c, 1, winset):
                winset.append((i, i))
                return True
        # triplet and sequence
        cnts_c = cnts.copy()
        cnts_c[i] -= 3
        if win(cnts_c, pair, winset):
            winset.append((i, i, i))
            return True
        # sequence * 4
        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

# lazy backtrack attempt

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))

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
        if r <= 2:
            if all(v == 2 for v in status.values() if v):
                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))