Knuth's Power Tree

Question

In The Art of Computer Programming, Knuth describes an algorithm to compute short addition chains. The algorithm works by computing a tree known as the Power Tree. The tree is rooted at 1, and each level is computed from the previous. Suppose we've computed level k. Then, for each node (n) in level k, and each ancestor (or self) a = 1, 2, ..., n of n, add the node n+a to level k+1 if it is not already in the tree; the parent of n+a is n.

Three important things to note:

• nodes should be visited in the order that they are created
• levels are to be computed one at a time (not recursively)
• traverse the ancestors from smallest to largest (or you end up a familiar, but less optimal tree)

A picture of the tree

Perhaps drawing this tree would be fun to golf? Hmm. At the least, the result would probably be a better-drawn tree. FWIW, 10 has 4 children.

             1
             |
             2
            / \
           3   4
          /\    \
         /  \    \
        5    6    8
       / \    \\   \
      /  |     \\   \
     /   |      \\   \
    7    10     9 12  16
   /   / /\ \    \ \   \\
  /   / /  \ \    \ \   \\
14  11 13  15 20  18 24 17 32

Naive Python Implementation

Since my verbose description of the tree seems to be lacking, here's a naive Python implementation. I store the tree as a dictionary here, parent(x) := tree[x]. There's lots of fun optimization to be had here.

def chain(tree,x):
    c = [x]
    while x!=1:
        x=tree[x]
        c.append(x)
    return c[::-1]

tree = {1:None} 
leaves = [1]
levels = 5
for _ in range(levels):
    newleaves = []
    for m in leaves:
        for i in chain(tree,m):
            if i+m not in tree:
                tree[i+m] = m
                newleaves.append(i+m)
    leaves = newleaves

Requirements

Your program should take one argument n, compute the complete tree with all integer nodes i with 0 <= i <= n, and then take input from the user. For each input, print out the path from the root to that input. If an input isn't an integer between 0 and n (inclusive), behavior is undefined. Terminate if the user inputs zero.

Example Session

./yourprogram 1000
?1000
1 2 3 5 10 15 25 50 75 125 250 500 1000
?79
1 2 3 5 7 14 19 38 76 79
?631
1 2 3 6 12 24 48 49 97 194 388 437 631
?512
1 2 4 8 16 32 64 128 256 512
?997
1 2 3 5 7 14 28 31 62 124 248 496 501 997
?0

Answer 1

Ruby, 172 148 139 137 characters

P={1=>[1]}
a=->k{P[k].map{|t|P[k+t]||=P[k]+[k+t]}}
P.keys.map{|v|a[v]}until(1..$*[0].to_i).all?{|u|P[u]}
STDIN.map{|l|p P[l.to_i]||break}

Most of the code is for input and output. Building the tree is only a few chars (lines 1-2). The tree is represented by a hash where key is the node and value its path to root. Since a tree of size n may not contain all numbers up to n we continuously add more levels until all numbers up to n are present in the tree.

For the example given above:

>1000
[1, 2, 3, 5, 10, 15, 25, 50, 75, 125, 250, 500, 1000]
>79
[1, 2, 3, 5, 7, 14, 19, 38, 76, 79]
>631
[1, 2, 3, 6, 12, 24, 48, 49, 97, 194, 388, 437, 631]
>512
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
>0

Edit 1: Now the hash contains the path for each node as value already and therefore there is no need to build the path each time.

Edit 2: Changed the break condition for the final loop.

Edit 3: Changed the condition for the build-loop.

Answer 2

Haskell, 174 185 195 characters

(%)=lookup
t(n,w)=map(\m->(n+m,n+m:w))w
_#0=return()
k#n=maybe(foldr(\e@(i,_)r->maybe(e:r)(\_->r)$i%r)k(k>>=t)#n)((>>main).print.reverse)$n%k
main=getLine>>=([(1,[1])]#).read

This version actually totally ignores the argument, and calculates the tree incrementally on demand.

1000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
79
[1,2,3,5,7,14,19,38,76,79]
631
[1,2,3,6,12,24,48,49,97,194,388,437,631]
512
[1,2,4,8,16,32,64,128,256,512]
997
[1,2,3,5,7,14,28,31,62,124,248,496,501,997]
0

Oh look! There wasn't any requirement to output a prompt. So now the code doesn't.

---

• Edit (195 → 185): combined main and i
• Edit (185 → 174): removed prompt

---

Ungolf'd

Here is an expanded version of the core computation:

type KPTree = [(Int, [Int])]
  -- an association from numbers to their ancester chains
  -- ancester chains are stored biggest to smallest
  -- the associations are ordered as in the tree, reading right to left,
  -- from the lowest level up

kptLevels :: [KPTree]
kptLevels = [(1,[1])] : map expand kptLevels
  -- a list of successive KPTrees, each one level deeper than the last
  where
    expand tree = foldr addIfMissing tree (concatMap nextLeaves tree)
    addIfMissing e@(n,_) tree = maybe (e:tree) (const tree) $ lookup n tree
    nextLeaves (n,w) = map (\m -> (n+m, n+m:w)) w

kptPath :: Int -> [Int]
kptPath n = findIn kptLevels
  -- find the ancestor chain for a given number
  where
    findIn (k:ks) = maybe (findIn ks) id $ lookup n k

To illustrate the strangeness of how to apply the pre-computation requirement to a lazy language, consider this version of main:

kptComputeAllTo :: Int -> [[Int]]
kptComputeAllTo n = map kptPath [1..n]
  -- compute all the paths for the first n integers

main :: IO ()
main = do
    n <- (read . head) `fmap` getArgs
    go $ kptComputeAllTo n
  where    
    go preComputedResults = loop
      where
        loop = getLine >>= process . read
        process 0 = return ()
        process i = (print $ reverse $ preComputedResults !! (i - 1)) >> loop

Even thought it builds an array of the results for the first n integers, only those that are used are ever actually computed! Here's how fast it runs with 50 million as an argument:

> (echo 1000; echo 0) | time ./3177-PowerTree 50000000
[1,2,3,5,10,15,25,50,75,125,250,500,1000]
        0.09 real         0.07 user         0.00 sys