Skip to content

Instantly share code, notes, and snippets.

@alexmic
Created October 5, 2013 22:24
Show Gist options
  • Save alexmic/6846774 to your computer and use it in GitHub Desktop.
Save alexmic/6846774 to your computer and use it in GitHub Desktop.
Project Euler problem #79.
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment