Two Boys And A Canoe
March 11, 2016
We have today an interview question from Google:
A group of Boy Scouts is taking a trip by canoe and needs to determine how many canoes to rent. A canoe can hold one or two boys and a total of 150 pounds. Given a list of boys’ weights, how many canoes are needed?
Your task is to write a program that determines how may canoes are needed. 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.
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