* Breadth First Search Missionaries and Cannibals @ 2013-04-30 2:48 Alex 2013-04-30 7:56 ` Georg Bauhaus 0 siblings, 1 reply; 5+ messages in thread From: Alex @ 2013-04-30 2:48 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Breadth First Search Missionaries and Cannibals 2013-04-30 2:48 Breadth First Search Missionaries and Cannibals Alex @ 2013-04-30 7:56 ` Georg Bauhaus 2013-04-30 10:29 ` Alex 2013-04-30 17:20 ` Jeffrey Carter 0 siblings, 2 replies; 5+ messages in thread From: Georg Bauhaus @ 2013-04-30 7:56 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Breadth First Search Missionaries and Cannibals 2013-04-30 7:56 ` Georg Bauhaus @ 2013-04-30 10:29 ` Alex 2013-04-30 13:37 ` Will Koch 2013-04-30 17:20 ` Jeffrey Carter 1 sibling, 1 reply; 5+ messages in thread From: Alex @ 2013-04-30 10:29 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Breadth First Search Missionaries and Cannibals 2013-04-30 10:29 ` Alex @ 2013-04-30 13:37 ` Will Koch 0 siblings, 0 replies; 5+ messages in thread From: Will Koch @ 2013-04-30 13:37 UTC (permalink / raw) 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. ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: Breadth First Search Missionaries and Cannibals 2013-04-30 7:56 ` Georg Bauhaus 2013-04-30 10:29 ` Alex @ 2013-04-30 17:20 ` Jeffrey Carter 1 sibling, 0 replies; 5+ messages in thread From: Jeffrey Carter @ 2013-04-30 17:20 UTC (permalink / raw) 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2013-04-30 17:20 UTC | newest] Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-04-30 2:48 Breadth First Search Missionaries and Cannibals Alex 2013-04-30 7:56 ` Georg Bauhaus 2013-04-30 10:29 ` Alex 2013-04-30 13:37 ` Will Koch 2013-04-30 17:20 ` Jeffrey Carter
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox