5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Please note: a tree of size n may not contain all numbers up to n. \$\endgroup\$ – Howard Jul 15 '11 at 8:11
  • 1
    \$\begingroup\$ Is it a requirement to compute the /complete/ tree even though the output does not require all that information? \$\endgroup\$ – Thomas Eding Jul 24 '11 at 7:46
  • \$\begingroup\$ Yeah, MtnViewMark's solution does not comply with that requirement. \$\endgroup\$ – boothby Jul 25 '11 at 7:32
  • \$\begingroup\$ That interpretation of the requirement excludes any lazy language. Since the program doesn't actually use the complete tree, nothing will ever cause the computation to happen. See my expanded solution notes. I suppose one could compel a lazy language to write those results to /dev/null... but why? \$\endgroup\$ – MtnViewMark Jul 26 '11 at 2:57
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ This doesn't compute the complete tree with n nodes. \$\endgroup\$ – boothby Jul 25 '11 at 7:33
  • \$\begingroup\$ It wasn't clear how to apply the requirements to a lazy language. Usually, an input value like this is given as a help so solutions can just allocate a fixed array. Solutions in dynamic languages often ignore such input (or limits in the spec). I took the input to be a hint to the program as a bound on subsequent inputs. Indeed a program that meets the input/output requirements of this problem needn't use it at all. Typically, code-golf doesn't mandate how the internals achieve the results. \$\endgroup\$ – MtnViewMark Jul 26 '11 at 1:58
  • \$\begingroup\$ Fascinating. What kind of runtime do you get to compute the chain for 50M? The algorithm Knuth describes is O(n lg n) time and 2n+lg n space. \$\endgroup\$ – boothby Jul 26 '11 at 7:08
  • \$\begingroup\$ The algorithm used was aiming for code-golf, not time efficiency: It is roughly O(n^3 lg n) in time, though oddly only O(n) in space. On my somewhat aging CPU, it can compute the chain for 10k in 9.58s, or just about 100x the time it took to compute the chain for 1k. I'm pretty sure computing the chain for 50M wouldn't be possible with this code. \$\endgroup\$ – MtnViewMark Jul 27 '11 at 4:31
  • \$\begingroup\$ So, that's why I make the requirement that you compute the whole tree. The point of code-golf (IMO) is to satisfy all requirements in the smallest number of characters. If you're not satisfying all the requirements, it's a fail. \$\endgroup\$ – boothby Jul 27 '11 at 4:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.