In Python: I need help using depth first search to solve this euler problem: The
ID: 3806623 • Letter: I
Question
In Python:
I need help using depth first search to solve this euler problem: The text file"keylog.txt" is at :https://drive.google.com/file/d/0B23lG851VqEdVnNSWlJsZ2ZYbjA/view and contains 50 succesful logins. Thank you in advance.
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. 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 lengthExplanation / Answer
from collections import defaultdict, deque
def find_number_universe(keylog):
numbers = set()
for attempt in keylog:
for num in attempt:
numbers.add(num)
return numbers
def connections(attempt):
l = len(attempt)
for i in range(l - 1):
for j in range(i + 1, l):
yield attempt[i], attempt[j]
def make_number_graph(keylog):
graph = defaultdict(set)
for attempt in keylog:
for a, b in connections(attempt):
graph[a].add(b)
return graph
def find_smallest_code(start, graph, number_universe):
queue = deque([(start, [start])])
while queue:
curr, path = queue.popleft()
neighbours = graph.get(curr, [])
for neighbour in neighbours:
new_path = path + [neighbour]
if not number_universe - set(new_path):
return len(new_path), new_path
queue.append((neighbour, new_path))
def solve(keylog):
number_universe = find_number_universe(keylog)
graph = make_number_graph(keylog)
candidates = []
for vertex in graph:
code = find_smallest_code(vertex, graph, number_universe)
if code: candidates.append(code)
return sorted(candidates[0])
if __name__ == '__main__':
with open('keylog') as log:
_, solution = solve(map(str.strip, log.readlines()))
print 'Solution:', ''.join(solution)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.