Project Euler 79 - Passcode derivation

Official link: https://projecteuler.net/problem=79

Thought Process

I originally solved this problem like so:

  1. First method

    1. Realising that only the numbers ['0', '1', '2', '3', '6', '7', '8', '9'] were used in the passcode.

    2. Seeing as we are determining the shortest code I assumed the passcode would be 8 digits long.

    3. Using the itertools.permutation() function to generate all permutations of these 8 numbers

      1. Go through the list and see if every successful login attempt matches a permutation

        1. If it does then we have our code


But I wasn't happy when I came back to it using the itertools module and came up with a much nicer and faster solution

  1. Second method

    1. Same first and second step are the same, only the numbers used in the passcode are ['0', '1', '2', '3', '6', '7', '8', '9'], and I assume its 8 digits long

    2. I then create a dictionary, mydict, where mydict[x] = set() for each x in the possible numbers above, and an empty string, passcode = ""

    3. Then I loop through the successful attempts and I see where each numbers 'points' to, for example: the first attempt is 319

      1. This means 1 'points' to 3 and 9 'points' to 1, so I make mydict[1].add(3) and mydict[9].add(1)

      2. After going through all the keys you should end up with the following dictionary = {'0': {'2', '8', '6', '1', '9'}, '1': {'7', '3'}, '2': {'1', '7', '6'}, '3': {'7'}, '6': {'7', '1', '3'}, '7': set(), '8': {'1', '2', '3', '6'}, '9': {'2', '8', '6', '1', '7'}}

        1. There is one number which stands out and that is '7': set() what this is saying is 7 points to no numbers, and this means that 7 must be the first digit of our passcode! So we add str(7) to passcode

      3. Then I remove the key 7 from the dictionary and I remove 7 from all the sets of each dictionary key and so on, after the first removal of 7 we get the following dictionary = {'0': {'2', '8', '6', '1', '9'}, '1': {'3'}, '2': {'1', '6'}, '3': set(), '6': {'1', '3'}, '8': {'1', '2', '3', '6'}, '9': {'2', '8', '6', '1'}}

        1. Again we see that '3': set() stands out, meaning it is the next digit of the passcode, so we add str(3) to passcode

I will let you figure out how you want to remove the elements so that this all works with a single run line, of course you could just do it by hand now Hint: (del mydict[x] deletes key x for a dictionary, set.remove(x) deletes element x for a set, mydict[x].remove(y) deletes element y for a the set = mydict[x])

Interactive Code

No interactive code, both methods are shown below