What are you waiting for? (A mahjong solver)

Question

Idea thanks to @MartinBüttner from a discussion in chat

Mahjong is a tile game that is immensely popular in Asia. It is typically played with four players, and the goal of the game is to be the first person to complete a valid hand using the tiles. For this challenge, we will consider a simplified version of the game — PPCG mahjong.

In PPCG mahjong, there are three suits – m, p and s – and the tiles are numbered from 1 to 9. There are exactly four copies of each tile, and the tiles are denoted by its number followed by its suit (e.g. 3m, 9s).

A completed PPCG mahjong hand consists of four sets of three and a pair, for a total of 14 tiles.

A set of three can be either:

• Three of the same tile (e.g. 4s 4s 4s, but not 4m 4p 4s), or
• A sequence of three consecutive tiles in the same suit (e.g. 1s 2s 3s or 6p 7p 8p but not 3s 4m 5m or 3p 5p 7p). Sequences do not wrap (so 9m 1m 2m is invalid).

A pair is simply two identical tiles (e.g. 5s 5s).

The challenge

Your program will receive a space-separated hand of 13 tiles, with each tile appearing no more than four times. You may write either a full program or a function which takes in a string.

Your task is to find all possible 14th tiles ("waits") which, when added to the hand, would form a completed PPCG mahjong hand. The outputted tiles should be space-separated, but can be in any order. Leading or trailing whitespace is allowed.

Your program should run in a reasonable amount of time, no longer than a minute.

Examples

Input: 1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s
Output: 9s

Input: 1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p
Output:

Input: 1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s
Output: 1s

Input: 1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m
Output: 1m 2m 3m 4m 5m 6m 7m 8m 9m

Input: 1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s
Output: 1m 4m 6s 9s 

In the first example, the 1m 4s 7p 3m all form existing triplets, leaving the lone 9s to form a pair.

In the second example, the 2s 3s and 7p 8p can only form sequences, and the remaining tiles can only form triplets. Hence no pair can be formed, and there is no output.

In the third example, the hand splits into 1m2m3m 2m3m4m 3m3m 1s1s 9s9s9s. Normally this would be a wait for 3m 1s, but as all four 3m have been used, the only available wait is 1s.

In the fourth example, all of the m tiles complete the hand. For example, for 1m, one could have 1m1m1m 1m2m3m 4m5m6m 7m8m9m 9m9m which is a completed hand.

Try to work out the rest of the fourth example and the fifth example :)

Scoring

This is code-golf, so the solution in the fewest bytes wins. Standard loopholes apply.

Answer 1

Python, 312 281 bytes

def W(S):H=lambda C,n=0,t=1:sum([m<C[0]and H([c-s for c in C][:l]+C[l:],n+1,u)for m,s,l,u in(2,3,1,t),(t,2,1,4),(4-5*all(C[:3]),1,3,t)])|H(C[1:],n,t)if C[2:]and max(C)<5else n>4;T=[i+s for s in"mps"for i in"12345678900"];return" ".join(t for t in T if("1"<t)*H(map((S+t).count,T)))

W takes a string as input and returns a string as output.

The small number of tiles (27) makes it fast enough to test if each of them completes the hand. The problem becomes to check if a hand is valid. The function uses a simple backtracking algorithm that considers all possible choices of sets and checks if any of them adds up to a complete hand.

Hands are represented as tile histograms, i.e. a list of tile counts (for all the tiles, not only the ones present in the hand.) This makes it easy to both check if we have a certain number of a certain tile, and if we have a sequence of adjacent tiles (padding between tiles of different suits prevent multi-suit sequences.)

Answer 2

JavaScript (E6) 306

F=h=>(
  R=(a,p,n=1)=>(a=[...a]).splice(p,n)&&a,
  K=(t,d=3)=>
    !t[0]
    |t.some(
      (v,p)=>
        v==t[p+1]&v==t[p+d-1]&&
        K(R(t,p,d))
      ||
        ~((r=t.indexOf((x=-~v[0])+v[1]))|(s=t.indexOf(-~x+v[1])))&&
        K(R(R(R(t,s),r),p))
    ),
  o=[],
  [for(s of'mps')for(i of'123456789')h.replace(t=i+s,s,'g')[34]
  &&K([t,...h.split(' ')].sort(),2)&&o.push(t)
  ],o
)

Explained

F=hand=>(
  Remove=(a,p,n=1)=>                // function to remove 1 or more element from an array, returning a new shorter array
    ((a=[...a]).splice(p,n), a),    // using array.splice on a new created array 

  Check=(ckHand, dim)=>  // recursive function to check hand. 
                         // removing pairs (at iteration 0) or sequence of three, if at last the hand remain empty then success
                         // parameter dim is 2 or 3 indicating how many equal elements are to be removed
    !ckHand[0]           // check if empty (element 0 does not exist)
    |ckHand.some(        // else traverse all array checking what can be removed
      (value, position)=> 
        value == ckHand[position + 1] 
        & value == ckHand[position + dim-1] &&   // look for 3 (or 2) equal elements
        Check(Remove(ckHand, position, dim), 3)   // if found, then remove elements and check again
      ||
        ~((r = ckHand.indexOf((x=-~value[0]) + value[1]))     // value[0] is number, value[1] is suit 
        |(s = ckHand.indexOf(-~x + value[1]))) &&              // look for an ascending sequence in following elements (the array is sorted)
        Check(Remove(Remove(Remove(ckHand, s), r), position),3) // if sequence found, remove elements and check again
    ),
  output=[], // start with an empty solution list
  [ // using array comprehension to implement a double loop
    for(s of'mps')        // loop for all suits
    for(i of'123456789')  // loop for all numbers
    (
       tile=i+s, // current tile 
       (hand.replace(tile,' ','g').length > 34)      // if tile is present 4 times in hand, the replaced length is 38-4 == 34
       && (                                       // else proceed with check
         ckHand = hand.split(' '), 
         ckHand.push(tile),    // in ckHand (as an array) the hand to be checked, that is base hand + current tile
         ckHand.sort(),        // sorting the array simplfy the checks
         Check(ckHand, 2)      // start checks looking for a pair
       )
       && 
         output.push(tile)   // if check ok, add tile to the solution list
    )   
  ],
  output // last expression in list is the function return value 
)

Test in FireFox/FireBug console

;["1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s", "1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p",
 "1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s", "1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m",
 "1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s"].forEach(s=>console.log(s+' => '+F(s)))

Output

1m 1m 1m 4s 4s 4s 7p 7p 7p 3m 3m 3m 9s => 9s
1m 1m 1m 3m 3m 3m 5m 5m 5m 2s 3s 7p 8p =>
1m 2m 2m 3m 3m 3m 3m 4m 1s 1s 9s 9s 9s => 1s
1m 1m 1m 2m 3m 4m 5m 6m 7m 8m 9m 9m 9m => 1m,2m,3m,4m,5m,6m,7m,8m,9m
1m 1m 1m 5p 2m 3m 5p 7s 8s 5p 9s 9s 9s => 1m,4m,6s,9s