PyPE solution to PE problem 79
PyPE solution to PE problem 79
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
-
Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Related branches
Related bugs
Sprints
Whiteboard
ProjectEule
===
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 asked 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.
Solution
--------
We create a dictionary `li` whose keys are the possible digits and whose
values are lists of digits that occur before the key digit in the passcode.
A set of digits tracks which digits are used in the passcode.
We parse each login into its three digits, and add the known information
to `li`. For example, from 381, we know that 3 occurs before 8 and 1, and
we know that 8 occurs before 1.
At the end, we sort the dictionary by the number of digits that occur before
each item, and remove any items that are not found in the list of digits.
Answer
------
73162890