Montana Tech of The University of Montana
Computer Science & Software Engineering

CSCI 135
Fundamentals of Computer Science I
Fall 2014



ASSIGNMENT 2

In this assignment, you will gain experience reading from standard input, using arrays, and using Math methods. You will also learn how to design a greedy algorithmic solution to a problem that would be tedious and error-prone for a human to calculate.


Part 1: Number Hunt
Create a game NumberHunt.java in which users try and guess a random number between 1 and 100. After each guess, the computer prints out a hint according to how close the guess was to the target value: If the user inputs a number that isn't between 1 and 100, you should print "Invalid input!". After correctly guessing the number, the game should print the total number of guesses (including invalid guesses). You can assume users will only enter integers and not floating-point numbers or text.

Your program should optionally take a single integer command line argument. If a command line argument is given, use this number instead of drawing a random number. This will help you test your program since you can start with a known number. You can assume the command line argument (if given) will always be between 1 and 100. Here are some example runs:
% java NumberHunt
Guess a number between 1-100? 50
Ice cold.
Guess a number between 1-100? 20
Getting warmer.
Guess a number between 1-100? 10
Hot.
Guess a number between 1-100? 5
Getting warmer.
Guess a number between 1-100? 15
Hot.
Guess a number between 1-100? 12
You nailed it!
It took you 6 guesses.

% java NumberHunt 42
Guess a number between 1-100? 10
Ice cold.
Guess a number between 1-100? 101
Invalid input!
Guess a number between 1-100? 30
Cold.
Guess a number between 1-100? 35
Getting warmer.
Guess a number between 1-100? 40
Hot.
Guess a number between 1-100? 41
On fire.
Guess a number between 1-100? 43
On fire.
Guess a number between 1-100? 42
You nailed it!
It took you 8 guesses.
How do I read in a number from the user? You need to use download the StdIn.java class and place it in the same directory as your NumberHunt.java program. When you want your program to read in an int from the user, call the method StdIn.readInt(). For an example program, see OrderProduct.java.

How do I check if a command line argument was given? You can use args.length to find out how many command line arguments were sent in. If args.length is zero, you know you need to draw a random number. If args.length is greater than zero, you can obtain the target value from args[0].

How do I draw a random number? You want to use the Math.random() method. Check out the TwoDice.java example of how to draw a number within a certain range.

How can I compute the absolute value of a number in Java? You can use the Math.abs() method.


Part 2: GreedyPath
Given a file containing a list of two-dimensional points, you need to develop a program that does the following: The file GreedyPath.zip contains some example input files as well as a program you can use to graphically display your answer. You can copy the files in the zip into your Eclipse project directory, then right-click on the project and select Refresh. Here is one of the provided input files, points7.txt:
 7
 0.0   1.0
 1.0   1.0
-1.0   1.0
 2.0   0.0
-2.0  -2.0
 1.0  -2.0
 2.0  -2.0
Your first task will be to read the point data using StdIn and put it into appropriate array variables. For an example of a program that uses such parallel arrays, check out ClassifyProducts.

You can assume the input file will be well-formed and contain at least one point. The first two lines of output of your program will be the lower-left and upper-right coordinates of the bounding box containing the points. After this should come a blank line and then a line containing the integer number of points you read in. You may want to get this working before working on the harder part of computing the path. Here are sample runs of just this part of the program:
% java GreedyPath < points7.txt
-2.0 -2.0
2.0 1.0

7

% java GreedyPath < points5.txt
0.0 0.0
1.9 1.65

5

% java GreedyPath < points3.txt
-1.0 0.0
1.0 1.0

3
We assume paths always start at the first point in the file. From there, the path always goes to the next closest point that has not already been visited. So for example in points7.txt, starting at (0.0, 1.0), the next closest point is (1.0, 1.0). From (1.0, 1.0), the next closest point would be (0.0, 1.0), but since we already visited this one, the next best one is (2.0, 0.0), and so on.

You will need to use your arrays of the x- and y-coordinates to figure out which point is closest given your current location. In the event of a tie, you should use the point that occurs first in the file. You will also need to keep track of whether each point has been visited or not. Hint: keeping track of something that has a yes or no answer is a perfect time for the boolean data type.

Everytime you decide on the next point (including the very first one), output the point's coordinate on a single line with the x- and y-coordinate separated by a space. Also as you go, you should keep track of the total distance accrued by your path (i.e. compute the Euclidean distance between the last point and the point being added to the path, adding this to a sum variable). After outputting all the points on the path, output a blank line followed by this distance.

Here is the complete output for some of the provided files:
% java GreedyPath < points7.txt
-2.0 -2.0
2.0 1.0

7
0.0 1.0
1.0 1.0
2.0 0.0
2.0 -2.0
1.0 -2.0
-2.0 -2.0
-1.0 1.0

11.576491222541476

% java GreedyPath < points5.txt
0.0 0.0
1.9 1.65

5
0.0 0.0
0.5 0.0
0.5 0.5
1.0 1.65
1.9 0.5

3.714301807049468

% java GreedyPath < points3.txt
-1.0 0.0
1.0 1.0

3
0.0 0.0
1.0 1.0
-1.0 1.0

3.414213562373095

% java GreedyPath < points3b.txt
-1.0 0.0
1.0 1.0

3
0.0 0.0
-1.0 1.0
1.0 1.0

3.414213562373095
If you would like to visualize how your path is constructed, you can use our provided program DrawPath.java. This program reads in from standard input, the output of your GreedyPath program. Using the StdDraw.java library, it graphically draws each line segment in your solution. The line segments change from red to blue as the path progresses. It also displays the path length computed by your GreedyPath program. Here are some examples of how to use it along with the output:
% java GreedyPath < points7.txt | java DrawPath 1000
% java GreedyPath < mona-20k.txt | java DrawPath 
% java GreedyPath < usa13509.txt | java DrawPath 

How do I compute the Euclidean distance between two points? You need to use the formula: In this formula p1 and p2 are the coordinates of one point and q1 and q2 are the coordinates of another. You can take a square root in Java using Math.sqrt(). While there is a math method for taking powers, if you are just squaring a value, it is much more efficient just to use the normal multiplication operator.

Does my program find the shortest path visiting all the points? Probably not. You might be surprised to learn this problem has been intensly studied for a very long time. Currently we can find pretty good, but not necessarily optimal solutions.
Extra credit. Come up with an algorithm that provides a shorter path than the simple greedy heuristic.
Submission. Submit your program NumberHunt.java and GreedyPath.java via Moodle. Be sure each submitted source file has the required header with your name, username, and a description of the program. If you did the extra-credit, submit a single zip file containing all the files required to run your creation to the extra-credit dropbox.

Page last updated: December 18, 2014