Three Boys And A Canoe

March 15, 2016

In the previous exercise we looked at a simple programming problem: determining the number of canoes needed for a group of boy scouts of varying weights, where each canoe could hold two boys. Today we extend that problem to the case of three boys or, more generally, n boys.

Your task is to modify your previous solution to handle the case of three boys; if you are ambitious, handle the case of n boys. There is no suggested solution, as I am on vacation visiting my daughter in Houston and don’t have time to write one. Feel free to post your solutions or discuss the exercise in the comments below.

3 Responses to “Three Boys And A Canoe”

  1. Zack said

    function create_weights_vector(n::Int64, mw::Int64 = 150)
    w = round(Int64, 10*randn(n) + 75)
    w[w .> mw] = mw
    return w
    end

    function find_number_of_kayaks(w_::Array{Int64, 1}, k::Int64 = 3, mw::Int64 = 0)
    if mw == 0
    mw = 75*k
    end

    mw1 = mw + 1
    w = copy(w_)
    n = length(w)
    z = Array(Int64, n)
    c = 1
    combos = collect(combinations(1:n, k))
    N = length(combos)
    d = Array(Int64, N) # distances vector for all possible combos

    for i = 1:N
    d[i] = mw – sum(w[combos[i]])
    end

    d[d .< 0] = mw1 # make negative differences really unattractive solutions

    while true
    ind = indmin(d) # index of best combo

    if d[ind] < mw
    q = combos[ind]
    z[q] = c
    w[q] = mw1

    for i = 1:N
    for j = 1:k
    if q[j] in combos[i]
    d[i] = mw1
    break
    end
    end
    end

    c += 1
    else # check if a single kid can go aboard (all usable combos have been exhausted)
    for i = 1:n
    if w[i] <= mw
    w[i] = mw1
    z[i] = c
    c += 1
    end
    end

    return z, maximum(z)
    end
    end
    end

    This solution works for various values of boat sizes (including 2 and 3) and is fairly fast. Adjusted the maximum weight that each vessel can hold, so that it ensures a capacity of n, for the majority of cases. Solution for 100 passengers and canoes having capacity of 3 takes about 0.58 sec on my laptop (without using multi-threading).

  2. matthew said

    Nice optimization problem. Here’s a backtracking solution in Haskell:

    import Control.Monad
    
    total = 15 :: Int
    maxlen = 3 :: Int
    weights = [10,9..1]
    
    scan sum t [] [] = [(t,[])]
    scan sum t (min:s) [] =
      if length t < maxlen && sum + min <= total then []
      else [(t,reverse(min:s))]
    scan sum t s (a:r) =
      if length t == maxlen then [(t,reverse s ++ (a:r))]
      else
      (if sum+a > total then [] else scan (sum+a) (a:t) s r) ++
      (scan sum t (a:s) r)
    
    scan1 (a:r) =
     if a > total then []
     else scan a [a] [] r
    
    allocations [] = [[]]
    allocations s = concatMap (\(t,r) -> map (t:) (allocations r)) (scan1 s)
    
    main = mapM_ print (map (\s->(length s, s)) (allocations weights))
    

    An allocation for some list of weights is an allocation to a single canoe of the largest weight and some other weights (such that we can’t add any more to the canoe without exceeding the limits) and an allocation of the remaining weights.

    For the parameters above, we find 70 solutions using 4 or 5 canoes, the first few are:

    (5,[[5,10],[6,9],[7,8],[2,3,4],[1]])
    (5,[[5,10],[6,9],[7,8],[1,3,4],[2]])
    (5,[[5,10],[6,9],[7,8],[1,2,4],[3]])
    (4,[[5,10],[6,9],[3,4,8],[1,2,7]])
    (4,[[5,10],[6,9],[2,4,8],[1,3,7]])
    ...
    
  3. matthew said

    And here is a backtracking solution in C++ using essentially the same method as the previous Haskell solution. We use Knuth’s dancing links trick to swap elements in and out of a double linked list (so the root always points to the list of unallocated elements). To keep things simple, this one doesn’t impose a limit on the number of boys per canoe, just the total weight (and the output format is a rather minimalistic).

    #include <stdio.h>
    #include <stdlib.h>
    
    struct Node {
      Node(Node *prev_, Node *next_, int value_)
        : prev(prev_), next(next_), aux(0), value(value_) {}
      Node *prev;
      Node *next;
      Node *aux;
      int value;
    };
    
    void remove(Node *p) {
      p->prev->next = p->next;
      p->next->prev = p->prev;
    }
    
    void restore(Node *p) {
      p->prev->next = p;
      p->next->prev = p;
    }
    
    void show(Node *p, bool top) {
      if (p) {
        show(p->aux,false);
        printf("%d%s", p->value, top?"\n":" ");
      }
    }
    
    Node *root;
    int total;
    
    // t is allocation so far, s is remaining elements
    void scan1(Node *t, Node *s);
    
    // sum is total weight for current canoe.
    void scan(Node *t, Node *s, int sum) {
      for ( ; s != root; s = s->next) {
        int a = s->value;
        if (sum+a <= total) {
          remove(s);
          s->aux = t;
          scan (s, s->next, sum+a); // recurse with s in the set
          restore(s);
        }
      }
      if (root->next == root) {
        show(t,true); // All elements used, we have a solution.
      } else {
        int min = root->prev->value; // last element is smallest
        if (sum + min > total) {     // check set is maximal
          scan1(t,root->next);
        }
      }
    }
    
    void scan1(Node *t, Node *s) {
      if (s->value <= total) {
        s->aux = t;
        remove(s);
        scan(s, s->next, s->value);
        restore(s);
      }
    }
    
    int main(int argc, char *argv[]) {
      int count = atoi(argv[1]);
      total = atoi(argv[2]);
      root = new Node(0,0,0);
      root->prev = root->next = root;
      for (int i = 1; i <= count; i++) {
        Node *p = new Node(root,root->next,i);
        restore(p); // Insert in list at front.
      }
      scan1(0,root->next);
    }
    

    Sample output:

    $ ./canoe 10 15
    10 5 9 6 8 7 4 3 2 1
    10 5 9 6 8 4 3 7 2 1
    10 5 9 6 8 4 2 1 7 3
    10 5 9 6 8 3 2 1 7 4
    10 5 9 4 2 8 7 6 3 1
    ...
    

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: