Along with Bobby Abraham and Larry Tooke at the computing department at the University of Natal, Pietermaritzburg, I organised the first South Africa university computer programming competition.
Here are the questions I suggested …
Large Multiplication
Normally, an integer is represented by a two byte binary number. Some languages allow larger integers, but even if some system allocated four bytes to each integer, numbers with more than 12 digits could still not be handled.
You must write a program which can accept integers up to 150 digits long and which can multiple such integers together. Note that although the multiplicands will contain at most 150 digits, your calculations may require up to 300 digits.
Input
The input file will contain two long integers on separate lines, e.g. —
1234567890987654321
9876500000
Output
Your program should print to a file the result of multiplying the two inputs together, e.g. —
12193209775339567901356500000
A “Typical” Sentence
Given a file of text, build a list of words used in that file. For each word, build another list which records the frequencies of all the words which immediately follow that word.
For instance, if the input file contained simply “The cat sat on the mat which was on the floor”, then your program must record each of the eight unique words (the, cat, sat, on, mat, which, was, and floor). Furthermore, your program must record that “on” is followed by “the” twice; that “the” is followed by “cat” once, “mat” once and “floor” once; etc.
Case should be ignored — so that “The” and “the” are classed as the same word. Any full-stops should be interpreted as part of the preceding word — so that “floor” and “floor.” are classed as different words. Any other punctuation should be ignored.
You may assume that there will be no more than 150 unique words in the input file.
Once the input file has been parsed in this way, your program should use the word pair frequencies to generate what we might call “the most typical sentence.” That is, given a starting word, WORD1, your program should display a sentence of the form WORD1 WORD2 WORD3 WORD4 … WORDn where successive words are related as follows –
i) WORDi+1 is the word in the input file which most frequently follows WORDi (if more than one word has the same frequency, then choose the one which comes first alphabetically); and
ii) WORDn is the first word in the sequence which ends with a full-stop.
It is possible that the sentence generated in this way becomes infinite, and so to avoid this we introduce one further restriction: no word should appear more than once in the generated sentence. Suppose WORDi is most frequently followed by WORDj, but that WORDj has already been used in the generated sentence. In such cases, rather than use WORDj a second time, use the next best choice (that is, either the word which follows WORDi with the same frequency as WORDj but comes alphabetically later, or if there is no such word, then the word which follows WORDi with the next highest frequency).
Given this restriction, there is actually two ways that sentence generation might terminate: a standard termination when a word is printed which ends in a full-stop; and a non-standard termination when no next word can be chosen because all possible words have already been used.
Input
The first line of the input file will contain WORD1. Following that will be some story or essay up to 1,000 words in length. No word will be longer than 20 characters, e.g. —
this
Nobody liked the frog called Martin. Nobody liked the way he looked and nobody liked the way he smelt.
One day Martin the frog went for a walk. To walk was one thing that Martin really liked. He liked it more than swimming. He liked it more than jumping and he even liked to walk more than catching the flies that went across his path. On this particular day Martin felt good. It was a bright day, a day full of hope, of joy and of happiness.
But, he could never have guessed that before the day was over his walk was to be disrupted by his worst fear.
Output
Your output file should contain the “typical sentence,” starting with WORD1 as defined in the input file.
With the example above the typical sentence would be “this particular day martin felt good.” As another example, if WORD1 had been “he”, then your program should generate the sentence “he liked the frog called martin.”
Explosion
Explosion is a two person game played something like noughts-and-crosses: the board is a 3×3 grid; the players take turns to place markers on the board; one player is X and the other is O. But the rules of play are quite different from noughts-and-crosses.
On each turn, a player may place his/her next marker in an empty square, and then that square is said to be “owned” by that player. Alternatively, a player may place his/her next marker in a square which is already owned by him/her. That is, one square may contain more than one marker, but all markers in a square will be of the same sort (either all X’s or all O’s). The object of the game is to gain ownership of every square in the grid.
Each square on the grid has a maximum capacity and once the number of markers in a square exceeds that capacity, the square explodes. A square’s capacity is determined by the number of (non-diagonal) neighbours to that square, as shown below –
2 3 2
3 4 3
2 3 2
When a square explodes, its contents spill into each of its neighbours. For instance, if the top-left square ever contains more than two markers, the explosion will send one marker into the top-centre square and one marker into the centre-left square. (The remaining marker (or markers in rare cases) stays in the top-left square.)
If a square explodes into a square owned by the other player, then that square is conquered and all the markers are converted into the conqueror’s mark. This may mean that the conquered square now exceeds its capacity and in such cases it immediately explodes as well. Thus, a player may place one marker in a square and cause a succession of explosions. A player’s turn ends when all resulting explosions have been processed.
Your program should act as referee and record-keeper. Your program should not play the game, but allow two external players to makes successive turns until either an illegal move is made (eg X tries to put a mark in a square owned by O) or one of the players has won.
When a series of explosions leads to all nine squares in the grid being owned by one player, then that player is the winner and the game ends. At the end of a game there are rare occasions in which explosions happen in a repeating cycle and hence your program may loop forever. Hence it is crucial that your program terminates as soon as someone has won, even if more squares are ready to explode.
Input
Each line in the input file represents the moves for one game. Each game is composed of a series of moves alternating between X and O (X always goes first). Each move will be the identifier of a square in which the player has chosen to place his/her next marker.
Square identifiers are as follows –
A B C
D E F
G H I
You may assume that there will be no invalid identifiers in a game description (ie only the letters A..I will be used). After the last game the file will contain a line with the single letter Z.
eg
ABACDCDGDGDCABIFIDIGFD
EFEIIBCBCFGADEFCBC
ABACDCDGDGDCABIFIDI
ABACDCDGDGDCABIFIDIGFDEFABC
Z
Output
The output file should contain the result of each game in the input file. For each game you should indicate which player won and display the contents of the grid immediately prior to the winning move. If the input file contains an illegal move, then an error message should be written to the output file.
eg (corresponding to the example input file above)
Game #1 – O won after 22 moves.
Game #2 – Move 5 (player X) is illegal.
Game #3 – After 19 moves, no-one has won.
Game #4 – O won after 22 moves.