Statistics

Problem Statement for "Uniscraper"

Problem Statement

You are the evil genius Dr. S, and you own a software company, Sware. You have seen a very popular game on the internet, and you want to make a clone that will steal some advertising profits from them. Because you don't want the game to be exactly the same (to avoid lawsuits), you create the game "Uniscraper" which has the same game concept, but only one pyramid.

The game play of Uniscraper is simple. Out of a standard 52-card deck, you are dealt 36 cards in a pyramid pattern in the following numeric order: 

               1
             2   3
           4   5   6
         7   8   9  10
      11  12  13  14  15
    16  17  18  19  20  21
  22  23  24  25  26  27  28
29  30  31  32  33  34  35  36

The cards are placed face up, so that cards dealt in lower rows are on top of cards in higher rows. For example, card 1 has cards 2 and 3 covering it.

Now, using the remaining cards in the deck, you turn over the first card called the play card. You can remove any card from the playing area which does not have other cards on top of it, and is one rank away from the play card. For example, if the play card is a 5, you could remove a 6 or a 4 from the playing area as long as it wasn't covered. The ranks wrap, so if the play card is a 2, you can remove an Ace, and vice versa. The card you just removed now becomes the play card. When you cannot play any more cards, you must use a new card from the deck. A "run" consists of a list of cards you can play off of the playing area without drawing a new card. The score you get from the game is multiplied by the longest run you get, so it is wise to maximize your run sizes.

Because you are so very evil, you want to implement a cheat feature that only you know about, just so you can boast how good you are at Uniscraper to the other evil geniuses. The cheat feature, when enabled, communicates the best run possible given the current situation.

Create a class Uniscraper that contains the method bestRun, which takes one argument:
config: a configuration as described below
The method should return a int[] which represent positions that have been removed for the best run. Positions are defined by the pyramid of numbers above. The order of the integers is the order they were taken off the playing area.

Each character in config represents what card is in what place in the above diagram. The cards are represented by the following characters:
A = Ace
K = King
Q = Queen
J = Jack
T = Ten
9..2 = 9..2
The current play card is the first character in the string, and the other characters' positions represent the position of that card as given in the diagram above, i.e. the cards, other than the play card, are in the String in the order in which the cards were dealt. For example, the string "6KQJT98765432AKQJT98765432AKQJT987654" represents the following configuration: 

       K
      Q J
     T 9 8
    7 6 5 4
   3 2 A K Q
  J T 9 8 7 6
 5 4 3 2 A K Q
J T 9 8 7 6 5 4

with the play card '6'.

Since you want to cheat even after the first move, the configuration can have cards missing that have already been used in a previous run. These missing cards will be represented by dots (.) in config. For example, if the best run out of the above pattern is taken, the cards would look as follows: 

       K
      Q J
     T 9 8
    7 6 5 4
   3 2 A K Q
  J T 9 8 7 6
 5 4 3 2 A K Q
              4

Let's say the next card from the deck is a Queen, your configuration string is now:

"QKQJT98765432AKQJT98765432AKQ.......4"

If a configuration has any trailing dots, the trailing dots do not necessarily need to be in config. For example, the configuration "AQKJT98.............................." may be passed as "AQKJT98....." or even "AQKJT98".

Definition

Class:
Uniscraper
Method:
bestRun
Parameters:
String
Returns:
int[]
Method signature:
int[] bestRun(String config)
(be sure your method is public)

Notes

  • You should assume that you cannot count on any other cards being in the draw pile. That is, there is no possibility to get a longer run by waiting for another draw card to come up.
  • If two runs have the same length, return the one that is lexicographically smaller. This means, if you are traversing the lists from left to right, the lexicographically smaller list is the first to have a lower number in the same position. Example {4, 2, 3, 1} would be returned before {4, 3, 2, 1} because the second element is where the first difference is, and the first list has the smaller number in that position.
  • Card ranks go in this order: 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A and back to 2. They can go in either direction.
  • If no cards can be played, return an empty int[].
  • If config is less than 37 characters long, assume the remaining characters are dots, and therefore, the cards at those positions are missing.
  • A card is considered covered if either the card to the lower left or the card to the lower right is still present on the playing area.

Constraints

  • config is 1 to 37 characters long inclusive, and contains only the numeric characters 2 through 9, T, J, Q, K, A, and the dot character '.'.
  • config contains at most 4 of each non-dot character.
  • The first character in config is not a dot.
  • There are no dots in positions of config that would not have been able to be removed during normal play. In other words, cards cannot be laying on top of empty positions. For example, if position 5 is a valid card, then neither position 2 nor position 3 can be dots.

Examples

  1. "6KQJT98765432AKQJT98765432AKQJT987654"

    Returns: { 35, 34, 33, 32, 31, 30, 29 }

    This is the example stated above. Since the first card is a 6, you can remove either a 5 or 7. Shown below are all 4 possible runs that you can make. The left picture is the starting configuration, and the right picture is the order the cards were taken off. Run 1: {33, 32, 31, 30, 29} K * Q J * * T 9 8 * * * 7 6 5 4 * * * * 3 2 A K Q * * * * * J T 9 8 7 6 * * * * * * 5 4 3 2 A K Q * * * * * * * J T 9 8 7 6 5 4 5 4 3 2 1 * * * Run 2: {33, 34, 35, 36} K * Q J * * T 9 8 * * * 7 6 5 4 * * * * 3 2 A K Q * * * * * J T 9 8 7 6 * * * * * * 5 4 3 2 A K Q * * * * * * * J T 9 8 7 6 5 4 * * * * 1 2 3 4 Run 3: {35, 34, 33, 32, 31, 30, 29} K * Q J * * T 9 8 * * * 7 6 5 4 * * * * 3 2 A K Q * * * * * J T 9 8 7 6 * * * * * * 5 4 3 2 A K Q * * * * * * * J T 9 8 7 6 5 4 7 6 5 4 3 2 1 * Run 4: {35, 36} K * Q J * * T 9 8 * * * 7 6 5 4 * * * * 3 2 A K Q * * * * * J T 9 8 7 6 * * * * * * 5 4 3 2 A K Q * * * * * * * J T 9 8 7 6 5 4 * * * * * * 1 2 Clearly, run 3 is the best since it is 7 cards long. Notice that in run 3, you cannot remove the Q in position 28 because it is covered by the 4 in position 36.

  2. "KJQKA2A"

    Returns: { 4, 5, 6, 3, 2, 1 }

    Run 1: {4, 5, 6, 3, 2, 1} J 6 Q K 5 4 A 2 A 1 2 3 Run 2: {6, 5, 4, 3, 2, 1} J 6 Q K 5 4 A 2 A 3 2 1 There are two possible runs, each uses all 6 cards. However, run 1 uses the lower numbered cards first, so it is returned.

  3. "A6877879898T9T9TQJQJQJKAKAKAK"

    Returns: { 22, 23, 24, 25, 26, 27, 28, 16, 17, 18, 19, 20, 21, 11, 12, 13, 7, 8, 14, 15, 9, 5, 4, 10, 6, 2, 3, 1 }

    The original configuration looks like: 6 8 7 7 8 7 9 8 9 8 T 9 T 9 T Q J Q J Q J K A K A K A K

  4. "KAKJA.TK..JQ...Q"

    Returns: { 15, 10, 6, 3, 11, 7, 4, 2, 1 }

    The original configuration looks like: A K J A T K J Q Q

  5. "36877879898T9T9TQJQJQJKAKAKAKA2323232"

    Returns: { 30, 31, 32, 33, 34, 35, 36, 23, 24, 25, 26, 27, 28, 29, 22, 16, 17, 18, 19, 20, 21, 11, 12, 13, 7, 8, 14, 15, 9, 5, 4, 10, 6, 2, 3, 1 }

  6. "K."

    Returns: { }

  7. "267565263A24.234A..3"

    Returns: { 19, 15, 14, 10, 16, 13, 9, 6, 8, 11, 5, 7, 3, 4, 2, 1 }

  8. "46877879898T9T9TQJQJQJKAKAKAK32323232"

    Returns: { 29, 30, 31, 32, 33, 34, 35, 36, 23, 22, 16, 24, 25, 26, 27, 28, 18, 17, 11, 19, 20, 21, 13, 12, 8, 7, 15, 14, 10, 9, 5, 4, 2, 6 }

  9. "JJT97.86..53...42....AK.....KQ......Q"

    Returns: { 29, 22, 36, 28, 21, 16, 11, 15, 10, 7, 4, 6, 3, 2, 1 }

  10. "3JTT9398..87...76....65.....52......4"

    Returns: { 29, 5, 36, 22, 16, 28, 21, 11, 7, 15, 10, 4, 2, 6, 3, 1 }

  11. "3JTT9398..87...76....65.....54......2"

    Returns: { 36, 5, 29, 22, 16, 28, 21, 11, 7, 15, 10, 4, 2, 6, 3, 1 }

  12. "23456789TJQKA23456789TJQKA"

    Returns: { 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }

  13. "K232425263738394T4J4Q"

    Returns: { 20, 18, 16 }

  14. "8565544A232843KA997T65"

    Returns: { 16, 19, 17, 11, 18, 20, 21, 12, 13, 8, 7, 14, 15, 10, 9, 5, 4, 6, 3, 2, 1 }

  15. "72345676543456789TJQJQKAKQJT98"

    Returns: { 29, 28, 27, 26, 21, 20, 25, 22, 23, 24, 19, 18, 17, 16, 15, 14, 13, 12, 9, 10, 11, 8, 5, 6, 7, 4, 3, 2, 1 }

  16. "A2A2KAK2"

    Returns: { 7, 5, 4, 2, 6 }

  17. "JAKJA.TK..JQ...Q"

    Returns: { 15, 10, 6, 3, 11, 7, 4, 2, 1 }

  18. "AK8495323486432JQT8324AA"

    Returns: { 20, 19, 14, 22 }

  19. "A6877879898T9T9TQJQJQJKAKAKAK"

    Returns: { 22, 23, 24, 25, 26, 27, 28, 16, 17, 18, 19, 20, 21, 11, 12, 13, 7, 8, 14, 15, 9, 5, 4, 10, 6, 2, 3, 1 }

  20. "JAKJA.TK..JQ...Q"

    Returns: { 15, 10, 6, 3, 11, 7, 4, 2, 1 }

  21. "AK8495323486432JQT8324AA"

    Returns: { 20, 19, 14, 22 }

  22. "A6877879898T9T9TQJQJQJKAKAKAK"

    Returns: { 22, 23, 24, 25, 26, 27, 28, 16, 17, 18, 19, 20, 21, 11, 12, 13, 7, 8, 14, 15, 9, 5, 4, 10, 6, 2, 3, 1 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: