Project Euler 79 - Passcode derivation
Official link: https://projecteuler.net/problem=79
Thought Process
I originally solved this problem like so:
First method
Realising that only the numbers ['0', '1', '2', '3', '6', '7', '8', '9'] were used in the passcode.
Seeing as we are determining the shortest code I assumed the passcode would be 8 digits long.
Using the itertools.permutation() function to generate all permutations of these 8 numbers
Go through the list and see if every successful login attempt matches a permutation
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
Second method
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
I then create a dictionary, mydict, where mydict[x] = set() for each x in the possible numbers above, and an empty string, passcode = ""
Then I loop through the successful attempts and I see where each numbers 'points' to, for example: the first attempt is 319
This means 1 'points' to 3 and 9 'points' to 1, so I make mydict[1].add(3) and mydict[9].add(1)
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'}}
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
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'}}
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