Programming Praxis

8 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
8. Will Ness said

   September 4, 2023 at 5:35 PM

   Hi Phil, hope all is well. :)

   https://www.dreamsongs.com/10ideas.html contains John McCarthy’s (himself!) Common Lisp solution using the “gopher” function, which surgically rotates each tree in turn to the right until its left child is a leaf.

   Similarly, the Haskell solution above is problematic. The implied constraint in the problem is that the leaves enumeration be done in O(n) i.e. without any unnecessary overhead, but that flatten implementation will be quadratic for trees which are left-degenerate. Instead, and similar to the “gopher” idea, it should be defined as

       flatten t = go t []  where
           go (Leaf x) xs = [x] ++ xs
           go (Node lt rt) xs = go lt (go rt xs)
   

   which can be seen as doing the said rotations implicitly, if we squint hard enough, since just as a gopher it burrows down to the leftmost leaf first, thanks to Haskell’s lazy evaluation.