[Assorted-commits] SF.net SVN: assorted:[1862] problems/other

[<yan...@us...>]

Revision: 1862
          http://sourceforge.net/p/assorted/svn/1862
Author:   yangzhang
Date:     2013-08-10 07:51:45 +0000 (Sat, 10 Aug 2013)
Log Message:
-----------
Add fn-cnjn exercise

Added Paths:
-----------
    problems/other/fn-cnjn/
    problems/other/fn-cnjn/go.py

Added: problems/other/fn-cnjn/go.py
===================================================================
--- problems/other/fn-cnjn/go.py	                        (rev 0)
+++ problems/other/fn-cnjn/go.py	2013-08-10 07:51:45 UTC (rev 1862)
@@ -0,0 +1,69 @@
+# Incomplete
+import collections as col, re
+Call = col.namedtuple('Call', 'name args')
+def parse(s):
+  def expr(toks):
+    if toks[0][0].isalpha():
+      nodes = []
+      rest = toks[1:]
+      assert rest[0] == '('
+      while rest[0] != ')':
+        assert rest[0] in ['(', ',']
+        node, rest = expr(rest[1:])
+        nodes.append(node)
+      return Call(toks[0], nodes), rest[1:]
+    elif toks[0][0].isdigit():
+      return int(toks[0]), toks[1:]
+    else:
+      assert False
+  root, rest = expr(re.findall(r'\(|\)|,|[A-Za-z]\w*|\d+', s))
+  assert rest == []
+  return root
+
+def compute(computations, reg):
+  def evaluate(x):
+    if type(x) is int:
+      return x
+    else:
+      return reg[x.name].apply(map(evaluate, x.args))
+  return [evaluate(parse(s)) for s in computations]
+
+class Function(object):
+  def __init__(self, f): self.f = f
+  def apply(self, args): return self.f(args)
+  def batchApply(self, batches): return map(self.f, batches)
+
+def compute(computations, reg):
+  reg = {name: Function(f) for name, f in reg}
+  tree = map(parse, computations)
+  while type(tree)
+    # find leaf calls
+    leafs = []
+    def leaf_calls(call):
+      if all(type(node) is int for node in call.args): leafs.append(call)
+      else: [leaf_calls(node) for node in call.args if type(node) is Call]
+    leaf_calls(tree)
+    # group by function name
+    grouped = {}
+    for leaf in leafs: grouped.setdefault(leaf.name, []).append(leaf)
+    # compute batches
+    results = [(reg[name].batchApply([leaf.args for leaf in leafs]), leaf)
+               for name, leafs in grouped]
+    # put results back into tree
+    def replace_nodes(call):
+      for i, node in enumerate(call.args):
+        for value, leaf in results:
+          if node is leaf:
+            call.args[i] = value
+    replace_nodes(tree)
+    return tree
+
+print parse('f(0)')
+print parse('f(f(0))')
+print parse('f(g(h(2,3),5),g(g(3),h(4)),10)')
+
+reg = {'f': (lambda x: 1 + x[0])}
+print compute(['f(0)'], reg)
+print compute(['f(f(0))'], reg)
+reg = {'f': sum, 'g': max, 'h': (lambda x: 0)}
+print compute(['f(g(h(2,3),5),g(g(3),h(4)),10)'], reg)

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.