Challenge Complete

challenge.py

import re

def is_dynamic(frag):
    return re.match("<.*>", frag) != None

class Node(object):
    def __init__(self, fragment, isDynamic):
        self.children = {}
        self.parent = None
        self.fragment = fragment
        self.isDynamic = isDynamic

    def addChild(self, child):
        self.children[child.fragment] = child

    def hasChild(self, element):
        return element in self.children

    def addParent(self, parent):
        self.parent = parent

    def iter_dynamic_children(self):
        for item in (node for node in self.children.values() if node.isDynamic):
            yield item

    def build_route(self):
        path = "/%s" % self.fragment
        p = self.parent
        while p != None and p.fragment != '/':
            path = "/%s" % p.fragment + path
            p = p.parent
        return path

class RouteEngine(object):
    def __init__(self):
        self.root = Node("/", False)

    def addRoute(self, route):
        current = self.root
        for chunk in route.split("/"):
            if not chunk:
                continue
            if current.hasChild(chunk):
                current = current.children[chunk]
                continue
            else:
                next = Node(chunk, is_dynamic(chunk))
                next.addParent(current)
                current.addChild(next)

    def walkBranch(self, chunks, current):
        while chunks:
            chunk = chunks.pop()
            if not chunk:
                continue
            if current.hasChild(chunk):
                current = current.children[chunk]
            else:
                # back to the dynamic game :(
                for node in current.iter_dynamic_children():
                    possible = self.walkBranch(chunks, node)
                    if possible != current:
                        current = possible
                        break
        return current

    def matchRoute(self, route):
        """Where all the hard work is"""
        current = self.root
        chunks = route.split("/")
        while chunks:
            chunk = chunks.pop(0)
            if not chunk:
                continue
            if current.hasChild(chunk):
                current = current.children[chunk]
                continue;
            else:
                # now it gets really trippy
                if not current.children:
                    # no children, not finished the route
                    return None
                if len(list(current.iter_dynamic_children())) == 0:
                    # no dynamic nodes.
                    return None
                # now we are left with dynamic nodes.
                for node in current.iter_dynamic_children():
                    possible = self.walkBranch(chunks, node)
                    if possible != current:
                        current = node;
                    
        return current.build_route()


a = RouteEngine()
a.addRoute("/hi")
a.addRoute("/hello")
a.addRoute("/hello/bob")
a.addRoute("/hello/jane")

assert a.matchRoute("/hello/bob") == "/hello/bob"
assert a.matchRoute("/hello/jane") == "/hello/jane"
assert a.matchRoute("/hello") == "/hello"