BIO 1995 Round One solution documentation

This document describes the solution of Round One Question One. See the marks scheme for an example solution to Question Two.

• Question Statement
• Marking Instructions
• codes.pas
  The solution to Question One
• magicsq.pas
  A simple recursive solution to Question Two.

Solution to Question One
Text encoder/decoder

This question was chosen to have a fairly easy start (writing the user interface) but to get rapidly very difficult, in order to distinguish between the top entrants.

Its main aims were to test:

• Basic programming skills
• String manipulation
• Ability to read and understand a difficult question
• Ability to work out a simple decoding algorithm.

Basic programming

The writing of a main menu was the most easily accessible part of the question. This is a fairly simple exercise in structured programming, and you are referred to the solution program for an example of how to do this.

Reading in the key

Although it was hoped that this would be easy, a number of students found difficulty either in understanding the rather concise definition given in the question or in implementing it in terms of string operations.

What was required was to read a code key as one line from the keyboard, then filter it to remove characters other than letters and the allowed punctuation, and multiple occurrences of each letter. It then had to be padded so that every character occured exactly once.

This is relatively straightforward to code, as long as you proceed carefully. Firstly, we will define two constants which define the characters to be used in the key.

const
  ValidChars = ['A'..'Z', ',', '.', ' ']; { uses Set notation }
  BaseKey : String = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ,. ';

The ValidChars set allows us to make a quick test to see if a character is valid. Alternative methods would use if or case statements. BaseKey will be useful when we have to complete the key by adding on the unused characters. A global string variable Key is suitable for storing the key that we read in. We'll do the main work of reading in the key using a procedure GetKey. It can be read using a single command but must then be filtered.

procedure GetKey;
var
  i, j: Integer;
  Found: Boolean;
begin
  WriteLn('Enter a code key:');
  ReadLn(Key);
  { filter and convert to upper case }
  i := 1;
  while i <= Length(Key) do
  begin
    Key[i] := UpCase(Key[i]);

    { ensure that the key contains only valid characters }
    if Key[i] in ValidChars then
      i := i + 1
    else
      { remove unwanted character }
      Key := Copy(Key, 1, i - 1) + Copy(Key, i + 1, Length(Key) - i);
  end;

  { remove duplicate occurrences of symbols }
  i := 1;
  while i <= Length(Key) do
  begin
    Found := False;

    { test that this character doesn't occur before... }
    for j := 1 to i - 1 do
      if Key[j] = Key[i] then Found := True;

    { and if it does, delete it. }
    if Found then
      Key := Copy(Key, 1, i - 1) + Copy(Key, i + 1, Length(Key) - i)
    else
      i := i + 1;
  end;
  { add symbols not already present from the base key,
    which contains all characters in the specified order }
  for i := 1 to 29 do
    if Pos(BaseKey[i], Key) = 0 then
      Key := Key + BaseKey[i];
end;

Reading and outputting the text blocks

These requirements escaped the notice of many candidates, who should be encouraged to read the question carefully!

Reading a string to encode or decode allowed a fairly free format: carriage returns were to be converted to spaces except where preceded by a \ (when they should be ignored), and the text had to be filtered to upper case and the given character set.

A particular obstacle for Pascal programmers was the need to check for string length and unwanted characters as the addition went on, as it was possible to get very close to the Pascal string length limit of 255 characters. A good way around this is to read the data in character by character, using the standard functions Read and EOLn (End of Line).

Here is a function which does the trick:

function ReadMsg: String;
var
  c: Char;
  s: String;
  i: Integer;
begin
  WriteLn('Enter Message (250 characters max) with # to finish.');
  s := '';
  c := 'z';
  repeat
    if EoLn(Input) then
    begin
      if (c <> '\') then
        if Length(s) < 250 then s := s + ' ';
        { treats CR as a space unless preceded by a \ }
      ReadLn;
    end
    else
    begin
      Read(c);
      c := UpCase(c);
      if (c in ValidChars) and (Length(s) < 250) then
        s := s + c;
    end;
  until c = '#';
  ReadLn;
  ReadMsg := s;
end;

Outputting the text blocks, in 50-character lines, has a slightly different form:

procedure OutMsg(Msg: String);
{ writes the message in standard format to the screen }
begin
  while Length(Msg) > 50 do
  begin
    WriteLn(Copy(Msg, 1, 50) + '\');
    Msg := Copy(Msg, 51, Length(Msg) - 50);
  end;
  WriteLn(Msg + '#');
end;

The question marking allowed for solutions which finished with '#' on a line of its own if the previous line was 50 characters long and ended with a '\'.

Encoding

This algorithm was carefully described in the question:

Your program should then encode the text as follows. Start with a marker, p, pointing to the first character in the key. For each character in the message, p is moved right by the value of the character and the key symbol at p gives the next character in the encoded message.

The value of characters is given in order: A=1, Z=26, space=29. If p moves beyond the end if the key, 29 is subtracted from it (in other words, it rolls round to the start).

That is:

  p := 1;
  OMsg := '';
  i := 1;
  while i <= Length(IMsg) do
  begin
    { adds the 'index' of the letter to p with wraparound }
    p := p + Pos(IMsg[i], BaseKey);
    p := 1 + ((p - 1) mod 29);

    { append the key letter p to the coded message }
    OMsg := OMsg + Key[p];
    i := i + 1;
  end;
  OutMsg(OMsg);

Getting to this stage, simple as it appears, required some careful thought and consideration of the examples given.

Decoding text

The important jump to be made is that it is the difference of value (ie. position in the code) between successive code characters that gives the required character in the key. It also makes it a pretty poor code, as space (with a value of 29) appears as a double character in all encoded text; because it is also the most frequent symbol, part of the structure of the code is immediately obvious to an eavesdropper.

We can see this by looking at the following code:

  p := 1;
  OMsg := '';
  i := 1;
  while i <= Length(IMsg) do
  begin
    nextp := Pos(IMsg[i], Key);
    OMsg := OMsg + BaseKey[1 + ((nextp - p + 28) mod 29)];
    p := nextp;
    i := i + 1;
  end;
  OutMsg(OMsg);

So there it is! The full text of the solution to this question, coded in Borland Pascal 7.0, is given in codes.pas.