![[BIO98 Logo]](../../../images/bio98-e-s.gif)
the computing competition for schools and colleges.
We are proud to present BIO'98.
![[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'98. |
|
 |
The 1998 British Informatics Olympiad exam
Solution to Question 2: Tamworth Two
This question was inspired by the success of the Tamworth pigs Butch and Sundance at escaping certain death. They roamed free - despite the best efforts of police, farmers and several dozen press photographers - for several days, winning a lifetime of retirement in an animal home as a reward for their courage. Admittedly, we had to simplify the pursuit a little to make it easier to program, but this question - like the real-life pigs - was greatly liked!
2 (a) [24 marks]. Write a interactive program to model the behaviour of the pigs and farmer. Your program should first read in a line containing two numbers, the x co-ordinate then the y co-ordinate of the pigs. A second line should then be input, consisting of the co-ordinates for the farmer. Note that both the farmer and the pigs start by facing up the grid. You should then output the grid.
Before we begin solving this, we can think of a simple way of storing the positions and dealing with the edge of the board. Each location can contain the pigs or farmer or both, or a tree; the pigs and farmer cannot move through trees. So if we store a board which has an extra (hidden band of squares all the way round, which are set to trees, our code can deal with the boundary with no extra effort.
We can represent the board, the elements on the board, and the characters that represent each element, as follows (in Java):
/**
* Representation of the board
*/
int[][] board = new int[12][12];
/**
* Definitions for the objects
*/
static int blank = 0;
static int obstacle = 1;
static int farmer = 2;
static int pigs = 3;
static int capture = 4;
/**
* Characters for each object
*/
static char[] objects = { '.', '*', 'F', 'P', '+' };
We also need to track the locations and directions of the pigs and farmer, and it will be useful to know the current move number:
/** * Directions the pigs and farmer are moving in (default up) */ int directionPigs = 0; int directionFarmer = 0; /** * Locations of pigs and farmer */ int xPigs, yPigs, xFarmer, yFarmer; /** * Current move number */ int move = 0;
Notice that the board is declared to be 12x12 - going from 0 to 11. We can then initialise the board so that the outside (invisible) edge is impassable, and the visible part (x and y from 1 to 10) is blank:
/* Initialise the board */
for( x = 0; x <= 11; x++ ) for( y = 0; y <= 11; y++ )
board[x][y] = obstacle;
for( x = 1; x <= 10; x++ ) for( y = 1; y <= 10; y++ )
board[x][y] = blank;
We read the locations of the pigs and farmers from the input
(in Java it is slightly fiddly to read text input, so we use a StreamTokenizer
object which does the work for us) to (xPigs, yPigs)
and (xFarmer, yFarmer). The starting
condition is set by placing the pigs and farmer on the board - we
assume that they will not start in the same place - and then we
display the starting board.
board[xPigs][yPigs] = pigs;
board[xFarmer][yFarmer] = farmer;
showBoard();
We will need to show the board again, so we define a function showBoard()
to do this - taking account of the fact that we have to print the
top row first:
void showBoard() {
int x, y;
out.println();
for( y = 10; y >= 1; y-- ) {
for( x = 1; x <= 10; x++ ) out.print( objects[board[x][y]] );
out.println();
}
out.println();
}
We are now ready to do the real business of placing trees and moving the pigs and farmer:
The program now needs to wait for a character and then
makeMove() n times. Show
the new board.The last piece of code we need is to define the function makeMove(),
which moves or turns the pigs and farmer once, adds one to the move
counter, and checks if the pigs and farmer have met.
int xPigsNew = xPigs;
int yPigsNew = yPigs;
/* Move pigs */
if( directionPigs == 0 ) yPigsNew += 1;
if( directionPigs == 1 ) xPigsNew += 1;
if( directionPigs == 2 ) yPigsNew -= 1;
if( directionPigs == 3 ) xPigsNew -= 1;
if( board[xPigsNew][yPigsNew] == obstacle ) {
/* We cannot move to this point, so we rotate */
xPigsNew = xPigs; yPigsNew = yPigs;
directionPigs = (directionPigs + 1) % 4;
}
We do the same for the farmer. The move is made by clearing
the squares previously occupied by the pigs and farmer, and
checking if they have met. If they have, the event is noted and
the capture marker placed on the board to indicate
that they are in the same square. Otherwise, the pigs and farmer
are placed separately:
board[xPigs][yPigs] = blank;
board[xFarmer][yFarmer] = blank;
xPigs = xPigsNew; yPigs = yPigsNew;
xFarmer = xFarmerNew; yFarmer = yFarmerNew;
move++;
if( (xPigs == xFarmer) && (yPigs == yFarmer) ) {
out.println( "Farmer and pigs meet on move " + move +
" at (" + xPigs + "," + yPigs + ")" );
board[xPigs][yPigs] = capture;
} else {
board[xPigs][yPigs] = pigs;
board[xFarmer][yFarmer] = farmer;
}
The full Java solution program, including the above code, is available as bio98q2.java. It can be viewed in a Java-enabled browser or run on a Java-capable computer from the example solution to Q2 page.
Marking
There are two multiple part tests used to check program 2(a). Marks are given within the tests, besides the expected output from the program. Comments are given on the right-hand side, indicating why the marks are being given. Incorrect output at any stage gets no marks for that stage. If the program crashes/hangs part way through a test, or takes longer than two minutes, the rest of that test should be discarded.
(Supplementary for 2(a) tests 1 and 2. If the 'F' and 'P' have their location swapped throughout both tests, only the first [2] marks on test 1 should be deducted.)
Test 1 [13 marks available]
| Mark | Program text | Explanation |
[2] [2] [2] [2] [1] [3] |
3 3 3 5 .......... .......... .......... .......... .......... ..F....... .......... ..P....... .......... .......... M 1 .......... .......... .......... .......... ..F....... .......... ..P....... .......... .......... .......... T 2 3 8 4 7 .......... .......... ..*....... ...*...... ..F....... .......... ..P....... .......... .......... .......... M 3 Farmer and pigs meet on move 4 at (3,7) .......... .......... ..*....... ..+*...... .......... .......... .......... .......... .......... .......... M 25 ...P.F.... .......... ..*....... ...*...... .......... .......... .......... .......... .......... .......... X |
Printing out initial position (see supplementary) Moving correctly Placing obstacles correctly Printing when Farmer & pigs meet Correctly printing a '+' Boundary conditions |
Test 2 [11 marks available]
| Mark | Program text | Explanation |
[1] [2] [1] [2] [2] [2] |
3 6 1 5 .......... .......... .......... .......... ..P....... F......... .......... .......... .......... .......... T 4 1 8 7 10 10 3 3 1 ......*... .......... *......... .......... ..P....... F......... .......... .........* .......... ..*....... M 55 Farmer and pigs meet on move 51 at (4,4) ......*... .......... *..P...... .......... .......... .......... F......... .........* .......... ..*....... M 300 Farmer and pigs meet on move 64 at (6,7) Farmer and pigs meet on move 301 at (6,4) Farmer and pigs meet on move 314 at (4,7) ......*... .......... *......... .......... .......... .......... .......F.. .........* .....P.... ..*....... X |
Printing out initial condition Placing obstacles correctly on boundary Printing when farmer & pigs meet Printing the board position after move 55, not when the farmer & pigs meet Printing several farmer & pig meetings ([2] marks should be given only if all three meetings are correctly listed) Making a large number of moves |
A total of 24 marks are available for 2 (a).
| |
2 (b) [2 marks]. Suppose the pigs start at (1,1), and they are trying to reach (10,10). What is the minimum number of trees that need to be placed on the grid to prevent the pigs reaching (10,10)? What is the maximum number that can be placed on the grid so that they can still reach (10,10)?
The minimum number is 1 [1 mark]. This is the case when a single tree is placed anywhere along the left or top sides. For example, a tree at (1,2) will make the pigs simply follow right and left along a straight line from (1,1) to (10,1).
The maximum number is 81 [1 mark]. This is the case when, for example, the whole board is full except for a path 1 tree wide along the left and top sides.
Maximum 2 marks for 2 (b).
| |
2 (c) [3 marks]. Suppose you are able to place the farmer and the pigs on an empty grid, and you can choose the direction they are both facing (up, down, left or right). For a given starting position either they never meet, or they first meet after x moves. What is the maximum value that x can take?
The answer, which gets 3 marks, is 19. This is the case, for example, when the pigs start at (1,1) and the farmer at (2,1), both facing up. This is demonstrated by bio98q2.java when the location of the pigs is set to (0,0). It can be viewed in a Java-enabled browser or run on a Java-capable computer from the example solution to Q2 page.
| |
2 (d) [5 marks]. Suppose you are able to place the farmer and the pigs on an empty grid, and you can choose the direction they are both facing (up, down, left or right). For a given starting position either they never meet, or they first meet after x moves. What is the maximum value that x can take?
This was marked as follows:
[1] Yes, we can always determine whether the farmer and pigs
will meet.
Additionally, up to four marks can be gained from the following
points:
[1] If the farmer and pigs will meet, we will know this when the
simulation reaches this position.
[1] If we return to a state (configuration / setup / position)
that we have seen before, all future states will be repetitions
of ones we have seen before.
[1] Once we have simulated all the possible states we will know
if the farmer and pigs will ever meet.
[1] The simulation only has a finite number of states.
[1] We must eventually repeat a state we have previously seen.
A maximum of 5 marks available.
| |
| |