Enigmatic Code

Programming Enigma Puzzles

Enigma 1517: Just forgotten

From New Scientist #2679, 25th October 2008

Joe was furious when he forgot one of his bank account numbers. He remembered that it had all the digits 0 to 9 in some order, so he tried the following four sets without success:

9462157830
8604391257
1640297853
6824319075

When Joe finally remembered his account number, he realised that in each set just four of the digits were in their correct position and that, if one knew that, it was possible to work out his account number.

What was it?

[enigma1517]

Advertisements

2 responses to “Enigma 1517: Just forgotten

  1. Jim Randell 17 September 2012 at 9:15 am

    While I was thinking of a more elegant way to approach this puzzle I wrote this simple Python program to brute force it, and was surprised to find that it ran in 2.3s (using PyPy) – well before I’d written a different program to solve it.

    from itertools import permutations
    from enigma import irange, printf
    
    codes = (
      (9, 4, 6, 2, 1, 5, 7, 8, 3, 0),
      (8, 6, 0, 4, 3, 9, 1, 2, 5, 7),
      (1, 6, 4, 0, 2, 9, 7, 8, 5, 3),
      (6, 8, 2, 4, 3, 1, 9, 0, 7, 5)
    )
    
    # how many digits are in the same position?
    def check(a, b):
      return sum(1 for (x, y) in zip(a, b) if x == y)
    
    # the actual pin is the digits 0-9 in some order
    for pin in permutations(irange(0, 9)):
      # with 4 digits in the correct place for each of the above codes
      if all(check(pin, c) == 4 for c in codes):
        printf("pin = {pin}")
    

    Solution: The account number is 9624317850.

    • Jim Randell 17 September 2012 at 9:21 am

      Here is a more efficient Python program to solve the puzzle. It runs in 35ms.

      However this provides is a good example of programmer efficiency. If you are only going to run the program once, then clearly the above code, which took a couple of minutes to write and runs a few seconds, is much more time efficient than time it took to come up with the following code.

      If however you want to re-use the code to solve thousands of similar problems a day, clearly this second program is going to make up for the development time on the first day.

      from itertools import combinations
      from enigma import irange, printf
      
      codes = (
        (9, 4, 6, 2, 1, 5, 7, 8, 3, 0),
        (8, 6, 0, 4, 3, 9, 1, 2, 5, 7),
        (1, 6, 4, 0, 2, 9, 7, 8, 5, 3),
        (6, 8, 2, 4, 3, 1, 9, 0, 7, 5)
      )
      
      # solve for pin, such that each code is correct in n places
      def solve(pin, codes, n):
        # are we done?
        if len(codes) == 0:
          if not(-1 in pin): printf("pin = {pin}")
          return
      
        # determine how many choices we have for the first code
        code = codes[0]
        (rest, r) = ([], n)
        for i in irange(0, 9):
          if code[i] in pin:
            # digit at index i is already used
            # if it matches we have one less choice
            if code[i] == pin[i]: r -=1
          else:
            # digit at index i is not used
            # if it's not filled out in the pin it's a candidate
            if pin[i] == -1: rest.append(i)
      
        if r == 0:
          # this code already has n digits matching
          # so check the remaining codes
          solve(pin, codes[1:], n)
        elif r > 0:
          # chose the digits from the candidates
          for s in combinations(rest, r):
            # fill them out in a new pin
            pin2 = list(pin)
            for i in s: pin2[i] = code[i]
            # and try to solve with the remaining codes
            solve(pin2, codes[1:], n)
      
      solve([-1] * 10, codes, 4)
      

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: