fractal-hedge-maze-solution.py

"""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()