Question 7 of 9: File I/O — Testing Two Files for High Similarity

Question 7: File I/O — Testing Two Files for High Similarity (20 marks)

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. Two file names supplied on standard input; a definition of similarity that ignores blanks, tabs and newlines entirely; an explicit warning that the files may differ in size; and a requirement to answer false at the earliest possible moment.

Find. A program that prints true when the two files agree character for character after all white space is removed, and false otherwise, stopping at the first disagreement.

Approach. Read both files as streams of significant characters, skipping white space in a helper, and compare one significant character from each per iteration; any mismatch — including a character against end of file — ends the comparison immediately.

1. Restate the requirement as an equality of filtered streams. Two files are highly similar exactly when the sequences obtained by deleting every white-space character are equal: $$\boxed{\sigma(F_{1}) = \sigma(F_{2}), \quad \sigma(F) = \text{the characters of } F \text{ with white space removed}}$$ Framing it this way makes the size warning in the question a non-issue: file lengths are irrelevant, only the filtered sequences matter.
2. Do not read either file into memory. The obvious implementation — load both files, strip white space, compare the two strings — needs space proportional to the file sizes and cannot possibly stop early, because it has already read everything. Comparing as streams needs only two characters at a time, giving $O(1)$ space and, in the failing case, time proportional only to the matching prefix.
3. Put the white-space skipping in one helper. A function that returns the next non-white-space character, or EOF, is the whole of the filtering logic, and having exactly one of them guarantees both files are filtered identically. isspace from <ctype.h> already covers blanks, tabs and newlines, and also carriage returns and form feeds, which is the behaviour wanted when files come from different operating systems.
4. Let a single comparison handle unequal lengths. If one file runs out of significant characters before the other, the exhausted stream yields EOF while the other yields a real character; since EOF is guaranteed distinct from every character value, the test a != b catches that case with no extra code. The files agree only if both reach EOF on the same iteration.

   #include <stdio.h>
   #include <ctype.h>
   
   /* Return the next character of f that is not white space, or EOF. */
   static int next_significant(FILE *f)
   {
       int c;
       while ((c = fgetc(f)) != EOF && isspace(c))
           ;                       /* blanks, tabs and newlines are skipped */
       return c;
   }
   
   int main(void)
   {
       char name1[FILENAME_MAX], name2[FILENAME_MAX];
       FILE *f1, *f2;
       int similar = 1;
   
       /* The two file names are read from standard input. */
       if (scanf("%s %s", name1, name2) != 2) {
           fprintf(stderr, "expected two file names\n");
           return 2;
       }
   
       f1 = fopen(name1, "r");
       f2 = fopen(name2, "r");
       if (f1 == NULL || f2 == NULL) {
           perror("fopen");
           if (f1) fclose(f1);
           if (f2) fclose(f2);
           return 2;
       }
   
       for (;;) {
           int a = next_significant(f1);
           int b = next_significant(f2);
   
           if (a != b) {           /* first difference: stop at once */
               similar = 0;
               break;
           }
           if (a == EOF)           /* both streams ended together */
               break;
       }
   
       fclose(f1);
       fclose(f2);
   
       printf(similar ? "true\n" : "false\n");
       return similar ? 0 : 1;
   }

5. Confirm the early exit and the boundary cases. The loop breaks on the first differing pair, so a mismatch in the opening bytes of two enormous files costs two reads. Worked cases: a file containing “hello world” and one containing “hello” then a newline then “world” are highly similar, because both filter to helloworld; “hello world” against “hello world!” is not, and is rejected when one stream yields ! and the other EOF; and an empty file is highly similar to a file of nothing but white space, since both filter to the empty sequence. Overall cost is $O(n)$ time and $O(1)$ space.