TopCoder problem "CircleGame" used in SRM 148 (Division I Level One)



Problem Statement

    

Tommy is learning a simple card game called Circle. To play the game, the single player shuffles a deck of cards. He or she then flips through the deck, removing all instances of the 'K' card, and all consecutive pairs of cards that add up to 13. The deck does wrap around, so that if the last card remaining in the deck and the first card remaining in the deck add up to 13, they are both removed. The player keeps cycling through the deck until no more cards can be removed.

Create a class CircleGame containing the method cardsLeft that takes a String deck representing a not-necessarily complete nor correct deck of cards. Each character of deck represents the value of a card without the suit. The values shown on the card represent the following numerical values:

'A' - 1
'2' - 2
'3' - 3
'4' - 4
'5' - 5
'6' - 6
'7' - 7
'8' - 8
'9' - 9
'T' - 10
'J' - 11
'Q' - 12
'K' - 13

Given deck, return the number of cards remaining after the game has been played to its fullest such that no more cards can be removed.

 

Definition

    
Class:CircleGame
Method:cardsLeft
Parameters:String
Returns:int
Method signature:int cardsLeft(String deck)
(be sure your method is public)
    
 

Notes

-There are no guarantees made about the contents of the deck. For example, there can be more than four of a given value of card.
-Note that if a particular card can make a sum of 13 with the card before or after it, it does not matter which is chosen. For example, 38582, whether you use the first 8 or the second 8, will still become 382 after the two cards (5 and 8) are removed.
 

Constraints

-deck will have between 10 and 50 characters, inclusive.
-each character of deck will be a character from the set {'2'-'9','A','T','J','Q','K'}.
 

Examples

0)
    
"KKKKKKKKKK"
Returns: 0
All K cards are always removed from the deck.
1)
    
"KKKKKAQT23"
Returns: 1
The K cards are removed, leaving AQT23. AQ are then removed because they add up to 13, leaving T23. Since the deck wraps around and T and 3 add up to 13, they are also removed, just leaving the 2.
2)
    
"KKKKATQ23J"
Returns: 6
Only the K cards can be removed.
3)
    
"AT68482AK6875QJ5K9573Q"
Returns: 4
The remaining deck is 6875.
4)
    
"AQK262362TKKAQ6262437892KTTJA332"
Returns: 24

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4545&pm=1735

Writer:

chogyonim

Testers:

lbackstrom , brett1479

Problem categories:

Simulation, String Manipulation