Re: Removing recursion

From:

"Mumia W." <paduille.4061.mumia.w+nospam@earthlink.net>

Newsgroups:

comp.lang.c++

Date:

Sun, 15 Apr 2007 07:33:15 GMT

Message-ID:

<%ykUh.3599$3P3.3271@newsread3.news.pas.earthlink.net>

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/