The second annual computer programming competition for South African universities, co-ordinated by Larry Tooke, Bobby Abraham and myself.
I can’t tell if these were the final set of questions, nor can I recall which ones I suggested. But there are some interesting ones …
Introduction
If you haven’t read the complete set of rules and instructions yet, please do so before attempting any of the following questions. You need to be aware of the submission and scoring procedure before commencing.
In particular, please note that ALL programs should read input from the standard input channel and output should go to the standard output channel. This makes it easy to either use keyboard and screen for your own testing, or to redirect I/O to files (which is what our automatic testing procedure does).
If you are using Turbo Pascal, DO NOT include the line “uses CRT” as this directs output directly to the screen rather than standard output.
Water Pouring
Background
There is a common type of logic puzzle in which containers of various sizes must be used to measure some specified quantity of water. For instance, suppose you have a three litre bucket and a five litre bucket and (for some reason known only to the inventor of the puzzle) require exactly one litre. How can you do it?
One solution would be as follows: fill the 3l bucket and then pour it into the 5l bucket. Fill the 3l bucket and use it to fill the 5l bucket, leaving 1l in the 3l bucket.
The Problem
Given n containers of size s1,s2,…sn (in litres), and an unlimited supply of water, we require exactly x litres in the largest container. Your program will need to print a list of water transfers, starting with all containers empty and finishing with the largest container holding the required amount.
A water transfer can only be one of three types:
- Fill a container from the tap
- Transfer water from container i to container j until either i is empty or j is full
- Empty a container down the drain
These types of task may have no solutions, but you may assume that we will not specify such unsolvable tasks. eg a task such as “use containers of size 3l and 6l to reach a final quantity of 2l” will not be asked. Any task which is solvable will in fact have multiple solutions, but you only have to find one solution.
The Input
Each line of the input will contain a comma-separated list of positive integers. The first of these is the amount of water required, and the rest of the list shows the sizes of the available containers. The containers will all have different capacities and they will be listed in increasing order of capacity.
There will be at most 10 containers.
The Output
For each task specified in the input file the output should contain a header line showing the task number, followed by a list of water transfers (one per line) which solve the task.
Water transfers must be indicated using the following notation:
-> i means fill container i from the tap
i -> j means transfer water from container i to container j until either i is empty or j is full
i -> means empty container i down the drain
Sample Input
1,3,5
18,7,11,18
Sample Output
Task 1
->3
3->5
->3
3->5
5->
3->5
Task 2
->18
Cross-number Puzzle
Background
The traditional concept of a crossword puzzle is to fit a set of words into a rectangular grid. The arrangement of words is chosen to be as difficult as possible and so people trying to solve the puzzle often have cross words with each other. But in this problem, no cross words are necessary: first because it is the computer rather than people which has to do all the hard work, and second because we will use numbers instead of words.
The Problem
Given a set of six three-digit numbers, find all possible ways that the numbers can be fitted into a 3×3 matrix. In order to avoid the complexity of rotations leading to multiple solutions, we will add one other constraint: the first three-digit number in the list must be placed on the top row of the matrix.
For instance the numbers 120, 319, 253, 132, 215 and 093 can only interlock in one way –
| 1 | 2 | 0 |
| 3 | 1 | 9 |
| 2 | 5 | 3 |
The Input
Each line of the input will contain a comma-separated list of six three-digit numbers. Each of these six numbers will be different from each other.
The Output
For each line of the input file, you should output the following –
- If there is no way to arrange the six numbers in a 3×3 matrix then output the message “There are no solutions”.
- If there is a unique arrangement of the six numbers, output the arrangement
- If there is more than one solution, output the number of solutions.
Sample input
120,319,253,132,215,093
424,351,153,431,255,413
111,222,333,444,555,666
Sample Output
120
319
253
There are 2 solutions
There are no solutions
Amicable Numbers
Background
The Ancient Greek Pythagoreans defined a perfect number to be one whose factors add up to the same number. eg The factors of 6 are 3,2 and 1 (1 is always included), and 1+2+3 also equals 6. Similarly, they called a pair of distinct numbers amicable if the sum of factors of one equalled the other and vice versa.
eg 220 and 284 are amicable since the sum of the factors of 220 (1,2,4,5,10,11,20,22,44,55 and 110) is 284, and the sum of the factors of 284 (1,2,4,71 and 142) is 220.
The Problem
Find all amicable pairs between a given minimum and maximum.
The Input
Each line of the input will contain a comma-separated pair of positive integers. The first is the minimum and the second is the maximum.
The Output
For each line of the input file, output a line containing all pairs of amicable pairs greater than or equal to the minimum and less than or equal to the maximum. Each pair should be listed with the lowest number first and separated by a space, and the list of pairs should be in ascending order of the first number in each pair and separated by a comma.
Sample Input
200,1300
400,1000
Sample Output
220 284,1184 1210
There are no solutions
Simple Arithmetic
Background
There is a game played competitively in high school mathematics in which contestants are given four numbers from which they must make an equation whose answer is a fifth number. For instance, form an equation using the numbers 12,3,15 and 9 whose answer is 19. One possible answer would be ((3*12)/9)+15.
The Problem
Given four numbers n1,n2,n3,n4 and the required answer x, produce a list of ALL arithmetic expressions in which the numbers n1,n2,n3,n4 occur once each, and whose answer is x. Only the four arithmetic operators +,-,* and / are allowed, and these operators are to be evaluated in strict left to right sequence. eg the expression 12+3*9-15 gives the answer 120.
The division sign “/” represents integer division — ie remainders are ignored.
The Input
Each line of the input will contain a comma-separated list of five positive integers. The first four are the numbers to be manipulated (n1,n2,n3,n4) to give the fifth number (x) as the answer. The numbers n1,n2,n3 and n4 will not contain any repeated numbers.
The Output
For each line in the input, the ouput should contain a header line showing the task number, followed by all combinations of the numbers n1,n2,n3,n4 and the operators +,-,* and / such that the result of the expression is x. These expressions may be listed in any order.
If the required answer x can never be written as an arithmetic expression containing all of the required numbers n1,n2,n3 and n4, then your program should output the message “There are no solutions”.
Sample Input
12,3,9,15,120
1,2,3,4,50
Sample Output
Task 1
12+3*9-15
12*9+15-3
12*9-3+15
3+12*9-15
9*12+15-3
9*12-3+15
9*15-12-3
9*15-3-12
15*9-13-3
15*9-3-12
15-3*9+12
Task 2
There are no solutions
Chicken McNuggets
Background
At McDonalds’ restaurants you can purchase Chicken McNuggets in quantities of 6, 9 or 20. If you want to buy exactly 21 McNuggets you must buy two lots of 6 and one 9. If you want to buy 17, you’re out of luck.
The Problem
Given a list of basic quantities, your program must be able to decide which quantities are purchasable and which are not. For instance if the basic quantities are 6, 9 and 20 your program should be able to determine that 17 is not a purchasable quantity.
The Input
Each line of the input contains a comma-separated list of up to 10 positive integers. The first of these is the quantity of McNuggets which you wish to purchase and the rest are the basic quantities available.
The Output
For each line of input, the output must contain either “yes” or “no” indicating whether or not the required quantity can be purchased.
Sample Input
21,6,9,20
10,8,4
Sample Output
yes
no
Musical Style
Background
A series of musical manuscripts were recently discovered in the organist’s chair of the Cathedral of Le Mons, in a remote French speaking area of Mongolia. Authorities have disputed the age and origin of the pieces, and while some claim they are the work of Johan Sebastian Mozart, others are convinced that they constitute an early collection of sonata’s for bass guitar written Egg Head, the lead vocalist of popular heavy metal band “Chicken Liver Pate”.
Your University has been contracted to design a computer program which can compare musical styles. This program is to be used to analyse these recently discovered manuscripts in order to settle the question once and for all.
Some (Slightly Unorthodox) Music Theory
Musical notes are named in ascending order of pitch as follows:
a
a sharp (which is the same as b flat)
b (which is the same as c flat)
c (which is the same as b sharp)
c sharp (which is the same as d flat)
d
d sharp (which is the same as e flat)
e (which is the same as f flat)
f (which is the same as e sharp)
f sharp (which is the same as g flat)
g
g sharp (which is the same as a flat in the next higher octave)
This sequence forms an octave, which is repeated 5 times. Each octave is numbered from 0 up to 5, so that the next note after “g sharp in octave 1” is “a in octave 2” etc. Notes within an octave are each separated by a semi-tone. Notes which are neither sharp nor flat are said to be natural. Music may also contain rests, when no note is played.
The other defining characteristic of a note (or a rest) is its duration. This may be for a single beat, two beats, three beats, four beats, or half a beat.
Every piece of music is split into bars, and each bar contains the same number of beats. However, the number of beats in a bar may differ between musical pieces: eg some pieces have bars of three beats while other pieces have bars of four or even more beats. We never allow the situation where one note stretches over two bars, and we never allow one piece to have bars of mixed length.
If every note in a bar (including rests) has the same duration, we say the bar has an even rhythm.
If the sequence of notes in a bar becomes progressively higher (that is, after the first note is played, each subsequent note is higher than the one before), then the bar is said to be ascending. Conversely, if the sequence of notes in a bar becomes progressively lower, then the bar is said to be descending.
The Problem
The musical style of J.S.Mozart can be summarised as follows –
Mozart sometimes writes in four beats to the bar and other times in three beats to the bar. When writing in four beats to the bar, he had the strange practise that whenever he wrote a bar with even rythym, the following bar (if there is one) was always ascending. Mozart was opposed to sudden changes in pitch and so he would never have two consecutive notes separated by more than ten semi-tones (eg he may have a jump from a to g (in the same octave), but never from a to g sharp). If a sharpened or a flattened note is played, then throughout that bar the note will be played the same way (eg Mozart would never have a c sharp and a c natural in the same bar, though he could write a c sharp and a b sharp in the same bar).
In contrast, heavy metal music invariably has the following structure –
All songs have four beats to the bar. Bars with even rhythm are neither ascending nor descending. To give the typical chaotic effect, heavy metal music is always fast and one never finds a four-beat note except occassionally in the final bar. Sometimes a sequence of at least four descending half-beat notes at the end of a bar will lead into a three-beat note at the start of the next bar, but that is the only time a three-beat note is ever used. Whenever half-beat rests occur (except at the end of a bar), the previous note (ignoring any other rests) is never the same pitch as the following note (ignoring any other rests).
Write a program which will read in a musical sequence, and determine whether it was written by Mr Mozart or Mr Head. Given the incompleteness of our understanding of musical style, it is possible that one piece of music matches both of the above descriptions, in which case your program will not be able to make a definitive decision. It is also possible that the music being analysed fits neither of the above descriptions in which case your program will announce that the music must have been written by a third (unknown) composer.
The Input
Each piece of music will consist of at most 100 notes written on one or more lines. Notes will be separated by a comma. Pieces of music will be separated by an empty line. Each note is represented by four items: the pitch (a,b,c,d,e,f, or r if no note is to be played); a pitch modifier (f for flat, n for natural, or s for sharp); an octave number (between 0 and 5); and a duration (h for half, o for one, t for two, e for three, or f for fours).
Notice that a rest is represented by an “r” followed by two spaces, followed by a duration.
The Output
For each line in the input, the output should say either “Mozart” or “Head” or “Either” or “Neither”.
Sample Input
cn1t,an2h,an2h,an2o,bn2o,an2o,en1o,gn1o,an2o,gs1h,an2h,bn2o,gs1h,an2h,gs1t,an2e
en1h,en1h,en1h,en1h,fn1h,fn1h,en1h,en1h,en1h,fn1h,af2o,en2o,r o,r h,bn2h,an2h,gn1h,fn1h,en1h,dn1e,en1h,fn1h,gn1t,an2o,an2o,cn2h,bf2h,an2h,gn1h,an2t
cn1o,dn2t,dn2o,dn2t,cn2t,bn2h,an2h,gn1o,an2t
Sample Output
Mozart
Either
Neither
Windows
Background
Graphical User Interfaces (GUI) are designed to make using computers easier and more intuitive. GUIs have become more popular with the advent of fast computer hardware and cheap colour displays that can support them. The aim of this problem is to implement a small part of the windows manager for a imaginary GUI.
Problem
Given a number of overlapping windows and mouse button presses and releases you are to determine the final position of the windows on a virtual screen.
Windows are defined by the co-ordinates of their top left and bottom right corners. The order in which the windows are specified indicates the order in which they overlap. This is know as the Z-order. The first window given is the ‘top’ window and overlaps any windows given after it. Even if two windows do not overlap one should be though of as being ‘above’ or ‘below’ the other. All window co-ordinates will be in the range 0 to 1000 and the origin is the top-left corner.
Given a series of mouse co-ordinates indicating presses and releases of a mouse button you must interpret these as follows:
Selection events
A press and release at the same co-ordinate indicate the selection of the window with the highest Z-order at that co-ordinate. A selected window must be re-ordered to become the first in the Z-order.
Sizing events
A press within an 11 by 11 pixel box centred on any corner of the window followed by a release at a different co-ordinate is a resizing event. If more then one window has a corner as specified then the sizing will be performed on the window first in the Z-order. Also note Sizing Events have a higher priority than Drag Events (described below).
Once a sizing event is detect the program places the selected window first in the Z-order and alters the selected corners co-ordinates so that the corner is in the same position relative to the cursor at the release point as it was at the press point.
When resizing a window by dragging a particular corner, the opposite corner always stays fixed and the window can never be made smaller than 20×20 pixels. If a resizing event attempt to make a window smaller than 20×20 then the window becomes a 20×20 window with corners in the same orientation as the original window.
Drag events
A press followed by a release at a different co-ordinate is a drag event if the press occurs on the selection bar of the window which is an area 20 pixels deep on the top of each window. Note that in the case of a drag the window must also be placed first in the Z-order.
Once a drag event is detected the selected window is placed first in the Z-order and the whole window is moved so that the window is in the same position relative to the cursor at the release point as it was at the press point. The window’s size does not change.
Windows must always be completely visible on the screen. If a drag event attempts to move any part of a window off the screen, then the window should be positioned against the edge of the screen.
Input
The input consists of a number of lines each containing four integers separated by spaces in the range -1000 to +1000 representing respectively the x cordinate of the top left corner, the y cordinate of the top left corner, the x cordinate of the bottom right co-ordinate and the y co-ordinate of the bottom left corner. The windows are given in Z-order. This section will end with the word ‘mouse’ on a single line to indicate the start of the mouse co-ordinates section. There will be no more than 100 windows.
The mouse section consists of a number of lines each containing four integers. The first two indicate the position at which the mouse button was pressed and the second two indicate the position at which the mouse button was released. This section ends with the word ‘end’. There will be no more than 500 mouse events.
Output
The output will be the window coordinates as given in the same form as the input definition. They must be in Z-order.
Sample Input
10 10 100 100
20 20 110 120
150 200 600 300
mouse
50 12 70 80
21 23 51 53
500 250 500 250
end
Example Output
150 200 600 300
50 50 110 120
30 78 120 168
Ant Antics
A robot ant has the mental power to execute an algorithm specified in Ant Code. This Ant code consists of nine different instructions. These instructions define the behaviour of the ant. You are required to write a program which will simulate the behaviour of the robot ant given a specific environment and ant-code program.
The nine ant-code instructions are as follows :
| step | Take one step forward |
| left | Turn left (ie 90 degrees anti-clockwise in a vertical plane) |
| right | Turn right (ie 90 degrees clockwise in a vertical plane) |
| jw label | Jump if wall in front. Start executing the instruction following the label. |
| jp label | Jump if poison in front. Start executing the instruction following the label. |
| jf label | Jump if food in front. Start executing the instruction following the label. |
| jmp label | Unconditional jump, goto the instruction following the label. |
| eat | Consume the food in the square in front of the ant. |
| halt | Stop executing the ant-code program. |
Labels occur on a line by themselves and always start will a “:”. Thus “:stop” is a valid label. Labels are never more than 10 characters long.
An Ant-code program will never have more than 1000 instructions.
The Input
The input to your program will consist of two parts (separated by one blank line): an ant-code program, followed by a picture of the environment.
You may assume that all ant programs are syntactically correct and the all labels used are defined. Each line of the ant program contains one ant-code instruction or a label.
The environment is given as a text grid. The following characters have special significance :
- “+” or “-” or “|” represent a wall.
- “@” represents the ant.
- “p” represents poison. (An ant eating this will die)
- “f” represents food. (An ant eating this will gain 10 energy points).
Any other characters represent a square in which nothing exists.
The Simulation
Your program must determine the final state of the environment after having simulated the execution the the ant-code program. The robot-ant starts with 10 energy points and looses one energy point each step it takes. Eating food increases the energy points by 10. Should the ant eat poison the it energy points are set to zero. Each time the ant attempts to walk into a wall it losses one energy point. The robot ant starts by facing north (ie towards the top of the page/screen).
The simulation stops when one of the following criteria is met:
- The halt instruction is executed.
- The ant eats poison.
- The ant’s energy level reaches zero.
- 300 instructions have been executed.
The Output
Once the simulation has stopped for any of the above reasons, your program should output the final state of the environment. On the line after the environment, print the reason for stopping the simulation: either “Halt”, “Poison”, “Dead” or “Instruction limit” respectively.
Sample Input
:start
step
jf :eat
jw :turn
jp :avoid
jmp :start
:turn
right
eat
jmp :start
:eat
eat
jmp :start
halt
:avoid
left
jmp :start
+-------------------------+
| f f f |
| @ +---------+
| f p |
+-------+ p |
| |
| fp |
+-------+
Sample Output
+-------------------------+
| @ +---------+
| f p |
+-------+ p |
| |
| fp |
+-------+
???
Darwin’s world
Background
Genetic algorithms are becoming a popular alternative to convential search techniques of problem solving. This question requires the simulation of evolution, but not using genetic algorithms!
The Problem
A population of organisms may be mutated by certain genetic rules. In this problem each organism is defined by a list of up to 9 features. The genetic rules are defined as production rules with a pattern matching part (the left-hand side) and an action part (the right-hand side).
The patterns can be either conjuctions or disjunctions of features which must be matched against the current population. eg the pattern “and f1 f2” will match against all organisms which have both feature f1 and feature f2.
The actions are separated from the pattern-matching part by an arrow “->”. There are three possible actions:
- ADD – A feature is to be added to all matching organisms
- DELETE – A feature is to be removed from all matching organisms
- KILL – The organism dies.
Reproduction from one generation to the next happens as follows. Each genetic rule is applied to every organism in the existing population. Rules are applied in the order they are listed in the input file. When an ADD or DELETE action is performed on an organaism, that organism has a mutated offspring which becomes part of the next generation. After all rules have been applied to the population, any organism which has not been mutated or KILLed lives on into to the next generation.
The next generation then becomes the current generation and the process is repeated until either the 300th generation is reached or none of the rules apply to any of the remaining organisms.
The Input
The input to your program consists of two parts: a list of at most 50 organisms in the starting population followed by a list of at most 20 genetic rules which determine how organisms in that population mutate and reproduce. A blank line will separate the population from the rules.
Features always start with the letter “f” which is followed by a single digit number. Thus there will never be more than 9 features. Features will always be given in numerical order (ie f7 must come before f8).
Those rules with KILL actions will always be listed after those with ADD and DELETE actions.
The Output
Once the simulation is complete, your program should output a complete list of all organisms in the final generation. Organisms may be listed in any order but their features must be in numerically ascending order.
Sample Input
f1 f2 f3 f4
f1 f5 f6 f8
f3 f8 f2 f7 f1
f2 f7 f1
and f1 f2 -> add f9
or f3 f6 -> add f4
and f5 f7 -> delete f7
and f7 -> kill
Sample Output
f1 f2 f3 f4 f9
f1 f4 f6 f8