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.

Posted by programmingpraxis

Filed in Exercises

8 Comments »

8 Responses to “Two Boys And A Canoe”

Ernie said
March 12, 2016 at 4:20 PM
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).
Ernie said
March 12, 2016 at 4:21 PM
int limit = 150 – weights[0];
int index = 0;
while(index < N && weights[index] <= limit)
index++;
int canoes = N – (index/2) + (index % 2);
Ernie said
March 12, 2016 at 6:33 PM
Just thought of a special case for which the above algorithm fails. So pairing appears necessary.
George Bullis said
March 13, 2016 at 8:26 PM
# 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
“””
George Bullis said
March 13, 2016 at 8:32 PM
# 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
"""
Zack said
March 14, 2016 at 6:25 PM
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).
kbob said
March 15, 2016 at 6:26 AM
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.
```
148 lb: Kevin, Davey
142 lb: Eric, Billy
139 lb: Craig, Brad
150 lb: Timmy, Carter
110 lb: Ralphie
112 lb: Alan
113 lb: Bobby
114 lb: Bart
119 lb: Johnny
```
kbob said
March 15, 2016 at 6:28 AM
Lovely formatting. (*sigh*) Here it is on Pastebin. http://pastebin.com/hW0bjYGC

Programming Praxis