“Lost in the woods… a simulation experiment”

Much of the software development work you will do in this course will be done in groups. In HW1, we will apply Pair Programming approach. You will be randomly assigned a partner (unless you choose one), and the two of you will work together on this assignment. You may NOT work with anyone else on this assignment. If you need clarifications, please email me.

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 doesn’t 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 what’s 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 won’t 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.

What to submit?

1. Your program! Which should AT LEAST do what is described above (the functional requirements): explain the simulation to an interactive user, get the values A and B from the user, do the simulation, and then output the result.
2. 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 won’t 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.”
3. Design document, at this stage, I need class diagrams of the classes used showing the relations between them.

WHICH PROGRAMMING LANGUAGE MUST YOU USE? Java, or Python, if you want to use another language, please contact me before.

PROGRAMMING TIP: Since you want the wandering to be “random,” you should make sure that if you run your program twice with the same A and B inputs, you usually get DIFFERENT behavior. (I have to say “usually” there because every once in a while, you could get exactly the same behavior just by chance.) To make this happen, randomize your random number generator ONCE (right at the start of your program). Don’t randomize it in an inner loop – that’s terribly inefficient and unnecessary. Most programming languages have a built-in random number generator.

It is better to hand in something simple that works, and on time, rather than handing in something fancy that is either late or doesn’t work. The best HW1 programs will work, be on time, be well documented (see below), and will do something interesting.

The specification above mentions “well documented.” Here are some hints of what good documentation might look like:

Start your program with an “opening comment.” You may include more items than the items listed here, but you may NOT leave out any of the items mentioned here. If you DO leave any of these out, or if you do a poor job on any of them, you will lose points. If one of these items is not applicable to your program (for example, if it doesn’t use any external files), then include the name of the item in your opening comment but add “N/A” or “none” to indicate that this isn’t applicable to your program.

Items to include in your opening comment:

• a title for your program
• the name of the file that holds your program
• a list of any external files necessary to run your program
• a list of external files your program creates (If you list any external files, briefly explain what each of them
  contains.)
• the names of any programmers working on the program (for HW1, this is just you)
• email address of all programmers
• the course number and section number of the course you’re writing this program for
• the date you finished the program and submitted it
• an explanation of what the program does
• any resources you used to complete the program (Always give credit where credit is due; for example, if you
  used a website to check on an algorithm, list that here.)
  Other comments that are required:
• each declaration should include a comment that explains its use
• each subprogram (function, subroutine, object,…) should have an opening comment describing its purpose)
• each loop should be preceded by a comment that describes its purpose
• any statement that is particularly unclear or “tricky” should have a comment clarifying its use to the human
  reader