P92

We represent the tree as nested lists in the form

# edge:  number
# node:  (number . name)
# tree:  (edge node [tree ..])

For example, the representation of the first example's solution is

   (7 (7 . a)
      (4 (3 . b)
         (3 (6 . c))
         (2 (5 . e)
            (1 (4 . f)) ) )
      (6 (1 . d))
      (5 (2 . g)) )

The function 'kochConjecture' iterates a tree skeleton like

(0 (0 . a)
   (0 (0 . b)
      (0 (0 . c))
      (0 (0 . e)
         (0 (0 . f)) ) )
   (0 (0 . d))
   (0 (0 . g)) ) )

to obtain solutions like the one above.

(de kochConjecture (Tree)
   (let
      (Cnt                             # Calculate number of nodes
         (recur (Tree)
            (if Tree
               (inc (sum recurse (cddr Tree)))
               0 ) )
         Edges (range 1 (dec Cnt))     # List of edge numbers
         Nodes (range 1 Cnt)           # List of node numbers
         L Nodes )
      (set Tree Cnt)                   # Set top edge (just for symmetry)
      (unless
         (recur (L)                    # Generate node number permutations
            (if (cdr L)
               (do (length L)
                  (NIL (recurse (cdr L)))
                  (rot L) )
               (use Nodes                 # Try next node number permutation
                  (recur (Tree)
                     (set (cadr Tree) (pop 'Nodes))
                     (mapc recurse (cddr Tree)) ) )
               (use Edges                 # Try to fit edges
                  (recur (Tree)
                     (let N (caadr Tree)  # Node number
                        (find
                           '((X)
                              (let E (abs (- N (caadr X)))  # Calculate edge
                                 (or
                                    (not (member E Edges))
                                    (prog
                                       (del E 'Edges)
                                       (set X E)
                                       (recurse X) ) ) ) )
                           (cddr Tree) ) ) ) ) ) )
         Tree ) ) )

Test run (using 'pretty' to pretty-print the result):

(pretty
   (kochConjecture
      (0 (0 . a)
         (0 (0 . b))
         (0 (0 . c)
            (0 (0 . d)
               (0 (0 . k)) )
            (0 (0 . e)
               (0 (0 . q)
                  (0 (0 . m))
                  (0 (0 . n)
                     (0 (0 . p)) ) ) )
            (0 (0 . f)) )
         (0 (0 . g))
         (0 (0 . h))
         (0 (0 . i)) ) ) )

This returns as the first solution

(14
   (1 . a)
   (1 (2 . b))
   (13
      (14 . c)
      (11 (3 . d) (9 (12 . k)))
      (3
         (11 . e)
         (6
            (5 . q)
            (2 (7 . m))
            (5 (10 . n) (4 (6 . p))) ) )
      (10 (4 . f)) )
   (7 (8 . g))
   (8 (9 . h))
   (12 (13 . i)) )

http://picolisp.com/wiki/?99p92

15jul10

abu