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

Pages: 1 2

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