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.
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.
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.
using Combinatorics, PyPlot
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) ]
;
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
;
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)
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")
# print out the probabilities and exact reduced fraction
[ handsizes props nums.//dens ]
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
# print out numerator and denominator
[ handsizes nums dens ]
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