99 lines
2.8 KiB
Python
99 lines
2.8 KiB
Python
#!/usr/bin/python
|
|
|
|
# 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, p079_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.
|
|
|
|
import sys
|
|
from itertools import permutations
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
def check_passcode(passcode, len_, logins, n):
|
|
# For every login attempt, check if all the digits appear in the passcode in the correct order. Return 0 if a login attempt
|
|
# incompatible with the current passcode is found.
|
|
for i in range(n):
|
|
k = 0
|
|
for j in range(len_):
|
|
if passcode[j] == int(logins[i][k]):
|
|
k = k + 1
|
|
|
|
if k == 3:
|
|
break
|
|
|
|
if k < 3:
|
|
return 0
|
|
|
|
return 1
|
|
|
|
|
|
@timing
|
|
def p079():
|
|
try:
|
|
with open('p079_keylog.txt', 'r', encoding='utf-8') as fp:
|
|
logins = fp.readlines()
|
|
except FileNotFoundError:
|
|
print('Error while opening file p079_keylog.txt')
|
|
sys.exit(1)
|
|
|
|
digits = [0] * 10
|
|
passcode_digits = [0] * 10
|
|
|
|
for i in logins:
|
|
keylog = int(i)
|
|
|
|
# Check which digits are present in the login attempts.
|
|
while True:
|
|
digits[keylog % 10] = digits[keylog % 10] + 1
|
|
keylog = keylog // 10
|
|
|
|
if keylog == 0:
|
|
break
|
|
|
|
j = 0
|
|
for i in range(10):
|
|
# To generate the passcode, only use the digits present in the login attempts.
|
|
if digits[i] > 0:
|
|
passcode_digits[j] = i
|
|
j = j + 1
|
|
|
|
found = 0
|
|
len_ = 4
|
|
|
|
while not found:
|
|
passcode = [0] * len_
|
|
|
|
# For the current length, generate the first passcode with the digits in order.
|
|
for i in range(len_):
|
|
passcode[i] = passcode_digits[i]
|
|
|
|
# Check if the passcode is compatible with the login attempts.
|
|
if check_passcode(passcode, len_, logins, 50):
|
|
found = 1
|
|
break
|
|
|
|
# For the given length, check every permutation until the correct
|
|
# passcode has been found, or all the permutations have been tried.
|
|
passcodes = permutations(passcode, len_)
|
|
|
|
for i in passcodes:
|
|
if check_passcode(i, len_, logins, 50):
|
|
found = 1
|
|
res = ''.join(map(str, i))
|
|
break
|
|
|
|
# If the passcode has not yet been found, try a longer passcode.
|
|
len_ = len_ + 1
|
|
|
|
print('Project Euler, Problem 79')
|
|
print(f'Answer: {res}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p079()
|