viennese.py

# Solving the puzzle at
# http://zulko.github.io/blog/2014/04/27/viennese-mazes-what-they-are/
class Digraph:
    def __init__(self):
        self.nodes = {}
        self.edges = []

    def makeNode(self, name):
        n = self.nodes.get(name)
        if n is None:
            n = Digraph.Node(name)
            self.nodes[name] = n
        return n

    def addEdge(self, a, b, data = None):
        nodeA = self.makeNode(a)
        nodeB = self.makeNode(b)
        if not nodeA.edges.get(b):
            e = Digraph.Edge(nodeA, nodeB, data)
            nodeA.edges[b] = e
            self.edges.append(e)

    def addSymmetricEdges(self, a, b, data = None):
        self.addEdge(a, b, data)
        self.addEdge(b, a, data)

    class Node:
        def __init__(self, name):
            self.edges = {}
            self.name = name

    class Edge:
        def __init__(self, nodeA, nodeB, data):
            self.data = data
            self.a = nodeA
            self.b = nodeB

g = Digraph()
g.addSymmetricEdges("a", "b", 1)
g.addSymmetricEdges("a", "c", 0)
g.addSymmetricEdges("a", "d", 2)
g.addSymmetricEdges("c", "b", 0)
g.addSymmetricEdges("c", "d", 1)
g.addSymmetricEdges("b", "i", 0)
g.addSymmetricEdges("b", "h", 0)
g.addSymmetricEdges("c", "g", 0)
g.addSymmetricEdges("d", "f", 0)
g.addSymmetricEdges("d", "e", 2)
g.addSymmetricEdges("i", "h", 0)
g.addSymmetricEdges("h", "g", 0)
g.addSymmetricEdges("g", "f", 0)
g.addSymmetricEdges("f", "e", 0)
g.addSymmetricEdges("i", "j", 1)
g.addSymmetricEdges("h", "j", 1)
g.addSymmetricEdges("g", "k", 0)
g.addSymmetricEdges("f", "l", 1)
g.addSymmetricEdges("e", "l", 2)
g.addSymmetricEdges("j", "k", 1)
g.addSymmetricEdges("k", "l", 1)
g.addSymmetricEdges("j", "m", 2)
g.addSymmetricEdges("k", "m", 1)
g.addSymmetricEdges("l", "m", 2)

def state_graph(g):
    s = Digraph()
    for e in g.edges:
        for t in xrange(3):
            if (e.data + t)%3 != 2:
                a = "%s%s" % (e.a.name, t%3)
                b = "%s%s" % (e.b.name, (t+1)%3)
                s.addEdge(a, b)
    return s

def BFS(g, starts, ends):
    from collections import deque
    s = deque()
    for n in starts:
        s.append([g.nodes[n]])

    while len(s) > 0:
        p = s.popleft()
        if p[-1].name in ends:
            return p
        for e in p[-1].edges.values():
            s.append(p + [e.b])
    return []

solution = BFS(state_graph(g), ["a0"], ["m0", "m1", "m2"])
print map(lambda n:n.name, solution)