Teaser 3273: A good deal?
From The Sunday Times, 15th June 2025 [link] [link]
Delia plays a game with a stack of different pieces of card. To shuffle the stack she deals them quickly into four equal piles (face-downwards throughout) — the top card starts the first pile, the next card starts the second pile, then the third starts the third pile and likewise the fourth. She continues to place the cards on the four piles in order. Then she puts the four piles back into one big stack with the first pile on the bottom, the second pile next, then the third, with the fourth pile on the top.
She is very pleased with her shuffling method because each card moves to a different position in the stack, so she decides to repeat the shuffle a few more times. However, this is counter-productive because after fewer than six such shuffles the cards will be back in their original order.
How many cards are in her stack?
There are now 1200 Teaser puzzles available on the S2T2 site.
[teaser3273]
Frits and 
Ruud and 
Hugo, 
John Crabtree are discussing. 
S2T2 
Jim Randell 7:00 am on 15 June 2025 Permalink |
See also: Enigma 710, Teaser 2446.
This Python program runs in 69ms. (Internal runtime is 328µs).
from enigma import (irange, inf, flatten, rev, printf) # perform a shuffle using <p> piles def shuffle(cs, p=4): return rev(flatten(cs[i::p] for i in irange(p))) # find when cards return to original order def solve(cs, fn, M=inf): cs0 = list(cs) for k in irange(1, M): cs = fn(cs) if cs == cs0: return k # consider sets of cards for n in irange(8, inf, step=4): cs = list(irange(1, n)) # check the shuffle leaves no card in its original position if any(x == y for (x, y) in zip(cs, shuffle(cs))): continue # find number of shuffles (< 6) to return to original order k = solve(cs, shuffle, 5) if k is None or k < 3: continue # output solution printf("{n} cards -> {k} shuffles") break # stop at first solutionSolution: There are 52 cards in the stack.
And the stack returns to the original order after 4 shuffles. (This can be verified with a standard pack of cards).
LikeLike
Jim Randell 11:26 am on 15 June 2025 Permalink |
Alternatively (shorter, and doesn’t do any unnecessary shuffles):
from enigma import (irange, inf, flatten, rev, repeat, cachegen, peek, printf) # perform a shuffle using <p> piles def shuffle(cs, p=4): return rev(flatten(cs[i::p] for i in irange(p))) # consider sets of cards for n in irange(8, inf, step=4): cs = list(irange(1, n)) # generate the result of repeated shuffles ss = cachegen(repeat(shuffle, cs)) # check shuffle 1 leaves no card in its original position if any(x == y for (x, y) in zip(ss(1), cs)): continue # find number of shuffles (2 .. 5) to return to original order k = peek((k for k in irange(2, 5) if ss(k) == cs), default=-1) if k < 2: continue # output solution printf("{n} cards -> {k} shuffles") break # stop at first solutionThe [[
cachegen()]] function has been in enigma.py for a while, waiting for a use to come up.LikeLike
Jim Randell 1:56 pm on 16 June 2025 Permalink |
Here is a neat alternative approach.
It analyses the cycle representation of the permutation that represents the shuffle, to determine the number of shuffles required to return to the original order, without needing to actually perform the shuffles.
It has an internal runtime of 286µs.
from enigma import (irange, inf, flatten, rev, cycles, mlcm, printf) # perform a shuffle using <p> piles def shuffle(cs, p=4): return rev(flatten(cs[i::p] for i in irange(p))) # consider sets of cards for n in irange(8, inf, step=4): cs = list(irange(1, n)) # find the length of cycles in a shuffle cycs = set(len(cyc) for cyc in cycles(shuffle(cs), cs)) # there are no 1-cycles if 1 in cycs: continue # calculate the number of shuffles to return to the original order k = mlcm(*cycs) if k < 6: printf("{n} cards -> {k} shuffles") break # stop at the first solutionLikeLiked by 1 person
Frits 10:28 am on 15 June 2025 Permalink |
Also printing the first solution.
# Delia's shuffle algorithm for cards <s> def shuffle(s, ln): # make 4 piles (4th pile first) s_ = [[s[i] for i in reversed(range(ln)) if i % 4 == (3 - j)] for j in range(4)] # put the 4 piles back into one big stack with the 1st pile on the bottom return [y for x in s_ for y in x] for m, _ in enumerate(iter(bool, 1), 1): # infinite loop, starting from 1 n = m * 4 # number of cards in the stack orig, new = list(range(n)), [] # Delia shuffles for the first time new = shuffle(orig, n) # each card moves to a different position in the stack if any(new[i] == i for i in range(n)): continue shuffle_count = 1 # Delia shuffles a few more times (meaning more than once) while new != orig and shuffle_count < 6: new = shuffle(new, n) shuffle_count += 1 if 2 < shuffle_count < 6: print(f"answer: {n} (first solution)") breakLikeLike
Frits 10:50 am on 15 June 2025 Permalink |
The program prints the expected answer.
The way I read the teaser there is another solution (allowing to already return back to the original order after two shuffles).
LikeLike
Jim Randell 11:07 am on 15 June 2025 Permalink |
I considered this, but decided the phrase “a few more times” excludes the possibility of just 1 additional shuffle reverting the original stack.
LikeLike
Frits 11:21 am on 15 June 2025 Permalink |
I see. I regard this as an additional requirement. I can’t determine that for sure from the puzzle text.
Delia will not check the cards after each shuffle so in my opinion nothing is to be excluded.
LikeLike
Frits 9:57 am on 16 June 2025 Permalink |
Using a dictionary
# Delia's shuffle algorithm for cards <s> using a dictionary dct = lambda s: dict(enumerate(sum((s[i::4] for i in range(4)), [])[::-1])) shuffle = lambda s: [d[x] for x in s] # infinite loop, starting from 2 (avoiding trivial case of four cards) for m, _ in enumerate(iter(bool, 1), 2): n = m * 4 # number of cards in the stack # dictionary of position changes d = dct(orig := list(range(n))) # Delia shuffles for the first time new = shuffle(orig) # each card moves to a different position in the stack if any(new[i] == i for i in range(n)): continue shuffle_count = 1 # Delia shuffles a few more times while new != orig and shuffle_count < 6: new = shuffle(new) shuffle_count += 1 if shuffle_count < 6: print(f"answer: {n} (first solution after trivial case n=4)") breakor using map()
# Delia's shuffle algorithm for cards <s> using a dictionary shuffle = lambda s: sum((s[i::4] for i in range(4)), [])[::-1] # infinite loop, starting from 2 (avoiding trivial case of four cards) for m, _ in enumerate(iter(bool, 1), 2): n = m * 4 # number of cards in the stack # Delia shuffles for the first time s1 = shuffle(orig := list(range(n))) # each card moves to a different position in the stack if any(s1[i] == i for i in range(n)): continue new = s1 shuffle_count = 1 # Delia shuffles a few more times while new != orig and shuffle_count < 6: new = list(map(lambda x: s1[x], new)) shuffle_count += 1 if shuffle_count < 6: print(f"answer: {n} (first solution after trivial case n=4)") breakLikeLike
Jim Randell 4:31 pm on 16 June 2025 Permalink |
@Frits: I can’t recommend the (ab)use of [[
sum()]] for joining lists. As a quick hack it may be acceptable to save a bit of typing, but the behaviour of [[sum()]] is only defined for numeric types, so it may not work at all (in CPython strings are explicitly rejected). And if it does work, it uses an inefficient algorithm for sequences (constructing a new sequence at each intermediate stage).I would recommend using [[
enigma.flatten]] (or [[itertools.chain]]) instead.LikeLike
Frits 12:03 pm on 19 June 2025 Permalink |
A more efficient version. Instead of always shuffling the whole stack of cards we keep track of the position of only one specific card.
flat = lambda group: [x for g in group for x in g] # Delia's shuffle algorithm for cards <s> using a dictionary shuffle = lambda s: flat(s[i::4] for i in range(4))[::-1] # determine new position of number at position <i> # in a sequence of 4 * m numbers shuffle1 = lambda i, m: m * (4 - i % 4) - i // 4 - 1 # check when number 1 will return to position 1 again (numbers 0...n-1) # infinite loop, starting from 2 (avoiding trivial case of four cards) for m, _ in enumerate(iter(bool, 1), 2): n = m * 4 # number of cards in the stack new, cnt = 1, 1 while cnt < 6: # shuffle one card (let's say the 2nd card) new = shuffle1(new, m) cnt += 1 # shuffle the whole stack if new == 1: # Delia shuffles for the first time s1 = shuffle(orig := list(range(n))) # each card moves to a different position in the stack if any(s1[i] == i for i in range(n)): break new, shuffle_count = s1, 1 # Delia shuffles a few more times while new != orig and shuffle_count < 6: new = list(map(lambda x: s1[x], new)) shuffle_count += 1 if shuffle_count < 6: print(f"answer: {n} (first solution after trivial case n=4)") exit(0) breakLikeLike