Two Boys And A Canoe
March 11, 2016
We use a greedy algorithm. First we sort, and discard any weights that exceed 150 pounds. Then we set pointers at the light and heavy boys. If the sum of the two doesn’t exceed 150 pounds, the two boys share a canoe and the two pointers move toward the middle. Otherwise, the boy at the heavy pointer gets his own canoe, and the heavy pointer moves to the middle. The process repeats until no boys are left:
(define (canoes xs)
(let ((xv (list->vector (sort < xs)))
(len (length xs)))
(define (x i) (vector-ref xv i))
(let loop ((lo 0) (hi (- len 1)) (cs (list)))
(cond ((< hi lo) cs)
((< 150 (x hi))
(loop lo (- hi 1)
(cons (list (x hi) 'toobig) cs)))
((= lo hi) (cons (list (x hi)) cs))
((<= (+ (x lo) (x hi)) 150)
(loop (+ lo 1) (- hi 1)
(cons (list (x lo) (x hi)) cs)))
(else (loop lo (- hi 1)
(cons (list (x hi)) cs)))))))
That gives a list of the canoe pairings. It’s easy to turn that into a count:
(define (canoe-count xs)
(length (filter (lambda (c)
(or (null? (cdr c))
(not (equal? (cadr c) 'toobig))))
(canoes xs))))
Here are some examples:
> (canoes '(40 120 122 124 156 100 140 20 50 80 30 60 80 100 40 70 30 20)) ((60 70) (50 80) (40 80) (40 100) (30 100) (30 120) (20 122) (20 124) (140) (156 toobig)) > (canoe-count '(40 120 122 124 156 100 140 20 50 80 30 60 80 100 40 70 30 20)) 9
That program runs in O(n log n), because of the sort; if you use a counting sort instead of a comparison sort, you could reduce that to O(n). You can run the program at http://ideone.com/6mnZM5.
By the way, the exercise is a lot more fun if you allow three boys per canoe, still retaining the maximum weight of 150 pounts.
Programming Praxis 
I believe we can avoid the pairing part of the algorithm as follows (in C#):
int limit = 150 – weights[0];
int index = 0;
while(index < N && weights[index] 150 removed, all weights > limit get their own canoe
and the remainder get remainder/2 canoes (adding 1 if remainder is odd).
int limit = 150 – weights[0];
int index = 0;
while(index < N && weights[index] <= limit)
index++;
int canoes = N – (index/2) + (index % 2);
Just thought of a special case for which the above algorithm fails. So pairing appears necessary.
# Simple version for the requirements. I think a nicer one would pair the heaviest pairs that would fit, to reduce the mismatch between boys.
# https://programmingpraxis.com/2016/03/11/two-boys-and-a-canoe/
boys = [40, 120, 122, 124, 156, 100, 140, 20, 50, 80, 30, 60, 80, 100, 40, 70, 30, 20]
limit = 150
boys.sort()
canoes = 0
while boys:
w = boys.pop()
if w > limit:
print “%d swims” % w
elif not boys or ( w + boys[0] > limit ):
canoes += 1
print “%d goes in canoe #%d”%(w, canoes)
else:
z = boys.pop(0)
canoes += 1
print “%d and %d go in canoe #%d”%(w,z, canoes)
“””
python boys_vs_canoes.py
156 swims
140 goes in canoe #1
124 and 20 go in canoe #2
122 and 20 go in canoe #3
120 and 30 go in canoe #4
100 and 30 go in canoe #5
100 and 40 go in canoe #6
80 and 40 go in canoe #7
80 and 50 go in canoe #8
70 and 60 go in canoe #9
“””
# https://programmingpraxis.com/2016/03/11/two-boys-and-a-canoe/
# with nicer pairing
boys = [40, 120, 122, 124, 156, 100, 140, 20, 50, 80, 30, 60, 80, 100, 40, 70, 30, 20]
limit = 150
boys.sort()
canoes = 0
while boys:
w = boys.pop()
if w > limit:
print “%d swims” % w
elif not boys or ( w + boys[0] > limit ):
canoes += 1
print “%d goes in canoe #%d”%(w, canoes)
else:
z = [ i for i in boys if (w+i) <= limit][-1] # heaviest matching boy
boys.remove(z)
canoes += 1
print "%d and %d go in canoe #%d"%(w,z, canoes)
"""
python boys_vs_canoes.py
156 swims
140 goes in canoe #1
124 and 20 go in canoe #2
122 and 20 go in canoe #3
120 and 30 go in canoe #4
100 and 50 go in canoe #5
100 and 40 go in canoe #6
80 and 70 go in canoe #7
80 and 60 go in canoe #8
40 and 30 go in canoe #9
"""
Somehow I thought the vessels were kayaks. Anyway, here is my code (in Julia):
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})
w = copy(w_)
mw = 150
n = length(w)
z = Array(Int64, n)
c = 1
while true
combos = collect(combinations(1:n, 2))
N = length(combos)
d = Array(Int64, N)
for i = 1:N
d[i] = mw – w[combos[i][1]] – w[combos[i][2]]
end
nnd = copy(d)
nnd[d .< 0] = 999 # non-negative differences
ind = indmin(nnd)
if nnd[ind] < mw
z[combos[ind]] = c
w[combos[ind]] = 999
c += 1
else
for i = 1:n
if w[i] < 999
z[i] = c
c += 1
end
end
return z, maximum(z)
end
end
end
Disclaimer: That's a pretty horrible algo I've used, but considering the requirements of the problem, I figured it should do the trick. Besides, in Julia everything works pretty fast.
It would be interesting to see how this problem escalates when a new type of vessel is introduced (e.g. boat), holding 3 kids in it. Also, it would cool to examine if more than vessel options exist (e.g. both canoes and boats).
I am learning Rust. Here’s my Rust solution. It prints the names of the boys in each canoe.
type WeightType = u32;
const TARGET_WEIGHT: WeightType = 150;
#[derive(Clone, Debug)]
pub struct Boy {
name: String,
weight: WeightType,
}
pub type CubPack = Vec<Boy>;
#[derive(Debug)]
pub enum Canoe {
Solo(Boy),
Duet(Boy, Boy),
}
impl Canoe {
fn weight(&self) -> WeightType {
match *self {
Canoe::Solo(ref boy) => boy.weight,
Canoe::Duet(ref b0, ref b1) => b0.weight + b1.weight,
}
}
}
pub type Canoes = Vec<Canoe>;
pub fn assign_canoes(cubs: &CubPack) -> Canoes {
let mut canoes: Canoes = Vec::new();
let mut cubs = cubs.clone();
cubs.sort_by_key(|boy| boy.weight + 0);
let mut assigned: Vec<bool> = cubs.iter().map(|_| false).collect();
let mut heavy = cubs.len();
for light in 0..cubs.len() {
if assigned[light] {
continue;
}
while !assigned[light] && heavy > light + 1 {
if cubs[light].weight + cubs[heavy – 1].weight <= TARGET_WEIGHT {
assigned[light] = true;
assigned[heavy – 1] = true;
canoes.push(Canoe::Duet(cubs[light].clone(),
cubs[heavy – 1].clone()));
}
heavy -= 1;
}
if !assigned[light] {
canoes.push(Canoe::Solo(cubs[light].clone()));
assigned[light] = true;
}
}
canoes
}
fn cub_pack() -> CubPack {
vec![
Boy { name: "Billy".to_string(), weight: 93 },
Boy { name: "Timmy".to_string(), weight: 67 },
Boy { name: "Johnny".to_string(), weight: 119 },
Boy { name: "Bobby".to_string(), weight: 113 },
Boy { name: "Ralphie".to_string(), weight: 110 },
Boy { name: "Bart".to_string(), weight: 114 },
Boy { name: "Carter".to_string(), weight: 83 },
Boy { name: "Davey".to_string(), weight: 101 },
Boy { name: "Kevin".to_string(), weight: 47 },
Boy { name: "Alan".to_string(), weight: 112 },
Boy { name: "Eric".to_string(), weight: 49 },
Boy { name: "Craig".to_string(), weight: 54 },
Boy { name: "Brad".to_string(), weight: 85 },
]
}
fn main() {
let canoes = assign_canoes(&cub_pack());
for canoe in canoes {
match canoe {
Canoe::Solo(ref boy) => {
println!("{} lb: {}", canoe.weight(), boy.name)
}
Canoe::Duet(ref b0, ref b1) => {
println!("{} lb: {}, {}", canoe.weight(), b0.name, b1.name)
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_none() {
let cub_pack: CubPack = vec![];
let canoes = assign_canoes(&cub_pack);
assert!(canoes.len() == 0);
}
#[test]
fn test_solos() {
let cub_pack: CubPack = vec![
Boy { name: "Billy".to_string(), weight: 85 },
Boy { name: "Timmy".to_string(), weight: 80 },
];
let canoes = assign_canoes(&cub_pack);
assert!(canoes.len() == 2);
if let Canoe::Solo(ref boy) = canoes[0] {
assert!(boy.name == "Timmy");
assert!(boy.weight == 80);
} else {
panic!("");
}
if let Canoe::Solo(ref boy) = canoes[1] {
assert!(boy.name == "Billy");
assert!(boy.weight == 85);
} else {
panic!("");
}
}
#[test]
fn test_duet() {
let cub_pack: CubPack = vec![
Boy { name: "Billy".to_string(), weight: 80 },
Boy { name: "Timmy".to_string(), weight: 70 },
];
let canoes = assign_canoes(&cub_pack);
assert!(canoes.len() == 1);
if let Canoe::Duet(ref b0, ref b1) = canoes[0] {
assert!(b0.name == "Timmy");
assert!(b0.weight == 70);
assert!(b1.name == "Billy");
assert!(b1.weight == 80);
} else {
panic!("");
}
}
#[test]
fn test_mixed() {
let cub_pack: CubPack = vec![
Boy { name: "Billy".to_string(), weight: 80 },
Boy { name: "Kevin".to_string(), weight: 70 },
Boy { name: "Timmy".to_string(), weight: 70 },
];
let canoes = assign_canoes(&cub_pack);
assert!(canoes.len() == 2);
if let Canoe::Duet(ref b0, ref b1) = canoes[0] {
assert!(b0.name == "Kevin");
assert!(b0.weight == 70);
assert!(b1.name == "Billy");
assert!(b1.weight == 80);
} else {
panic!("");
}
if let Canoe::Solo(ref boy) = canoes[1] {
assert!(boy.name == "Timmy");
assert!(boy.weight == 70);
} else {
panic!("");
}
}
}
Here is the output.
Lovely formatting. (*sigh*) Here it is on Pastebin. http://pastebin.com/hW0bjYGC