## Sticks

### October 7, 2016

It might help you to know that the exercise is given in the chapter on priority queues:

(define (stick xs) (if (null? xs) 0 (let loop ((pq (list->pq < xs)) (cost 0)) (let ((s1 (pq-first pq))) (set! pq (pq-rest < pq)) (if (pq-empty? pq) cost (let ((s2 (pq-first pq))) (set! pq (pq-rest < pq)) (loop (pq-insert < (+ s1 s2) pq) (+ cost s1 s2))))))))

This solution repeatedly picks the two smallest sticks from the bunch, combines them, then throws the new (combined) stick back in the bunch, stopping when there is only one stick remaining; the bunch is stored in a priority queue so it is easy to find the two smallest sticks. Here are some examples:

> (stick '()) 0 > (stick '(1)) 0 > (stick '(1 2 4)) 10 > (stick '(1 9 6 2 5)) 48 > (stick '(24 25 28 4 6 10 9)) 270 > (stick '(10 6 1 4 11)) 69

You can run the program at http://ideone.com/xJnzXK, where you will also see the priority queue code from a previous exercise.

Advertisements

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);

}

In Ruby