Question 2 of 9: Programming — Reverse a Line and the Saddle Point

Question 2: Programming — Reverse a Line and the Saddle Point (20 marks: (a) 10, (b) 10)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A line of text up to 256 characters, read repeatedly until an empty line. (b) An $n\times n$ integer array with entries in $[1,99]$, stated to contain exactly one saddle point; the worked $6\times 6$ example above.

Find. (a) Each entered line printed in reverse character order. (b) The value and (row, column) location of the array's saddle point.

Approach. (a) Read each line into a fixed char array with fgets, strip the trailing newline, then print it back index-by-index from the last character to the first. (b) For every row find its minimum and remember which column it sits in; a row's minimum is a saddle point exactly when it is also the largest value anywhere in that column, so check each row-minimum against a linear scan of its own column.

(a) Reverse each line (10 marks)

1. Read, strip the newline, print backwards.

   #include <stdio.h>
   #include <string.h>
   
   #define MAXLEN 257   /* 256 chars + '\0' */
   
   int main(void)
   {
       char line[MAXLEN];
       int len, i;
   
       printf("enter a line of text: ");
       while (fgets(line, MAXLEN, stdin) != NULL) {
           len = (int) strlen(line);
           if (len > 0 && line[len - 1] == '\n') line[--len] = '\0';
           if (len == 0) break;                 /* empty line -> stop */
   
           printf("the reversed line is: ");
           for (i = len - 1; i >= 0; i--)
               putchar(line[i]);
           putchar('\n');
           printf("enter a line of text: ");
       }
       return 0;
   }

2. Trace the paper's own examples. Reversing is a pure index-order flip, so each character stays the same, only its position mirrors: Computer programming is fun. $\to$ .nuf si gnimmargorp retupmoC; CN Tower $\to$ rewoT NC; hello $\to$ olleh — all three match the sample session exactly.

(b) Find the saddle point (10 marks)

1. Compute each row's minimum, then test it against its column. $$\text{saddle}(r,c) \iff A(r,c)=\min_{j} A(r,j) \ \text{ and } \ A(r,c)=\max_{i} A(i,c)$$ The row-minimum step is $O(n)$ per row ($O(n^2)$ total); the column check for a candidate is another $O(n)$, so the whole search is $O(n^2)$ — no faster algorithm is needed for an exam-sized array.

   #include <stdio.h>
   
   #define MAXN 20
   
   void find_saddle(int a[MAXN][MAXN], int n)
   {
       int r, c, j, i, min_val, min_col, is_col_max;
   
       for (r = 0; r < n; r++) {
           min_val = a[r][0];
           min_col = 0;
           for (j = 1; j < n; j++)
               if (a[r][j] < min_val) { min_val = a[r][j]; min_col = j; }
   
           is_col_max = 1;
           for (i = 0; i < n; i++)
               if (a[i][min_col] > min_val) { is_col_max = 0; break; }
   
           if (is_col_max) {
               printf("Saddle point: value=%d at row=%d, col=%d\n",
                      min_val, r + 1, min_col + 1);   /* 1-indexed, as in the paper */
               return;
           }
       }
       printf("No saddle point found.\n");
   }

2. Trace it on the paper's own $6\times6$ array. Row 3 (1-indexed) is $8,9,4,5,6,8$, whose minimum is $4$ at column 3. Column 3's entries across all six rows are $1,2,4,3,1,2$, whose maximum is $4$ — the same value, at the same row. Row 1 and row 2's own minima ($1$ at column 3, and $1$ at columns 1 and 6) both fail the column-max test first, so row 3 is the first and only row where both conditions hold. $$\boxed{\text{saddle point } A(3,3)=4}$$