The Setup: Imagine two people are lost in a large forest. There is an impossibly difficult barrier that surrounds the forest. The two people wander around aimlessly. If they happen to end up in roughly the same part of the forest, they see each other and are happier than if they are all alone. Depending on how big the forest is, and how quickly they wander about, I wonder how long it will take for them to find each other?

Your Assignment: Write a program that works on the following problem:

1. The woods are represented by a rectangular grid that is A units wide and B units tall. We will assume for this assignment that both A and B are integers, and that 2 <= A <=50, and 2 <= B <= 50, and that A and B may or may not be the same integer. We will leave the units for A and B unnamed. (Maybe it is yards, maybe kilometers it doesnt matter for the assignment.) At the start of your program, you should ask the interactive user to enter values for A and B. Your program should tell the user whats going on in the simulation, and should prompt with the limits made clear. If the user does not enter an appropriate value for A or B, the program should give an appropriate error message, and then re-prompt (again with the limits shown) until both A and B have been specified correctly by the user.
2. I will call the two people wandering Pat and Chris. Pat will start in the upper left corner of the grid, and Chris will start in the lower right corner of the grid. The grid is surrounded on all four sides by the impossible barrier.
3. Pat and Chris try to move from one cell in the grid to another cell in the grid simultaneously. Time units are integers; time starts at 0 and is incremented by one at each time step. (Again, we wont specify what the time units represent. They could be seconds, or hours, or) Your program does NOT need to go as slowly as the two people wandering around in the woods!
4. At each time unit, each person tries to move one unit by randomly choosing one direction, either North, South, East, West, Northeast, Northwest, Southeast, or Southwest. However, if the randomly selected direction takes the person into the barrier, they just stay at the same place they were at the start of that time unit. For example, since Pat starts in the upper left corner of the grid, if Pat randomly decides to go North, West, Northwest, Southwest, or Northeast, then Pat will not move out of the upper left corner on that turn. However, if Pat randomly decides to go any of the other three directions, than Pat will actually move to a new cell.
5. Simulate the random moves of Pat and Chris until one of two things happens: (A) Pat and Chris wind up in the same cell of the grid (they find each other), or (B) they do not meet after 1 million time units. When either of these things occurs, the problem halts and outputs to the screen how the simulation ended, and how many time steps occurred before the simulation ended. The program should pause until the interactive user pushes ENTER so that the user can read the output to the screen. After the user pushes ENTER, the program should halt.

Your program should AT LEAST do what is described above: explain the simulation to an interactive user, get the values A and B from the user, do the simulation, and then output the result.

HOWEVER, for full marks,you should do MORE than what is described above. The more is up to you. How might you visually display the results using text? Maybe you could run the simulation multiple times and give things like the maximum, minimum, and average time until Pat and Chris meet. After you get your program working, you might want to play with it a little, adding some code to explore a question or two about wandering in the woods. For example, it stands to reason that in a smaller forest (like a 2 X 2), it wont take very long (on average) for our two hapless hikers to meet. As the forest gets bigger (4 X 4, 6 X 6, 8 X 8, and so on), we expect it to take longer (on average) for Pat and Chris to meet. But is the increase linear in the size of the grid? Or might it be geometric? What other interesting questions might you explore? Graphics are going to be tough this time (more on this soon), so think numbers and text, not pictures, for your more.