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 |