![\"grid](\"https:\/\/c-for-dummies.com\/blog\/wp-content\/uploads\/2024\/05\/0601-figure1.png\")
Figure 1. Just a few of the many possible rectangles to be found in the grid.<\/p><\/div><\/p>\n
My approach is has three steps:<\/p>\n
- \n
- Scan the entire grid. Use a nested loop to look for any asterisk.<\/li>\n
- When an asterisk is found, look down the same row for an asterisk in that column.<\/li>\n
- Scan across both rows searching for matching asterisks.<\/li>\n<\/ol>\n
These steps mimicked how I found rectangles when I tried this exercise on paper: I scanned down columns first for matching asterisks, then I checked each columns’ rows. You could instead do it by columns and then rows as well. Same difference.<\/p>\n
I updated the code from last week’s Lesson<\/a>, which uses pointers instead of a two-dimensional array.<\/p>\n
In the main()<\/em> function, I constructed the second nested loop, which re-uses variables
row<\/code> andcol<\/code> to plow through the entire grid. A test is added to check for an asterisk:<\/p>\nif( *(grid+row*COLS+col) == '*' )<\/code><\/p>\nIf true, I call the scan_column()<\/em> function, which scans down the same column for another asterisk. It’s passed the grid’s address and the current row, column values:<\/p>\n
\r\n\/* look in the current column `c` for a star *\/<\/span>\r\nint scan_column(char *g,int r,int c)\r\n{\r\n int scandown;\r\n\r\n for( scandown=r+1; scandown<ROWS; scandown++ )\r\n {\r\n if( *(g+scandown*COLS+c) == '*' )\r\n return(scandown);\r\n }\r\n return(0);\r\n}<\/pre>\nThe for<\/em> loop scans down the column, using variable
scandown<\/code> to track the current row. When an asterisk is found, its row value is returned to the main()<\/em> function. Otherwise, zero is returned.<\/p>\nUpon success (a non-zero value) a second function is called from within the nested loop, find_right()<\/em>. This function scans both rows for matching asterisks. When found, the column number is returned:<\/p>\n
\r\nint find_right(char *g,int r1,int c1,int r2)\r\n{\r\n int f;\r\n\r\n for( f=c1+1; f<COLS; f++ )\r\n {\r\n if( *(g+r1*COLS+f)=='*' && *(g+r2*COLS+f)=='*' )\r\n return f;\r\n }\r\n return(0);\r\n}<\/pre>\nUpon success, the main()<\/em> function has the coordinates of four asterisks in the same column\/row positions — a rectangle. A
count<\/code> variable is incremented and the coordinate pairs are output.<\/p>\nHere is the full code:<\/p>\n
2024_06_01-Lesson.c<\/a><\/h3>\n
\r\n#include <stdio.h>\r\n#include <stdlib.h>\r\n#include <time.h>\r\n\r\n#define ROWS 16\r\n#define COLS ROWS*2\r\n#define SIZE COLS*ROWS\r\n#define PROB 5\r\n\r\nvoid output_grid(char *g)\r\n{\r\n int r,c;\r\n\r\n for( r=0; r<ROWS; r++ )\r\n {\r\n for( c=0; c<COLS; c++ )\r\n {\r\n putchar( *(g+r*COLS+c) );\r\n }\r\n putchar('\\n');\r\n }\r\n}\r\n\r\n\/* look in the current column `c` for a star *\/<\/span>\r\nint scan_column(char *g,int r,int c)\r\n{\r\n int scandown;\r\n\r\n for( scandown=r+1; scandown<ROWS; scandown++ )\r\n {\r\n if( *(g+scandown*COLS+c) == '*' )\r\n return(scandown);\r\n }\r\n return(0);\r\n}\r\n\r\nint find_right(char *g,int r1,int c1,int r2)\r\n{\r\n int f;\r\n\r\n for( f=c1+1; f<COLS; f++ )\r\n {\r\n if( *(g+r1*COLS+f)=='*' && *(g+r2*COLS+f)=='*' )\r\n return f;\r\n }\r\n return(0);\r\n}\r\n\r\nint main()\r\n{\r\n char *grid;\r\n int row,col,r,c,count;\r\n\r\n \/* seed the randomizer *\/<\/span>\r\n srand( (unsigned)time(NULL) );\r\n\r\n \/* allocate grid *\/<\/span>\r\n grid = malloc( sizeof(char) * SIZE );\r\n if( grid==NULL )\r\n {\r\n fprintf(stderr,\"Unable to allocate memory\\n\");\r\n exit(1);\r\n }\r\n\r\n \/* fill the grid *\/<\/span>\r\n for( row=0; row<ROWS; row++ )\r\n {\r\n for( col=0; col<COLS; col++ )\r\n {\r\n if( rand() % PROB )\r\n *(grid+row*COLS+col) = '.';\r\n else\r\n *(grid+row*COLS+col) = '*';\r\n }\r\n }\r\n\r\n \/* output the grid *\/<\/span>\r\n output_grid(grid);\r\n\r\n count = 0;\r\n \/* scan for two in a column *\/<\/span>\r\n for( row=0; row<ROWS-1; row++ )\r\n {\r\n for( col=0; col<COLS; col++ )\r\n {\r\n \/* find a star in the row *\/<\/span>\r\n if( *(grid+row*COLS+col) == '*' )\r\n {\r\n \/* look for a matching star in the same column *\/<\/span>\r\n r = scan_column(grid,row,col);\r\n if(r)\r\n {\r\n c = find_right(grid,row,col,r);\r\n if(c)\r\n {\r\n count++;\r\n printf(\"%2d %02d:%02d - %02d:%02d\\n\",\r\n count,row,col,row,c);\r\n printf(\" %02d:%02d - %02d:%02d\\n\",\r\n r,col,r,c);\r\n }\r\n }\r\n }\r\n }\r\n }\r\n\r\n return 0;\r\n}<\/pre>\nHere is a sample run (though not all of it):<\/p>\n
......**......*............*....
\n....*......*.*.*...**...........
\n...***............*.*.**........
\n*......*.....*.*.........*...*.*
\n.........**.........*.*.........
\n......*.**...*.*....****........
\n.............**.................
\n..*..*.*......*.**..........*.*.
\n.*.....*..........**.*...*.**...
\n*...*.*....***....**........*.*.
\n..*..*...*..................*...
\n..*......*.............*.....*.*
\n....**..*....*......*..*.......*
\n........*........*...........*..
\n...............**.....*....**..*
\n...*....*...*.........*..*......
\n 1 01:04 - 01:20
\n 02:04 - 02:20
\n 2 01:11 - 01:13
\n 09:11 - 09:13
\n 3 01:13 - 01:15
\n 03:13 - 03:15
\n. . .
\n23 09:04 - 09:13
\n 12:04 - 12:13
\n24 10:02 - 10:09
\n 11:02 - 11:09
\n25 11:23 - 11:31
\n 12:23 - 12:31<\/code><\/p>\nI got so excited with the results that I forgot two things: First, that recursion obviously isn’t need. But more important, the program isn’t really finding all the rectangles; a flaw exists in the code.<\/p>\n
In next week’s Lesson<\/a>, I update the code to graphically output the rectangles. Only then did I discover the flaw.<\/p>\n","protected":false},"excerpt":{"rendered":"
This update to the grid locates rectangular patterns and reports the coordinates. Continue reading