A Grid of Random Stars, Half III

The subsequent replace to my pattern-finding program is to search out and discover a clutch of asterisks within the grid that kind a rectangle. Determine 1 illustrates what I’m after.

Determine 1. Only a few of the various doable rectangles to be discovered within the grid.

My method is has three steps:

1. Scan the complete grid. Use a nested loop to search for any asterisk.
2. When an asterisk is discovered, look down the identical row for an asterisk in that column.
3. Scan throughout each rows trying to find matching asterisks.

These steps mimicked how I discovered rectangles after I tried this train on paper: I scanned down columns first for matching asterisks, then I checked every columns’ rows. You would as a substitute do it by columns after which rows as properly. Identical distinction.

I up to date the code from final week’s Lesson, which makes use of pointers as a substitute of a two-dimensional array.

Within the principal() perform, I constructed the second nested loop, which re-uses variables row and col to plow by means of the complete grid. A check is added to examine for an asterisk:

if( *(grid+row*COLS+col) == '*' )

If true, I name the scan_column() perform, which scans down the identical column for one more asterisk. It’s handed the grid’s tackle and the present row, column values:

int scan_column(char *g,int r,int c)
{
    int scandown;

    for( scandown=r+1; scandown<ROWS; scandown++ )
    {
        if( *(g+scandown*COLS+c) == '*' )
            return(scandown);
    }
    return(0);
}

The for loop scans down the column, utilizing variable scandown to trace the present row. When an asterisk is discovered, its row worth is returned to the principal() perform. In any other case, zero is returned.

Upon success (a non-zero worth) a second perform is known as from throughout the nested loop, find_right(). This perform scans each rows for matching asterisks. When discovered, the column quantity is returned:

int find_right(char *g,int r1,int c1,int r2)
{
    int f;

    for( f=c1+1; f<COLS; f++ )
    {
        if( *(g+r1*COLS+f)=='*' && *(g+r2*COLS+f)=='*' )
            return f;
    }
    return(0);
}

Upon success, the principal() perform has the coordinates of 4 asterisks in the identical column/row positions — a rectangle. A rely variable is incremented and the coordinate pairs are output.

Right here is the total code:

2024_06_01-Lesson.c

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

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

void output_grid(char *g)
{
    int r,c;

    for( r=0; r<ROWS; r++ )
    {
        for( c=0; c<COLS; c++ )
        {
            putchar( *(g+r*COLS+c) );
        }
        putchar('n');
    }
}


int scan_column(char *g,int r,int c)
{
    int scandown;

    for( scandown=r+1; scandown<ROWS; scandown++ )
    {
        if( *(g+scandown*COLS+c) == '*' )
            return(scandown);
    }
    return(0);
}

int find_right(char *g,int r1,int c1,int r2)
{
    int f;

    for( f=c1+1; f<COLS; f++ )
    {
        if( *(g+r1*COLS+f)=='*' && *(g+r2*COLS+f)=='*' )
            return f;
    }
    return(0);
}

int principal()
{
    char *grid;
    int row,col,r,c,rely;

    
    srand( (unsigned)time(NULL) );

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

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

    
    output_grid(grid);

    rely = 0;
    
    for( row=0; row<ROWS-1; row++ )
    {
        for( col=0; col<COLS; col++ )
        {
            
            if( *(grid+row*COLS+col) == '*' )
            {
                
                r = scan_column(grid,row,col);
                if(r)
                {
                    c = find_right(grid,row,col,r);
                    if(c)
                    {
                        rely++;
                        printf("%2nd %02d:%02d - %02d:%02dn",
                                rely,row,col,row,c);
                        printf("   %02d:%02d - %02d:%02dn",
                                r,col,r,c);
                    }
                }
            }
        }
    }

    return 0;
}

Here’s a pattern run (although not all of it):

......**......*............*....
....*......*.*.*...**...........
...***............*.*.**........
*......*.....*.*.........*...*.*
.........**.........*.*.........
......*.**...*.*....****........
.............**.................
..*..*.*......*.**..........*.*.
.*.....*..........**.*...*.**...
*...*.*....***....**........*.*.
..*..*...*..................*...
..*......*.............*.....*.*
....**..*....*......*..*.......*
........*........*...........*..
...............**.....*....**..*
...*....*...*.........*..*......
 1 01:04 - 01:20
   02:04 - 02:20
 2 01:11 - 01:13
   09:11 - 09:13
 3 01:13 - 01:15
   03:13 - 03:15
. . .
23 09:04 - 09:13
   12:04 - 12:13
24 10:02 - 10:09
   11:02 - 11:09
25 11:23 - 11:31
   12:23 - 12:31

I received so excited with the outcomes that I forgot two issues: First, that recursion clearly isn’t want. However extra essential, this system isn’t actually discovering all of the rectangles; a flaw exists within the code.

In subsequent week’s Lesson, I replace the code to graphically output the rectangles. Solely then did I uncover the flaw.