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

Advertisements

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

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

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:

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

Sample output: