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.

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 )

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: