Question 8 of 9: File I/O — Replicating and Interleaving a Sound Stream

Question 8: File I/O — Replicating and Interleaving a Sound Stream (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 six-value example stream, 17 15 91 68 52 84, and the coded stream it must produce, 17 15 17 91 15 17 68 91 15 52 68 91 84 52 68 84 52 84; a replication factor of three; an input of unknown length read from a file; and an explicit instruction to be as efficient in time and space as possible.

Find. The rule that generates the printed coded sequence, and a program implementing it that reads and writes files without knowing the sequence length in advance.

Approach. Recover the interleaving rule by indexing the given output against the input, recognise it as a sliding window of the three most recent values, and implement it with a three-element ring buffer plus a short flush after end of file.

1. Recover the rule from the example, rather than guessing it. Label the inputs $v_{0}\dots v_{5}$ and rewrite the printed coded sequence as source indices: $$0,\;1,0,\;2,1,0,\;3,2,1,\;4,3,2,\;5,4,3,\;5,4,\;5$$ The structure is now unmistakable. The output is a concatenation of groups; the group at step $k$ lists $v_{k},\,v_{k-1},\,v_{k-2}$, and any index outside $0 \le i < n$ is simply skipped. $$\boxed{\text{group } k = \big(v_{k},\,v_{k-1},\,v_{k-2}\big), \quad k = 0,1,\dots,n+1, \text{ in-range indices only}}$$
2. Check the rule reproduces the printed output and the counts. The groups run 1, 2, 3, 3, 3, 3, 2, 1 in size — ramping up while the window fills and down while it drains — for a total of $$1+2+3+3+3+3+2+1 = 18 = 3 \times 6$$ so every value is written exactly three times, as replication demands. Applying the rule to 17 15 91 68 52 84 regenerates the question's coded sequence character for character.
3. Confirm the rule achieves what interleaving is for. The three copies of a value are never adjacent: in the coded stream, 91 sits at positions 3, 7 and 11 and 68 at 6, 10 and 14 — four slots apart — while values near the two ends are still at least two apart. A localised scratch that destroys three consecutive stored numbers can therefore take at most one copy of any value, which is precisely the protection the plain triplicated form fails to give.
4. Choose the data structure the rule implies. Group $k$ needs only $v_{k}$, $v_{k-1}$ and $v_{k-2}$, so at no point are more than three values required. A three-element array indexed by $\texttt{cnt} \bmod 3$ — a ring buffer — holds exactly those, overwriting each value only once it can never be needed again. Space is therefore $O(1)$, independent of the sequence length, which answers the question's demand for space efficiency and its warning that the length is unknown until end of file.
5. Handle the tail. When the input ends, the window still holds the last values and two shorter groups remain to be emitted — the $k = n$ and $k = n+1$ groups, whose leading indices have run past the data. The guard idx < cnt drops those, and cnt - idx <= COPIES keeps the emission to values still resident in the buffer.

   #include <stdio.h>
   
   #define COPIES 3
   
   int main(void)
   {
       char inName[FILENAME_MAX], outName[FILENAME_MAX];
       FILE *in, *out;
       int buf[COPIES];        /* the ONLY storage: three values, whatever n is */
       long cnt = 0;           /* how many values have been read so far */
       long k, idx;
       int v, j;
   
       if (scanf("%s %s", inName, outName) != 2) {
           fprintf(stderr, "expected an input and an output file name\n");
           return 2;
       }
       in  = fopen(inName,  "r");
       out = fopen(outName, "w");
       if (in == NULL || out == NULL) {
           perror("fopen");
           if (in)  fclose(in);
           if (out) fclose(out);
           return 2;
       }
   
       /* One value at a time. After reading v_k, emit the diagonal that ends at
          it: v_k, v_(k-1), v_(k-2), skipping indices that do not exist yet. */
       while (fscanf(in, "%d", &v) == 1) {
           buf[cnt % COPIES] = v;
           cnt++;
           for (j = 0; j < COPIES; j++) {
               idx = cnt - 1 - j;
               if (idx >= 0)
                   fprintf(out, "%d ", (int)buf[idx % COPIES]);
           }
       }
   
       /* Flush: two further diagonals whose leading index has run past the end of
          the data. The (cnt - idx <= COPIES) guard keeps us to values that are
          still resident in the ring buffer. */
       for (k = cnt; k <= cnt + COPIES - 2; k++)
           for (j = 0; j < COPIES; j++) {
               idx = k - j;
               if (idx >= 0 && idx < cnt && cnt - idx <= COPIES)
                   fprintf(out, "%d ", (int)buf[idx % COPIES]);
           }
   
       fprintf(out, "\n");
       fclose(in);
       fclose(out);
       return 0;
   }

6. Confirm the cost. Each input value is read once and written three times, so the program runs in $\Theta(n)$ time — optimal, since the output alone has length $3n$ — using three integers of working storage regardless of $n$.