Velocity Reviews > C++ > Ways to solve a puzzle in C++ -- variety

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

Alf P. Steinbach
Guest
Posts: n/a

 10-10-2005
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
Guest
Posts: n/a

 10-10-2005
* 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
Guest
Posts: n/a

 10-10-2005
* 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@gmail.com
Guest
Posts: n/a

 10-10-2005

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
Guest
Posts: n/a

 10-10-2005
* http://www.velocityreviews.com/forums/(E-Mail Removed):
>
> 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@gmail.com
Guest
Posts: n/a

 10-10-2005

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
Guest
Posts: n/a

 10-10-2005
* (E-Mail Removed):
>
> 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@gmail.com
Guest
Posts: n/a

 10-10-2005

Alf P. Steinbach wrote:
> * (E-Mail Removed):
> 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.

http://www.eisenbach.com/~andre/posted/nac.cpp.txt

Cheers,
Andre

int2str@gmail.com
Guest
Posts: n/a

 10-10-2005

(E-Mail Removed) wrote:
> 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
Guest
Posts: n/a

 10-11-2005
* (E-Mail Removed):
>
> (E-Mail Removed) wrote:
> > 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?