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 myNCannibalsAtL eft;
unsigned myNNunsAtLeft;
RiverSideEnum myBoatPosition;

public:
State(): myNCannibalsAtL eft( 0 ), myNNunsAtLeft( 0 ), myBoatPosition( right ) {}

State( unsigned nCannibalsAtLef t, unsigned nNunsAtLeft, RiverSideEnum aBoatPos )
:
myNCannibalsAtL eft( nCannibalsAtLef t ),
myNNunsAtLeft( nNunsAtLeft ),
myBoatPosition( aBoatPos )
{
assert( 0 <= myNCannibalsAtL eft && myNCannibalsAtL eft <= 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? myNCannibalsAtL eft : myNNunsAtLeft);
return (side == left? nOfKindAtLeft : nPersonsOfAKind - nOfKindAtLeft );
}

RiverSideEnum boatPosition() const { return myBoatPosition; }
unsigned nCannibalsAtBoa t() 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 isCannibalistic Orgy() const
{
return (
n( cannibal, left ) >= n( nun, left ) ||
n( cannibal, right ) >= n( nun, right )
);
}

bool canTransfer( unsigned nCannibals, unsigned nNuns )
{
return
!isCannibalisti cOrgy() &&
nCannibals <= nCannibalsAtBoa t() &&
nNuns <= nNunsAtBoat() &&
0 < (nCannibals + nNuns) && (nCannibals + nNuns) <= maxPerTransfer;
}

void transfer( unsigned nCannibals, unsigned nNuns )
{
assert( canTransfer( nCannibals, nNuns ) );

if( myBoatPosition == left )
{
myNCannibalsAtL eft -= nCannibals;
myNNunsAtLeft -= nNuns;
}
else
{
myNCannibalsAtL eft += 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 isCannibalistic Orgy() 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
!isCannibalisti cOrgy() &&
nCannibals <= nCannibalsAtBoa t() &&
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.c om:

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
!isCannibalisti cOrgy() &&
nCannibals <= nCannibalsAtBoa t() &&
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.c om:

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
!isCannibalisti cOrgy() &&
nCannibals <= nCannibalsAtBoa t() &&
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.c om:
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.c om 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.c om:

in*****@gmail.c om 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_cannib als/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?