Sorting a hand with one move

By Laurent Lessard

This problem was posed on Friday Oct 26, 2018 on the Riddler blog. Here is a paraphrased version of the problem statement:

You play so many card games that you’ve developed a very specific organizational obsession. When you’re dealt your hand, you want to organize it such that the cards of a given suit are grouped together and, if possible, such that no suited groups of the same color are adjacent. (Numbers don’t matter to you.) Moreover, when you receive your randomly ordered hand, you want to achieve this organization with a single motion, moving only one adjacent block of cards to some other position in your hand, maintaining the original order of that block and other cards, except for that one move.

Suppose you’re playing pitch, in which a hand has six cards. What are the odds that you can accomplish your obsessive goal? What about for another game, where a hand has N cards, somewhere between 1 and 13?

This solution solves two different interpretations of the problem. While it's generally forbidden to have two cards of a different suit next to each other if they are the same color, what do we do when it's unavoidable? i.e. our hand consists of one heart and one diamond, so no matter what we do, they will always end up adjacent.

  1. Interpretation 1: allow this case because it's unavoidable. So the hand (heart,diamond) is considered sorted, but the hand (heard,diamond,spade) is considered unsorted. This interpretation means that every hand is sortable.

  2. Interpretation 2: disallow this case. So the hand (heart,diamond) is considered unsorted and can never be sorted.

Depending on the interpretation we use (governed by the flag ALLOW_DUPLICATES_IF_UNAVOIDABLE), this tells us which case we're solving.

In [80]:
using Combinatorics, PyPlot
In [89]:
SUITSIZE = 13
MAX_HAND_SIZE = 13

ALLOW_DUPLICATES_IF_UNAVOIDABLE = true

memo_good = Dict()
memo_goodable = Dict()
memo_hand = Dict()
deck = [ repeat([:c],SUITSIZE); repeat([:d],SUITSIZE); repeat([:h],SUITSIZE); repeat([:s],SUITSIZE) ]
;
In [90]:
function cuthand( hand, cut, target )
    # cut is a triplet (a,b,c) that says that (a,b) gets swapped with (b,c)
    target[:] = hand[:]
    target[ cut[1]:cut[3]-1 ] = [ hand[cut[2]:cut[3]-1] ; hand[cut[1]:cut[2]-1] ]
end

function shortenhand!( hand )
    # shorten a hand by removing adjacent duplicates
    markedind = []
    for i = 2:length(hand)
        if hand[i-1] == hand[i]
            push!(markedind,i)
        end
    end
    deleteat!(hand,markedind)
end

function isgood( hand )
    # is a hand in a legal sorted order?
    # assume hand has already been shortened as much as possible
    
    # memoisation: don't do more work than you have to!
    if get(memo_good,hand,"new_item") != "new_item"
        return memo_good[hand]
    else
        # suit duplicated (bad!)
        if count( hand .== :c ) > 1 || count( hand .== :d ) > 1 || count( hand .== :h ) > 1 || count( hand .== :s) > 1
            memo_good[hand] = false
            return false
        end
        
        if ALLOW_DUPLICATES_IF_UNAVOIDABLE
            # if you have a black card (spade or club) in hand, you can't have a heart next to a diamond.
            if :s in hand || :c in hand
                for i = 2:length(hand)
                    if hand[i-1:i] in ([:h,:d],[:d,:h])
                        memo_good[hand] = false
                        return false
                    end
                end
            end
            # if you have a red card (heart or diamond) in hand, you can't have a spade next to a club.
            if :h in hand || :d in hand
                for i = 2:length(hand)
                    if hand[i-1:i] in ([:s,:c],[:c,:s])
                        memo_good[hand] = false
                        return false
                    end
                end
            end
        else # heart next to diamond or spade next to club is ALWAYS bad in this case
            for i = 2:length(hand)
                if hand[i-1:i] in ([:h,:d],[:d,:h],[:s,:c],[:c,:s])
                    memo_good[hand] = false
                    return false
                end
            end
        end 
        memo_good[hand] = true
        return true
    end
end

function isgoodable( hand )
    if get(memo_goodable, hand, "new_item") != "new_item"
        return memo_goodable[hand]
    else    
        N = length(hand)
        # if the hand is already good, then it's clearly goodable
        if isgood(hand)
            memo_goodable[hand] = true
            return true
        end
        # no hope for a hand that has 8 or more cards
        if length(hand) >= 8
            memo_goodable[hand] = false
            return false
        end
        for cut in combinations(1:N+1,3)
            target = copy(hand)
            cuthand( hand, cut, target )
            shortenhand!(target)
            if isgood(target)
                memo_goodable[hand] = true
                return true
            end
        end
        memo_goodable[hand] = false
        return false
    end
end
            
permcount = [ length(permutations(1:SUITSIZE,ct)) for ct in 0:SUITSIZE ]

function handweight(hand)
    # compute the weight we should associate with a given hand
    s,h,c,d = count( hand .== :s ),count( hand .== :h ),count( hand .== :c ),count( hand .== :d )
    cts = [s,h,c,d]
    sort!(cts)
    if get(memo_hand, cts, "new_item") != "new_item"
        return memo_hand[cts]
    else
        memo_hand[cts] = permcount[s+1] * permcount[h+1] * permcount[c+1] * permcount[d+1]
        return memo_hand[cts]
    end
end      

function evaluategame(handsize)
    # assemble all possible hands and shorten them
    # for each hand, retrieve all possible moves. if any are good, mark hand as good.
    num,den = BigInt(0),BigInt(0)
    for hand in multiset_permutations(deck, handsize)
        wt = handweight(hand)
        shortenhand!(hand)
        den += wt
        if isgoodable(hand)
            num += wt
        end
    end
    num,den
end
;
In [91]:
nums = []
dens = []
props = []
handsizes = 1:MAX_HAND_SIZE
for handsize = handsizes
    println(handsize)
    num,den = @time evaluategame(handsize)
    push!(nums,num)
    push!(dens,den)
    push!(props,convert(Float64,num/den))
end
1
  0.670090 seconds (600.81 k allocations: 26.201 MiB, 10.03% gc time)
2
  0.000723 seconds (874 allocations: 517.438 KiB)
3
  0.001102 seconds (3.94 k allocations: 1.776 MiB)
4
  0.055148 seconds (19.20 k allocations: 6.448 MiB, 94.55% gc time)
5
  0.079001 seconds (133.45 k allocations: 27.176 MiB, 65.45% gc time)
6
  0.390616 seconds (853.95 k allocations: 122.451 MiB, 74.72% gc time)
7
  1.679665 seconds (4.51 M allocations: 542.637 MiB, 72.00% gc time)
8
  3.386861 seconds (2.90 M allocations: 1.231 GiB, 83.83% gc time)
9
 16.011125 seconds (13.79 M allocations: 4.892 GiB, 82.20% gc time)
10
 43.108588 seconds (59.81 M allocations: 19.528 GiB, 74.38% gc time)
11
136.019208 seconds (251.39 M allocations: 78.154 GiB, 66.02% gc time)
12
587.881908 seconds (990.19 M allocations: 311.159 GiB, 70.59% gc time)
13
2437.045203 seconds (4.09 G allocations: 1.217 TiB, 63.63% gc time)
In [94]:
figure(figsize=(13,5))
bar(handsizes,props, tick_label=1:MAX_HAND_SIZE)
grid()
xlabel("hand size")
ylabel("probability")
if ALLOW_DUPLICATES_IF_UNAVOIDABLE
    title("Probability that a hand can be sorted in one move (adjacent same-color different-suit permitted only if unavoidable)")
else
    title("Probability that a hand can be sorted in one move (adjacent same-color different-suit is never permitted)")
end
for (i,p) in enumerate(props)
    annotate("$(round(p,digits=5))",(handsizes[i],p+0.01),ha="center")
end
xlim([0.4,13.6])
tight_layout()
savefig("hand_sort_updated.png")
In [97]:
# print out the probabilities and exact reduced fraction
[ handsizes props nums.//dens ]
Out[97]:
13×3 Array{Any,2}:
  1  1.0                   1//1             
  2  1.0                   1//1             
  3  1.0                   1//1             
  4  1.0                   1//1             
  5  0.852417         213019//249900        
  6  0.608892          51083//83895         
  7  0.373213       33606799//90047300      
  8  0.201846       29210911//144718875     
  9  0.0986108     133194539//1350709500    
 10  0.0443227     367755247//8297215500    
 11  0.0185895   22673450197//1219690678500 
 12  0.00735592   1751664923//238130084850  
 13  0.00277031  30785713171//11112737293000
In [98]:
# print out numerator and denominator
[ handsizes nums dens ]
Out[98]:
13×3 Array{Any,2}:
  1                    52                      52
  2                  2652                    2652
  3                132600                  132600
  4               6497400                 6497400
  5             265847712               311875200
  6            8925221760             14658134400
  7          251647710912            674274182400
  8         6124476443904          30342338208000
  9       131651613460224        1335062881152000
 10      2544466191531264       57407703889536000
 11     44821601899835904     2411123563360512000
 12    727176927343426560    98856066097780992000
 13  10954472929065768960  3954242643911239680000
In [ ]: