The two problems I recognized in the code from last week’s Lesson were that scan_column() and find_right() don’t need to be separate functions. Also, the code fails to find all the rectangles in the grid, which is bad. Time to fix the code!

Pulling the code from the two functions into the main() function was easy. Each function is basically a for statement with an if test inside — two lines. No value needs to be returned as the if test triggers whether the next for loop is executed.

Further, by moving the functions into the main nested loop, the problem with not finding the next rectangle in the same row is immediately solved! Remember, my original assumption was that the scan_column() and find_right() functions would be called recursively. They don’t need to be as long as the loops continue to work within the main program loop.

Here is the updated, consolidated code, which is rather wide on this page:

2024_06_15-Lesson.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ROWS 16
#define COLS ROWS*2
#define SIZE COLS*ROWS
#define PROB 5

struct rect {
    int top;
    int bottom;
    int left;
    int right;
};

void output_grid(char *g,struct rect r)
{
    int row,col;

    for( row=0; row<ROWS; row++ )
    {
        for( col=0; col<COLS; col++ )
        {
            if(
                    (row==r.top && (col>r.left && col<r.right) ) ||
                    (row==r.bottom && (col>r.left && col<r.right) )
              )
                putchar('-');
            else if(
                    (col==r.left && (row>r.top && row<r.bottom) ) ||
                    (col==r.right && (row>r.top && row<r.bottom) )
                   )
                putchar('|');
            else
                putchar( *(g+row*COLS+col) );
        }
        putchar('\n');
    }
}

int main()
{
    char *grid;
    int row,col,count;
    struct rect r;

    /* seed the randomizer */
    srand( (unsigned)time(NULL) );

    /* allocate grid */
    grid = malloc( sizeof(char) * SIZE );
    if( grid==NULL )
    {
        fprintf(stderr,"Unable to allocate memory\n");
        exit(1);
    }

    /* fill the grid */
    for( row=0; row<ROWS; row++ )
    {
        for( col=0; col<COLS; col++ )
        {
            if( rand() % PROB )
                *(grid+row*COLS+col) = '.';
            else
                *(grid+row*COLS+col) = '*';
        }
    }

    count = 0;
    /* scan for two in a column */
    for( r.top=0; r.top<ROWS-1; r.top++ )
    {
        for( r.left=0; r.left<COLS; r.left++ )
        {
            /* find a star in the row */
            if( *(grid+r.top*COLS+r.left) == '*' )
            {
                /* look for a matching star in the same column */
                for( r.bottom=r.top+1; r.bottom<ROWS; r.bottom++ )
                {
                    if( *(grid+r.bottom*COLS+r.left) == '*' )
                    {
                        for( r.right=r.left+1; r.right<COLS; r.right++ )
                        {
                            if( *(grid+r.top*COLS+r.right)=='*' && *(grid+r.bottom*COLS+r.right)=='*' )
                            {
                                count++;
                                printf("Rectangle %d:\n",count);
                                output_grid(grid,r);
                            }
                        }
                    }
                }
            }
        }
    }
    printf("Found %d rectangles\n",count);

    return 0;
}

No changes were needed for the output_grid() function. My goal here is only to incorporate the scan_column() and find_right() and ensure that all the rectangles are found. Otherwise, the code runs the same as it did before, outputting subsequent rectangles as they’re found in the grid. Here is partial output:

Rectangle 1:
.*-------------**......*...*...*
.|*....*.......|..*..*..........
.|.*...........|...*.*....**....
.*-------------*...*.*...**.....
.....................*..*.......
....*..*........*..........*....
...........**..................*
.*.......*..**..****.*.....*....
.....*..***...........*.*....*..
..*.*....**....*....*....*..*..*
....*...*.....*......*.**.......
..*.....**.......*.**.*......*.*
*.....*.***....*........*....*..
...*.........*..................
*..*.*.*...*.*.*...........**.*.
...*...**.*........*.....**.....
Rectangle 2:
.*----------*.***......*...*...*
.|*....*....|.....*..*..........
.|.*........|..*...*.*....**....
.|.........*|..*...*.*...**.....
.|..........|........*..*.......
.|..*..*....|...*..........*....
.|.........*|..................*
.*----------**..****.*.....*....
.....*..***...........*.*....*..
..*.*....**....*....*....*..*..*
....*...*.....*......*.**.......
..*.....**.......*.**.*......*.*
*.....*.***....*........*....*..
...*.........*..................
*..*.*.*...*.*.*...........**.*.
...*...**.*........*.....**.....

Rectangle 82:
.*..........*.***......*...*...*
..*....*..........*..*..........
...*...........*...*.*....**....
.*.........*...*...*.*...**.....
.....................*..*.......
....*..*........*..........*....
...........**..................*
.*.......*..**..****.*.....*....
.....*..***...........*.*....*..
..*.*....**....*....*....*..*..*
....*...*.....*......*.**.......
..*.....**.......*.**.*......*.*
*.....*.***....*........*....*..
...*---------*..................
*..*---------*.*...........**.*.
...*...**.*........*.....**.....
Rectangle 83:
.*..........*.***......*...*...*
..*....*..........*..*..........
...*...........*...*.*....**....
.*.........*...*...*.*...**.....
.....................*..*.......
....*..*........*..........*....
...........**..................*
.*.......*..**..****.*.....*....
.....*..***...........*.*....*..
..*.*....**....*....*....*..*..*
....*...*.....*......*.**.......
..*.....**.......*.**.*......*.*
*.....*.***....*........*....*..
...*.........*..................
*..*---*...*.*.*...........**.*.
...*---**.*........*.....**.....
Found 83 rectangles

The total of 83 rectangles seems more appropriate. I also confirmed the number by printing the output and checking each location. Yes, the computer does the job far faster than a human.

My task is essentially complete. I’m able to generate a grid of random asterisks and use the computer to locate them, highlighting the output. Being a programmer nerd, however, I’m not quite done yet. I would like to create output similar to Figure 1, though in ASCII.

Figure 1. Output like this would be preferred, but in ASCII of course.

In next week’s Lesson, I shorten the output to display the original grid and then another that shows all the triangles, or as many of them as can be mapped in text output.