"""Find exit from the fractal maze. | |
See http://puzzling.stackexchange.com/questions/37675/alice-and-the-fractal-hedge-maze | |
""" | |
from unittest import TestCase | |
from Queue import PriorityQueue | |
from collections import defaultdict | |
from itertools import count, product | |
def bfs(start, neighbors, priority=None): | |
if priority is None: | |
counter = count() | |
priority = lambda node: next(counter) | |
visited = {start} | |
queue = PriorityQueue() | |
queue.put((priority(start), start, None)) | |
while not queue.empty(): | |
_, node, prev = queue.get() | |
yield node, prev | |
for neighbor in neighbors(node): | |
if neighbor not in visited: | |
visited.add(neighbor) | |
queue.put((priority(neighbor), neighbor, node)) | |
def complete_graph(graph): | |
complete = defaultdict(set) | |
for v, nexts in graph.items(): | |
knot = [v] + nexts | |
for a, b in product(knot, knot): | |
if a != b: | |
complete[a].add(b) | |
complete[b].add(a) | |
return dict(complete) | |
def get_fractal_neighbors(graph, node): | |
neighbors = graph.get(node, set()) | |
neighbors |= {node[:-1] + v for v in graph.get(node[-1:], set())} | |
neighbors |= {node[:-2] + v for v in graph.get(node[-2:], set())} | |
return neighbors | |
class TestBfs(TestCase): | |
@staticmethod | |
def traverse(graph, node): | |
return list(node for node, _ in bfs(node, graph)) | |
def test_empty_graph(self): | |
graph = lambda node: [] | |
traversal = self.traverse(graph, 1) | |
self.assertEqual(traversal, [1]) | |
def test_binary_graph(self): | |
graph = {1: [2], 2: [1]} | |
traversal = self.traverse(lambda node: graph[node], 1) | |
self.assertEqual(traversal, [1, 2]) | |
def test_angle_graph(self): | |
graph = {1: [2, 3], 2: [], 3: []} | |
traversal = self.traverse(lambda node: graph[node], 1) | |
self.assertEqual(traversal, [1, 2, 3]) | |
def test_complex_graph(self): | |
graph = {1: [2, 3], 2: [3, 4, 5], 3: [6], 4: [7], 5: [3], 6: [], 7: [6]} | |
traversal = self.traverse(lambda node: graph[node], 1) | |
self.assertEqual(traversal, [1, 2, 3, 4, 5, 6, 7]) | |
class TestComplete(TestCase): | |
def test_empty(self): | |
graph = {} | |
self.assertEqual(complete_graph(graph), {}) | |
def test_simple(self): | |
graph = {1: [2]} | |
self.assertEqual(complete_graph(graph), {1: {2}, 2: {1}}) | |
def test_larger(self): | |
graph = {1: [2, 3], 2: [4]} | |
self.assertEqual( | |
complete_graph(graph), | |
{1: {2, 3}, 2: {1, 3, 4}, 3: {1, 2}, 4: {2}} | |
) | |
class TestFractalNeighbors(TestCase): | |
@staticmethod | |
def neighbors(graph, node): | |
complete = complete_graph(graph) | |
return get_fractal_neighbors(complete, node) | |
def test_empty(self): | |
graph = {} | |
self.assertEqual(self.neighbors(graph, '1'), set()) | |
def test_simple(self): | |
graph = {'1': ['2']} | |
self.assertEqual(self.neighbors(graph, '1'), {'2'}) | |
def test_prefix(self): | |
graph = {'1': ['2']} | |
self.assertEqual(self.neighbors(graph, 'ABCA1'), {'ABCA2'}) | |
self.assertEqual(self.neighbors(graph, 'ABCA2'), {'ABCA1'}) | |
def test_internal_and_external_edges(self): | |
graph = {'2': ['1'], 'A1': ['3']} | |
self.assertEqual(self.neighbors(graph, 'ABCA1'), {'ABCA2', 'ABC3'}) | |
# 1..12 -> 1..9a..c | |
GRAPH = { | |
'1': ['c', 'Ac', 'A5'], | |
'2': ['8', 'A9', 'a', 'C4'], | |
'3': ['B1', 'B4'], | |
'4': ['B5', 'B6'], | |
'5': ['D4', 'D5'], | |
'6': ['D8'], | |
'7': ['Da', 'B7'], | |
'8': [], # see '2' | |
'9': ['C7', 'Cb'], | |
'a': [], # see '2' | |
'b': ['Aa'], | |
'c': [], # see '1' | |
'Bb': ['Bc'], | |
'B8': ['D1', 'D3'], | |
'Db': ['Dc'], | |
'C2': ['Cc'], | |
} | |
START = 'A3' | |
ENDS = list('123456789abc') | |
VISITED_LIMIT = 1000 | |
def get_path(node, previous_node): | |
yield node | |
current = node | |
while current is not None: | |
previous = previous_node[current] | |
yield previous | |
current = previous | |
def main(): | |
graph = complete_graph(GRAPH) | |
neighbors = lambda node: get_fractal_neighbors(graph, node) | |
came_from = {} | |
nodes = bfs(START, neighbors, priority=len) | |
for counter, (node, prev) in enumerate(nodes): | |
came_from[node] = prev | |
if counter > VISITED_LIMIT: | |
break | |
if node in ENDS: | |
print "success" | |
print list(reversed(list(get_path(node, came_from)))) | |
return | |
print "not found" | |
if __name__ == '__main__': | |
main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment