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.

Advertisements

Pages: 1 2

9 Responses to “Sticks”

  1. 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.

  2. programmingpraxis said

    @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.

  3. Paul said

    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
    
  4. Zack said

    @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…

  5. 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

  6.  
        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

  7. 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))))))
    
  8. Aquiles Peña said

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

  9. V said

    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
        
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: