Brain-Teaser 879: Seven criminals
From The Sunday Times, 11th June 1978 [link]
The instructor at the police training college spoke to the six constables in his class in these words:
“You have been studying full-face photographs of seven criminals whom we are calling P, Q, R, S, T, U and V. Now l am going to show you one photograph, taken in profile, of each criminal, and you have to write down their names in the
order in which I present them.”This was done and the constables handed in the following
six answers:1. P Q R S T U V
2. P Q R U T S V
3. P S U V R T Q
4. P S Q U R T V
5. P U R V T S Q
6. R P U Q T S V“I am pleased to see that each criminal has been correctly identified by at least one of you”, said the instructor. “And I note that you all have a different number of correct answers and so I can give out the prizes”.
In what order were the photographs presented?
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.
[teaser879]
Frits are discussing. 
Jim Olson and 
Tony Brooke-Taylor, 
GeoffR, and 
John Crabtree, and 
Hugh Casement, and 
S2T2 
Jim Randell 7:16 am on 14 October 2021 Permalink |
It is straightforward to check all possible arrangements.
This Python program runs in 87ms.
Run: [ @replit ]
from enigma import subsets, seq_all_different, join, printf # the six answers ans = [ 'PQRSTUV', 'PQRUTSV', 'PSUVRTQ', 'PSQURTV', 'PURVTSQ', 'RPUQTSV', ] # count number of items in correct position correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys)) # consider possible orderings for ss in subsets('PQRSTUV', size=len, select="P"): # how many are in the correct position? pos = list(correct(xs, ss) for xs in ans) if not seq_all_different(pos): continue # check each item is correct in one of the answers if not all(any(xs[i] == x for xs in ans) for (i, x) in enumerate(ss)): continue # output solution printf("{ss} -> {pos}", ss=join(ss, sep=" ", enc="()"))Solution: The photographs were presented in the following order: R, P, U, V, T, S, Q.
And the number of photographs correctly identified by the constables were: 1, 2, 3, 0, 4, 5.
There is only a single solution without the condition that each criminal was identified correctly by (at least) one of the constables. But we see that the last constable got Q and V wrong (and the rest right), but the penultimate constable got these two right, so each miscreant was identified correctly by one of the constables.
LikeLike
Frits 10:12 am on 15 October 2021 Permalink |
Borrowing from above program and the solve() function in Teaser 3080 (One of a kind).
The program runs in 2ms.
# find members of each set, such that each member is used exactly once def solve(ss, ns=[], ds=set()): # are we done? if not(ss): yield ns else: # choose an element from the next set for n in ss[0]: if not(ds.intersection(n)): yield from solve(ss[1:], ns + [n], ds.union(n)) # count number of items in correct position correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys)) # the six answers ans = [ 'PQRSTUV', 'PQRUTSV', 'PSUVRTQ', 'PSQURTV', 'PURVTSQ', 'RPUQTSV', ] nr_criminals = len(ans[0]) nr_answers = len(ans) # make list of used values lst = [set(a[i] for a in ans) for i in range(nr_criminals)] for ss in solve(lst): pos = set(correct(xs, ss) for xs in ans) if len(pos) != nr_answers: continue print(f"{', '.join(ss)} --> {pos}")LikeLike
Jim Randell 2:57 pm on 15 October 2021 Permalink |
You can use the following to turn a collection of rows into the corresponding collection of columns:
(And [[
unzip()]] is an alias for this in enigma.py).We can also simplify the way the [[
solve()]] function operates. (I’ve renamed it [[select()]]).from enigma import unzip, seq_all_different, join, printf # the six answers ans = [ 'PQRSTUV', 'PQRUTSV', 'PSUVRTQ', 'PSQURTV', 'PURVTSQ', 'RPUQTSV', ] # select distinct elements from each set in list of sets <ss> def select(ss, rs=[]): # are we done? if not ss: yield rs else: for x in ss[0].difference(rs): yield from select(ss[1:], rs + [x]) # count number of items in correct position correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys)) # each photograph was identified correctly in at least one answer # so the the correct value occurs in each column # consider possible correct orderings for ss in select(list(set(col) for col in unzip(ans))): # how many are in the correct position? pos = list(correct(xs, ss) for xs in ans) if not seq_all_different(pos): continue # output solution printf("{ss} -> {pos}", ss=join(ss, sep=" ", enc="()"))I did try a version of [[
select()]] that chooses from the column with the smallest number of values available, but it is no advantage on a problem of this size.LikeLike