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.
Programming Praxis 
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.
def stick(seq): cost = 0 heap = list(seq) heapify(heap) while len(heap) > 1: newitem = heappop(heap) + heap[0] cost += newitem heapreplace(heap, newitem) return cost@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
var sticks1 = [10, 6, 1, 4, 11] var e1 = 69 var sticks2 = [1,2,4] var e2 = 10 function mincost(sticks) { var total = 0 var sortedSticks = sticks.sort(function(a,b) { return a > b }); /* remove limit case */ if(sortedSticks.length < 2) return 0 var total = sortedSticks.shift() + sortedSticks.shift() var combine = total sortedSticks.forEach(function(stick) { total = (combine = combine + stick) + total }) return total; } console.log(mincost(sticks2), e2) console.log(mincost(sticks1), e1)Thank’s
In Common Lisp :
(defun stick (s) (setf s (sort s #'<)) (let ((cost 0) (the-sum 0)) (do ((x (pop s) (or (null s) (pop s)))) ((null s) cost) (setf the-sum (+ x (car s)) cost (+ cost the-sum) s (insert-sorted the-sum (cdr s)))))) (defun insert-sorted (obj lst) (if (null lst) (cons obj nil) (if (< obj (car lst)) (cons obj lst) (cons (car lst) (insert-sorted obj (cdr lst))))))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
def combine(xs, cost=0) if xs.size < 2 cost else a, b, *rest = xs.sort combine([a + b].concat(rest), a + b + cost) end end combine([]) -> 0 combine([1]) -> 0 combine([2,1,4]) -> 10 combine([24,25,28,4,6,10,9]) -> 270