1995 BIO Round One

You should attempt both questions.
Time allowed: 4 hours total.

Question One must be coded on a computer and you should test it both with the given data and with some you devise yourself. Your program should give exactly the same wording and output format as given in the question.

Question Two should be answered on paper. You should write clearly and concisely, drawing diagrams where appropriate. Specific use of flow charts is not required. Pay attention to all questions asked and label your answers to correspond with them.

In both questions your attention is drawn to the marking scheme. You should have access to pens, pencils, a ruler, calculator and paper, and should write the computer program to solve question one on an IBM PC or compatible in Pascal, C or Qbasic. Your program should print your name and school (which should also be given in comments at the top) and you should write your name on every sheet for your solution of question two.


1. Encoder/Decoder for text strings

You are required to implement a program to encode and decode text 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 to 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 to 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 'ABCDEFGHIJKLMNOPQRSTUVWXYZ,. '

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 to 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 the same line must be and the input buffer must be cleared to the end of the line.

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 key, 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 coding 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 for Question 1

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.
ooanjP,gpxxltluxppqcc#
Decoded message is
I WANAHRED LONELY AS #

Press ENTER to continue...

(End of sample output)

Marking scheme for Question 1

                                             Mark
Required menu structure and exit message.     10
Correctly inputs and creates the key.
  If options 2 and 3 fail, marks may still
  be awarded if this can be shown, for
  example by an extra menu option.            10
Correctly reads in and filters messages to
  be coded.Output of what decoded message
  will look like is correct.                  10
Outputs correctly encoded messages.           15
Outputs correctly decoded messages.           15
All program output is correct (format
  included).  Only available if all
  requirements of question are fulfilled.     10

Total marks available for Question 1          70

2. Magic Squares

In this question you will be asked how, in outline, you would implement a program to find magic squares. A magic square is an n by n grid containing the integers 1 to n2, which fulfils this condition: each of the sums of the n numbers on any row or column must add up to 0.5n(n2 + 1). Based on this definition, an example magic square for n = 4 is

16	15	1	2
6	4	10	14
9	8	12	5
3	7	11	13

Questions

Marking scheme for Question 2

                                       Mark
Question 2.1 including explanation.      5
Question 2.2 - any suitable form.        5
Question 2.3 with good description of
  a valid technique.                     5
Question 2.4
  to within a few orders of magnitude
  and with justification.                5
Question 2.5                             5
Marks for clear handwriting and
  concise answers.                       5

Total marks available for Question 2     30

Total marks available BIO 1995 Round One 100

End of the British Informatics Olympiad Round One paper.


The British Informatics Olympiad