New Scientist Enigma 570 – Dead Right
by Susan Denham
From Issue #1723, 30th June 1990
Two friends play a number game related to a popular board-game. Alan thinks of a secret four-figure number (that is, between 1000 and 9999) and Brian has to guess what it is. Each of Brian’s guesses is ‘marked’ by Alan who tells Brian how many of the digits are ‘dead-right’ (that is, correct and in the correct place) and how many others are ‘misplaced’ (that is, correct but in the wrong place). For example if the secret number were 4088 then the guess 4840 would get the marks ‘one dead-right, two misplaced’. Brian has to find the secret number with as few guesses as he can.
In a recent game Brian’s first few guesses and their ‘marks’ were:
First guess: 1234. One dead-right, one misplaced
Second guess: 1355. One dead-right, none misplaced.
Third guess: 1627. None dead-right, one misplaced.
For his fourth guess Brian chose the lowest number which could still be the secret number but it had none dead-right. I forget how many it had ‘misplaced’ but from the marks for the fourth guess Brian was able to work out what the secret number was.
What was it?
-
Brian Gladman permalink1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950from itertools import permutationsfrom collections import defaultdictguesses = (('1234', 1, 1), ('1355', 1, 0), ('1627', 0, 1))# for a number and a guess, count the positions in which their# digits match and how many digits match in different positionsdef marks(sn, gu):# count correctly placed digit matches and total matchesdr = sum(x == y for x, y in zip(gu, sn))# credit Frits/Jim Randell for this linemc = sum(min(sn.count(c), gu.count(c)) for c in set(gu))return dr, mc - dr# for the first guess consider all possible positions of# the correct digit (pc), the misplaced digit (pm) and# its actual position (pa) and save all resulting numbers# that match the marks for the first three guessessol = set()for pc, pm, pa, pr in permutations(range(4)):# try all possible digits in the other two positionsfor i in range(100):j, k = divmod(i, 10)t = list('1234')t[pa] = '1234'[pm]t[pm] = str(j)t[pr] = str(k)nb = ''.join(t)if t[0] != '0':if all(marks(nb, gu) == (dr, dp) for gu, dr, dp in guesses):sol.add(nb)# guess four is the lowest resulting numberguess4 = ''.join(sorted(sol)[0])# find values for which the fourth guess has no 'dead right' digits# and collect the results indexed on their number of misplaced digitsmp2s = defaultdict(list)for cv in sol:if cv != guess4:dr, mp = marks(cv, guess4)if not dr:mp2s[mp].append(cv)# output any numbers with a unique number of misplaced digitsfor k, v in mp2s.items():if len(v) == 1:print(f"The hidden number was {''.join(v[0])} (4th guess {guess4}).")
