Possible "boat loads"

Question

You know the river-crossing problems. Here is a sort description:

Once upon a time, three cannibals were guiding three missionaries through a jungle. They were on their way to the nearest mission station. After some time, they arrived at a wide river, filled with deadly snakes and fish. There was no way to cross the river without a boat. Fortunately, they found a row boat with two oars after a short search. Unfortunately, the boat was too small to carry all of them. It could barely carry two people at a time. Worse, because of the river's width there was no way to bring the boat back other than to row it back. Since the missionaries could not trust the cannibals they had to figure out a plan to get all six of them safely across the river. The problem was that these cannibals would kill and eat missionaries as soon as there were more cannibals than missionaries at some place. Thus our missionary-programmer had to devise a plan that guaranteed that there were never any missionaries in the minority at either side of the river. The cannibals, however, can be trusted to cooperate otherwise. Specifically, they won't abandon any potential food, just as the missionaries won't abandon any potential converts.

My question is a part of this problem. I'm trying to design a function which returns list of possible boat-loads (for example if boat_capacity is 3 then [(3mis, 0can), (2mis, 1can), (1mis, 1can), ...]). I have num(number of missionaries or cannibals) and boat-capacity as inputs of my function.

How do you design your function and algorithm?

Answer 1

Think about this in a recursive fashion, which is to say you want to think of it in terms of possible subproblems. So, if you have a boat ful of three occupants, that's obviously like a boat with one occupant, plus any of the combinations of two occupants.

A boat that has two occupants has an occupant plus "a boat full of one occupant".

So your algorithm is going to basically look like

to find all combinations of n occupants,
    pick an occupant
    if n = 1 return
    if n > 1 find all combinations of (n-1) occupants.

Note this isn't the exact solution, as this looks a lot like a homework problem.

Answer 2

I solved the problem in a Scheme environment. Probably it is not very fast, but it works.

;;; boat-loads : mc_num  boat_capacity --> list of boat_loads 
;;; returns a list of possible (cannibals cannot be more than missionaries)
;;; boat-loads

(define (boat-loads mc bc storage)
 (local 
  ((define isBoatBig (> bc mc))
   (define (both  mc bc storage)
     (cond 
         [(< mc 1) storage]
         [else 
          (both (- mc 1) bc (append storage (list (list mc (- bc mc)))))]))
   (define (single mc bc storage)
    (cond 
      [(= mc 0) storage]
      [else 
       (single (- mc 1) bc (append storage (list (list mc 0) (list 0 mc))))]))
  (define (filt l)
    (local
      ((define (filter-equal l acc)
         (local 
           ((define (filter-equal-inner f  l)
              (cond 
                [(empty? l) (list f)]
                [(equal? f (first l))  (filter-equal-inner (first l) (rest l))]
                [else (append (list (first l))
                              (filter-equal-inner f (rest l)))]))
            (define done (filter-equal-inner (first l) (rest l))))
           (cond 
             [(= 0 acc) done]
             [else (filter-equal done (- acc 1))]))))
       (filter-equal l (length l)))))
  (cond
   [(= bc 0) storage]
   [else 
    (filt (boat-loads mc
                      (- bc 1)
                      (append storage
                              (if isBoatBig 
                                  (filter (lambda (x)
                                            (if (>= (first x) (second x))
                                                true false))
                                          (append (both mc bc empty)
                                                  (single mc bc empty)))
                                  (filter (lambda (x)
                                            (if (>= (first x) (second x))
                                                true false))
                                          (append (both bc bc empty)
                                                  (single bc bc empty)))))))])))

Answer 3

Or you could think of it instead as generating all strings of length 1,2, and 3 composed of two symbols. Like, for example, M's and C's. Or, hmm, zeroes and ones! 0 for missionaries and 1 for cannibals.

0 to 1, 00 to 11, and 000 to 111. The 'how' of generating them just jumps out at you now, right?