Programming Praxis

7 Responses to “Carl Hewitt’s Same-Fringe Problem”

1. Programming Praxis – Carl Hewitt’s Same-Fringe Problem « Bonsai Code said

   August 3, 2010 at 10:21 AM

   [...] Praxis – Carl Hewitt’s Same-Fringe Problem By Remco Niemeijer In today’s Programming Praxis exercise we have to implement Carl Hewitt’s same-fringe algorithm, which [...]
2. Remco Niemeijer said

   August 3, 2010 at 10:21 AM

   My Haskell solution (see http://bonsaicode.wordpress.com/2010/08/03/programming-praxis-carl-hewitt%E2%80%99s-same-fringe-problem/ for a version with comments):

   data Tree a = Node (Tree a) (Tree a) | Leaf a
   
   flatten :: Tree a -> [a]
   flatten (Node l r) = flatten l ++ flatten r
   flatten (Leaf x)   = [x]
   
   sameFringe :: Eq a => Tree a -> Tree a -> Bool
   sameFringe a b = flatten a == flatten b
   
3. kbob said

   August 3, 2010 at 11:56 AM

   Here’s a Python solution using generators. Just for grins, I implemented seqsamefringe, which compares an arbitrary number of trees. Because cons cell is not a primitive type in Python, I implemented that, too.

   #!/usr/bin/python
   
   from itertools import izip_longest   # requires Python 2.6
   
   
   # Define a tree/node class.
   
   class Node:
       def __init__(self, left, right):
           self.left = left
           self.right = right
       def __str__(self):
           return "(%s %s)" % (str(self.left), str(self.right))
           
   def is_leaf(tree):
       return not isinstance(tree, Node)
   
   
   ###### samefringe ######
   
   def samefringe(tree1, tree2):
       class uniq: pass                    # unique object
       g1 = leaves(tree1)
       g2 = leaves(tree2)
       return all(l1 == l2 for (l1, l2) in izip_longest(g1, g2, fillvalue=uniq))
   
   def leaves(tree):
       if is_leaf(tree):
           yield tree
       else:
           for leaf in leaves(tree.left):
               yield leaf
           for leaf in leaves(tree.right):
               yield leaf
   
   
   # Compare a sequence of trees' fringes.
   
   def seqsamefringe(*trees):
       class uniq: pass
       return all(all(ls[0] == l
                      for l in ls)
                  for ls in izip_longest(*(leaves(tree)
                                           for tree in trees), fillvalue=uniq))
   
4. Kanak Kshetri said

   August 3, 2010 at 12:54 PM

   Bug in your solution.

   > (define (same-fringe? eql? tree1 tree2)
   > (stream-equal? = (flatten tree1) (flatten tree1)))

   should be
   (stream-equal? = (flatten tree1) (flatten tree2))
5. programmingpraxis said

   August 3, 2010 at 1:27 PM

   Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.
6. Carl Hewitt said

   August 21, 2010 at 8:58 PM

   You might be interested in the solution in scriptJ(TM) at

   http://arxiv4.library.cornell.edu/abs/1008.2748v1

   Cheers,
   Carl
7. programmingpraxis said

   August 22, 2010 at 12:38 PM

   Carl,

   Thanks for the link. And thanks for visiting my corner of the web.

   Phil