# What are you waiting for? (A mahjong solver)

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 , so the solution in the fewest bytes wins. Standard loopholes apply.

• Thank you for actually doing Mahjong, rather than the (IMO annoying) solitaire using the tiles that westerners seem to think of whenever they hear the word "Mahjong". – Justin Oct 16 '14 at 5:00
• @Quincunx Fun fact: This challenge came about because I wanted to do a challenge with an ASCII representation of Mahjong solitaire (which I might still do at some point...). I did call it "Mahjong solitaire" though. ;) – Martin Ender Oct 16 '14 at 10:43
• @Quincunx: I don't think it's their fault. It's game developers' fault for calling their "Mahjong solitaire" games "Mahjong" and nothing else. – Joe Z. Oct 20 '14 at 18:50
• What about seven pairs? thirteen orphans? you could do something even more complex with honors :) Do you think it's out-of-purpose if I create a codegolf that asks to calculate the shanten (minimal number of tiles needed before getting tenpai - ready to win) of a hand? – V. Courtois Jul 20 '17 at 7:41
• @VCourtois It's been a while, but I recall specifically excluding seven pairs, thirteen orphans, honours and already made calls so as to not overcomplicate the challenge for people new to the game. I think I considered making a shanten challenge later after that but never did in the end - if you'd like to post one I think it'd make a fine challenge. – Sp3000 Jul 20 '17 at 8:18

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

• Ah, you beat me :P Anyway, it looks like you can use map in a couple of places, like: H(map((S+t).count,T)) – FryAmTheEggman Oct 17 '14 at 0:48
• @FryAmTheEggman Missed that. Thanks! – Ell Oct 17 '14 at 8:40
• @Sp3000 It's Python 2. That's strange; it works fine for me on 2.7.8. – Ell Oct 17 '14 at 11:28
• @Ell Works in 2.7.8 - 2.7.5 didn't like the 5else :P – Sp3000 Oct 17 '14 at 13:06

# 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
),
[ // 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