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])
Update: I got an email from Martin Ueding where he said my blog helped him solve the problem, on his own blogpost about the problem he provides great illustrations of what is going on, and he also provides much more succinct code, and most importantly he shows why the assumption of unique digit is essential with my method.
Interactive Code
No interactive code, both methods are shown below