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:

1. If you receive the letter T followed by an integer n, you should read in n more lines, each consisting of the x and y co-ordinates for a tree. You should then display the grid. [Note: This does not count as a move.]
2. If you receive an M followed by an integer n, you are to simulate the next n moves. If after any move during this simulation both the farmer and the pigs are in the same square, you should output how many moves have taken place (since the start of the program) and the square they have met at. After all n moves you should display the grid.
4. Ignore any other input.

The program now needs to wait for a character and then

1. If it is a T, read in a number n, then read in and place n trees on the board (assume that the trees will not be placed over the pigs or farmer). Show the new board.
2. If it is an M, read in a number n, then call function `makeMove()` n times. Show the new board.
3. if it is an X, terminate.

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.