PyPE solution to PE problem 79

Registered by Scott Armitage

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

Sprints

Whiteboard

    ProjectEuler.net problem 79
    ===========================

    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

(?)

Work Items

This blueprint contains Public information 
Everyone can see this information.

Subscribers

No subscribers.