Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
"""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
You can’t perform that action at this time.