# 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
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 [ ]: