[BIO98 Logo] The British Informatics Olympiad is
the computing competition for schools and colleges.
We are proud to present BIO'98. 		[Data Connection logo]
-----

The 1998 British Informatics Olympiad exam

Question 2

-----
Question 2
Tamworth Two		 A pair of pigs are loose somewhere in a large wooded area and an experienced farmer has been sent in to catch them. Your task in this question is to model their behaviour.

The chase takes place on a 10 by 10 grid, the bottom left square being (1,1). Squares can be empty or contain a tree, the pigs (who always travel together) or the farmer. Only the pigs and the farmer can ever share a square. Each square is represented as follows:

. Empty Square
* Tree
P Pigs
F Farmer
+ Pigs and Farmer
  The pigs wander around the grid in a set way. They move one square in the direction they are facing, unless there is a tree or the edge of the board in the way. If their move was blocked they just turn 90 degrees clockwise. The farmer, wise in the ways of pigs, moves in exactly the same way.

The farmer and the pigs can be considered to move simultaneously. If the farmer and the pigs pass each other during a move, they are not considered to have met. Furthermore, due to the difficulty in catching pigs, the farmer and pigs continue to move after they have met.
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.

Until your program terminates you should repeatedly wait for input, and then:

  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.
  3. If you receive an X, your program should terminate.
  4. Ignore any other input.

Sample run
5 6
4 8

..........
..........
...F......
..........
....P.....
..........
..........
..........
..........
..........

T 2
4 10
1 1

...*......
..........
...F......
..........
....P.....
..........
..........
..........
..........
*.........

M 4

Farmer and pigs meet
on move 3 at (5,9)

...*P.....
.....F....
..........
..........
..........
..........
..........
..........
..........
*.........

X
   
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)?
   
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?
   
2 (d)
[5 marks]		 For a given grid, with trees and starting positions (with directions) for the farmer and pigs, will we always be able to determine whether or not the farmer and pigs will meet? Consider both the case where they will eventually meet, and when they will not.
-----
The British Informatics Olympiad