dmilicev

find_the_word_in_the_crossword_puzzle_v1.c

Oct 3rd, 2020
219
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 16.91 KB
  1. /*
  2.  
  3.     find_the_word_in_the_crossword_puzzle_v1.c
  4.  
  5.     Task:
  6.     https://www.facebook.com/photo/?fbid=1487687438086412&set=gm.788787108602994
  7.     Picture of task:
  8.     http://www.mediafire.com/view/atbcm8jbg06i7uk/Task+substrings+in+table.jpg/file
  9.  
  10.  
  11.     I think we need to work with a character matrix M[n][n] .
  12.     char M[n][n];
  13.  
  14.     8 possible directions for the required word should be introduced:
  15.     Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight.
  16.  
  17.     Then you should go in order on the matrix
  18.     until you find the first letter from the required word.
  19.     In all 8 directions, examine whether there is a required word,
  20.     ie whether in the given direction the next letter is equal to the
  21.     next letter of the required word and so on until the end of the required word.
  22.     If the search word in that direction exists, increase the counter.
  23.     Be careful not to exceed the matrix limits during the test.
  24.     Repeat this until the end of the matrix M[n*n].
  25.  
  26.  
  27.     You can find all my C programs at Dragan Milicev's pastebin:
  28.  
  29.     https://pastebin.com/u/dmilicev
  30.  
  31. */
  32.  
  33. #include <stdio.h>
  34.  
  35. #define MAX_SIZE 1000   // max size of requested word in matrix M[MAX_SIZE][MAX_SIZE]
  36. #define UP          0   // define 8 possible directions
  37. #define DOWN        1
  38. #define LEFT        2
  39. #define RIGHT       3
  40. #define UP_LEFT     4
  41. #define UP_RIGHT    5
  42. #define DOWN_LEFT   6
  43. #define DOWN_RIGHT  7
  44.  
  45.  
  46. // Displays characters of the matrix M[r][c] that has r rows and c columns
  47. void print_matrix( char *text, char M[][MAX_SIZE], int r, int c )
  48. {
  49.     int i, j;
  50.  
  51.     printf("%s", text );
  52.  
  53.     for(i=0;i<r;i++) {
  54.         for(j=0;j<c;j++)
  55.             printf(" %c ", M[i][j] );
  56.  
  57.         printf("\n\n");
  58.     }
  59. }
  60.  
  61.  
  62. // Returns the number of occurrences of the requested word in the matrix M
  63. int number_off_occurrences( char word[], char M[][MAX_SIZE], int rows, int columns )
  64. {
  65.     int i, row, column, r, c, counter=0, direction, end_of_table, end_of_word, match;
  66.     // i is index of word characters
  67.     // row and column are coordinates of matrix character that we examine in all directions
  68.     // r and c are current row and column (auxiliary coordinates)
  69.     // rows and columns are the sizes of the whole matrix M
  70.  
  71.     // Let's go in order by the elements of the matrix.
  72.     // When we come across an element of the matrix that is equal to the first
  73.     // character of the requested word, we process that element in all directions,
  74.     // looking for the following characters of the requested word.
  75.     for( row=0; row<rows; row++ )
  76.     {
  77.         for( column=0; column<columns; column++ )
  78.         {
  79.             i = 0;
  80.  
  81.             if( M[row][column] == word[i] )             // character of M equal to first character of word
  82.             {
  83.                 direction = 0;
  84.  
  85.                 while( direction < 8 )
  86.                 {
  87.                     i = 0;                              // index of first character of word
  88.                     match = 1;                          // first character of word and character of matrix M match
  89.                     end_of_table = 0;                   // it is not yet end of table
  90.                     end_of_word = 0;                    // it is not yet end of word
  91.                     r = row;                            // from current row
  92.                     c = column;                         // from current column
  93.  
  94.                     switch( direction++ )
  95.                     {
  96.                     case UP :
  97.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  98.                         {
  99.                             if( r >= 0 )                        // if can go UP in matrix M
  100.                                 r--;                            // go UP in matrix M
  101.                             else
  102.                                 end_of_table = 1;               // if can't go UP in matrix M, end
  103.  
  104.                             if( word[++i] == '\0' )             // if we reach the end of word,
  105.                                 end_of_word = 1;                // it is the end of word
  106.  
  107.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  108.                                 match = 0;                      // they don't match
  109.                         } // while( match && !end_of_word && !end_of_table )
  110.  
  111.                         if( match )                             // if all characters of word are match
  112.                         {
  113.                             counter++;                          // count that word
  114.                             printf("\n M[%d][%d] = %c \t found UP \n", row+1, column+1, M[row][column] );
  115.                         }
  116.                         break;
  117.  
  118.                     case DOWN :
  119.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  120.                         {
  121.                             if( r < rows )                      // if can go DOWN in matrix M
  122.                                 r++;                            // go DOWN in matrix M
  123.                             else
  124.                                 end_of_table = 1;               // if can't go DOWN in matrix M, end
  125.  
  126.                             if( word[++i] == '\0' )             // if we reach the end of word,
  127.                                 end_of_word = 1;                // it is the end of word
  128.  
  129.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  130.                                 match = 0;                      // they don't match
  131.                         } // while( match && !end_of_word && !end_of_table )
  132.  
  133.                         if( match )                             // if all characters of word are match
  134.                         {
  135.                             counter++;                          // count that word
  136.                             printf("\n M[%d][%d] = %c \t found DOWN \n", row+1, column+1, M[row][column] );
  137.                         }
  138.                         break;
  139.  
  140.                     case LEFT :
  141.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  142.                         {
  143.                             if( c >= 0 )                        // if can go LEFT in matrix M
  144.                                 c--;                            // go LEFT in matrix M
  145.                             else
  146.                                 end_of_table = 1;               // if can't go LEFT in matrix M, end
  147.  
  148.                             if( word[++i] == '\0' )             // if we reach the end of word,
  149.                                 end_of_word = 1;                // it is the end of word
  150.  
  151.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  152.                                 match = 0;                      // they don't match
  153.                         } // while( match && !end_of_word && !end_of_table )
  154.  
  155.                         if( match )                             // if all characters of word are match
  156.                         {
  157.                             counter++;                          // count that word
  158.                             printf("\n M[%d][%d] = %c \t found LEFT \n", row+1, column+1, M[row][column] );
  159.                         }
  160.                         break;
  161.  
  162.                     case RIGHT :
  163.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  164.                         {
  165.                             if( c < rows )                      // if can go RIGHT in matrix M
  166.                                 c++;                            // go RIGHT in matrix M
  167.                             else
  168.                                 end_of_table = 1;               // if can't go RIGHT in matrix M, end
  169.  
  170.                             if( word[++i] == '\0' )             // if we reach the end of word,
  171.                                 end_of_word = 1;                // it is the end of word
  172.  
  173.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  174.                                 match = 0;                      // they don't match
  175.                         } // while( match && !end_of_word && !end_of_table )
  176.  
  177.                         if( match )                             // if all characters of word are match
  178.                         {
  179.                             counter++;                          // count that word
  180.                             printf("\n M[%d][%d] = %c \t found RIGHT \n", row+1, column+1, M[row][column] );
  181.                         }
  182.                         break;
  183.  
  184.                     case UP_LEFT :
  185.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  186.                         {
  187.                             if( r >= 0 && c >=0)                // if can go UP_LEFT in matrix M
  188.                             {
  189.                                 r--;                            // go UP in matrix M
  190.                                 c--;                            // go LEFT in matrix M
  191.                             }
  192.                             else
  193.                                 end_of_table = 1;               // if can't go UP_LEFT in matrix M, end
  194.  
  195.                             if( word[++i] == '\0' )             // if we reach the end of word,
  196.                                 end_of_word = 1;                // it is the end of word
  197.  
  198.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  199.                                 match = 0;                      // they don't match
  200.                         } // while( match && !end_of_word && !end_of_table )
  201.  
  202.                         if( match )                             // if all characters of word are match
  203.                         {
  204.                             counter++;                          // count that word
  205.                             printf("\n M[%d][%d] = %c \t found UP_LEFT \n", row+1, column+1, M[row][column] );
  206.                         }
  207.                         break;
  208.  
  209.                     case UP_RIGHT :
  210.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  211.                         {
  212.                             if( r >= 0 && c < columns )         // if can go UP_RIGHT in matrix M
  213.                             {
  214.                                 r--;                            // go UP in matrix M
  215.                                 c++;                            // go RIGHT in matrix M
  216.                             }
  217.                             else
  218.                                 end_of_table = 1;               // if can't go UP_RIGHT in matrix M, end
  219.  
  220.                             if( word[++i] == '\0' )             // if we reach the end of word,
  221.                                 end_of_word = 1;                // it is the end of word
  222.  
  223.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  224.                                 match = 0;                      // they don't match
  225.                         } // while( match && !end_of_word && !end_of_table )
  226.  
  227.                         if( match )                             // if all characters of word are match
  228.                         {
  229.                             counter++;                          // count that word
  230.                             printf("\n M[%d][%d] = %c \t found UP_RIGHT \n", row+1, column+1, M[row][column] );
  231.                         }
  232.                         break;
  233.  
  234.                     case DOWN_LEFT :
  235.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  236.                         {
  237.                             if( r < rows && c >= 0 )            // if can go DOWN_LEFT in matrix M
  238.                             {
  239.                                 r++;                            // go DOWN in matrix M
  240.                                 c--;                            // go LEFT in matrix M
  241.                             }
  242.                             else
  243.                                 end_of_table = 1;               // if can't go DOWN_LEFT in matrix M, end
  244.  
  245.                             if( word[++i] == '\0' )             // if we reach the end of word,
  246.                                 end_of_word = 1;                // it is the end of word
  247.  
  248.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  249.                                 match = 0;                      // they don't match
  250.                         } // while( match && !end_of_word && !end_of_table )
  251.  
  252.                         if( match )                             // if all characters of word are match
  253.                         {
  254.                             counter++;                          // count that word
  255.                             printf("\n M[%d][%d] = %c \t found DOWN_LEFT \n", row+1, column+1, M[row][column] );
  256.                         }
  257.                         break;
  258.  
  259.                     case DOWN_RIGHT :
  260.                         while( match && !end_of_word && !end_of_table ) // while three conditions
  261.                         {
  262.                             if( r < rows && c < columns )       // if can go DOWN_RIGHT in matrix M
  263.                             {
  264.                                 r++;                            // go DOWN in matrix M
  265.                                 c++;                            // go RIGHT in matrix M
  266.                             }
  267.                             else
  268.                                 end_of_table = 1;               // if can't go DOWN_RIGHT in matrix M, end
  269.  
  270.                             if( word[++i] == '\0' )             // if we reach the end of word,
  271.                                 end_of_word = 1;                // it is the end of word
  272.  
  273.                             if( M[r][c] != word[i] && !end_of_word )    // if characters don't match,
  274.                                 match = 0;                      // they don't match
  275.                         } // while( match && !end_of_word && !end_of_table )
  276.  
  277.                         if( match )                             // if all characters of word are match
  278.                         {
  279.                             counter++;                          // count that word
  280.                             printf("\n M[%d][%d] = %c \t found DOWN_RIGHT \n", row+1, column+1, M[row][column] );
  281.                         }
  282.                         break;
  283.  
  284.                     default :
  285.                         break;
  286.  
  287.                     } // switch( direction )
  288.  
  289.                 } // while( direction < 8 )
  290.  
  291.             } // if( M[row][column] == word[i] )
  292.  
  293.         } // for(column=0; column<columns; column++)
  294.  
  295.     } // for(row=0; row<rows; row++)
  296.  
  297.     return counter;
  298. } // number_off_occurrences( char word[], char M[][MAX_SIZE], int rows, int columns )
  299.  
  300.  
  301. // serves to test the program
  302. void input_test_matrix( char M[][MAX_SIZE], int *rows, int *columns, char word[] )
  303. {
  304.     *rows = 4;
  305.     *columns = 4;
  306.  
  307.     M[0][0] = 'O';
  308.     M[0][1] = 'O';
  309.     M[0][2] = 'O';
  310.     M[0][3] = 'O';
  311.  
  312.     M[1][0] = 'O';
  313.     M[1][1] = 'O';
  314.     M[1][2] = 'O';
  315.     M[1][3] = 'O';
  316.  
  317.     M[2][0] = 'O';
  318.     M[2][1] = 'O';
  319.     M[2][2] = 'W';
  320.     M[2][3] = 'O';
  321.  
  322.     M[3][0] = 'O';
  323.     M[3][1] = 'O';
  324.     M[3][2] = 'O';
  325.     M[3][3] = 'O';
  326.  
  327. //  M[0][0] = 'A';
  328. //  M[0][1] = 'B';
  329. //  M[0][2] = 'C';
  330. //  M[0][3] = 'D';
  331. //
  332. //  M[1][0] = 'E';
  333. //  M[1][1] = 'F';
  334. //  M[1][2] = 'G';
  335. //  M[1][3] = 'H';
  336. //
  337. //  M[2][0] = 'I';
  338. //  M[2][1] = 'J';
  339. //  M[2][2] = 'K';
  340. //  M[2][3] = 'L';
  341. //
  342. //  M[3][0] = 'M';
  343. //  M[3][1] = 'N';
  344. //  M[3][2] = 'O';
  345. //  M[3][3] = 'P';
  346.  
  347.     print_matrix("\n Matrix: \n\n", M, *rows, *columns );
  348.  
  349.     printf("\n Enter requested word: ");
  350.     scanf("%s", word);
  351. }
  352.  
  353.  
  354. // input from user, numbers of rows, columns and matrix elements
  355. void input_matrix( char M[][MAX_SIZE], int *rows, int *columns, char word[] )
  356. {
  357.     int r, c;
  358.  
  359.     printf("\n Enter number of rows of    matrix M [rows] [columns] ,  rows    = ");
  360.     scanf("%d", rows);
  361.  
  362.     printf("\n Enter number of columns of matrix M [%d] [columns] , \t columns = ", *rows );
  363.     scanf("%d", columns);
  364.  
  365.     for(r=0; r < (*rows); r++)
  366.         for(c=0; c < (*columns); c++)
  367.         {
  368.             printf("\n Enter M[%d][%d] = ", r, c );
  369.             scanf(" %c", &M[r][c] );
  370.         }
  371.  
  372.     print_matrix("\n Matrix: \n\n", M, *rows, *columns );
  373.  
  374.     printf("\n Enter requested word: ");
  375.     scanf("%s", word);
  376. }
  377.  
  378.  
  379. int main(void)
  380. {
  381.     int rows, columns, counter = 0;                 // sizes of matrix M[rows][columns]
  382.     char word[MAX_SIZE];                            // requested word
  383.     char M[MAX_SIZE][MAX_SIZE];                     // matrix M (a big one)
  384.  
  385.  
  386.     input_test_matrix( M, &rows, &columns, word );  // serves to test the program
  387.  
  388.     counter = number_off_occurrences( word, M, rows, columns );
  389.  
  390.     printf("\n There are %d words \"%s\" in the matrix M[%d][%d] \n", counter, word, rows, columns );
  391.  
  392.  
  393.     input_matrix( M, &rows, &columns, word );       // input from user
  394.  
  395.     counter = number_off_occurrences( word, M, rows, columns );
  396.  
  397.     printf("\n There are %d words \"%s\" in the matrix M[%d][%d] \n", counter, word, rows, columns );
  398.  
  399.  
  400.     return 0;
  401.  
  402. } // main()
  403.  
RAW Paste Data Copied