449,412 Members | 993 Online
Need help? Post your question and get tips & solutions from a community of 449,412 IT Pros & Developers. It's quick & easy.

Ways to solve a puzzle in C++ -- variety

 P: n/a I'm writing a little piece on pointers, to be "bundled" with my attempted correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at least think about that again), and while thinking of good examples I came up with the idea of solving the puzzle explained in code below, with the solver optimized so that a state is never analysed more than once. However, I soon realized that this could be done most naturally (for me, at least) _without_ using any pointers -- but perhaps that's not so for you? So now I'm interested in what's _your_ "natural" way to do this. Please don't look at the old tutorial first, which has a similar example, because that could influence the way you choose to tackle the problem. I'm thinking that you can just post working code or URLs to working code here in this thread, and to be able to compare solutions, please use the below spec unchanged except perhaps for renaming, indentation and such, and fixing bugs, if any (the spec compiles but I haven't tried it out yet). namespace nac_puzzle { enum RiverSideEnum{ left, right }; // We have a river with a left and right bank. inline RiverSideEnum opposite( RiverSideEnum side ) { return RiverSideEnum( 1 - side ); } enum PersonKindEnum{ cannibal, nun }; // There are cannibals and nuns, on the right. inline PersonKindEnum opposite( PersonKindEnum kind ) { return PersonKindEnum( 1 - kind ); } enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat holds max 2 persons... class State { private: unsigned myNCannibalsAtLeft; unsigned myNNunsAtLeft; RiverSideEnum myBoatPosition; public: State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ), myBoatPosition( right ) {} State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft, RiverSideEnum aBoatPos ) : myNCannibalsAtLeft( nCannibalsAtLeft ), myNNunsAtLeft( nNunsAtLeft ), myBoatPosition( aBoatPos ) { assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <= nPersonsOfAKind ); assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <= nPersonsOfAKind ); assert( myBoatPosition == left || myBoatPosition == right ); assert( !( n( cannibal, left ) + n( nun, left ) == 0 && boatPosition() == left ) ); assert( !( n( cannibal, right ) + n( nun, right ) == 0 && boatPosition() == right ) ); } unsigned n( PersonKindEnum kind, RiverSideEnum side ) const { unsigned const nOfKindAtLeft = (kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft); return (side == left? nOfKindAtLeft : nPersonsOfAKind - nOfKindAtLeft ); } RiverSideEnum boatPosition() const { return myBoatPosition; } unsigned nCannibalsAtBoat() const { return n( cannibal, boatPosition() ); } unsigned nNunsAtBoat() const { return n( nun, boatPosition() ); } bool isSolution() const { return n( cannibal, left ) == nPersonsOfAKind && n( nun, left ) == nPersonsOfAKind; } bool isCannibalisticOrgy() const { return ( n( cannibal, left ) >= n( nun, left ) || n( cannibal, right ) >= n( nun, right ) ); } bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } void transfer( unsigned nCannibals, unsigned nNuns ) { assert( canTransfer( nCannibals, nNuns ) ); if( myBoatPosition == left ) { myNCannibalsAtLeft -= nCannibals; myNNunsAtLeft -= nNuns; } else { myNCannibalsAtLeft += nCannibals; myNNunsAtLeft += nNuns; } myBoatPosition = opposite( myBoatPosition ); } }; // class State } // namespace nac_puzzle -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 10 '05 #1
27 Replies

 P: n/a * Alf P. Steinbach: and fixing bugs, if any (the spec compiles but I haven't tried it out yet). Of course the criterion for cannibals going amok should be that there are _more_ of them on one side, otherwise one wouldn't even get started. I.e. the comparision operator should be ">", not ">=" as I wrote... Grr. ;-) -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 10 '05 #2

 P: n/a * Alf P. Steinbach: * Alf P. Steinbach: and fixing bugs, if any (the spec compiles but I haven't tried it out yet). Of course the criterion for cannibals going amok should be that there are _more_ of them on one side, otherwise one wouldn't even get started. I.e. the comparision operator should be ">", not ">=" as I wrote... Grr. ;-) bool isCannibalisticOrgy() const { return ( n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 || n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0 ); } -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 10 '05 #3

 P: n/a Alf P. Steinbach wrote: So now I'm interested in what's _your_ "natural" way to do this. Are you talking about our way of doing this state class, or the solver? bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } canTransfer() dosn't check how many n/c are left on that side... Cheers, Andre Oct 10 '05 #4

 P: n/a * in*****@gmail.com: Alf P. Steinbach wrote: So now I'm interested in what's _your_ "natural" way to do this. Are you talking about our way of doing this state class, or the solver? I meant the solver, unless there's a radically different way of doing the state class (not counting just a pure value class) ;-) If anyone's interested I could post my own solver code; it's not that long. But it's essentially the same as the one I presented in the tutorial (for a similar problem), and I think that could influence how people choose to do this, the angle of attack, so to speak. bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } canTransfer() dosn't check how many n/c are left on that side... Yep. You're allowed to get to the state where the cannibals feast, but you're not allowed to derive a new state from that state. I think in the original formulation there was a big brush fire on the right hand side of the river, which was the reason the nuns are trying -- with their lives at stake, given the cannibals' diet -- to save the poor cannibals. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 10 '05 #5

 P: n/a Alf P. Steinbach wrote: canTransfer() dosn't check how many n/c are left on that side... Yep. You're allowed to get to the state where the cannibals feast, but you're not allowed to derive a new state from that state. But, it looks like you're allowed a state where you've shipped more people than actually exist ;). Like the old saying goes, "if there's 3 people in a room, and 4 leave...." Cheers, Andre Oct 10 '05 #6

 P: n/a * in*****@gmail.com: Alf P. Steinbach wrote: canTransfer() dosn't check how many n/c are left on that side... Yep. You're allowed to get to the state where the cannibals feast, but you're not allowed to derive a new state from that state. But, it looks like you're allowed a state where you've shipped more people than actually exist ;). Like the old saying goes, "if there's 3 people in a room, and 4 leave...." Well, here's that code, again: bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } After the line with 'return', the first line checks that there's no gourmet h-meat dinner going on (can't proceed from that state), the second line, that the number of cannibals to transfer is actually less than or equal to the number of cannbibals on that side -- and so on. Of course, the litmus test is that it works. From my own experience, to check that a solver actually does work it should display the series of states that leads to the solution. Otherwise it can seemingly work, but not actually, so to anyone doing this, I recommend displaying the solution steps. -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 10 '05 #7

 P: n/a Alf P. Steinbach wrote: * in*****@gmail.com: Of course, the litmus test is that it works. From my own experience, to check that a solver actually does work it should display the series of states that leads to the solution. Otherwise it can seemingly work, but not actually, so to anyone doing this, I recommend displaying the solution steps. Yes, I agree. Alright, here we go... It's undoubtably not the most efficient, nor elegant solution, but I'd like to hear some comments on it anyway. and to the best of my knowledge, it seems to be working. Link: http://www.eisenbach.com/~andre/posted/nac.cpp.txt Cheers, Andre Oct 10 '05 #8

 P: n/a in*****@gmail.com wrote: Link: http://www.eisenbach.com/~andre/posted/nac.cpp.txt I've updated the code slightly (only cleanups). The current version (see top) is "1.03". Cheers, Andre Oct 10 '05 #9

 P: n/a * in*****@gmail.com: in*****@gmail.com wrote: Link: http://www.eisenbach.com/~andre/posted/nac.cpp.txt I've updated the code slightly (only cleanups). The current version (see top) is "1.03". I see no difference... ? Comments, I'm not sure. It's a clean implementation, except for the depth-search cutoff which had me baffled (it starts at 0 and the criterion for not trying one more level is >=, which allows a 12-step solution to be found for cutoff 10). What did you intend to use from ? As it is I can't see that anything's used from . It would be interesting if someone had some very different kind of solution, e.g., one using pointers (!); anyway, for comparision, here's mine: . -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 11 '05 #10

 P: n/a Alf P. Steinbach wrote: I see no difference... ? You must have missed the earlier revision(s). Syntactical cleanups only. Comments, I'm not sure. It's a clean implementation, except for the depth-search cutoff which had me baffled (it starts at 0 and the criterion for not trying one more level is >=, which allows a 12-step solution to be found for cutoff 10). The depth cutoff was only there to prevent runaway solutions where the stats (possibly) repeat over and over again. This is not really an issue with this "Cannibals and Nuns" problem, but I'm just used to it from problems where you cannot search to the full depth. I've removed it for this example though (see below). What did you intend to use from ? As it is I can't see that anything's used from . For some strange reason I thought std::min was in algorithm. But I guess it's also included in . anyway, for comparision, here's mine: . It's funny, our two solutions both arrive at the same end result after 12 iterations, but take a different route getting there. Also, I believe my solution is a little "cleaner" (may be not objective enough to judge though :D ), but your solution was by a factor of 40 faster than mine! Loops beat recursion again :). However, I got the speed discrepancy down quite a bit by removing the extra indirection that "GetValidMoves()" caused in my solution. Here's an updated solution: http://www.eisenbach.com/~andre/posted/SolverAndre.h Also, just for fun, here's both solutions in one project: http://www.eisenbach.com/~andre/posted/nac.tar To swerve slightly back on topic, what would you think pointers could be used for in this problem? Cheers, Andre Oct 11 '05 #11

 P: n/a Alf P. Steinbach wrote: I'm writing a little piece on pointers, to be "bundled" with my attempted correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at least think about that again), and while thinking of good examples I came up with the idea of solving the puzzle explained in code below, with the solver optimized so that a state is never analysed more than once. However, I soon realized that this could be done most naturally (for me, at least) _without_ using any pointers -- but perhaps that's not so for you? So now I'm interested in what's _your_ "natural" way to do this. Please don't look at the old tutorial first, which has a similar example, because that could influence the way you choose to tackle the problem. I'm thinking that you can just post working code or URLs to working code here in this thread, and to be able to compare solutions, please use the below spec unchanged except perhaps for renaming, indentation and such, and fixing bugs, if any (the spec compiles but I haven't tried it out yet). I refuse. The specs make is unnecessarily hard to use standard containers. Thus, I added a total order and comparison on states: #include #include #include #include #include #include namespace nac_puzzle { enum RiverSideEnum{ left, right }; // We have a river with a left and right bank. inline RiverSideEnum opposite( RiverSideEnum side ) { return RiverSideEnum( 1 - side ); } enum PersonKindEnum{ cannibal, nun }; // There are cannibals and nuns, on the right. inline PersonKindEnum opposite( PersonKindEnum kind ) { return PersonKindEnum( 1 - kind ); } enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat holds max 2 persons... class State { private: unsigned myNCannibalsAtLeft; unsigned myNNunsAtLeft; RiverSideEnum myBoatPosition; public: State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ), myBoatPosition( right ) {} State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft, RiverSideEnum aBoatPos ) : myNCannibalsAtLeft( nCannibalsAtLeft ), myNNunsAtLeft( nNunsAtLeft ), myBoatPosition( aBoatPos ) { assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <= nPersonsOfAKind ); assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <= nPersonsOfAKind ); assert( myBoatPosition == left || myBoatPosition == right ); assert( !( n( cannibal, left ) + n( nun, left ) == 0 && boatPosition() == left ) ); assert( !( n( cannibal, right ) + n( nun, right ) == 0 && boatPosition() == right ) ); } unsigned n( PersonKindEnum kind, RiverSideEnum side ) const { unsigned const nOfKindAtLeft = (kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft); return (side == left? nOfKindAtLeft : nPersonsOfAKind - nOfKindAtLeft ); } RiverSideEnum boatPosition() const { return myBoatPosition; } unsigned nCannibalsAtBoat() const { return n( cannibal, boatPosition() ); } unsigned nNunsAtBoat() const { return n( nun, boatPosition() ); } bool isSolution() const { return n( cannibal, left ) == nPersonsOfAKind && n( nun, left ) == nPersonsOfAKind; } bool isCannibalisticOrgy() const { return ( n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 || n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0 ); } bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } void transfer( unsigned nCannibals, unsigned nNuns ) { assert( canTransfer( nCannibals, nNuns ) ); if( myBoatPosition == left ) { myNCannibalsAtLeft -= nCannibals; myNNunsAtLeft -= nNuns; } else { myNCannibalsAtLeft += nCannibals; myNNunsAtLeft += nNuns; } myBoatPosition = opposite( myBoatPosition ); } // fixed this: bool operator< ( State const & other ) const { if ( this->myNCannibalsAtLeft < other.myNCannibalsAtLeft ) { return( true ); } if ( other.myNCannibalsAtLeft < this-> myNCannibalsAtLeft ) { return( false ); } if ( this->myNNunsAtLeft < other.myNNunsAtLeft ) { return( true ); } if ( other.myNNunsAtLeft < this-> myNNunsAtLeft ) { return( false ); } if ( this->myBoatPosition < other.myBoatPosition ) { return( true ); } if ( other.myBoatPosition < this-> myBoatPosition ) { return( false ); } return( false ); } bool operator== ( State const & other ) const { if ( ( this->myNCannibalsAtLeft == other.myNCannibalsAtLeft ) && ( this->myNNunsAtLeft == other.myNNunsAtLeft ) && ( this->myBoatPosition == other.myBoatPosition ) ) { return( true ); } return( false ); } bool operator!= ( State const & other ) const { return( ! ( *this == other ) ); } }; // class State } // namespace nac_puzzle // solver code goes here: // ====================== // Graph data structure: // --------------------- // the Graph is directed so that graph[state].first is a // predecessor state from which state is obtained by the // transfer graph[state].second. typedef nac_puzzle::State Vertex; typedef std::pair< unsigned, unsigned > Move; typedef std::pair< Vertex, Move > DirectedEdge; typedef std::map< Vertex, DirectedEdge > Graph; // output support: // --------------- namespace std { std::ostream & operator<< ( std::ostream & ostr, Move const & move ) { ostr << "transfer " << move.first << " cannibals and " << move.second << " nuns."; return( ostr ); } } // collecting vertices until a solution state is encountered: // ---------------------------------------------------------- void solve ( Vertex current_vertex, Graph & graph ) { if ( current_vertex.isSolution() ) { throw ( current_vertex ); } if ( current_vertex.isCannibalisticOrgy() ) { return; } for ( unsigned nPersons = 0; nPersons <= nac_puzzle::maxPerTransfer; ++ nPersons ) { for ( unsigned nCannibals = 0; nCannibals <= nPersons; ++ nCannibals ) { unsigned nNuns = nPersons - nCannibals; Move current_move ( nCannibals, nNuns ); if ( current_vertex.canTransfer( current_move.first, current_move.second ) ) { Vertex next = current_vertex; next.transfer( current_move.first, current_move.second ); if ( graph.find( next ) == graph.end() ) { graph[next] = DirectedEdge( current_vertex, current_move ); solve( next, graph ); } } } } } int main ( void ) { Graph graph; try { solve( Vertex(), graph ); std::cout << "Sorry, I did not find a solution.\n"; } catch ( Vertex solution ) { std::stack< Move > reverse; while ( solution != Vertex() ) { reverse.push( graph[solution].second ); solution = graph[solution].first; } std::cout << "Yay, I found a solution.\nPlease, proceed as follows:\n"; while ( ! reverse.empty() ) { std::cout << " " << reverse.top() << '\n'; reverse.pop(); } } } And now, I am going to have a look at the posted solution. Best Kai-Uwe Bux Oct 11 '05 #12

 P: n/a Alf P. Steinbach wrote: * Kai-Uwe Bux: Alf P. Steinbach wrote: > I'm thinking that you can just post working code or URLs to working > code here in this thread, and to be able to compare solutions, please > use the below spec unchanged except perhaps for renaming, indentation > and such, and fixing bugs, if any (the spec compiles but I haven't > tried it out yet). I refuse. The specs make is unnecessarily hard to use standard containers. Thus, I added a total order and comparison on states: Yes, but the public interface is suffient to do that in e.g. a wrapper class, not to mention a derived class. You are right. I just didn't understand the interface correctly. Once I saw your solution, it dawned upon me that there is a way to peek into a state. I guess I should make it a habit to understand what I read before I start coding. Oh well. Thanks Kai-Uwe Bux Oct 11 '05 #14

 P: n/a "Alf P. Steinbach" wrote in message news:43***************@news.individual.net... I'm writing a little piece on pointers, to be "bundled" with my attempted correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at least think about that again), and while thinking of good examples I came up with the idea of solving the puzzle explained in code below, with the solver optimized so that a state is never analysed more than once. However, I soon realized that this could be done most naturally (for me, at least) _without_ using any pointers -- but perhaps that's not so for you? So now I'm interested in what's _your_ "natural" way to do this. Well, I couldn't see need for pointers in this case. This is my solution (though I didn't test it for all cases). int main(int argc, char *argv[]) { using namespace nac_puzzle; assert(!(maxPerTransfer%2)); State s; while(!s.isSolution()) { unsigned nc = s.n(cannibal,s.boatPosition()); unsigned nn = s.n(nun,s.boatPosition()); printf("nc:%u\n",nc); printf("nn:%u\n",nn); printf("Nuns left:%u Cannibals left:%u\n", s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle: :left)); fflush(stdout); if(s.boatPosition() == nac_puzzle::left) { if(nn==nc) s.transfer(1,1); else s.transfer(1,0); } else { if((nn>nc && nn-nc == maxPerTransfer) || (nn==nc && nn == maxPerTransfer)) { s.transfer(0,maxPerTransfer); } else { if(nn==nc && nn+nc == maxPerTransfer) s.transfer(1,1); else s.transfer(nc>maxPerTransfer?maxPerTransfer:nc,0); } } } printf("Nuns left:%u Cannibals left:%u\n", s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle: :left)); fflush(stdout); return 0; } You should assert for (3,0) (0,3) and boat on the nuns side and for (1,2) (2,1), I think. Greetings, Bane. Oct 12 '05 #15

 P: n/a This is finished version which uses linked list as required by asignment. This is still not thoroughly tested, but it should work. Basically if solution can be found then assert, otherwise, display. ------- nac_puzzle.h #include namespace nac_puzzle { enum RiverSideEnum{ left, right }; // We have a river with a left and right bank. inline RiverSideEnum opposite( RiverSideEnum side ) { return RiverSideEnum( 1 - side ); } enum PersonKindEnum{ cannibal, nun }; // There are cannibals and nuns, on the right. inline PersonKindEnum opposite( PersonKindEnum kind ) { return PersonKindEnum( 1 - kind ); } enum { nPersonsOfAKind = 3, maxPerTransfer = 2 }; // The boat holds max 2 persons... class State { private: unsigned myNCannibalsAtLeft; unsigned myNNunsAtLeft; RiverSideEnum myBoatPosition; public: State(): myNCannibalsAtLeft( 0 ), myNNunsAtLeft( 0 ), myBoatPosition( right ) {} State( unsigned nCannibalsAtLeft, unsigned nNunsAtLeft, RiverSideEnum aBoatPos ) : myNCannibalsAtLeft( nCannibalsAtLeft ), myNNunsAtLeft( nNunsAtLeft ), myBoatPosition( aBoatPos ) { assert( 0 <= myNCannibalsAtLeft && myNCannibalsAtLeft <= nPersonsOfAKind ); assert( 0 <= myNNunsAtLeft && myNNunsAtLeft <= nPersonsOfAKind ); assert( myBoatPosition == left || myBoatPosition == right ); assert( !( n( cannibal, left ) + n( nun, left ) == 0 && boatPosition() == left ) ); assert( !( n( cannibal, right ) + n( nun, right ) == 0 && boatPosition() == right ) ); } unsigned n( PersonKindEnum kind, RiverSideEnum side ) const { unsigned const nOfKindAtLeft = (kind == cannibal? myNCannibalsAtLeft : myNNunsAtLeft); return (side == left? nOfKindAtLeft : nPersonsOfAKind - nOfKindAtLeft ); } RiverSideEnum boatPosition() const { return myBoatPosition; } unsigned nCannibalsAtBoat() const { return n( cannibal, boatPosition() ); } unsigned nNunsAtBoat() const { return n( nun, boatPosition() ); } bool isSolution() const { return n( cannibal, left ) == nPersonsOfAKind && n( nun, left ) == nPersonsOfAKind; } bool isCannibalisticOrgy() const { return ( n( cannibal, left ) > n( nun, left ) && n( nun, left ) > 0 || n( cannibal, right ) > n( nun, right ) && n( nun, right ) > 0 ); } bool canTransfer( unsigned nCannibals, unsigned nNuns ) { return !isCannibalisticOrgy() && nCannibals <= nCannibalsAtBoat() && nNuns <= nNunsAtBoat() && 0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer; } void transfer( unsigned nCannibals, unsigned nNuns ) { assert( canTransfer( nCannibals, nNuns ) ); if( myBoatPosition == left ) { myNCannibalsAtLeft -= nCannibals; myNNunsAtLeft -= nNuns; } else { myNCannibalsAtLeft += nCannibals; myNNunsAtLeft += nNuns; } myBoatPosition = opposite( myBoatPosition ); } }; // class State } // namespace nac_puzzle ------ end ------ nac_puzzle.cpp #include #include #include #include "nac_puzzle.h" using namespace std; using namespace nac_puzzle; struct print_list{ void operator()(const State& s)const { printf("Nuns left:%u Cannibals left:%u" "\tNuns right:%u Cannibals right%u" "\tBoat position:%s\n", s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle: :left), s.n(nun,nac_puzzle::right),s.n(cannibal,nac_puzzle ::right), s.boatPosition() == nac_puzzle::left?"left":"right" ); fflush(stdout); } }; int main(int argc, char *argv[]) { assert(maxPerTransfer>nPersonsOfAKind/2); // no solution for such cases at least for me :) unsigned max = maxPerTransfer>=nPersonsOfAKind?nPersonsOfAKind-1:maxPerTransfer; // this is just to simplify algo list l; l.push_back(State()); while(!l.back().isSolution()) { l.push_back(l.back()); unsigned nc = l.back().n(cannibal,l.back().boatPosition()); unsigned nn = l.back().n(nun,l.back().boatPosition()); if(l.back().boatPosition() == nac_puzzle::left) { if(nn==nc) l.back().transfer(1,1); else l.back().transfer(nc>max?nc-max:1,0); } else { if((nn>nc && nn-nc >= max) || (nn==nc && nn <= max)) { l.back().transfer(0,nnmax?max:nc,0); } } } printf("Solution:\n"); for_each(l.begin(),l.end(),print_list()); return 0; } ------- end Oct 12 '05 #16

 P: n/a Branimir Maksimovic wrote: This is finished version which uses linked list as required by asignment. .... if(nn==nc) l.back().transfer(1,1); else l.back().transfer(nc>max?nc-max:1,0); quick fix and I think that's it: if(nn==nc) { if(l.back().n(nun,nac_puzzle::right)>max-1) l.back().transfer(0,nn); else l.back().transfer(1,1); } Oct 12 '05 #17

 P: n/a Branimir Maksimovic wrote: Branimir Maksimovic wrote: This is finished version which uses linked list as required by asignment. ... if(nn==nc) l.back().transfer(1,1); else l.back().transfer(nc>max?nc-max:1,0); Of course, else stays. quick fix and I think that's it: if(nn==nc) { if(l.back().n(nun,nac_puzzle::right)>max-1) l.back().transfer(0,nn); else l.back().transfer(1,1); } else l.back().transfer(nc>max?nc-max:1,0); Oct 12 '05 #18

 P: n/a Alf P. Steinbach wrote: namespace nac_puzzle { enum RiverSideEnum{ left, right }; // We have a river with a left and right bank. inline RiverSideEnum opposite( RiverSideEnum side ) { return RiverSideEnum( 1 - side ); } etc. Can you specify the problem? I've heard of wolf, goat and cabbage crossing the river, but not nun and cannibal. Oct 12 '05 #19

 P: n/a The problem is layed out in the comments: // We have a river with a left and right bank. // There are cannibals and nuns, on the right. // The boat holds max 2 persons... The only ommited part is: "There's a wildfire on the right. The nuns and cannibals need to get to the left side. If there's more cannibals than nuns on either side of the river, the cannibals will eat the nuns". Cheers, Andre Oct 12 '05 #20

 P: n/a * Branimir Maksimovic: --> #include #include #include #include "nac_puzzle.h" using namespace std; using namespace nac_puzzle; struct print_list{ void operator()(const State& s)const { printf("Nuns left:%u Cannibals left:%u" "\tNuns right:%u Cannibals right%u" "\tBoat position:%s\n", s.n(nun,nac_puzzle::left),s.n(cannibal,nac_puzzle: :left), s.n(nun,nac_puzzle::right),s.n(cannibal,nac_puzzle ::right), s.boatPosition() == nac_puzzle::left?"left":"right" ); fflush(stdout); } }; int main(int argc, char *argv[]) { assert(maxPerTransfer>nPersonsOfAKind/2); // no solution for such cases at least for me :) unsigned max = maxPerTransfer>=nPersonsOfAKind?nPersonsOfAKind-1:maxPerTransfer; // this is just to simplify algo list l; l.push_back(State()); while(!l.back().isSolution()) { l.push_back(l.back()); unsigned nc = l.back().n(cannibal,l.back().boatPosition()); unsigned nn = l.back().n(nun,l.back().boatPosition()); if(l.back().boatPosition() == nac_puzzle::left) { if(nn==nc) { if(l.back().n(nun,nac_puzzle::right)>max-1) l.back().transfer(0,nn); else l.back().transfer(1,1); } else l.back().transfer(nc>max?nc-max:1,0); } else { if((nn>nc && nn-nc >= max) || (nn==nc && nn <= max)) { l.back().transfer(0,nnmax?max:nc,0); } } } printf("Solution:\n"); for_each(l.begin(),l.end(),print_list()); return 0; } <-- Well, yes, but how does it work? As far as I can see the list is only used to record the sequence of moves for the final display? I.e., except for the final display the list could be removed from the code, and one would have a while-loop that generated only a correct move in each iteration? So, is the difference from hard-coding the moves that this can handle other puzzle parameters (number of nuns & cannibals, max per transfer)? Anyway, good job, and I have a suggestion for the code. Namely, the print_list 'struct'. You can make that simply a function. ;-) Cheers, - Alf -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 12 '05 #21

 P: n/a Alf P. Steinbach wrote: Well, yes, but how does it work? As far as I can see the list is only used to record the sequence of moves for the final display? Yes, it only needs one State. I.e., except for the final display the list could be removed from the code, and one would have a while-loop that generated only a correct move in each iteration? So, is the difference from hard-coding the moves that this can handle other puzzle parameters (number of nuns & cannibals, max per transfer)? Yes, you can input anything in State and it will find correct solution. Even you can change nPersonsOfAKind and maxPerTransfer and it will still work (provided that assert wouldn't fail). What is good about it solution is found in a straight way, rather then brute force method. try for example nPersonsOfAKind 7 maxPerTransfer 4 and State(3,3,left); Anyway, good job, and I have a suggestion for the code. Namely, the print_list 'struct'. You can make that simply a function. ;-) You can guess that I'm used to function objects :) This is really a function, but function object can be used to print step numbers for example :) Greetings, Bane. Oct 12 '05 #22

 P: n/a in*****@gmail.com wrote: The problem is layed out in the comments: // We have a river with a left and right bank. // There are cannibals and nuns, on the right. // The boat holds max 2 persons... The only ommited part is: "There's a wildfire on the right. The nuns and cannibals need to get to the left side. If there's more cannibals than nuns on either side of the river, the cannibals will eat the nuns". It seems you also need the condition "there are at most three nuns and three cannibals", otherwise there isn't any solution. I note that the solutions posted so far are all recursive brute-force searches. My preferred option would be a best-first or A* search, using a priority queue to store the currently open states; although for a problem this small it really doesn't matter. Oct 13 '05 #23

 P: n/a "Alf P. Steinbach" wrote in message news:43****************@news.individual.net... this also has to be fixed: if(nn==nc && nn+nc <= max) { l.back().transfer(nc,nn); } else l.back().transfer(nc>max?max:nc,0); if(nn==nc) { if(nn+nc <= max) l.back().transfer(nc,nn); else l.back().transfer(max/2,max/2); } else l.back().transfer(nc>max?max:nc,0); Covers the cases like nPersonsOfAKind = 35 maxPerTransfer = 18, State(10,10,right); which I forgot to test. Only your solution was cappable of solving this so far. Greetings, Bane. Oct 13 '05 #24

 P: n/a "Old Wolf" wrote in message news:11*********************@o13g2000cwo.googlegro ups.com... in*****@gmail.com wrote: The problem is layed out in the comments: // We have a river with a left and right bank. // There are cannibals and nuns, on the right. // The boat holds max 2 persons... The only ommited part is: "There's a wildfire on the right. The nuns and cannibals need to get to the left side. If there's more cannibals than nuns on either side of the river, the cannibals will eat the nuns". It seems you also need the condition "there are at most three nuns and three cannibals", otherwise there isn't any solution. no: only condition needed is assert(maxPerTransfer>nPersonsOfAKind/2); which is basicaly 3,3 if maxPerTransfer == 2 Greetings, Bane. P.S. Take a look into my solution it does not use brute force search. Oct 13 '05 #25

 P: n/a Alf P. Steinbach wrote: I'm writing a little piece on pointers, to be "bundled" with my attempted correct C++ tutorial (see FAQ item 29.20, yes, I've finally started to at least think about that again), and while thinking of good examples I came up with the idea of solving the puzzle explained in code below, with the solver optimized so that a state is never analysed more than once. However, I soon realized that this could be done most naturally (for me, at least) _without_ using any pointers -- but perhaps that's not so for you? So now I'm interested in what's _your_ "natural" way to do this. This seems like a pretty involved problem for a language tutorial. I would think it more appropriate for an algorithms tutorial, in fact. As far as method of solution, it's clearly a path-finding problem on a graph whose nodes are implicitly defined by the total numbers of each type of person and the cannibalistic orgy condition, and whose edges are defined by the capacity of the boat. This can be solved efficiently by breadth-first search (approaches like Dijkstra et al. would work too but are overkill here). Beyond that it's all implementation details... :) Here's a similar "classic" problem which I'll offer in case you're interested. You have two jugs of capacity c1 and c2 and wish to measure out quantity q in one of the jugs. (As usual, you can fill either jug from an infinite reservoir, empty either jug, or pour the contents of one jug into the other until either the former is empty or the latter is full). With a few wording changes, the previous paragraphs explains the solution to this one too. Having said all that, unless your intended audience is fairly proficient with algorithms and data structures, I think you run the risk of obscuring the language tutorial with an intimidating algorithm tutorial. Mark Oct 13 '05 #26

 P: n/a * Old Wolf: I note that the solutions posted so far are all recursive brute-force searches. The solution I presented is a best-first search using a simple queue, i.e. the degenerate case of best-first where the score is the number of steps so far and better score is smaller value, commonly known as breadth first. My preferred option would be a best-first or A* search, using a priority queue to store the currently open states; I think it would be interesting to see the A* implementation or the best-first with priority queue, both because I haven't the foggiest idea how to estimate the remaining number of steps from a given state any better than the number of steps so far already does (not exactly on-topic in clc++, but...), and because it could perhaps finally bring in some "natural" pointer usage? although for a problem this small it really doesn't matter. Note that the problem size can easily be increased, without bounds. ;-) Also, the approach does matter in that simple depth-first searches that don't check for already visited can go off to infinity or to their depth cut-off without finding any solution (for the problem with parameters as posted there are, as I recall, four solutions, symmetrical in the state graph). -- A: Because it messes up the order in which people normally read text. Q: Why is it such a bad thing? A: Top-posting. Q: What is the most annoying thing on usenet and in e-mail? Oct 13 '05 #27

 P: n/a "Alf P. Steinbach" wrote in message news:43****************@news.individual.net...* Old Wolf: I note that the solutions posted so far are all recursive brute-force searches. The solution I presented is a best-first search using a simple queue, i.e. the degenerate case of best-first where the score is the number of steps so far and better score is smaller value, commonly known as breadth first. Yes only int2str's search uses pure brute force I think (judging by execution times, not exactly sure). Yours and Kai's does not scale exponentialy with problem growth, rather yours is balanced with variety of situations but Kai's is optimised for only certain situations. For all test cases that I have made, only yours and mine passed all of them. Mine is based on algorithm that came to my mind when I solved problem without computer. It simply chooses next move by analising State and applying biased set of rules in a way that each move eventually leads to solution. although for a problem this small it really doesn't matter. Note that the problem size can easily be increased, without bounds. ;-) Yes, for example with nPersonsOfAKind = 352, maxPerTransfer = 177 this becomes big problem for searching algorithms. Greetings, Bane. Oct 13 '05 #28