Cheap and Secure Web Hosting Provider : See Now

Algorithm to build a "hand" calculation for riichi mahjong game

, , No Comments
Problem Detail: 

I would like to discuss an algorithm to build a "hand" calculation for riichi mahjong game.

I will simplify terms to focus on the algorithm and not on the game specific terms.

Let's imagine that we have a card deck with three suits. Each suit contains cards from 1 to 9 and each card has four copies.

So card deck looks like this:

111122223333444455556666777788889999a (a is a first suit) 111122223333444455556666777788889999b (b is a second suit) 111122223333444455556666777788889999c (c is a third suit)

Each player has 14 cards in his hand and hand should contains four sets and one pair to be able win. Set can be built from three consecutive cards (123a) or from three same cards (444a).

Input data: 14 cards.

Output data: all possible variants of 4 sets and one pair.

Examples:

Input: 123678a234678b44c

Output: [123a 678a 234b 678b 44c]

Input: 233445a 44556677b

Output: [123a 345a 456b 456b 77b], [123a 345a 567b 567b 44b]

Also, it can be cases with 5-10 possible variants of the hand.

I tried to build it with recursion, but I wasn't successful. The main question how to determine that we don't have remaining variants?

Thanks for your help in advance.

Asked By : Tom
Answered By : D.W.

Pretty much any approach will be fine. The trick is to focus on generating all possible ways to partition the hand into groups of size 4+4+4+2, then test each candidate to see whether it is valid. If you've enumerated all possible ways in the first step, then you'll know you've found all possible variants/solutions.

Even a totally dumb, unoptimized brute-force approach will probably be fast enough: enumerate all partitions of the 14 cards into groups of size 4+4+4+2, and for each, check whether it's valid. There are

$${14 \choose 4} \times {10 \choose 4} \times {6 \times 4} /6 = 525,525$$

different such partitions. Therefore, you should be able to enumerate all partitions and for each check whether it satisfies the rules.

Of course there are likely much faster algorithms. For instance, you can enumerate all possibilities for the first card in the first "set", then enumerate all ways to complete the first "set" (usually there won't be that many, given the restrictions on a valid "set"), then enumerate all possibilities for the first card in the second "set" out of the remaining cards, then enumerate all ways to complete the second "set", and so on. In practice this will probably be even faster.

It's easy to find all variants with this kind of approach. You just test each possible partition/grouping, and output each one that is valid.

As another optimization, it's easy to figure out the suit that you must use for the "pair". Count the number of cards you have in each suit. For there to exist a valid combination, two of these numbers must be $0 \bmod 3$ and one must be $2 \bmod 3$. The latter is the suit that the pair must come from. Try all possibilities for how to choose the pair (from that set) -- there usually won't be that many possibilities, as there usually won't be many repeated cards in that suit. For each such possibility, try all ways to divide the remaining 12 cards into 3 "sets".

As another optimization, after you've chosen and removed the pair, if you have a suit that contains exactly 3 cards, you know that if there is any valid combination, those 3 cards must be placed together in a set -- you have no choice (it's forced). This further cuts down on the number of possible combinations you must examine. If there's a suit that contains exactly 6 cards, there are only ${6 \choose 3} = 20$ ways to divide it into two groups of 3; you can check each candidate division to see which ones are comprised of two valid "sets". These two cases will cover most hands. The only difficult case is where there's a single suit that contains exactly 9 or 12 cards (after removing the pair), and you can fall back to enumerating all partitions for those (rare) hands, or devise alternative strategies for handling those specific cases.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/64560

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback