## Sticks

### October 7, 2016

We continue our occasional series of textbook exercises:

You are given a bunch of sticks, each of integer length. Two sticks can be combined into a single, larger stick by a process that costs the sum of the lengths of the two sticks. Your goal is to build a single stick combining all the original sticks, at minimal cost.

For example, suppose you initially have three sticks of lengths 1, 2, and 4. You could combine sticks 2 and 4 at a cost of 6, then combine that stick with stick 1 at a cost of 7, for a total cost of 13. But it is better to first combine sticks 1 and 2 at a cost of 3, then combine that stick with stick 4 at a cost of 7, for a total cost of 10.

Your task is to write a program that combines a bunch of sticks at minimal cost. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

APL

mincost ← {+/1↓+\(⍵,⍬)[⍋⍵,⍬]}

Examples:

mincost ⍬

0

mincost 1

0

mincost 1 2 4

10

mincost 1 9 6 2 5

48

mincost 24 25 28 4 6 10 9

295

mincost 10 6 1 4 11

69

Explanation: +/1↓+\(⍵,⍬)[⍋⍵,⍬] (from right to left)

⍵,⍬ the left argument concatenated to empty vector (zilde)

⍋⍵,⍬ get sorted vector indexes

(⍵,⍬)[⍋⍵,⍬] sort the vector

+\ running sum

1↓ drop first item

+/ sum numbers

Note: I got 295 for the second from bottom example! shouldn’t that be the answer?

Note2: Beginner in APL.

@Ala’a Alawi: The answer to the second-last problem is 270:

1) 4 6 9 10 24 25 28 combine 4 and 6 at a cost of 10

2) 9 10 10 24 25 28 combine 9 and 10 at a cost of 19

3) 10 19 24 25 28 combine 10 and 19 at a cost of 29

4) 24 25 28 29 combine 24 and 25 at a cost of 49

5) 28 29 49 combine 28 and 29 at a cost of 57

6) 49 57 combine 49 and 57 at a cost of 106

The total cost is 10 + 19 + 29 + 49 + 57 + 106 = 270.

In Python.

@Ala’s Alawi, yes. You got it right.

Here is my implementation of the solution, in Julia.

function s(x::Array)

n = length(x)

sx = sort(x)

z = (n-1)*(sx[1] + sx[2])

for i = 3:n

z += (n+1-i)*sx[i]

end

return z

end

For an array of 10^6 random integers, it yields a solution in less than 0.1 sec, using less than 1MB of memory. I think that’s quite decent for a first draft, developed on the REPL…

Thanks programmingpraxis for the explanation. “then combine that stick with” twice got me there (i.e. implicitly saying that the next will be added to the already assembled stick)

Here is the update (I know it may not be the best APL, but excuse my newbie mode)

∇cost←mincost sticks ;C;S ⍝ Calculate the minimum cost of assembling a vector of sticks.

cost←0 ◊ →(0=⍴1↓sticks)/0 ⍝ Initialize cost to zero, exit if sticks are 1 or less (/0 jump to line 0 meaning exit).

C ← +/2↑S←sort sticks ⍝ Calculate cost ‘C’ from the first smallest items taken from sorted sticks ‘S’.

cost ← C + mincost C,2↓S ⍝ Recur with the new glued stick added to the rest of the sticks.

mincost ⍬

0

mincost 1

0

mincost 1 2 4

10

mincost 1 9 6 2 5

48

mincost 24 25 28 4 6 10 9

270

mincost 10 6 1 4 11

69

Thank’s

In Common Lisp :

In PHP

function minimal_sum($A) {

$a=array_values($A);

$l=sizeof($A)-1;

$n=0;

for($i=0; $i<$l; $i++) {

asort($a);

$a=array_values($a);

$a[1]=$a[0]+$a[1];

$n=$n+$a[1];

unset($a[0]);

}

return print_r($n);

}