Re: Breadth First Search Missionaries and Cannibals

[Georg Bauhaus <rm.dash-bauhaus@futureapps.de>]

On 30.04.13 04:48, Alex wrote:
> Given the following Function signature how would I go about using breadth first search to find out the minimum number of trips it would take to get all the missionaries and cannibals across the river. *MUST USE BREADTH FIRST SEARCH* If you are not familiar with the problem see the wiki page here :
>
> http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem
>
> The only difference between the problem in the wiki article is in this one the number of missionaries and cannibals and the number of people the boat can hold can change.
>
> M is missionaries, C is cannibals and R is the number of people you can fit in the boat.
>
>     function Min_Crossings(M, C, R : Integer) return Integer is
>        -- you can assume M, C, and R are all >= 2 and C <= M

While this does not address the combinatorial part, if modern IT
is permitted to be built atop vague, implementation defined
types stuck in the 1970s (Integer), why not boldly move on to the
1980s and turn the assumption "all are >= 2" into a rock solid type?

    type Entity_Count is range 2 .. Max_Possible_Number;

    function Min_Crossings(M, C, R : Entity_Count) return ...

If the suffix of Entitiy_Count hides too much information ("Is this an int,
actually?") in the context of an algorithmic exercise, you could call it
Entity_int.