Breadth First Search Missionaries and Cannibals

Breadth First Search Missionaries and Cannibals

[Alex]

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
   begin
      return -999;
   end Min_Crossings;

Thanks a bunch.

Re: Breadth First Search Missionaries and Cannibals

[Georg Bauhaus]

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.

Re: Breadth First Search Missionaries and Cannibals

[Alex]

On Tuesday, April 30, 2013 3:56:17 AM UTC-4, Georg Bauhaus wrote:
> 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.

I do not know the answer to your question.

Re: Breadth First Search Missionaries and Cannibals

[Will Koch]

willmann817@gmail.com wrote:

> On Tuesday, April 30, 2013 3:56:17 AM UTC-4, Georg Bauhaus wrote:
> > On 30.04.13 04:48, willmann817@gmail.com 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.
> 
> I do not know the answer to your question.

He is objecting to the use of Integer type in the function signature
[which, for a 32-bit integer, has a range of -2^31 to (2^31) - 1]
rather than modeling your problem more precisely by using Ada's ability
to specify a new type (or subtype) that only allows values greater than
or equal to 2. If M, C, and R should never be less than 2, then maybe
the code shouldn't allow values less than 2 to be passed to it without
throwing an exception.

Re: Breadth First Search Missionaries and Cannibals

[Jeffrey Carter]

On 04/30/2013 12:56 AM, Georg Bauhaus wrote:
>
> 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.

It's pretty clear that these are homework problems, and the subprogram 
declaration is provided by the instructor, who for some reason is not using 
subtypes or user-defined types.

-- 
Jeff Carter
"Strange women lying in ponds distributing swords
is no basis for a system of government."
Monty Python & the Holy Grail
66