TopCoder problem "Mhing" used in TCCC '04 Semifinals 2 (Division I Level Three)



Problem Statement

    

Plugin users: There is a picture in the problem statement.

Mhing is a card game based on the more famous Mah Jong. The deck of cards contains suit cards, honor cards and mhing cards. In this problem, we will assume there is an infinite supply of each type of card.

There are three different suits: bamboo, characters and dots. A suit card belongs to one of these suits and has a value between 1 and 9, inclusive. The shorthand notation for suit cards will be (quotes for clarity) "<suit><value>" where <suit> is the first letter of the suit. "b5" and "d9" will thus represent "suit bamboo, value 5" and "suit dots, value 9", respectively.

There are two types of honor cards: dragons and winds. There are three different dragons: red, green and white. The shorthand notation for these cards will be "dr", "dg" and "dw", respectively. There are also four different winds: north, south, east and west, with their respective shorthand notations "wn", "ws", "we" and "ww".



A mhing card works like a joker in regular card games. That is, the player with the card decides which suit card or honor card it should represent. The shorthand notation for a mhing card is "mh".

At the start of the game, each player has 13 cards. During a player's turn, he first gets a new card. If the 14 cards form a mhing hand (see below), he wins the game. Otherwise he throws away one card, and the turn ends. A mhing hand is a partioning of the 14 cards into five groups, four of the them containing exactly three cards, and one containing exactly two cards (a pair). Each card must belong to exactly one group.

A group can either be a triplet, a sequence or a pair. A triplet contains three identical cards, either suit cards or honor cards. So, {"c5", "mh", "c5"} and {"dw", "dw", "dw"} are two possible triplets (remember that a mhing card can be any other card) while {"b2", "d2", "d2"} and {"wn", "ws", "we"} are not triplets. A sequence contains three suit cards in the same suit where the values form a sequence of three consecutive numbers. For instance, {"d6", "d7", "d8"} is a sequence, while {"b8", "b9", "b1"} is not (wrapping around is thus not allowed). A pair is just like a triplet except it only contains two cards instead of three (remember that exactly one group should be a pair).

Create a class Mhing containing the method howMany which takes a String[] cards containing the initial 13 cards, and returns an int, the minimum number of cards the player needs to get a mhing hand.

 

Definition

    
Class:Mhing
Method:howMany
Parameters:String[]
Returns:int
Method signature:int howMany(String[] cards)
(be sure your method is public)
    
 

Notes

-Since the player starts with 13 cards, he will always need at least one extra card.
-Remember that a player always throws away a card after he gets one, unless the 14 cards form a mhing hand.
 

Constraints

-cards will contain exactly 13 elements.
-Each element in cards will be one of the shorthand notations described in the problem statement.
 

Examples

0)
    
{"c2","c3","c5","c5","c5","ww","dw","mh","mh","b4","b5","d7","d9"}
Returns: 2

This input corresponds to the picture in the problem statement. If the player for instance gets the cards "c4" and "ww" and throws away "dw", the 14 cards can be partitioned into groups like this:

  • {"c2", "c3", "c4"}
  • {"c5", "c5", "c5"}
  • {"b4", "b5", "mh"}
  • {"d7", "mh", "d9"}
  • {"ww", "ww"}
1)
    
{"dr","b3","c1","d1","d4","d8","we","dw","dw","ww","dw","ww","ww"}
Returns: 5

The player must throw away 4 cards (for instance "dr", "b3", "c1" and "we") and get 5 new cards (for instance "d1", "d1", "d4", "d4" and "d8") to get a mhing hand.

  • {"dw","dw","dw"}
  • {"ww","ww","ww"}
  • {"d1","d1","d1"}
  • {"d4","d4","d4"}
  • {"d8","d8"}
2)
    
{"c5","c9","c6","c5","c8","c9","c9","c5","c5","c4","c7","c5","c2"}
Returns: 1

The player only needs one card, "c3", to get a mhing hand:

  • {"c2","c3","c4"}
  • {"c5","c5","c5"}
  • {"c6","c7","c8"}
  • {"c9","c9","c9"}
  • {"c5","c5"}
3)
    
{"c9","c9","c6","c9","c8","c9","c9","c5","c5","c4","c7","c5","c2"}
Returns: 1

These are the same cards as in the previous example, except that a "c5" has been changed into a "c9". The player still only needs one more card, although the groups must be partitioned a bit differently. The needed card is "c2".

  • {"c4","c5","c6"}
  • {"c5","c5","c5"}
  • {"c7","c8","c9"}
  • {"c9","c9","c9"}
  • {"c2","c2"}
4)
    
{"c2","d6","b4","c3","b9","d6","d4","b5","b3","d3","b6","b3","b3"}
Returns: 2
5)
    
{"ws","mh","mh","mh","mh","mh","mh","b1","mh","b3","b2","dr","ws"}
Returns: 1

Here the player can afford to make groups consisting of only mhing cards!

6)
    
{"wn","ws","ww","we","dw","dr","dg","mh","mh","wn","ws","dr","dg"}
Returns: 3

Only honor cards and mhing cards.

7)
    
{"b1","b4","b7","c1","c4","c7","d1","d4","d7","wn","ws","we","ww"}
Returns: 9

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2278

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5077&pm=2278

Writer:

Yarin

Testers:

zoidal , lbackstrom , brett1479

Problem categories:

Brute Force