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.

Advertisement

Pages: 1 2

8 Responses to “Two Boys And A Canoe”

  1. Ernie said

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

  2. Ernie said

    int limit = 150 – weights[0];
    int index = 0;
    while(index < N && weights[index] <= limit)
    index++;
    int canoes = N – (index/2) + (index % 2);

  3. Ernie said

    Just thought of a special case for which the above algorithm fails. So pairing appears necessary.

  4. # 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
    “””

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

  6. Zack said

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

  7. kbob said

    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
    
  8. kbob said

    Lovely formatting. (*sigh*) Here it is on Pastebin. http://pastebin.com/hW0bjYGC

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: