5
$\begingroup$

Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.

A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example

  • ♣QJ3♥K4♠AQ974♦K76 is a sorted hand
  • ♥K4♣QJ3♠AQ974♦K76 is not a sorted hand because the two black suits are touching
  • ♣QJ♥K4♠AQ974♦K76♣3 is not a sorted hand because the clubs are not together
  • ♣3JQ♥K4♠AQ974♦K76 is not a sorted and because the clubs are not sorted in decreasing rank.

The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:

  • A card can be temporarily removed from the hand and inserted back somewhere else. For example the ♣3 in ♣QJ♥K4♠AQ974♦K76♣3 can be inserted after the second card to sort the hand.
  • Any number of consecutive cards can similarly be removed from the hand and inserted back somewhere else. For example the ♣QJ3 in ♥K4♣QJ3♠AQ974♦K76 can be moved to the front. This is considered one move.

What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Fun question! What have you tried? Have you tried heuristic search methods from AI, e.g., uniform cost search, A*, etc.? They won't give you a useful provable upper bound on the running time, but it's possible they might work reasonably well in practice. We want you to make an effort to solve your question before asking and to show us in the question what you've tried or what you've considered. This helps us give you better answers that are more likely to be useful to you. $\endgroup$
    – D.W. ♦
    Jun 16, 2015 at 23:58
  • $\begingroup$ I will try a brute force method for now, pruning which moves I try, but other than that I have no ideas which is why I wanted to ask here. $\endgroup$
    – nmore
    Jun 17, 2015 at 2:02
  • $\begingroup$ It's widely know that insertion sort is the closest to the way humans do sorts. I would guess that the minimum number of edits would be based on the longest common subsequence $\endgroup$
    – o11c
    Jun 17, 2015 at 5:02
  • $\begingroup$ OK, well, I encourage you to take a look at the methods I suggested, try them out, and then edit your question to indicate whether they turn out to be suitable or not. $\endgroup$
    – D.W. ♦
    Jun 17, 2015 at 5:54
  • $\begingroup$ It is a lot more complicated than insertion sort or longest decreasing sub sequence, but it might be a way to decide which suit to start sorting first. I have a feeling that brute force with good pruning of moves is the way to go for now. I will post my solution in the next few days and see if people have improvements. Then once I have something that works I can look at the patterns in the solutions and see if I can find a better solution. $\endgroup$
    – nmore
    Jun 17, 2015 at 6:05

2 Answers 2

Reset to default
3
$\begingroup$

This problem is harder than you might think. Your operation of removing a block of adjacent cards and re-inserting the block somewhere else is known as a transposition. Sorting by transpositions has been studied in the context of bioinformatics and is known to be hard. Of course, if you limit the length to 13 cards, then efficiency becomes much less of a concern--even an exponential algorithm is likely to be fast enough.

I recommend breaking the problem into two related parts. The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N. This may be inefficient, but for small N, should be fast enough.

The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...). There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing. For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13. Then you can call the first part above as a subroutine.

Improve this answer
$\endgroup$
2
  • $\begingroup$ But won't breaking the problem into two parts increase the computational complexity? If we generalize this problem to have n cards and m red and black suits, n cards (now integers) must be sorted at least 4*m! times. My algorithm above tackles both suit and rank constraints at once instead of in two steps. But, maybe I am misunderstanding because sorting the integers is much less complex than sorting the cards with both constraints at once, and can be done much faster. $\endgroup$
    – nmore
    Jun 25, 2015 at 20:22
  • $\begingroup$ Running the subroutine once for every ordering of the suits may or may not increase the overall complexity (in the generalization to 2m suits). It depends on the details of how that subroutine is implemented. For example, if the subroutine uses BFS, as your code seems to do, then you might indeed do better dealing with the different constraints all together. But I suspect that BFS would be space-prohibitive in the generalized setting. $\endgroup$
    – Chris Okasaki
    Jun 26, 2015 at 0:29
1
$\begingroup$

I ended up implementing this with a brute force method while pruning the moves I chose next. From any given hand, I calculated the next possible moves that I should make, and searched the move space like a BFS algorithm. I followed the following rules to weed out candidates for the next moves, which make the algorithm run, even for 26 cards, within a few seconds:

  1. Only consider moves in the forward direction (left to right). This works because if you want to move a card or range backwards, you can move a range of cards forwards to achieve the same state.

  2. Cards that must appear in consecutive order in the sorted hand must be moved together. I used a list of list data structure to model this, and only considered moving groups of cards, with the cards in each group being consecutive in the sorted hand. For example in ♦K♠Q9♦7♠A74(...hearts and clubs), the consecutive groups in the first half of the hand are the following 5: ♦K, ♠Q9, ♦7, ♠A, ♠74.

  3. No moves can cause cards of any suit to get unsorted. For example in ♦K♠Q9♦7♠A74 moving ♦K♠Q9 after ♠A is not considered as a next move since the ♦K was moved passed the ♦7, and is now unsorted. My reasoning is that moving everything except the unsorted cards (i.e. 2 ranges on either side of that card) requires at most the same number of moves as moving the entire range and then moving the unsorted cards back. However, I have not proved this.

  4. Only take moves that minimize the number of previously mentioned consecutive card groups. Only the move ♠Q9 after ♠A in the above hands will be considered in the above hand to minimize the number of groups to 2: ♦K♦7, ♠AQ974. My reasoning was that since no cards are being unsorted (rule 3), the most greedy approach should win every time. However I have not proved this.

  5. If a move consisting of a single suit is moved next to other cards with the same suit, do not consider any similar moves in that suit. For example in ♠23456789TJQKA, only ♠2 after ♠3 will be considered as a next move. ♠2 after ♠4 will not be considered due to rule 4. ♠3 after ♠4 will not be considered since all cards moved are in ♠, end up next to other cards in ♠, and another move like this in ♠ had already been considered. My reasoning is that these moves within the suit will have to be made anyway, and there is no point in considering all permutations at every iteration. However I have not proved this. There are also more optimizations in this class of rule (find equivalently good next hands), but I can't think of one that would have a big impact.

Full Java implementation: http://pastebin.com/4eRX2a1w

Here is a run with 13 random cards (also below): http://pastebin.com/fLz4xRAf

level 0, bfs queue size 0
D H D S C D H S D D C S C 
J 5 5 Q J 8 2 J K A Q 8 3 
level 1, bfs queue size 1
D H D SS D D CC D H S C 
J 5 5 QJ K A QJ 8 2 8 3 
level 2, bfs queue size 23
SS DD H D D CC D H S C 
QJ KJ 5 5 A QJ 8 2 8 3 
level 3, bfs queue size 181
DD H D D CC D H SSS C 
KJ 5 5 A QJ 8 2 QJ8 3 
level 4, bfs queue size 336
DDD H D CC D H SSS C 
AKJ 5 5 QJ 8 2 QJ8 3 
level 5, bfs queue size 687
DDD D CC D HH SSS C 
AKJ 5 QJ 8 52 QJ8 3 
level 6, bfs queue size 632
DDDDD CC HH SSS C 
AKJ85 QJ 52 QJ8 3 

original hand
D H D S C D H S D D C S C 
J 5 5 Q J 8 2 J K A Q 8 3 
move groups 5 to 7 after group 11
D H D SS D D CC D H S C 
J 5 5 QJ K A QJ 8 2 8 3 
move groups 1 to 4 after group 5
DD H D SS D CC D H S C 
KJ 5 5 QJ A QJ 8 2 8 3 
move groups 1 to 4 after group 5
DDD H D SS CC D H S C 
AKJ 5 5 QJ QJ 8 2 8 3 
move groups 3 to 4 after group 6
DDD H CC DD SS H S C 
AKJ 5 QJ 85 QJ 2 8 3 
move groups 3 to 5 after group 6
DDD HH CC DD SSS C 
AKJ 52 QJ 85 QJ8 3 
move groups 2 to 3 after group 5
DDDDD SSS HH CCC 
AKJ85 QJ8 52 QJ3 
sorted in 6 moves
level 6, bfs queue size 595

Here is a run with 26 random cards: http://pastebin.com/Bw8kzfgU

Here is the run with spades in the reverse order: http://pastebin.com/NwAXavxE

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Huge chunks of programming code are unsuitable for this site. The pastebin links are quite enough for interested parties; the core algorithm is better presented with pseudo code. $\endgroup$
    – Raphael ♦
    Jun 25, 2015 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.