1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
# update a list at index i with value v def update(x, i, v): x = list(x) x[i] = v return x # ds - candidate digits ('?' for unassigned) # ns - remaining numbers to check def solve(ds, ns): # are we done? if len(ns) == 0: print(''.join(ds)) else: # consider the digits of the next number ms = list(zip(ds, ns[0])) # if any digits already match move on to the next one if any(a == b for (a, b) in ms): solve(ds, ns[1:]) else: # set one of the unassigned digits for (i, m) in enumerate(ms): if m[0] != '?': continue solve(update(ds, i, m[1]), ns[1:]) solve(['?'] * 4, ('1933', '2829', '3133', '4630', '5089', '5705', '6358', '6542')) |

1 2 3 4 5 |
print [x for x in xrange(1000,10000) if all( len([1 for i in xrange(4) if str(x)[i]==e[i]])>0 for e in ('1933','2829','3133','4630','5089','5705','6358','6542'))] |

Here is a more extensive search for unique solutions for subsets of the list of extensions:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
from itertools import combinations as comb for cn in xrange(2,8): for c in comb(('1933','2829','3133','4630','5089','5705','6358','6542'),cn): solutions=[] count=0 for n in xrange(1000,10000): str_n = str(n) for e in c: count = len([1 for i in xrange(4) if str_n[i]==e[i]]) if count == 0: break if count>0: solutions.append(n) if len(solutions)>1: break if len(solutions)==1: print c, solutions[0] |

It rather depends on what you mean by ‘prove’! All possible correct extensions are tried and only one is shown to meet the condition spelt out in the teaser.

Maybe you are uncertain about what the ‘break’ on line 17 does? The inner loop tries the extensions in turn but the ‘break’ terminates this loop as soon as a number is found in which no digts in the same positions match. This ‘break’ would continue to line 21 if there was one but, as there isn’t, it simply continues with the next value from line 10. If the inner loop completes with no break then the else on line 18 is used and the value is printed out before going on to the next number from line 11.

The only difference between the program above and my earlier one is that the latter tried all numbers from 1000 to 9999 whereas the one above works out which digits can occur in each of the four positions and tries only numbers that use these. This cuts the search from 9000 numbers down to less than 2000.

]]>Does your program prove uniqueness? What would have happened if the set of tried numbers had given more than one extension meeting the condition?

I suspect that your earlier program which I saw did not prove uniqueness but as a non-prgrammer I was not sure.

]]>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
from itertools import product # the extension numbers tried nbrs = ('1933', '2829', '3133', '4630', '5089', '5705', '6358', '6542') # collect the digits for each digit position - one # of these must be correct cand = (set(n[i] for n in nbrs) for i in range(4)) # try each possible correct extension number for ext in product(*cand): # for each extension tried for tried in nbrs: # skip extension numbers where no digits match # those in any of those tried if all(ext[i] != tried[i] for i in range(4)): break else: # if at least one digit matches in all extensions tried print('The correct extension number is {:s}.'.format(''.join(ext))) |