GDC Project Euler: problem 79 – Jaroslaw Pawlak
I have decided to describe this problem, mainly because it’s a bit different than all the others. It takes less time to solve it with a pen and paper than to implement some structure for that purpose.
- Solved: Problem 79
- Difficulty: extremely easy
- Techniques used:
Pen and paper :)
- How much time did it take:
Few minutes to solve a problem with pen and paper. Few days spent on the research. Algorithm for simple case (no digit occurs twice) implemented in about 30 minutes, finds an answer in less than 1 ms.
- First / final solution:
My solution bases on the assumption, which appeared to be correct. If it would not, the problem would be much more difficult and maybe even impossible to solve with pen and paper.
My first observation was that some of the login attempts are the same. If for the same login attempts we assume that a user was asked for different digits, it gives quite a lot of information (e.g. that some of digits occurs twice). As it should be solved in the most general way, we should consider only confident information. The least number of information we get when we assume that whenever login attempt is the same, the digits user was asked for were also the same. And this means that all repeated occurrences can be removed which gives 33 successful login attempts.
Those 33 sorted login attempts are: 129, 160, 162, 168, 180, 289, 290, 316, 318, 319, 362, 368, 380, 389, 620, 629, 680, 689, 690, 710, 716, 718, 719, 720, 728, 729, 731, 736, 760, 762, 769, 790, 890.
So for each login attempt we can conclude that one digit lexicographically is before the other digit – e.g. for 129 we may say that 1 is before 2 and 9 is after 2.
Let’s consider 129 and 162. We could say that 6 is between 1 and 2. This is correct as long as all digits occur in the password exactly once. But a password (or rather its part for those two login attempts) might be 12962. For first login attempt user was asked for digits 1st, 2nd and 3rd, for second attempt for 1st, 4th and 5th. Both login attempts are correct but 6 is not between 1 and 2. So we may say that this assumption is incorrect and we should consider something more general. But we are asked for the shortest possible password – so as long as everything works, we do not have to consider repeated occurrences of digits.
So now the solution:
from 129 we get _1_2_9_
from 162 we get _1_6_2_9_
from 289 we get _1_6_2_8_9_
from 316 we get _3_1_6_2_8_9_
from 731 we get _7_3_1_6_2_8_9_
from 790 we get _7_3_1_6_2_8_9_0_
There are exactly 8 digits (4 and 5 are missing so the shortest password is 8 digit long) and a password 73162890 is correct for all remaining login attempts. Having this password, any digit can be inserted between any two digits, and the password generated in this way will also be correct for given login attempts.
After doing some research, I have figured out that if in all login attempts digits are always in the same order then the shortest password is as long as many digits occur in login attempts. I.e. if 1 is always before 6, 7 is always before 9, etc., and there are two digits missing, then the shortest possible password is 8 digits long. So what happens if order is now always the same in login attempts? E.g. one login attempt is 129 and the other is 219? Then we have to consider two cases (so we may get two different shortest password, it depends on other login attempts): one is _1_2_1_9_, the other is _2_1_2_9_. The rest of algorithm remains the same. So if there is a login attempt 316 (let’s consider more difficult branch first), then 3 is before 1 – but we don’t know which one so it may be 31219 or 12319. In such case we just have to consider this 1 as the rightmost one. And from here the rest of algorithm is really the same :)
Few days later I have implemented an algorithm which solves simple cases (i.e. every digit occurs in the passcode at most once). In case of complex password, algorithm returns as much as it can do assuming that the case is simple. The idea is quite simple:
Firstly, I have created a class Node which contains integer value, and two sets of integers called before and after. For every distinct digit in the login attempts, separate Node is created (so there are up to 10 Nodes). Sets before and after contains those digits which must be before or after current digit. Let me describe it on the example, let’s take login attempt 123. Three nodes are created with values 1, 2 and 3. Node with value 1 should have empty “before” set and set “after” should contain 2 and 3. Node with value 2 should have 1 in “before” set and 3 in “after” set. Finally Node with value 3 should have empty “after” set and set “before” should contain 1 and 2. Now from all the nodes we choose this one which has empty any of the sets. If a node has empty “before” set, it means that its value is the first in the passcode. Then we remove this value from “before” sets in all of the nodes. So in the given example, 1 is set as the first character of passcode, node with value 2 has empty “before” set and “after” set contains only 3, while the node with value 3 has only 2 in its “before” set. After all this leftmost node just found is removed from the nodes list. Similarly can be done for the rightmost node. Algorithm I have implemented looks for leftmost and rightmost nodes at the same time.
- Problems encountered:
When solving the problem first time, I have read that the text file contains failed login attempts. While implementing an algorithm, I tried to make it work even for complex cases (some digits occurs more than once), which makes a problem much more complicated.
- What I have learnt:
I should extremely careful read what I am expected to do – it was not first time when I was calculating something completely different than I was asked for… I have also learnt that my bank passcode should contain multiple occurrences of the same characters, in case someone was able to intercept my answers without bank’s questions ^^