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

[Alf P. Steinbach]

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?

[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. ;-)

--
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?

[Alf P. Steinbach]

* 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?

[int2str]

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

[Alf P. Steinbach]

* 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?

[int2str]

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

[Alf P. Steinbach]

* 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?

[int2str]

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

[int2str]

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

[Alf P. Steinbach]

* 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 <algorithm>? As it is I
can't see that anything's used from <algorithm>.

It would be interesting if someone had some very different kind of solution,
e.g., one using pointers (!); anyway, for comparision, here's mine:
<url: http://home.no.net/alfps/misc/nuns_and_cannibals/solveit.cpp.txt>.

--
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?

[int2str]

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 <algorithm>? As it is I
can't see that anything's used from <algorithm>.
For some strange reason I thought std::min was in algorithm. But I
guess it's also included in <vector>.
anyway, for comparision, here's mine:
<url: http://home.no.net/alfps/misc/nuns_and_cannibals/solveit.cpp.txt>.

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

[Kai-Uwe Bux]

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 <cassert>
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <stack>

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

[Alf P. Steinbach]

* 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.

I think your solution is the most innovative so far, a fresh breath of outside
air! E.g. the way you use 'throw' to break out of a recursively nested call,
to indicate _success_. Also, your loop for generating transfer() arguments is
both more clear and more efficient than mine and Andre Eisenbach's (you avoid
generating (0, 0), we didn't). And using a std::map.

Here's a reworked version of your code so that the spec is left unchanged and
just assumed to be in a header file (the operators could be put in a class
instead of extending the namespace), which I think better shows what's part of
the solver code:

#include "NacPuzzle.h" // nac_puzzle::*

#include <cassert>
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <stack>

// State comparision:
// ------------------

namespace nac_puzzle
{
bool operator< ( State const & lhs, State const & rhs ) {
if ( lhs.n( cannibal, left ) < rhs.n( cannibal, left ) ) {
return( true );
}
if ( rhs.n( cannibal, left ) < lhs. n( cannibal, left ) ) {
return( false );
}
if ( lhs.n( nun, left ) < rhs.n( nun, left ) ) {
return( true );
}
if ( rhs.n( nun, left ) < lhs. n( nun, left ) ) {
return( false );
}
if ( lhs.boatPosition() < rhs.boatPosition() ) {
return( true );
}
if ( rhs.boatPosition() < lhs. boatPosition() ) {
return( false );
}
return( false );
}

bool operator== ( State const & lhs, State const & rhs ) {
if ( ( lhs.n( cannibal, left ) == rhs.n( cannibal, left ) )
&&
( lhs.n( nun, left ) == rhs.n( nun, left ) )
&&
( lhs.boatPosition() == rhs.boatPosition() ) ) {
return( true );
}
return( false );
}

bool operator!= ( State const & lhs, State const & rhs ) {
return( ! ( lhs == rhs ) );
}
} // namespace nac_puzzle
// 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.

As you'll see, while you and Andre Eisenbach have chosen to use recursion in
the algorithm and iteration in the results display, I chose to use iteration
in the algorithm and recursion in the results display... Otherwise your and
Andre's algorithms are pretty much identical, but expressed very differently
in C++. I guess this can rightly be called a multi-paradigm language!

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?

[Kai-Uwe Bux]

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

[Branimir Maksimovic]

"Alf P. Steinbach" <al***@start.no> 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.

[Branimir Maksimovic]

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 <cassert>

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 <cstdio>
#include <algorithm>
#include <list>
#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<State> 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,nn<max?nn:max);
}
else
{
if(nn==nc && nn+nc <= max)
{
l.back().transfer(nc,nn);
}
else
l.back().transfer(nc>max?max:nc,0);
}
}
}

printf("Solution:\n");
for_each(l.begin(),l.end(),print_list());

return 0;

}

------- end

[Branimir Maksimovic]

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);
}

[Branimir Maksimovic]

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);

[Old Wolf]

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.

[int2str]

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

[Alf P. Steinbach]

* Branimir Maksimovic:

--> #include <cstdio>
#include <algorithm>
#include <list>
#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<State> 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,nn<max?nn:max);
}
else
{
if(nn==nc && nn+nc <= max)
{
l.back().transfer(nc,nn);
}
else
l.back().transfer(nc>max?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?

[Branimir Maksimovic]

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.

[Old Wolf]

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.

[Branimir Maksimovic]

"Alf P. Steinbach" <al***@start.no> 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.

[Branimir Maksimovic]

"Old Wolf" <ol*****@inspire.net.nz> 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.

[Mark P]

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

[Alf P. Steinbach]

* 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?

[Branimir Maksimovic]

"Alf P. Steinbach" <al***@start.no> 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.