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

[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

 

[Branimir Maksimovic]

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]

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]

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]

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]

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

 

[Branimir Maksimovic]

* Old Wolf:

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.

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.