# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1037: The perfect shuffle

From New Scientist #2193, 3rd July 1999 [link]

I recently took an ordinary pack of playing cards and placed them on the table, face down. Somewhere in the pack the four aces were together, and in places further down the kings were together, the queens were together, and the jacks were together.

I then did the “perfect shuffle”. In other words I took the top 26 cards in my left hand, and the other 26 in my right, I flicked the bottom left-hand card on to the table, followed by the bottom right-hand card on top of it, followed by the next left on top of them, next right, next left, and so on. The cards remained face down at all times.

My fellow players were so impressed with this performance that I did three more perfect shuffles with the same pack. When I had finished, the arrangement of suits within the pack was exactly the same as when I started (for example, the top card was a heart before and after the four shuffles, the next was a spade before and after the four shuffles, and so on).

Counting from the top, what was the position of the ace of hearts after the four shuffles?

[enigma1037]

### One response to “Enigma 1037: The perfect shuffle”

1. Jim Randell 9 November 2018 at 8:13 am

Programatically it’s a bit tricky to come up with a general program, and as it turns out the full generality is not needed to solve this puzzle. (See the manual solution below).

This Python program runs in 73ms.

Run: [ @repl.it ]

from itertools import product, combinations
from enigma import flatten, irange, find, update, tuples, arg, printf

def interleave(*s):
return flatten(zip(*s))

def shuffle(pack):
n = len(pack) // 2
return list(interleave(pack[n:], pack[:n]))

# original pack, top card = 0, bottom card = 51
pack = list(irange(0, 51))

# suffle the pack n times
n = arg(4, 0, int)
p = pack
for _ in irange(1, n):
p = shuffle(p)

# associate suits with cards (order is the same in p and pack)
def associate(p):

suit = [None] * 52

def associate(i, s):
while suit[i] is None:
suit[i] = s
i = p[i]
assert suit[i] == s

# initial assignments:
initial = [
# current card 0 is a heart
(0, 'H'),
# original card 0 is a heart
(p.index(0), 'H'),
# current card 1 is a spade
(1, 'S'),
# original card 1 is a spade
(p.index(1), 'S'),
]
for (i, s) in initial:
associate(i, s)

# now fill in remaining values
v = 1
while True:
i = find(suit, None)
if i == -1: break
associate(i, v)
v += 1

# count the number of cards for each value
vs = set(suit)
d = dict((v, suit.count(v)) for v in vs)

# available suits
suits = set('CDHS')
for s in 'HS':
if d[s] == 13:

# and assign the values to suits
vs = list(vs)
for ss in product(suits, repeat=len(vs)):
# count cards in assigned suits
_d = dict((s, d.get(s, 0)) for s in suits)
for (v, s) in zip(vs, ss):
_d[s] += d[v]
if not all(x == 13 for x in _d.values()): continue

# return a suit assignment
r = suit
for (v, s) in zip(vs, ss):
r = update(r, list(i for (i, x) in enumerate(r) if x == v), [s] * d[v])
yield r

# associate suits to the shuffed pack
for suit in associate(p):
# find locations where each of the 4 suits occur next to each other
js = list(j for (j, s) in enumerate(tuples(suit, 4)) if len(set(s)) == 4)
# choose 4 locations for the A, K, Q, J cards in the original pack,
# A comes first and we don't really care what order the K, Q, J are in
for (A, K, Q, J) in combinations(js, 4):
# check they do not overlap
if not(A + 3 < K and K + 3 < Q and Q + 3 < J): continue
# find the ace of hearts
for i in irange(A, A + 3):
if suit[i] == 'H':
# where does card i end up in the suffled pack?
j = p.index(i)
printf("initially AH at index {i}, finally AH at index {j}")

Solution: The Ace of Hearts is the 44th card down in the shuffled pack.

If we number the cards from 1 (top) to 52 (bottom), after 4 shuffles we have the following situation:

(The diagram should really be one long table, with card 1 at the top and card 52 at the bottom. I’ve split it into 4 sections to make it more screen friendly).

The first column gives the final position of the cards, and the second column gives the initial position of the corresponding card.

The third column gives the suits of the cards. The sequence of suits is the same in the shuffled pack as the original pack.

Here is a manual solution:

So we are told the top card of the shuffled pack is a Heart. The top card of the shuffled pack is the 10th card in the original pack, so the 10th card in the shuffled pack must also be a Heart. And the 10th card in the shuffled pack is the 47th card in the original pack, so the 47th card in the shuffled pack must also be a Heart. And so on.

In this way we can mark the cards in positions: 1, 10, 47, 46, 36, 42, 49, 13, 24, 28, 15, 44, 16, as Hearts. And this accounts for all 13 Hearts.

Similarly, the 2nd card in the shuffled pack is a Spade. So we can mark the cards in positions: 2, 20, 41, 39, 19, 31, 45, 26, 48, 3, 30, 35, 32 as Spades. And this accounts for all 13 Spades.

The next card that is not allocated a suit is card 4. As no distinction is made in the puzzle between Clubs and Diamonds we can mark card 4 as a Club, and this leads us to marking cards: 4, 40, 29, 25, 38, 9, 37, 52, 43, 6, 7, 17, 11 as Clubs. This accounts for all 13 Clubs.

Card 5 can then be marked as a Diamond, and this leads to marking the cards: 5, 50, 23, 18, 21, 51, 33, 12, 14, 34, 22, 8, 27 as Diamond. This accounts for all 13 Diamonds.

Now all cards have been assigned a suit (there is a second solution where Clubs and Diamonds are interchanged, but it won’t change the answer to the puzzle).

We can now look for consecutive sequences of cards of length 4 where all suits are represented, and we find the following sequences work:

(16, 17, 18, 19), (23, 24, 25, 26), (24, 25, 26, 27), (25, 26, 27, 28), (26, 27, 28, 29), (27, 28, 29, 30), (34, 35, 36, 37)

And we need 4 non-overlapping sequences. The only possible option is:

(16, 17, 18, 19), (23, 24, 25, 26), (27, 28, 29, 30), (34, 35, 36, 37)

So cards (16, 17, 18, 19) in the original pack are the Aces, and the other three sequences are the Kings, Queens and Jacks.

So the Ace of Hearts was card 16 in the initial pack, and card 16 ends up in position 44 in the shuffled pack, so in the shuffled pack the Ace of Hearts is the 44th card.

This site uses Akismet to reduce spam. Learn how your comment data is processed.