Python Implementation of Problem 79
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 79
Problem:
A common security method used for online banking is to ask the user for three random characters from a passcode. For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply would be: 317.
The text file, keylog.txt, contains fifty successful login attempts.
Given that the three characters are always asked for in order, analyse the file so as to determine the shortest possible secret passcode of unknown length.
1"""
2Project Euler Problem 79
3
4Problem:
5
6A common security method used for online banking is to ask the user for three random characters from a passcode.
7For example, if the passcode was 531278, they may ask for the 2nd, 3rd, and 5th characters; the expected reply
8would be: 317.
9
10The text file, keylog.txt, contains fifty successful login attempts.
11
12Given that the three characters are always asked for in order, analyse the file so as to determine the shortest
13possible secret passcode of unknown length.
14"""
15from collections import defaultdict
16from functools import reduce
17from typing import DefaultDict, List, Set
18
19from .lib.utils import get_data_file
20
21
22def main() -> int:
23 dependencies: DefaultDict[int, Set[int]] = defaultdict(set)
24 for line in get_data_file("p0079_keylog.txt").splitlines():
25 x, y, z = (int(i) for i in line)
26 dependencies[x].add(y)
27 dependencies[y].add(z)
28
29 dep_iter = iter(dependencies.values())
30 smallest_set = next(dep_iter)
31 for s in dependencies.values():
32 if len(s) < len(smallest_set):
33 smallest_set = s
34
35 passcode: List[int] = list(smallest_set)
36 while dependencies:
37 for i, d in dependencies.copy().items():
38 if all(n in passcode for n in d):
39 passcode.insert(0, i)
40 del dependencies[i]
41
42 return reduce(lambda x, y: x * 10 + y, passcode)