Re: Removing recursion

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/