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:

1. If the ray hits an atom it is absorbed (example ray 1).
2. If the ray is about to pass though a square next to an atom, it is deflected by 90 degrees away from the atom (example ray 2).
3. A ray that would pass between two atoms one square apart is reflected (example ray 3).

These rules are given in order of precedence. Note that sample ray 1 is absorbed rather than deflected.

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:

1. If you receive 'T', 'B', 'L' or 'R' followed by an integer between 1 and 10, you should treat it as the entry point for a ray. You should display the black box, using a '+' to indicate any square the ray enters which was empty, and a '*' for any it enters that contained an atom.

If the ray was absorbed or reflected you should output the corresponding word; otherwise you should output the exit point.

2. If you receive the input "X 0" you should terminate.
3. Ignore any other input.

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.

• Because no atoms can lie in the outermost layer of the box, it is always valid for us to place an atom at the edge and move it from there.
• When moving, we need to keep track of both the position and direction of the ray.
• If we move outside the board or the ray is absorbed, we stop.
• If we hit a reflection, the ray will exactly retrace its steps so we can also stop.

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.

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:

1. Every row of the array either contains an atom, or is touching a row containing an atom.
2. Every column of the array either contains an atom, or is touching a column containing an atom.
3. The number of atoms in the example corresponds to the value given. [Note that a value that scores no marks can still lead to an example that scores marks.]

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.