PROBLEM STATEMENT: (NOTE: Do NOT assume that the definition of gin here is
accurate. Use the definitions in the problem statement.)
Given a Gin hand, return the minimum "dead wood" value for the hand.
Gin is a card game played with a standard 52-card deck of playing cards.
Players keep seven cards in their hand at all times.
A standard 52-card deck contains 13 cards of four suits: clubs, diamonds,
hearts, and spades. Clubs and spades are known as the black suits, and
diamonds and hearts are known as the red suits. Clubs and diamonds are also
known as the minor suits, and hearts and spades are also known as the major
suits. Within each suit, each card also has a rank (one of
A,2,3,4,5,6,7,8,9,10,J,Q,K). 'A' is the lowest rank and 'K' is the highest
rank. Each card can be represented with two or three characters. If the rank
of the card is not 10, then the first character corresponds to the rank of the
card and the second character corresponds to the (first letter of the) suit.
If the rank of the card is 10, then the first and second characters are '1' and
'0', respectively, and the third character corresponds to the suit. An example
of a gin hand is AD,AS,3C,AC,8S,10H,3H.
The play of gin is outside the context of this problem. We will deal only with
analyzing a given hand of seven cards. A hand of gin can be broken up into
"safe" cards and "dead wood". A card is safe if it can be grouped with at
least 2 other cards based on the following rules:
1) All cards in the group have the same rank. (3C, 3D, 3H)
2) All cards in the group have the same suit and the ranks of the cards are
consecutive. (AC, 2C, 3C). No rank succeeds 'K' and no rank precedes 'A'.
Thus, a set of cards like QC, KC, AC is not considered consecutive.
3) A card used in one group cannot be used in another group.
If a card is not in a safe group, it is called dead wood.
To demonstrate, suppose the gin hand is AC, AD, AS, 2C, 3C, 2D, 3D. We can
group these cards in 3 ways: Use AC, AD, AS as a group, leaving 4 cards as dead
wood, or we can use the AC, 2C, 3C as a group and AD, 2D, 3D as a group,
leaving 1 card as dead wood. We can also group them so that all cards are
considered dead wood.
Or, suppose the gin hand is AC, 2C, 3C, 4C, 5S, 6S, 7S. We can group these
cards in several ways. Here are 4 of them:
Way 1: Use AC, 2C, 3C, 4C as a group, and 5S, 6S, 7S as a group, leaving no
dead wood.
Way 2: Use AC, 2C, 3C as a group, and 5S, 6S, 7S as a group, leaving the 4C as
deadwood.
Way 3: Use 2C, 3C, 4C as a group, and 5S, 6S, 7S as a group, leaving the AC as
dead wood.
Way 4: Leave all cards as dead wood.
Note that it is possible to consider a card dead wood if it is not explicitly
grouped, even if it can be grouped.
The value of a hand is based on the amount of dead wood. The dead wood value
is calculated as follows:
Card Value: Points:
A 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
J 10
Q 10
K 10
If there is no dead wood in a hand, the value of the dead wood is 0. If there
is dead wood, add the dead wood value of each unsafe card together to get the
total dead wood value of the hand.
DEFINITION:
Class: Gin
Method: minDeadWood
Parameters: String
Returns: int
Method signature: int minDeadWood(String hand)
(be sure your method is public)
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
*hand has between 14 and 18 characters, inclusive.
*hand contains only the characters '0' through '9' inclusive, 'A', 'J', 'Q',
'K', 'C', 'D', 'H', 'S'.
*hand is of the form
"<Number><Suit><Number><Suit><Number><Suit><Number><Suit><Number><Suit><Number><
Suit><Number><Suit>" (seven cards).
*<Number> is one of 'A', '2', '3', '4', '5', '6', '7', '8', '9', "10", 'J',
'Q', 'K'.
*<Suit> is one of 'C', 'D', 'H', 'S'.
WORKED EXAMPLES:
hand = "AC2C3C4C5C6C7C"
All cards can be grouped, being in order and of the same suit. There is no
deadwood, return 0.
hand = "3C2C5C4C7C6CAC"
This is exactly the same hand as the last example. return 0.
hand = "ACASAH2C3CKC10C"
There are two ways to take out safe groups of cards (without every card being
dead wood):
Way 1: AC2C3C
DeadWood 1: ASAHKC10C
DeadWood value: 1 + 1 + 10 + 10 = 22
Way 2: ACASAH
DeadWood 2: 2C3CKC10C
DeadWood value: 2 + 3 + 10 + 10 = 25
22 is the smallest value, so return 22.
TEST CASES:
"KHQDJC10S10HJDKS" returns 70.
"4S5S6D7S8S9D10S" returns 49.
"5D9H5H9S10S5C9D" returns 10.