SRM 183, D2, 550Pointer (BridgeSort)
James S. Plank
Tue Feb 28 16:59:28 EST 2017
This is a sorting problem. Unfortunately, though, you have to somehow turn "cards" into
something on which you can sort. Here are three approaches that you can take. I took
the first of these when I solved the problem, but they are all valid solutions.
Solution #1: Convert Cards to Integers and Use a Map
My first step was to turn the string into a vector of
twocharacter strings, so that I could simply focus on these. I used the substr() method
to do this. For example the first string:
"HAH2H3C4D5ST"  becomes  { "HA", "H2", "H3", "C4", "D5", "ST" }.
Next, I took each string in the vector, and turned it into an integer.
I used two helper strings for this:
string suit = "CDHS";
string rank = "23456789TJQKA";

I used the find() method of these strings to convert each card's suit into a number between 0
and 3, and each card's rank into a number between 0 and 12.
I then multiplied the suit by 13 and added
the rank. For example, the two of clubs is 0, the three of clubs is 1, and the two of diamonds is
13.
Next, I used a map whose keys were integers and whose vals were strings, and I inserted the
integer/card into the map. At the end, I traversed the map and created the return string.
Solution #2: Enumerate the possible cards in order
Because the number of possible cards is so small (52), you can simply enumerate the cards in
order, and then test to see if each card is in the string. To do this, I used the same two
helper strings above, and then a doublynested for loop to create each card. I
created each card as a string, and then used the find() method of strings to see
if the card was in the original string. If so, I added the card to the return string.
As you can see, this solution requires no map and no sorting. It may not be the most efficient
in the world, but the constraints of the problem are so small that it doesn't matter.
Solution #3: Convert the cards to integers, sort the integers, and convert back
This solution is similar to the first one, but you don't need to create a vector of strings
or a map. Instead, you can traverse the input string two characters at a time, converting
each pair of characters to an integer. Push each integer onto a vector, and then sort the
vector. Then, traverse the vector, and convert each integer back to a suit character and
a rank character, and add them to the return string.