PROBLEM STATEMENT
Implement a class Bridge with a method minSort to determine how easily a Bridge
hand can be sorted. A Bridge hand is a set of 13 cards from a standard 52-card
deck. minSort returns the fewest number of insertions required to perform an
insertion sort subject to certain restrictions.
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
2,3,4,5,6,7,8,9,T,J,Q,K,A). '2' is the lowest rank and 'A' is (always) the
highest rank. Each card can be represented with two characters. The first
character corresponds to the rank of the card and the second character
corresponds to the (first letter of the) suit. An example of an unsorted
bridge hand is "AD,AS,3C,AC,8S,JH,4H,4D,9D,2S,JD,5D,TD".
A bridge hand is sorted if and only if the following conditions are met:
* All cards of each suit are together.
* The cards of each suit must be in ascending order defined by
(2,3,4,5,6,7,8,9,T,J,Q,K,A) with '2' being the lowest and 'A' being the highest.
* Suits must alternate between the red suits (diamonds and hearts) and the
black suits (clubs and spades), with either color coming first. Exception: if
ALL the cards are the same color, diamonds and hearts may be adjacent or clubs
and spades may be adjacent.
* The minor suits (clubs and diamonds) must come before the major suits (hearts
and spades).
For example, if all four suits are present, the only possible orders of suits
allowed are [clubs, diamonds, spades, hearts] and [diamonds, clubs, hearts,
spades]. Some example sorted bridge hands are
"2C,3C,4C,5C,6C,7C,8C,9C,TC,JC,QC,KC,AC",
"2C,3C,4C,5C,6C,7C,8C,5H,6H,7H,8H,9H,KH", and
"2C,5C,8C,9C,4D,5D,TD,9S,TS,QS,KS,AS,7H". Note that the last hand could also
be sorted as "4D,5D,TD,2C,5C,8C,9C,7H,9S,TS,QS,KS,AS".
An insertion is defined as removing a single card from a bridge hand, followed
by reinsering it at a different position in the hand, preserving the order of
the other cards. For example "3C,4C,5C,6C,7C,8C,2C,9C,TC,JC,QC,KC,AC" requires
one insertion to be sorted: remove the "2C" and reinsert it at the beginning of
the hand.
DEFINITION
Class Name: Bridge
Method Name: minSort
Parameters: String
Returns: int
Method signature (be sure your method is public): int minSort(String hand);
String hand is of the form: "CS,CS,CS,CS,CS,CS,CS,CS,CS,CS,CS,CS,CS" (no
spaces). 'C' represents a card-rank and 'S' represents a suit. All cards are
valid and unique. These conditions will be checked.
Return value:
Return the minimum number of insertions needed to sort the input bridge hand.
EXAMPLES
- "AD,AS,3C,AC,8S,JH,4H,4D,9D,2S,JD,5D,TD", minSort should return 8
- "8D,8S,TS,QD,6S,9S,AH,8C,TD,2H,4D,2S,KC", minSort should return 8
- "JD,QD,KD,2S,4S,6S,JS,3H,5H,8H,9H,TH,JH", minSort should return 0
- "AC,TS,TD,JC,6D,4H,4S,JH,TC,2S,AD,7D,AH", minSort should return 8
- "8C,6D,QD,9S,9C,AH,QS,JC,2D,AC,3H,7S,5C", minSort should return 6
- "5C,7D,6H,9H,2C,AD,3H,TS,6D,TH,6C,KD,KH", minSort should return 7
- "JC,9S,3C,8S,QC,7C,5S,AS,2H,AC,6C,3S,KH", minSort should return 9
- "AS,4D,QS,QC,6H,2C,QD,9C,6S,4C,3H,QH,AD", minSort should return 8
- "2S,TC,5H,TD,3H,5D,7C,QC,4H,AC,JS,9D,8S", minSort should return 8