program Codes;
{ Borland Pascal 7.

  The Encoding problem from Round One of the
  1995 British Informatics Olympiad.

  See the end of this file for copyright notice and disclaimer. }

{-------------------- The Problem ------------------------} {

You are required to implement a coder/decoder using a
string-based coding method as described below.  Your program
should have a simple menu-based structure.  Its main menu is

  1) Enter an encoding "key" string.
  2) Encode a section of text using the current key.
  3) Decode a section of text using the current key.
  4) Exit the program.

  Choice?

When Option 1 is selected, the program should read in a one-line
string from the keyboard.  This should be converted to upper case,
all characters other than A..Z, comma, full stop and space should
be deleted, and the string adapted to be used as a code key as
follows.

The key must contain all the characters A..Z, comma, full stop and
space exactly once.  If a character occurs more than once, the
second, third etc. occurrences should be deleted.  If a character
does not occur in the string, it should be added to the end in the
order given above - so a blank input string would simply give the
code string 'ABCD--YZ,. '

For example, the input string 'I wandered lonely as a cloud' gives
the code key 'I WANDERLOYSCUBFGHJKMPQTVXZ,.'

When Option 2 is chosen, the program should read in a text message
from the keyboard; this may not be more than 250 characters long
and your program should check for this limit.  Note that Pascal will
not let you enter more than 127 characters per line.  Characters
other than A..Z, comma, full stop and space should be removed, and
the input should finish when a # character is encountered in the
text.  Line breaks, except when immediately preceded by a \
character (see below), should be converted into spaces.  No text or
spaces before the # should be deleted, but all text after it on a
line must be.

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).  This means that
one error in copying the encoded message will result in two
character errors in the decoded message, but this is acceptable.

For example, with the above code, the message 'I WANDER' would be
encoded as follows.  p starts with a value of 1, pointing to the
I in the key.  The value of the first character in the message
(also I), 9, is added to give 10; the 10th key character is O.
Space has a value of 29 - and therefore, when rolled round, p
is again 10 and the first two output characters are OO.  W has
a value of 23, so the 4th character in the code is selected next:
A.  And so on, to give the encoded form 'OOANJQ,G'

The encoded message is output in this way.  It is printed as lines
of maximum length 50 characters, and if it must be split after the
50th character on a line, a \ should be printed to indicate that
the line end should be ignored.  At the end of the text, a #
should be printed.

You should also output the original message, after transformation
to upper case etc, in the same format, to allow the user to
see what the message will look like when decoded.

Option 3 requires you to reverse this process, using the
same input and output methods with the exception of printing
the encoded text again.  The same key should be used.

When option 4 is selected your program should terminate.
After the other menu options have been executed, you might like to
ask the user to press enter before returning to the main menu.


Sample Output
=============

Choose a menu option:

1) Enter an encoding "key" string.
2) Encode a section of text using the current key.
3) Decode a section of text using the current key.
4) Exit the program.

Choice? 1
Enter a code key:
I wandered lonely as a cloud

Press <enter> to continue...

Choose a menu option:

1) Enter an encoding "key" string.
2) Encode a section of text using the current key.
3) Decode a section of text using the current key.
4) Exit the program.

Choice? 2
Encode a message using the current key.
Enter Message (250 characters max) with # to finish.
I wandered lonely as a cloud
that floats on high o'er dale and hill
when all at once I saw a crowd,
a flock of wand'ring daffodils.#
Message is
I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH O\
ER DALE AND HILL WHEN ALL AT ONCE I SAW A CROWD, A\
 FLOCK OF WANDRING DAFFODILS.#
Coded message is
OOANJQ,GPXXLTLUXPPQCCUUG.BEYY OY  RKDEZGGWGGVNSKKD\
Y..ANGPPQRSSK.STTHX FFG.SSCAAJAESSMMYSDDEEO,URSOOY\
YG.BH..BMMBFINQWGTT,.DSZ YQCS#

Press <enter> to continue...

Choose a menu option:

1) Enter an encoding "key" string.
2) Encode a section of text using the current key.
3) Decode a section of text using the current key.
4) Exit the program.

Choice? 3
Decode a message using the current key.
Enter Message (250 characters max) with # to finish.
OOANJQ,GPXXLTLUXPPQCCUUG.BEYY OY  RKDEZGGWGGVNSKKD\
Y..ANGPPQRSSK.STTHX FFG.SSCAAJAESSMMYSDDEEO,URSOOY\
YG.BH..BMMBFINQWGTT,.DSZ YQCS#
Decoded message is
I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH O\
ER DALE AND HILL WHEN ALL AT ONCE I SAW A CROWD, A\
 FLOCK OF WANDRING DAFFODILS.#

Press <enter> to continue...

Choose a menu option:

1) Enter an encoding "key" string.
2) Encode a section of text using the current key.
3) Decode a section of text using the current key.
4) Exit the program.

Choice? 3
Decode a message using the current key.
Enter Message (250 characters max) with # to finish.
ooanjK,gpxxltluxppqcc#
Decoded message is
I WANAHRED LONELY AS #

Press <enter> to continue...

(End of sample output)

}
{---------------------------------------------------------}
{                     The Solution                        }
{---------------------------------------------------------}

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

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]);
    if Key[i] in ValidChars then
      i := i + 1
    else
      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;
    for j := 1 to i - 1 do
      if Key[j] = Key[i] then Found := True;
    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 }
  for i := 1 to 29 do
    if Pos(BaseKey[i], Key) = 0 then
      Key := Key + BaseKey[i];
end;

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;

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;

procedure Encode;
var
  IMsg, OMsg: String;
  i, p: Integer;
begin
  WriteLn('Encode a message using the current key.');
  IMsg := ReadMsg;
  WriteLn('Message is');
  OutMsg(IMsg);
  WriteLn('Coded message is');

  { ** the encoding algorithm ** }
  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);
end;

procedure Decode;
var
  IMsg, OMsg: String;
  i, p, nextp: Integer;
begin
  WriteLn('Decode a message using the current key.');
  IMsg := ReadMsg;
  WriteLn('Decoded message is');
  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);
end;

procedure Menu;
var o: Integer;
begin
  repeat
    WriteLn('Choose a menu option:');
    WriteLn;
    WriteLn('1) Enter an encoding "key" string.');
    WriteLn('2) Encode a section of text using the current key.');
    WriteLn('3) Decode a section of text using the current key.');
    WriteLn('4) Exit the program.');
    WriteLn;
    Write('Choice? ');
    ReadLn(o);
    case o of
      1: GetKey;
      2: Encode;
      3: Decode;
      4: WriteLn('Exiting...');
    else
      WriteLn(o, ' is not a valid menu option.');
    end;
    WriteLn;
    if o <> 4 then
    begin
      Write('Press <enter> to continue...');
      ReadLn;
    end;
    WriteLn;
  until o = 4;
end;

begin
  WriteLn;
  WriteLn('*******************************************************');
  WriteLn('*                                                     *');
  WriteLn('*  British Informatics Olympiad 1995                  *');
  WriteLn('*  =================================                  *');
  WriteLn('*                                                     *');
  WriteLn('*  Coding/Decoding problem   -   (C) Antony Rix 1995  *');
  WriteLn('*  Question statement and sample solution in Pascal.  *');
  WriteLn('*                                                     *');
  WriteLn('*******************************************************');
  WriteLn;
  Menu;
end.
{ END OF BIO 1995 ROUND ONE QUESTION ONE SOLUTION }
{ Program copyright (c) 1997 The British Informatics Olympiad (BIO).

  This program may be freely copied by persons or organisations
  involved in the British Informatics Olympiad or the International
  Olympiad in Informatics, on condition that no changes are made and
  this notice is not altered. Distribution for profit is forbidden
  unless permission is first obtained in writing from the BIO.

  This program is for educational purposes only and comes with no
  warranty, implied or otherwise, as to its fitness for any purpose.

  Author:   Antony Rix
  Internet: http://www.christs.cam.ac.uk/bio/
  E-mail:   a.rix@lineone.net
  S-mail:   The British Informatics Olympiad
            Christ's College
            Cambridge CB2 3BU
            United Kingdom
}