October 7, 2016 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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.
By Ala'a Alawi (@AlaaMgrahi) on October 7, 2016 at 7:40 PM
@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.
By programmingpraxis on October 7, 2016 at 7:49 PM
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 costBy Paul on October 7, 2016 at 8:50 PM
@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…
By Zack on October 8, 2016 at 12:10 AM
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
By Ala'a Alawi (@AlaaMgrahi) on October 8, 2016 at 5:24 PM
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
By Julien Laville on October 10, 2016 at 3:43 PM
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))))))By Jérôme Radix (@_jradix_) on October 11, 2016 at 10:11 AM
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);
}
By Aquiles Peña on October 18, 2016 at 3:39 PM
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]) -> 270By V on October 28, 2016 at 7:33 AM