Created
July 21, 2016 09:15
-
-
Save barahilia/d3b27ab92a5b45958ed9e989e06f57b6 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"""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