Scopely Tree Challenge

gistfile1.py

#!/usr/bin/env python
from operator import itemgetter

## ELAPSED DEVELOPMENT TIME: ~45m ##

## Helper Functions ##

def juxt(*fns):
  def _juxter(arg):
    return [fn(arg) for fn in fns]
  return _juxter

def powerset(l):
  def _reducer(acc, e):
    return acc + [x + [e] for x in acc]
  return sorted(reduce(_reducer, l, [[]]), key=len)

def cart(l, *ls):
  m = [[e] for e in l]
  if ls:
    return [a + b for b in cart(*ls) for a in m]
  return m

## Path Manipulation ##

def combo(parts):
  return ["-".join(e) for e in powerset(parts)[1:]]

def parse_path(path):
  return [combo(e.split("|")) for e in path.split("/") if e]

def expand_path(path):
  return cart(*parse_path(path))

## Tree Manipulation ##

_value = itemgetter("value")
_children = itemgetter("children")
_expand = juxt(_value, _children)

def make_node(v, children=None):
  return { "value": v, "children": (children or []) }

def insert_child(node, value):
  child = make_node(value)
  _children(node).append(child)
  return child

def insert_node(node, child):
  _children(node).append(child)

def find_child(node, value):
  for child in _children(node):
    if _value(child) == value:
      return child
  return None

def insert_keys(node, keys):
  if keys:
    key, rest = keys[0], keys[1:]
    child = find_child(node, key) or insert_child(node, key)
    insert_keys(child, rest)

def insert_path(node, path):
  for p in expand_path(path):
    insert_keys(node, p)

def compare_tree(t1, t2):
  v1, c1 = _expand(t1)
  v2, c2 = _expand(t2)
  if v1 == v2 and len(c1) == len(c2):
    return all(compare_tree(x, y) for x, y in zip(c1, c2))
  return False

## Debug ##

def print_node(node, space=0):
  print (" " * space) + _value(node)
  for child in _children(node):
    print_node(child, space + 2)

if __name__ == "__main__":
  print parse_path("a")
  print parse_path("a/b")
  print parse_path("a/b|c")

  print expand_path("a")
  print expand_path("a/b")
  print expand_path("a/b|c")
  print expand_path("a/b|c/d|e")

  node = make_node("root")
  insert_path(node, "a/b|c/d|e")
  insert_path(node, "sploded/1|2|3/x|y|z/boom")
  print_node(node)