Project 2: A Needle in a Haystack

Goals:

There are three primary goals for this project.
•  to have you demonstrate your ability to write a variety of patterns of loops
• to give you practice with dividing your project into manageable tasks (i.e., methods)
• to continue to develop your problem solving skills
Secondarily, I expect you to more adept at using conditionals and I want you to be applying the communication/style issues that I have been discussing in class (in particular, with loops and methods). Finally, I am also interested in seeing how well you can learn Java pre-defined methods on your own. The program will require you to generate random numbers. Java's Random class handles this. The text describes the class in chapter 2.

The Assignment:
.
For this programming assignment, I thought you might have fun writing a program that involves creating a game. However, most
games are complicated and are difficult to program (especially if the computer player needs to have a strategy). At this stage, you'll only be able to easily program only a few well-known games - and I've already assigned most of them in earlier semesters (and supplied solutions). Lately,  I've had to come up with original games - these games usually don't end up being interesting in the long run but they should be amusing for awhile.

Suppose that the computer has a 100x100 square and within that 100x100 square will be a single needle. The goal of a game will be to find the location of the  needle in as few guesses as possible. At each turn, the human player will make a guess of two integers (x,y) representing where the player thinks the needle is situated. We'll use a standard math-class Cartesian coordinate system. The x-value represents the number of columns are to the left of the vertical axis and the y-value represents the number of rows above the horizontal axis. Valid guesses for the x and y values range from 0 through 99 inclusive.

At this point, the computer could just say "Yes, you found it" or "No, not there" but this makes for a dull game -- essentially, the human player is just making guesses. Instead, once the human player makes a guess, the computer will either say "Yes, you found it" (when the game is won) or one of the following eight directional clues.

"No, the needle is Northeast",
"No, the needle is Northwest",
"No, the needle is Southeast",
"No, the needle is Southwest",
"No, the needle is NORTH",
"No, the needle is SOUTH",
"No, the needle is EAST", or
"No, the needle is WEST"
From these directional clues, the human player will be able to make better guesses. In the latter four clues, the human has either learned the appropriate row or the appropriate column.

To better explain, here's a sample image

In this sample image, the needle (the correct answer) is at (25,17). Assume that the player has guessed (72,33). In this case, the answer should be that the needle is southwest of the guess.

Beyond playing a single game as described above, your program will also need to be able to play multiple games and keep track of

• the number of games played,
• the number of guesses required,
• the average number of guesses, and
• the "best score" (i.e., the minimal number of guesses the player needed to find the needle).
The final requirement only exists to help us in grading. For the first game played, the needle must be at the location (30,40). When we are grading your program, we will assume that this is the location and then we can judge the correctness of your game based on the program responses to our "guesses"; you'll lose a letter grade if this is not the case. After the first game, the needle location must be selected randomly.

A Sample Output:

Here is my solution to the project. You can use it to clarify any of the rules and to check your program computation against my project's solution.

Here is an example run of my program on the first game.

This is the game "Needle in a Haystack"
What is your guess for the x coordinate? 20
What is your guess for the y coordinate? 20
No, the needle is Northeast
Do you want to continue? y
What is your guess for the x coordinate? 60
What is your guess for the y coordinate? 60
No, the needle is Southwest
Do you want to continue? y
What is your guess for the x coordinate? 40
What is your guess for the y coordinate? 50
No, the needle is Southwest
Do you want to continue? y
What is your guess for the x coordinate? 25
What is your guess for the y coordinate? 30
No, the needle is Northeast
Do you want to continue? y
What is your guess for the x coordinate? 35
What is your guess for the y coordinate? 45
No, the needle is Southwest
Do you want to continue? y
What is your guess for the x coordinate? 30
What is your guess for the y coordinate? 50
No, the needle is SOUTH
Do you want to continue? y
What is your guess for the x coordinate? 30
What is your guess for the y coordinate? 30
No, the needle is NORTH
Do you want to continue? 30
Sorry, you must answer 'Y' or 'N'
Do you want to continue? y
What is your guess for the x coordinate? 30
What is your guess for the y coordinate? 40
Yes, you found it
Total Games Played: 1
Average Score per game: 8.0
Best Score: 8
Do you want to play another game? n
Better luck next time

Design Suggestion

For this project, it will be your job to put together more of the design. I won't be providing the directions for solving the problem but you should read the section on Coding Suggestions (below) before you start designing a solution.

In thinking about a project, you have to distinquish between general  (design)  issues and specific (implementation) issues. The end result of a program design is an outline of how to go about writing the program. The design is a verbalization of how you've chosen to solve the problem. The analogy of a program design is a outline for a paper -- you'll rarely see a well-written paper which was not outlined first.

An implementation of a design is a program -- the words implementation and coding are synonyms.

A good rule of thumb regarding design vs. issues is the following:

Design issues are "what" questions.
Implementation issues are "how" questions.
When you put together an outline for a solution to a program, you're interested in questions like "What should I do next?".  Your answer should constitute the next step of your design. These are the important types of questions. Don't sweat the details; the design is only an outline.

However, new programmers often go off onto "tangents" when trying to produce a design. They end up drowning in the details. Generally, these students are worrying about the "how" questions like "How should the loop work?". Although it's possible that you will have to write this loop when you're ready to code the project, it is just as likely that you may not need this step (if you later make changes to your design). It is a waste of your time to worry about a detail until you know that the step will be necessary.  When details are avoided, it's easier to modify the outline to address all possible cases that you may not have originally considered. Once you've completed the outline., the design stage is over; at this point, you're ready to get involved with coding.

I'm not trying to pretend that this is easy. Designing a solution to a programming problem is a learned skill. While learning this skill, your designs will probably also include unnecessary details.  I try to assign projects where you're likely to be successful in determining a good design.

Finally, whenever you have questions for me or a CA, start by showing your design outline. It tells me know how you've organized your solution which makes it easier to determine whether you have a design problem or a coding problem. When you have a coding problem, I can more easily correct the program if I've seen your design.. On the other hand, I seldom meet with students who've made a serious attempt at a design -- what does this say? Either students don't pay attention to my recommendations or else those students who take the time to do this initial design work have a much simpler time solving the problem. Since a design phase is necessary for any efficient and successful solution to a  larger programming problem, it is obvious that a little forethought (design) is crucial to writing a program in a shorter amount of time.

Coding Suggestions

This is general information for organizing the way you code a solution to a program problem. This modus operandi for programming is built from effective solutions to common experiences.  Being aware of common coding techniques also makes it easier to focus on the "what" (rather than the "how") during the design phase.

As the semester progresses, you'll learn additional practical suggestions but here are three useful ones that are sensible now. It may be difficult to understand on the first reading because there are interconnections between these techniques.

Println Debugging:

When you've got your program to compile (which may still be a lot of work), your output may not produce what you expect. Debugging uses a set of techniques that let you figure out what is wrong with the logic of your program. CodeWarrior has an on-line debugger (which we'll talk about about) but there are simpler debugging tricks.

The simplest is debugging technique (always my personal first attack) is println debugging. The output that your program produces is generally not sufficient to determine what has gone wrong. Consequently, you'll want to introduce additional lines of code (println statements) that display intermediate values in your computations. When you see an intermediate value which is different from what you've expected, you know that the logical error occurs before the location of the println.

You can add println statements to your code while debugging. Although these statements won't be part of your final program, it is generally better for new programmers to comment out debugging statements rather than deleting them. I suggest this because it can save time: you may get rid of a problem at one point but then it will reoccur later on. If you only comment out, it is easy to reintroduce the debug statement; however, if it is deleted, you have to rewrite the statement.  Secondarily, if you needed to have a debugging statement at a certain point in your code, then it is possible that this same piece of code deserves additional commenting.

A special case for using debugging println statements occurs when you are uncertain about whether the program's flow of control works correctly. Add the following statements to the method myMethod:

System.out.println("Entering myMethod");

... the original myMethod  ...

System.out.println("Leaving myMethod");

If you're still uncertain of how parameters work, you can also print parameter values after noting that you've entered a method. This technique becomes less useful once you become confident in using methods. However, when helping students, I'll still use this trick to determine whether their program does what they claim it does..

In general, my personal preference for debugging println statements has the following form:

System.out.println("DBG:: " +
methodName +">>> "
+ local details );
Substages:

As programming projects become more involved, it is useful to try to develop your code so that portions (steps or stages) of your program's design can be tested early and be discovered to work.  Breaking your program into individual methods helps in this regard because you can test that an individual method works properly prior to knowing that all of the methods work together to solve the problem.

Some substages are easy to see and hence will be easy to test separately (and early in the process). For example, getting the player's input for a move can be thought of as an action that is easy to test separately.  Similarly, it will be more important to determine how to play a single game. If you've put together a good design and have divided the design into methods appropriately, it should not be too difficult to expand your code to play multiple games.

Other substages will depend upon how you've approached the design of a solution.  Developing a design that allows you to always incrementally implement and test is not always easy to do and is often impossible.

One substage that is generally easy to debug and test early is the generation of random values for the game. However, although you can implement this early, you should also "turn off" this feature right after getting it to work. The reason for this is that although it is fun to play a game when you don't know the answers, it is difficult to debug  your program because you will be uncertain whether your code is doing the right thing. Similarly, it is difficult for us to test your program when we don't know whether your hints are appropriate.  When you know what the solution to the game is, say (30,40), then you can test your program by making specific guesses and seeing if your program produces the correct code. For example, a guess of (50,40) should produce the answer WEST.  In this way, you can easily figure out appropriate guesses to determine that your program produces all of the right hints for those guesses.

Methods (& Design)

For this project, you're required to subdivide your program into a sequence of methods.

Your first exposure to methods was given as an alternative to repeating similar code groups by creating a single named block of code. However, methods are also a valuable way to organize a solution to a problem. Essentially, design steps, even if they're done only once, generally correspond to methods. Using the analogy to a paper outline, a line item on an outline often corresponds to a paragraph of your paper. In the same way, a step in your program design (representing what you want to do) corresponds to a method of your implementation (the method body corresponds to how you do the step). Note also that the comments required for a describing a method are associated with the "what". Comments within a method clarify the "how".

With programming, if the size of the project warrents it, groups of steps can themselves be described as methods. It is probably reasonable to have a single method that corresponds to playing a game. That method will then call other methods that you write.