Skip to content

Instantly share code, notes, and snippets.

# alexmic/problem_79.py Created Oct 5, 2013

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) if __name__ == '__main__': with open('keylog') as log: _, solution = solve(map(str.strip, log.readlines())) print 'Solution:', ''.join(solution)
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.