## 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],])
(5,[[5,10],[6,9],[7,8],[1,3,4],])
(5,[[5,10],[6,9],[7,8],[1,2,4],])
(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);
total = atoi(argv);
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
...
```