Removing recursion

[Mumia W.]

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

Here is the program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

const int max_points = 10;
extern int maxy, maxx;

struct Point {
int y;
int x;
Point () { y = x = 0; }
Point (int ey, int ex) { y = ey; x = ex; }
void set (int ey, int ex) { y = ey; x = ex; }
bool inbounds() {
if (y < 0 || y >= maxy) { return false; }
if (x < 0 || x >= maxx) { return false; }
return true;
}
char * as_string() {
char * temp = new char [10];
sprintf(temp, "(%d,%d)", y, x);
return temp;
}
void print() { printf("%s ", as_string()); }
};

struct Pointgrp {
int len;
Point points [max_points];
void print () {
for (int pos = 0; pos < len; ++pos) {
points[pos].print();
}
puts("");
}
};

struct Seen {
char data [1000];
Seen() { clear(); }
void clear() { memset(data,0,sizeof(data)); }
char & pos(int y, int x) {
return data[(y * maxx) + x];
}
void init(const Pointgrp & pts) {
for (int pix = 0; pix < pts.len; ++pix) {
const Point & mypt = pts.points[pix];
pos(mypt.y, mypt.x) = 1;
}
}
char & posPoint(const Point & pt) {
pos(pt.y, pt.x);
}
};

char * yoyo1 [] = {
" YOY ",
" YOYOO ",
"OYYOYYO",
" OYYYO ",
" YOY ",
"",
};

char * yoyo2 [] = {
"YO",
"OY",
"",
};

char * yoyo3 [] = {
"YOYOOY",
"OYOYOO",
"YOYYOY",
"OYOOYO",
"OYYOYO",
"",
};

char ** grid = yoyo1;
int maxx = 7;
int maxy = 5;

const char * search_for = "YOYO";
int search_len = 4;
int wordcount = 0;

// ------------------------------------------

char & atgrid (int y, int x) {
return grid[y][x];
}

char * collect_points (const Pointgrp & pts) {
char * temp = new char [15];
*temp = 0;
for (int pix = 0; pix < pts.len; ++pix) {
char part [3] = "*";
const Point & mypt = pts.points[pix];
part[0] = atgrid(mypt.y, mypt.x);
strcat(temp, part);
}
return temp;
}

void run_partial (Pointgrp group) {
Pointgrp newgrp = group;
if (group.len >= 4) {
char * str = collect_points(group);
bool dbgf = false;

if (0 == memcmp(str,search_for,search_len)) {
// dbgf = true;
wordcount++;
}

if (dbgf) {
puts("Points:");
newgrp.print();
puts(str);
}
delete[] str;
return;
}

Seen * seenobj = new Seen;
seenobj->init(newgrp);

Point & lastpt = group.points[group.len-1];
Point & newpt = newgrp.points[group.len];
newgrp.len++;

for (int yi = -1; yi < 2; ++yi) {
for (int xi = -1; xi < 2; ++xi) {
if (0 == yi && 0 == xi) { continue; }
// printf("(%d,%d) ", yi, xi);
newpt.set(lastpt.y + yi, lastpt.x + xi);
if (! newpt.inbounds()) { continue; }
if (seenobj->posPoint(newpt)) { continue; }
run_partial(newgrp);
}
// puts("");
}

delete seenobj;
}

void run (int y, int x) {
Point pt(y,x);
Pointgrp grp;

grp.len = 1;
grp.points[0] = pt;
run_partial(grp);
}

void load_game (int num) {
static char ** games [] = { yoyo1, yoyo2, yoyo3 };
int ndx;
grid = games[num-1];

maxx = 0;
for (ndx = 0; grid[ndx][0]; ++ndx) {
int len = strlen(grid[ndx]);
if (len maxx) { maxx = len; }
}
maxy = ndx;
}

// ------------------------------------------

int main (void)
{
load_game(3);

for (int row = 0; row < maxy; ++row) {
for (int col = 0; col < maxx; ++col) {
run(row, col);
}
}
printf("Wordcount = %d\n", wordcount);
return 0;
}

----------------------end---------------

I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)

I've already written this program in Perl-Tk, but the recursion that
occurs when the program is counting YOYOs conflicts with having a
responsive GUI interface. IOW, the program freezes at times.

The C++ program does essentially the same thing as the Perl-Tk program
but without the GUI. I created the C++ program to get rid of extraneous
stuff that doesn't relate to my core problem--the need to get rid of
recursion.

I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can't begin to coalesce any
ideas. Can someone help me remove the recursion from this program?
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

[dave_mikesell]

On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w
[e-mail]:

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"

[dave_mikesell]

On Apr 13, 7:16 am, [e-mail] wrote:

On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w

[e-mail]:

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"- Hide quoted text -

- Show quoted text -

Note that the above will solve the Yiddish version ("OYOY") as
well. ;-)

[Markus Moll]

da***********@fastmail.fm wrote:

On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w

>My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"

Indeed, inlining should be possible when the recursion depth is fixed
;-) But you should include some "seen" array so that no field is used
twice within the same word (e.g. you produce yoyo from "Y O")

However, the more general solution would be to use a FIFO and push/pop
states containing the field to visit and the current depth.

Markus

[Markus Moll]

Markus Moll wrote:

However, the more general solution would be to use a FIFO and push/pop

^^^^

make that a LIFO...

[dave_mikesell]

On Apr 13, 8:03 am, Markus Moll <[e-mail]:

[e-mail] wrote:

On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w

My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"

Indeed, inlining should be possible when the recursion depth is fixed
;-) But you should include some "seen" array so that no field is used
twice within the same word (e.g. you produce yoyo from "Y O")

I think all you would have to do is make sure that in the 3rd "for
each" you don't examine the starting character of the current string.

Dammit, I got too much yard work this weekend but I know I'm going to
code this up anyway. :-p

[Ulrich Eckhardt]

Mumia W. wrote:

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

Here is the program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

const int max_points = 10;
extern int maxy, maxx;

struct Point {
int y;
int x;
Point () { y = x = 0; }
Point (int ey, int ex) { y = ey; x = ex; }

Look up "initialiser list" in your C++ book.

bool inbounds() {
if (y < 0 || y >= maxy) { return false; }
if (x < 0 || x >= maxx) { return false; }
return true;
}

Make this a const memberfunction, it doesn't modify the point on which it
is used.

char * as_string() {
char * temp = new char [10];
sprintf(temp, "(%d,%d)", y, x);
return temp;
}

Use std::string. If you really need, at least use sprintf.

void print() { printf("%s ", as_string()); }

Make this const, too.

struct Pointgrp {
int len;
Point points [max_points];
void print () {
for (int pos = 0; pos < len; ++pos) {
points[pos].print();
}
puts("");
}
};

Use std::vector<>.

char * yoyo2 [] = {
"YO",
"OY",
"",
};

If you write "foo" in a program, this is a string literal. String literals
are immutable, i.e. you must not try to modify them, like any constant.
The conversion to a not-const 'char*' which you use above is only for
compatibility with old C and dangerous because it allows accidental
modification. Use a 'char const*' instead.

char ** grid = yoyo1;

Bad idea, use a real container, e.g. std::list or std::vector.

I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)

It's really hard to tell, because your program is very complicated
(unnecessarily, because it mixes stuff like manual memory management with
the logic) and undocumented.

Anyway, recursions are not always avoidable, but if you are searching for
YOYOs, the first thing you need i a Y. From each Y, you start searching
the other three letters by first pushing all Os onto the result list. For
all those, you then search the surroundings again for the next letter and
so on.

For yoyo2 above, you would first find a Y at 0;0 and 1;1, let's start with
the first point:

{0,0}

you have three points around, only two have an O, so the next step you have

{0,0}, {0,1}
{0,0}, {1,0}

in the third step, you replace each of these pairs with triplets that
include the third letter:

{0,0}, {0,1}, {0,0}
{0,0}, {0,1}, {1,1}
{0,0}, {1,0}, {0,0}
{0,0}, {1,0}, {1,1}

The same step applies to the fourth step. Depending on what you want, you
can already there weed out cases where the same point is used twice.

I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can't begin to coalesce any
ideas.

The problem with a stack is managing the stack. Since you are not using the
C++-supplied container classes, you have to do it yourself, which presents
a big overhead. Stop that, you can't be productive like that. Other than
that, you can always use an iterative style for a problem that is rather
recursive, but when your iteration multiplies in number of calls this is
always some overhead, because you need to store the temporaries somewhere.

Uli

--
FAQ: http://ma.rtij.nl/acllc-c++.FAQ.html
Asking smart questions: http://www.catb.org/~esr/faqs/smart-questions.html

[Mumia W.]

On 04/13/2007 07:03 AM, Markus Moll wrote:

da***********@fastmail.fm wrote:

>On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w

>>My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"

Indeed, inlining should be possible when the recursion depth is fixed
;-) But you should include some "seen" array so that no field is used
twice within the same word (e.g. you produce yoyo from "Y O")

However, the more general solution would be to use a FIFO and push/pop
states containing the field to visit and the current depth.

Markus

That's exactly what I want to do (with a stack of course :-) ). I just
can't figure out how to do it. I know that, in the iterative version,
the function "run_partial" will go away, and the data that was its
arguments will instead go onto a stack.

But I can't figure out when to push the current Pointgrp (point-group)
onto the stack and when the pop it off.
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

[Mumia W.]

On 04/13/2007 10:31 AM, Ulrich Eckhardt @ Usenet wrote:

Mumia W. wrote:

>Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

Here is the program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

const int max_points = 10;
extern int maxy, maxx;

struct Point {
int y;
int x;
Point () { y = x = 0; }
Point (int ey, int ex) { y = ey; x = ex; }

Look up "initialiser list" in your C++ book.

> bool inbounds() {
if (y < 0 || y >= maxy) { return false; }
if (x < 0 || x >= maxx) { return false; }
return true;
}

Make this a const memberfunction, it doesn't modify the point on which it
is used.

> char * as_string() {
char * temp = new char [10];
sprintf(temp, "(%d,%d)", y, x);
return temp;
}

Use std::string. If you really need, at least use sprintf.

> void print() { printf("%s ", as_string()); }

Make this const, too.

>struct Pointgrp {
int len;
Point points [max_points];
void print () {
for (int pos = 0; pos < len; ++pos) {
points[pos].print();
}
puts("");
}
};

Use std::vector<>.

>char * yoyo2 [] = {
"YO",
"OY",
"",
};

If you write "foo" in a program, this is a string literal. String literals
are immutable, i.e. you must not try to modify them, like any constant.
The conversion to a not-const 'char*' which you use above is only for
compatibility with old C and dangerous because it allows accidental
modification. Use a 'char const*' instead.

>char ** grid = yoyo1;

Bad idea, use a real container, e.g. std::list or std::vector.

Thanks. I'll try to find out what those are.

>I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)

It's really hard to tell, because your program is very complicated
(unnecessarily, because it mixes stuff like manual memory management with
the logic) and undocumented.

Anyway, recursions are not always avoidable, but if you are searching for
YOYOs, the first thing you need i a Y. From each Y, you start searching
the other three letters by first pushing all Os onto the result list. For
all those, you then search the surroundings again for the next letter and
so on.

For yoyo2 above, you would first find a Y at 0;0 and 1;1, let's start with
the first point:

{0,0}

you have three points around, only two have an O, so the next step you have

{0,0}, {0,1}
{0,0}, {1,0}

in the third step, you replace each of these pairs with triplets that
include the third letter:

{0,0}, {0,1}, {0,0}
{0,0}, {0,1}, {1,1}
{0,0}, {1,0}, {0,0}
{0,0}, {1,0}, {1,1}

The same step applies to the fourth step. Depending on what you want, you
can already there weed out cases where the same point is used twice.

Yes, this is similar to what my program currently does, but my program
does it recursively.

>I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can't begin to coalesce any
ideas.

The problem with a stack is managing the stack. Since you are not using the
C++-supplied container classes, you have to do it yourself, which presents
a big overhead. Stop that, you can't be productive like that. Other than
that, you can always use an iterative style for a problem that is rather
recursive, but when your iteration multiplies in number of calls this is
always some overhead, because you need to store the temporaries somewhere.

Uli

Yes, they would be stored on a stack. But when do they go onto the
stack, and when do they come off the stack?
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

[gw7rib]

On 13 Apr, 17:15, "Mumia W." <paduille.4061.mumia.w
[e-mail]:

On 04/13/2007 07:03 AM, Markus Moll wrote:

[e-mail] wrote:

On Apr 13, 4:30 am, "Mumia W." <paduille.4061.mumia.w
My program works great, but it uses recursion, and I want to work
iteratively.

What am I missing?

for each char in grid:
for each surrounding opposite char:
for each surrounding opposite char:
for each surrounding opposite char:
"found yoyo"

Indeed, inlining should be possible when the recursion depth is fixed
;-) But you should include some "seen" array so that no field is used
twice within the same word (e.g. you produce yoyo from "Y O")

However, the more general solution would be to use a FIFO and push/pop
states containing the field to visit and the current depth.

Markus

That's exactly what I want to do (with a stack of course :-) ). I just
can't figure out how to do it. I know that, in the iterative version,
the function "run_partial" will go away, and the data that was its
arguments will instead go onto a stack.

But I can't figure out when to push the current Pointgrp (point-group)
onto the stack and when the pop it off.

Is the aim simply to do it iteratively, or is there some reason (such
as practice) that you want a stack to be involved?

If you are simply looking for an iterative solution then Dave's
solution should work fine - no stack required.

If you do want to use a stack, then I suggest first that you write a
non-stack version along the lines of Dave's program. Call your
variables a, b, c and d. Now, take a piece of paper and write the
letters a, b, c and d on it, in a row. Each of these letters will
represent a number stored on the stack. Starting with d (the variable
used in the innermost loop), re-write your program so that instead of
using the most innermost vaiable it stores a number on the stack. You
will need to put a starting value on, you will need to read it at
various points, you will need to replace it with a higher value, and
eventually you will need to get rid of it completely. Once you've got
rid of d, do the same (it's always easier the second time) until you
have got rid of c, b and a. I'll leave the details to you.

Hope that helps.
Paul.

[Bart van Ingen Schenau]

Mumia W. wrote:

Hello all.

<snip>

I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)

I've already written this program in Perl-Tk, but the recursion that
occurs when the program is counting YOYOs conflicts with having a
responsive GUI interface. IOW, the program freezes at times.

Then I have some moderately bad news for you.
Rewriting the program with an iterative version of the algorithm will
not make the responsiveness issues go away.

>
The C++ program does essentially the same thing as the Perl-Tk program
but without the GUI. I created the C++ program to get rid of
extraneous stuff that doesn't relate to my core problem--the need to
get rid of recursion.

I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can't begin to coalesce any
ideas. Can someone help me remove the recursion from this program?

Your best bet to get a responsive system is to make the core-loop of the
algorithm message based.
This is actually not too hard, if you start with the current, recursive,
implementation.

The trick is that you replace each call to the run_partial() function
with an event trigger (or the sending of a message).
In the event-loop of the application, you now make the call to
run_partial() whenever the corresponding event is being processed.

Unfortunately, I can't give you any code examples, as C and C++ do not
have event loops, and Perl-Tk is too far off-topic.

Bart v Ingen Schenau
--
a.c.l.l.c-c++ FAQ: http://www.comeaucomputing.com/learn/faq
c.l.c FAQ: http://www.eskimo.com/~scs/C-faq/top.html
c.l.c++ FAQ: http://www.parashift.com/c++-faq-lite/

[Mumia W.]

On 04/14/2007 03:48 PM, Bart van Ingen Schenau wrote:

>
Then I have some moderately bad news for you.
Rewriting the program with an iterative version of the algorithm will
not make the responsiveness issues go away.
[...]

Yes, I've figured that out.

Your best bet to get a responsive system is to make the core-loop of the
algorithm message based.
This is actually not too hard, if you start with the current, recursive,
implementation.

For me it's very hard. Removing recursion is something I've never been
able to do well.

The trick is that you replace each call to the run_partial() function
with an event trigger (or the sending of a message).
In the event-loop of the application, you now make the call to
run_partial() whenever the corresponding event is being processed.
[...]

That's what I now intend to do. I decided to "simplify" my program by
removing some unneeded classes and making it non-functional :-)

Now I have this skeleton, but I can't figure out what to put into
tick_count(). I know that each point has to go onto the stack, and each
point has to come off the stack for processing--but when?

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>

const int max_points = 10;
const int Y = 0;
const int X = 1;
// Operation: This object represents a YOYO finding
// operation.
struct Operation {
int tick_count;
int ptpos;
int points [max_points][2];
int row;
int col;

int nine[9][2];

Operation();
void setup();
bool timer_tick();
void push (const int (&)[2]);
bool pop (int (&)[2]);
int stack_size() const;
};

// ---------------------------------------

// What follow are some sample YOYO games.
const char * yoyo1 [] = {
" YOY ",
" YOYOO ",
"OYYOYYO",
" OYYYO ",
" YOY ",
"",
};

const char * yoyo2 [] = {
"YO",
"OY",
"",
};

const char * yoyo3 [] = {
"YOYOOY",
"OYOYOO",
"YOYYOY",
"OYOOYO",
"OYYOYO",
"",
};

const char ** grid; // which grid to use
int maxy; // number of rows in grid
int maxx; // number of columns in grid

// ---------------------------------------

// atgrid: Extract the character in the grid
// given by row=y and column=x.
char atgrid (int y, int x) {
return grid[y][x];
}

// Load the game given by "num" (1-3).
void load_game (int num) {
static const char ** games [] = { yoyo1, yoyo2, yoyo3 };
int ndx;
grid = games[num-1];

maxx = 0;
for (ndx = 0; grid[ndx][0]; ++ndx) {
int len = strlen(grid[ndx]);
if (len maxx) { maxx = len; }
}
maxy = ndx;
}

// error_exit: Display a message then exit.
void error_exit (const char * fmt,...) {
va_list ap;
va_start(ap,fmt);
vfprintf(stderr, fmt, ap);
exit(EXIT_FAILURE);
}

// Convert a group of points into a string by
// extracting characters from corresponding
// positions in the grid.
char * collect_points (int len, int (*pts)[2]) {
char * temp = new char [15];
*temp = 0;
for (int pix = 0; pix < len; ++pix) {
char part [3] = "*";
int * mypt = pts[pix];
part[0] = atgrid(mypt[Y], mypt[X]);
strcat(temp, part);
}
return temp;
}

// ---------------------------------------

Operation::Operation () {
tick_count = ptpos = row = col = 0;
memset(points,0,sizeof(points));
setup();
}

void
Operation::setup() {
int npos = 0;
for (int yi = -1; yi < 2; ++yi) {
for (int xi = -1; xi < 2; ++xi) {
nine[npos][Y] = yi;
nine[npos++][X] = xi;
}
}
}

int
Operation::stack_size() const {
return ptpos;
}

void
Operation::push (const int (&pt)[2]) {
if (ptpos >= max_points) {
error_exit("Max points (%d) exceeded.\n", max_points);
}
*points[ptpos++] = *pt;
}

bool
Operation::pop (int (&pt)[2]) {
if (ptpos < 1) { return false; }
*pt = *points[--ptpos];
return true;
}

// timer_tick: The algorithm for finding YOYOs needs
// to go here.
bool
Operation::timer_tick () {
// printf("Tick = %d\n", tick_count);

if (col >= maxx) { row++; col = 0; puts(""); }
if (row >= maxy) { return false; }

printf("(%d,%d) ", row, col);

col++;
return true;
}
// ---------------------------------------

int main (void)
{
Operation opr;
load_game(1);

int mypt [2] = { 2, 3 };
int & tcount = opr.tick_count;
opr.push(mypt);

for (tcount = 0; tcount < 110; ++tcount) {
bool domore = opr.timer_tick();
if (!domore) { break; }
}

return EXIT_SUCCESS;
}
------------end-code---------

All the hard stuff will have to go into Operation::timer_tick(). Yes I
know that just printing out grid positions is somewhat anti-climatic,
but that's where I'm stuck :-(
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

[Mumia W.]

On 04/13/2007 03:30 AM, Mumia W. wrote:

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

Here is the program:
[...]

I've looked on the Internet, and this is the type of problem that is
"hard" to solve. And because my program is event-driven, it seems that I
need to create a state machine while removing the recursion.

What fun :-\

Has anyone faced something like this before?
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/

[Sam of California]

I don't know how to do that except that I want to use iterative solutions
for recursive data such as child windows of GUI windows and also for
subdirectories of file systems. I have a book about data design for Pascal
that seems to have answers but I have not read it yet.

What I am getting at is that there nearly certainly are books about C++ that
will help. Perhaps you have a library nearby where you can find books, at
least to the extent of determining a book to buy that has answers.

I assume that a stack would be needed, or the equivalent of a stack. Just
think in terms of what needs to be done that would be done automatically by
recursion.
"Mumia W." <pa**************************@earthlink.netwrote in message
news:tc*****************@newsread1.news.pas.earthl ink.net...

Hello all.

I have a C++ program that can count the YOYOs that are in a grid of
Y's and O's. For example, this

Y O Y O O Y
O Y O Y O O
Y O Y Y O Y
O Y O O Y O
O Y Y O Y O

should have 406 YOYO's in it. YOYO's an go up, down, right and left with
bends and diagonals.

My program works great, but it uses recursion, and I want to work
iteratively.

Here is the program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

const int max_points = 10;
extern int maxy, maxx;

struct Point {
int y;
int x;
Point () { y = x = 0; }
Point (int ey, int ex) { y = ey; x = ex; }
void set (int ey, int ex) { y = ey; x = ex; }
bool inbounds() {
if (y < 0 || y >= maxy) { return false; }
if (x < 0 || x >= maxx) { return false; }
return true;
}
char * as_string() {
char * temp = new char [10];
sprintf(temp, "(%d,%d)", y, x);
return temp;
}
void print() { printf("%s ", as_string()); }
};

struct Pointgrp {
int len;
Point points [max_points];
void print () {
for (int pos = 0; pos < len; ++pos) {
points[pos].print();
}
puts("");
}
};

struct Seen {
char data [1000];
Seen() { clear(); }
void clear() { memset(data,0,sizeof(data)); }
char & pos(int y, int x) {
return data[(y * maxx) + x];
}
void init(const Pointgrp & pts) {
for (int pix = 0; pix < pts.len; ++pix) {
const Point & mypt = pts.points[pix];
pos(mypt.y, mypt.x) = 1;
}
}
char & posPoint(const Point & pt) {
pos(pt.y, pt.x);
}
};

char * yoyo1 [] = {
" YOY ",
" YOYOO ",
"OYYOYYO",
" OYYYO ",
" YOY ",
"",
};

char * yoyo2 [] = {
"YO",
"OY",
"",
};

char * yoyo3 [] = {
"YOYOOY",
"OYOYOO",
"YOYYOY",
"OYOOYO",
"OYYOYO",
"",
};

char ** grid = yoyo1;
int maxx = 7;
int maxy = 5;

const char * search_for = "YOYO";
int search_len = 4;
int wordcount = 0;

// ------------------------------------------

char & atgrid (int y, int x) {
return grid[y][x];
}

char * collect_points (const Pointgrp & pts) {
char * temp = new char [15];
*temp = 0;
for (int pix = 0; pix < pts.len; ++pix) {
char part [3] = "*";
const Point & mypt = pts.points[pix];
part[0] = atgrid(mypt.y, mypt.x);
strcat(temp, part);
}
return temp;
}

void run_partial (Pointgrp group) {
Pointgrp newgrp = group;
if (group.len >= 4) {
char * str = collect_points(group);
bool dbgf = false;

if (0 == memcmp(str,search_for,search_len)) {
// dbgf = true;
wordcount++;
}

if (dbgf) {
puts("Points:");
newgrp.print();
puts(str);
}
delete[] str;
return;
}

Seen * seenobj = new Seen;
seenobj->init(newgrp);

Point & lastpt = group.points[group.len-1];
Point & newpt = newgrp.points[group.len];
newgrp.len++;

for (int yi = -1; yi < 2; ++yi) {
for (int xi = -1; xi < 2; ++xi) {
if (0 == yi && 0 == xi) { continue; }
// printf("(%d,%d) ", yi, xi);
newpt.set(lastpt.y + yi, lastpt.x + xi);
if (! newpt.inbounds()) { continue; }
if (seenobj->posPoint(newpt)) { continue; }
run_partial(newgrp);
}
// puts("");
}

delete seenobj;
}

void run (int y, int x) {
Point pt(y,x);
Pointgrp grp;

grp.len = 1;
grp.points[0] = pt;
run_partial(grp);
}

void load_game (int num) {
static char ** games [] = { yoyo1, yoyo2, yoyo3 };
int ndx;
grid = games[num-1];

maxx = 0;
for (ndx = 0; grid[ndx][0]; ++ndx) {
int len = strlen(grid[ndx]);
if (len maxx) { maxx = len; }
}
maxy = ndx;
}

// ------------------------------------------

int main (void)
{
load_game(3);

for (int row = 0; row < maxy; ++row) {
for (int col = 0; col < maxx; ++col) {
run(row, col);
}
}
printf("Wordcount = %d\n", wordcount);
return 0;
}

----------------------end---------------

I used recursion because that was the only way I could envision a
solution, but now I want to remove the recursion because I need the
operations to be done in the event-loop of a Perl-Tk program :-)

I've already written this program in Perl-Tk, but the recursion that
occurs when the program is counting YOYOs conflicts with having a
responsive GUI interface. IOW, the program freezes at times.

The C++ program does essentially the same thing as the Perl-Tk program but
without the GUI. I created the C++ program to get rid of extraneous stuff
that doesn't relate to my core problem--the need to get rid of recursion.

I know that there /has/ to be an iterative solution for this
problem--probably involving a stack, but I can't begin to coalesce any
ideas. Can someone help me remove the recursion from this program?
--
Count the YOYOs:
http://home.earthlink.net/~mumia.w.18.spam/games_fever/