Question 5 of 9: File I/O — Run-Length Encoding

Question 5: File I/O — Run-Length Encoding (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. A file to be scanned one character at a time, encoded with the marker \ followed by a decimal run-length count and the repeated character.

Find. A single-pass encoder that only replaces a run when doing so does not increase (and usually decreases) the output length.

Approach. Read one character at a time (as required), counting how many consecutive characters equal the current one; the encoded form of a run of length $r$ is always exactly 3 output characters (\, the count, the character), so encode only when $r \ge 3$ and otherwise emit the run's characters literally.

1. Derive the break-even run length from the example. A run of $a$'s of length 5 encodes to 3 characters (\5a) — a net saving. A run of $d$'s of length 3 also encodes to 3 characters (\3d) — the question calls this "no effect," confirming the break-even point is exactly $r=3$: below it (runs of 1 or 2, like bb, e, f, g) the 3-character encoding would be longer than the run itself, so those runs are left untouched. $$\boxed{\text{encode a run iff its length } r \ge 3}$$
2. Write the program. Reading "one character at a time" is honoured literally by buffering only the current run's character and count (constant extra space, as the question asks for), never the whole file.

   #include <stdio.h>
   
   int main(void)
   {
       FILE *in, *out;
       int c, run_char, run_len;
   
       in = fopen("input.txt", "r");
       out = fopen("compressed.txt", "w");
   
       run_char = fgetc(in);
       if (run_char == EOF) { fclose(in); fclose(out); return 0; }
       run_len = 1;
   
       for (;;) {
           c = fgetc(in);
           if (c == run_char) {
               run_len++;
               continue;
           }
           /* run of run_char (length run_len) has ended: flush it */
           if (run_len >= 3) {
               fprintf(out, "\\%d%c", run_len, run_char);
           } else {
               int i;
               for (i = 0; i < run_len; i++) fputc(run_char, out);
           }
           if (c == EOF) break;
           run_char = c;
           run_len = 1;
       }
       fclose(in);
       fclose(out);
       return 0;
   }

3. Confirm against the full worked example. Feeding aaaaabbccccdddefg through the run-detector produces runs $a{:}5,\ b{:}2,\ c{:}4,\ d{:}3,\ e{:}1,\ f{:}1,\ g{:}1$; applying the $r\ge3$ rule to each in turn gives \5a, bb, \4c, \3d, e, f, g, which concatenates to exactly the paper's stated output. $$\boxed{\texttt{aaaaabbccccdddefg} \to \texttt{\textbackslash5abb\textbackslash4c\textbackslash3defg}}$$