Re: Breadth First Search Missionaries and Cannibals

["Will Koch" <willmann817@gmail.com>]

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.