Teaser 3093: Shout snap!
From The Sunday Times, 2nd January 2022 [link] [link]
My grandson and I play a simple card game. We have a set of fifteen cards on each of which is one of the words ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, SHOUT and SNAP. We shuffle the cards and then display them one at a time. Whenever two consecutive cards have a letter of the alphabet occurring on both we race to shout “Snap!”. In a recent game there were no snaps. I counted the numbers of cards between the “picture-cards” (J, Q, K) and there was the same number between the first and second picture-cards occurring as between the second and third. Also, the odd-numbered cards (3, 5, 7, 9) appeared in increasing order during the game.
In order, what were the first six cards?
[teaser3093]
Brian Gladman, and 
NigelR are discussing. 
Hugh+Casement and 
Tony Brooke-Taylor, 
galoisest are discussing. 
GeoffR, 
Frits are discussing. 
S2T2 
Jim Randell 4:48 pm on 30 December 2021 Permalink |
The following Python 3 program runs in 478ms.
Run: [ @replit ]
from enigma import subsets, intersect, join, printf # the cards cards = "ACE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN JACK QUEEN KING SHOUT SNAP".split() # which cards snap? snap = set() for (x, y) in subsets(cards, size=2): if intersect([x, y]): snap.update([(x, y), (y, x)]) # generate sequences with no snaps def generate(cards, xs=[], pics=[], subseq=None): # are we done? if not cards: yield xs else: # choose the next card for (i, x) in enumerate(cards): if xs and (x, xs[-1]) in snap: continue # check subsequence cards appear in order ss = subseq if x in subseq: if x != subseq[0]: continue ss = ss[1:] # check picture cards appear equally distanced ps = pics if x in {'JACK', 'QUEEN', 'KING'}: ps = ps + [len(xs)] if len(ps) == 3 and ps[2] - ps[1] != ps[1] - ps[0]: continue # solve for the remaining cards yield from generate(cards[:i] + cards[i + 1:], xs + [x], ps, ss) # find solutions for ss in generate(cards, subseq=['THREE', 'FIVE', 'SEVEN', 'NINE']): printf("{ss}", ss=join(ss, sep=" "))Solution: The first six cards were: EIGHT, SNAP, THREE, KING, ACE, SHOUT.
And the full sequence is:
There are 4 cards between KING and QUEEN, and 4 cards between QUEEN and JACK.
LikeLike
NigelR 3:50 pm on 31 December 2021 Permalink |
A typical brute force approach from me. It is neither pretty nor quick, but it gets the job done (eventually!). I could probably have mined a bitcoin using less processing effort.
# STBT 3093 from itertools import permutations as perm cards=['ACE','TWO','THREE','FOUR','FIVE','SIX', 'SEVEN', 'EIGHT', 'NINE', 'TEN', 'JACK', 'QUEEN', 'KING','SHOUT','SNAP'] oddnums=['THREE','FIVE','SEVEN','NINE'] odds=[] evens=[] def oddtest(self): #test self for numbers 3-9 in correct sequence ind = [self.index(z) for z in oddnums] for z in range(0,3): if ind[z]>ind[z+1]:return False return True def pictest(): #test picture cards for consistent spacing j,q,k=seq.index('JACK'),seq.index('QUEEN'),seq.index('KING') if q<j and q<k:return False #Q must be between J & K for equal spacing since q is an even and other two are odds if q>j and q>k:return False if abs(q-j)!=abs(k-q): return False #check for equal spacing return True def seqtest(): #test seq for no shared letters in adjacent cards for i in range(0,14): for z in seq[i]: if z in seq[i+1]:return False return True seq=cards evens=[x for x in cards if 'E' in x] # there are 8 cards with letter E, so can only be placed on even slots to avoid adjacency odds=[x for x in cards if x not in evens] for x in list(perm(evens)): if not oddtest(x): continue for y in list(perm(odds)): for i in range(0,8): seq[i*2]=x[i] for i in range(1,8): seq[(2*i)-1]=y[i-1] if not pictest():continue if not seqtest():continue print ('The first six cards drawn in order were:',seq[0:6])LikeLike
Jim Randell 10:54 am on 2 January 2022 Permalink |
My first program was quite slow too. I generated all sequences without a “snap” and then applied the remaining conditions.
To improve the speed I moved the conditions inside the [[
generate()]] function, and that got the code down to running in less than a second.Your observation that there are 8 cards with an E, and 7 cards without (so they must be interleaved, starting with an E), speeds up my code to 287ms.
We replace line 20 in my program with:
if xs: # can't snap with the previous card if (x, xs[-1]) in snap: continue else: # first card must have an E if not ('E' in x): continueLikeLike
Brian Gladman 4:37 pm on 4 January 2022 Permalink |
@Jim I went down exactly the same path and arrived at a close to identical solution to your own.
I missed the significance of cards with ‘E’s until it was pointed out here and this provides a major improvement in performance.
If I add this to your version after line 18:
pos_even = not (len(xs) & 1)and this after line 20:
if pos_even and 'E' not in x: continuethe run time for me (using profile )drops by a factor of over 20.
LikeLike
Jim Randell 9:51 pm on 4 January 2022 Permalink |
Using the observation that the “with E” and “without E” sets of cards must be interleaved allows us to go back to the simpler approach where we generate (interleaved) sets of cards, and then check them for the remaining conditions, and still have the program run in a short time.
from enigma import (cproduct, intersect, filter2, join, printf) # the cards cards = "ACE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN JACK QUEEN KING SHOUT SNAP".split() # partition the cards into 2 sets (cs1, cs2) = filter2((lambda x: 'E' in x), cards) assert len(cs1) == len(cs2) + 1 # which cards snap? snap = set() for (x, y) in cproduct([cs1, cs2]): if intersect([x, y]): snap.update([(x, y), (y, x)]) # generate sequences with no snaps, interleaving cs1 and cs2 def generate(cs1, cs2, xs=[]): # are we done? if not cs1: yield xs else: # choose the next card for (i, x) in enumerate(cs1): if xs and (x, xs[-1]) in snap: continue # solve for remaining cards yield from generate(cs2, cs1[:i] + cs1[i + 1:], xs + [x]) # find solutions for ss in generate(cs1, cs2): pos = lambda x: ss.index(x) # check THREE, FIVE, SEVEN, NINE appear in order if not (pos('THREE') < pos('FIVE') < pos('SEVEN') < pos('NINE')): continue # check JACK, QUEEN, KING are evenly spaced (i, j, k) = sorted(pos(x) for x in ['JACK', 'QUEEN', 'KING']) if not (j - i == k - j): continue # output solution printf("{ss}", ss=join(ss, sep=" "))LikeLike