![[BIO99 Logo]](../../../images/bio99-logo.gif){kind=logo}
the computing competition for schools and colleges.
We are proud to present BIO'99.
![[Data Connection logo]](../../../images/dc_logo3-s.gif){kind=logo}
| |
The British Informatics
Olympiad is the computing competition for schools and colleges. We are proud to present BIO'99. |
|
 |
The 1999 British Informatics
Olympiad - Round One
Worked solution to question 2
Scientists are studying an enigmatic Black Box by firing rays into it and observing the results. The rays are influenced by atoms within the box. Your task for this question is to model the rays' behaviour. The box is a 10 by 10 grid. Each square is either empty or contains a single atom. The 36 squares on the boundary of the box, i.e. the squares adjacent to an outside edge, never contain atoms.
Rays are fired into the box from a point on the grid's edge, and can travel horizontally and vertically. Rays continue travelling in straight lines, unless affected by atoms as follows:
These rules are given in order of precedence. Note that sample ray 1 is absorbed rather than deflected.
![[See sample run in question statement]](../../../images/bio99q2.gif)
2 (a). Write an interactive program to show how the rays are affected by a black box containing five atoms. The entry and exit points for rays will be given by a single letter followed by an integer. The letter, 'T', 'B', 'L' or 'R', indicates the side of the grid: top, bottom, left or right. The number indicates the position on the given side; for the top and bottom sides, 1 is on the left; for the left and right sides, 1 is at the bottom.
Your program should first read in 5 lines each containing two numbers; the x co-ordinate then the y co-ordinate for an atom. The bottom left corner is (1,1). You should then output the black box - using '.' for an empty square and 'A' for one containing an atom.
Until your program terminates you should repeatedly wait for input, and then:
If the ray was absorbed or reflected you should output the corresponding word; otherwise you should output the exit point.
Worked solution.
We begin this question with some preliminary definitions: the box (denoted "board" below), and the constants that will be used to represent the atoms and rays in the box. It is sufficient to use an integer to represent each element, and a two-dimensional array of integers is ideal for the board.
It will simplify the code we write if the board is made a little wider than required in the question (where columns and rows are numbered from 1 to 10). Counting from 0 to 11 ensures we can always make a move outside the "allowed" area of the box without having to check to prevent the program crashing. In Pascal we specifically set the required range of the array, but in Java array indices always count from 0.
| Pascal | Java |
const Blank = 0;
const Atom = 1;
const Ray = 2;
const Hit = 3;
var Board: array[0..11,0..11] of integer;
procedure init_board;
var i, j: integer;
begin
for i := 0 to 11 do for j := 0 to 11 do
Board[i][j] := Blank;
end;
|
static int Blank = 0;
static int Atom = 1;
static int Ray = 2;
static int Hit = 3;
int[][] Board = new int[12][12];
public void init_board() {
int i, j;
for( i = 0; i < 12; i++ )
for( j = 0; j < 12; j++ )
Board[i][j] = Blank;
}
|
The constants for a blank space, an atom and the ray are straightforward. Hit will be used to show a ray that has collided with an atom, to be displayed using the * character. After plotting the path of a ray we need to re-set the board to its original state, which can be done with the following procedure.
| Pascal | Java |
procedure reset_board;
var x, y: integer;
begin
for x := 0 to 11 do for y := 0 to 11 do
case Board[x][y] of
Blank: Board[x][y] := Blank;
Atom: Board[x][y] := Atom;
Ray: Board[x][y] := Blank;
Hit: Board[x][y] := Atom;
end;
end;
|
public void reset_board() {
int x, y;
for( x = 0; x < 12; x++ )
for( y = 0; y < 12; y++ )
switch (Board[x][y]) {
case 0: Board[x][y] = Blank; break;
case 1: Board[x][y] = Atom; break;
case 2: Board[x][y] = Blank; break;
case 3: Board[x][y] = Atom; break;
}
}
|
The procedure we will call to display the current state of the box is not much more complex.
| Pascal | Java |
procedure show_board;
var x, y: integer;
begin
for y := 10 downto 1 do begin
for x := 1 to 10 do
case Board[x][y] of
Blank: write( '.' );
Atom: write( 'A' );
Ray: write( '+' );
Hit: write( '*' );
end;
writeln;
end;
end;
|
public void show_board() {
int x, y;
for( y = 10; y >= 1; y-- ) {
for( x = 1; x <= 10; x++ )
switch (Board[x][y]) {
case 0: System.out.print( "." ); break;
case 1: System.out.print( "A" ); break;
case 2: System.out.print( "+" ); break;
case 3: System.out.print( "*" ); break;
}
System.out.print( "\n" );
}
}
|
In the Java switch statement that you will have seen above we have to use numbers (0..3) rather than referring to the values Blank etc. This is because Java requires these to be constants, but the values are just static integers. Fortunately Pascal is more elegant as we are able to use true constants.
We now turn to the real business of tracing the path of a ray that is shone into the box. Before we do this, it is worth noting a few usefil things.
The first step is to translate the instructions as to where to fire the ray into a useful format.
Pascal
procedure trace_ray( side: char; pos: integer );
var
direct: integer;
x, y, nx, ny: integer;
begin
{ Starting position and direction }
if side = 'B' then begin direct := 0; x := pos; y := 1; end
else if side = 'L' then begin direct := 1; y := pos; x := 1; end
else if side = 'T' then begin direct := 2; x := pos; y := 10; end
else if side = 'R' then begin direct := 3; y := pos; x := 10; end
else exit;
...
Java
public void trace_ray( String side, int pos ) {
int direct;
int x, y, nx, ny;
/* Starting position and direction */
if( side.equalsIgnoreCase("B") ) { direct = 0; x = pos; y = 1; }
else if( side.equalsIgnoreCase("L") ) { direct = 1; y = pos; x = 1; }
else if( side.equalsIgnoreCase("T") ) { direct = 2; x = pos; y = 10; }
else if( side.equalsIgnoreCase("R") ) { direct = 3; y = pos; x = 10; }
else return;
...
(Interesting note for programmers new to the Java language. Because strings are objects in Java, it is not appropriate to use tests such as side == "B". This is because side will always be a different object to "B", even though their values may be identical. Use the equals or equalsIgnoreCase methods to get around this problem. Similar problems can arise when checking or copying arrays, which are also objects.)
We can now start with the ray at position (x,y), and move it until it leaves the box, is absorbed, or reflects. This can be done with a simple while loop that executes if we are within the board. We break out of this in the case of absorbtion etc using the exit statement in Pascal (which leaves the loop) or the return statement in Java (which leaves this procedure).
The basic movement commands are therefore:
Pascal
while (x > 0) and (x < 11) and (y > 0) and (y < 11) do begin
Board[x][y] := Ray;
{ Find new position }
nx := x; ny := y;
case direct of
0: ny := y + 1;
1: nx := x + 1;
2: ny := y - 1;
3: nx := x - 1;
end;
...
check move
...
{ Update position }
x := nx;
y := ny;
end;
Java
while( (x > 0) && (x < 11) && (y > 0) && (y < 11) ) {
Board[x][y] = Ray;
/* Find new position */
nx = x; ny = y;
switch (direct) {
case 0: ny = y + 1; break;
case 1: nx = x + 1; break;
case 2: ny = y - 1; break;
case 3: nx = x - 1; break;
}
...
check move
...
/* Update position */
x = nx;
y = ny;
}
As such, this code only allows the atoms to move in a straight line. At the point shown by check move it is necessary to verify if we can in fact go to (nx,ny) in the next move. The easiest to check is absorbtion:
| Pascal | Java |
if Board[nx][ny] = Atom then begin
Board[nx][ny] := Hit;
show_board;
writeln( 'Absorbed' );
exit;
end;
|
if( Board[nx][ny] == Atom ) {
Board[nx][ny] = Hit;
result = "Absorbed";
return;
}
|
We need to check for a reflection before we check for deflection. Although reflection is essentially two right-angle deflections occuring one after the other in the same direction, the program is required to tell the difference. Reflections are picked up by looking if we would end up between a pair of atoms if we continue moving in the same direction:
Pascal
{ If reflected, simply return - the ray will retrace its path }
if (direct = 0) or (direct = 2) then begin
if (Board[nx-1][ny] = Atom) and (Board[nx+1][ny] = Atom) then begin
show_board;
writeln( 'Reflected' );
exit;
end;
end
else begin
if (Board[nx][ny-1] = Atom) and (Board[nx][ny+1] = Atom) then begin
show_board;
writeln( 'Reflected' );
exit;
end;
end;
Java
/* If reflected, simply return - the ray will retrace its path */
if( (direct == 0) || (direct == 2) ) {
if( (Board[nx-1][ny] == Atom) && (Board[nx+1][ny] == Atom) ) {
result = "Reflected"; return;
}
}
else {
if( (Board[nx][ny-1] == Atom) && (Board[nx][ny+1] == Atom) ) {
result = "Reflected"; return;
}
}
Finally, we check for a deflection. In this case we can't return; instead, we backtrack by setting (nx,ny) to (x,y), and change direction.
Pascal
{ Check for a deflection. If we deflect, move back to the last
position and change direction. }
if (direct = 0) or (direct = 2) then begin
if Board[nx-1][ny] = Atom then begin direct := 1; ny := y; end;
if Board[nx+1][ny] = Atom then begin direct := 3; ny := y; end;
end
else begin
if Board[nx][ny-1] = Atom then begin direct := 0; nx := x; end;
if Board[nx][ny+1] = Atom then begin direct := 2; nx := x; end;
end;
Java
/* Check for a deflection. If we deflect, move back to the last
position and change direction. */
if( (direct == 0) || (direct == 2) ) {
if( Board[nx-1][ny] == Atom) { direct = 1; ny = y; }
if( Board[nx+1][ny] == Atom) { direct = 3; ny = y; }
}
else {
if( Board[nx][ny-1] == Atom) { direct = 0; nx = x; }
if( Board[nx][ny+1] == Atom) { direct = 2; nx = x; }
}
All that remains is to read in the positions of the atoms, repeatedly read instructions and display the results. See the example programs for code that achieves this.
A Java example program solving question 2(a) is in file bio99q2.java. An equivalent Turbo Pascal example program is in file bio99q2.pas, and a DOS executable of this program (compressed with PKZIP) is in bio99q2.zip.
Marking 2(a).
There are three multiple part tests used to check program 2(a). Marks are given within the tests, besides the expected output from the program; this will either be a 10 by 10 grid of characters, or a single line of text.
Incorrect output at any stage gets no marks for that stage; for an output grid every character must be correct. If the program crashes/hangs part way through a test, or takes longer than two minutes, the rest of that test should be discarded.
If the program terminates without crashing/hanging at the end of all three tests, an additional [2] marks should be awarded.
| Mark | Test 1 | Mark | Test 2 | Mark | Test 3 | ||
[1] [1] [1] [1] [1] [1] [1] |
4 4 5 8 6 4 6 7 8 3 .......... .......... ....A..... .....A.... .......... .......... ...A.A.... .......A.. .......... .......... B 5 .......... .......... ....A..... .....A.... .......... .......... ...A.A.... ....+..A.. ....+..... ....+..... Reflected R 7 .......... .......... ....A..... .....*++++ .......... .......... ...A.A.... .......A.. .......... .......... Absorbed B 7 .......... .......... ....A..... .....A.... .......... .......... ...A.A.... .......A.. +++++++... ......+... Exits at L 2 X 0 |
[1] [1] [1] [1] [1] [2] [2] |
8 2 3 5 8 8 3 8 8 9 .......... .......A.. ..A....A.. .......... .......... ..A....... .......... .......... .......A.. .......... T 1 +......... +......A.. +.A....A.. +......... +......... +.A....... +......... +......... +......A.. +......... Exits at B 1 T 4 ...+...... ...++++*.. ..A....A.. .......... .......... ..A....... .......... .......... .......A.. .......... Absorbed L 3 .......... .......A.. ..A....A.. ...++++... ...+++++++ ..A...+... ......+... +++++++... .......A.. .......... Exits at R 6 X 0 |
[1] [1] [1] [1] [1] [1] [1] |
4 2 6 7 9 9 6 2 9 5 .......... ........A. .......... .....A.... .......... ........A. .......... .......... ...A.A.... .......... L 6 .......... ........A. .......... .....A.... +++++..... ....+...A. ....+..... ....+..... ...A.A.... .......... Reflected R 3 ......+... ......+.A. ......++.. .....A.+.. ......++.. ......+.A. ......+... ......++++ ...A.A.... .......... Exits at T 7 R 8 .......... ........A. .........+ .....A...+ .........+ ........A. .......... .......... ...A.A.... .......... Exits at R 6 X 0 |
A total of [25] marks are available for a complete solution to 2 (a).
| |
2 (b). What is the smallest number of atoms that can be placed in an empty black box, so that all 40 possible rays will be affected? Draw a suitable arrangement to illustrate your answer.
Four atoms are required, for example in the following arrangement. This ensures that every ray entering the box is either absorbed or deflected.
![[four atoms along a diagonal]](../../../images/bio99q2b.gif)
Marking 2(b).
The correct answer, getting [2] marks, is 4. An additional [1] mark is available for giving an example. The example should consist of a 10 by 10 array, with a number of atoms marked on it. An example is correct if and only if:
The solution given above is one of many. A correct arrangement would only get 3 marks if accompanied by a statement that 4 atoms are required.
| |
2 (c). A ray is fired into a box at T 5 and emerges at B 5. If there are four atoms inside the box, how many different paths might that ray have taken?
To solve this, it is necessary to investigate the number of different ray paths. This can be done by hand. Note that the question asks the number of ray paths, not the number of permutations in the atom positions that could produce the required set of bounces. These numbers will not be the same as some of the arrangements have several possible positions for atoms that do not affect the ray.
One possible ray path is (using letters for each atom for reference in the explanation below):
....+..... .C..+..... ..+++..... ..+...A... ..+....... ..+....... ..+...B... ..+++..... .D..+..... ....+.....
This involves 4 deflections, each from a different atom. We
count the permutations for this case.
Vertically: atoms A and B must lie in rows 4 to 7, and atom B
must be below atom A. This gives 6 vertical permutations.
Horizontally: consider the column containing atoms C and D. This
may be column 2 or column 3 (requiring A and B to be in column
6), or columns 7, 8 or 9 (requiring A and B to be in column 4).
This gives 5 vertical permutations.
30 total permutations involving reflections from different atoms.
The case where the atom in main column is the same (i.e. atoms A and B are the same) gives an extra 4 vertical permutations, again with the same 5 horizontal permutations, a total of 20. The location of the remaining atom doesn't matter.
There is also one permutation for straight through, involving no deflections.
The answer is therefore 51 different ray paths.
Marking 2(c).
The correct answer, getting [4] marks, is 51.
(Supplementary. There are several wrong answers which also
score marks:
[3] 148 or 50;
[2] 147 or 31;
[1] 106, 105, 30 or 1.)
| |
2 (d). A ray might pass through a square once (e.g. squares on the path of sample ray 2) or twice (e.g. squares on the path of sample ray 3). How about exactly 3 times? How about exactly 4 times? Justify your answers.
This requires a detailed explanation. Almost all of the points on the marks scheme have to be made to get full marks for this part. The answer is that a ray can't pass through a square exactly 3 times, but can pass through exactly 4 times.
Marking 2(d).
"3 times" case [5 marks available
for this case]
[1] No (it cannot enter a square exactly 3 times)
[1] If a ray enters a square twice in the same direction, it
is [trapped/on an infinite loop], and will enter the square more
than three times.
[1] A ray that has entered a square 3 times must have entered
from the left & right, or the top & bottom.
[1] A ray that enters a square from the left & right, or top
& bottom, must have been reflected.
[1] A reflected ray enters all squares an even number of times.
"4 times" case [3 marks available
for this case]
[1] Yes (it can enter a square 4 times)
A maximum of [2] marks are available for justification:
[1] A ray can pass through a square twice from deflections.
[1] A ray that passes through a square twice and is then
reflected, will pass through the square twice more.
[2] An example illustrating a ray entering a square four times. A
typical example is shown below:
A A +++ A + + +++++ A + A +
A valid example must show the ray (illustrated above by '+' symbols) bending several times, crossing over itself, and have one end with atoms (shown as 'A') on two adjacent diagonals.