Homework 08

Assignment: Two problems, worth 25 points each (plus up to 20% extra credit, 10% for additional modifications to problem 2, and 10% for doing an optional problem 3), due on:

11:59 PM on Sunday, October 23, 2005 (M/T sections)

11:59 PM on Monday, October 24, 2004 (W/Th sections)

Reading: Your CS5 lecture notes and the online readings for week 8.

Problem 1 Lies, Damned lies, and ... (25 points) [topic: using arrays and methods]

Time Travel Securities, Inc., (NYSE: TTS), has contracted you to write a program that will help it analyze prices and provide advice to its customers. The company is interested in a number of different statistical measures of stock prices -- and, in particular, in helping its customers plan when to buy and sell stocks before they use their souper-douper time machine, which sends their clients back in time so they can actually buy the stocks.

Your program should begin by prompting the user for a number (an int) of stock prices to be considered. The user is then prompted to enter that many prices, which are stored in an array of doubles of the appropriate size. You may assume that these numbers are the daily closing price of a particular security, starting with Day 0. You may also assume they will all be valid prices (nonnegative doubles), and that two or more days worth of data will always be entered.

The program then displays the following menu of options for the user:

  
 (0) Print prices and days
 (1) Sum
 (2) Average
 (3) Standard Deviation
 (4) Print minimum price 
 (5) Print the minimum price's DAY
 (6) Print maximum price 
 (7) Print the maximum price's DAY
 (8) Print the best investment strategy!

 (9) Quit

When the user picks a valid choice, that action should be performed. Otherwise an error should be displayed. In either case, the menu should then be redisplayed and the process repeated, until the user chooses the Quit option (Option 9).

For full credit, you must define and use the following methods:

public static void printMenu()
public static void printPrices(double [] A)
public static double sum(double [] A)
public static double average(double [] A)
public static double stdev(double [] A)
public static double min(double [] A)
public static int minIndex(double [] A)
public static double max(double [] A)
public static int maxIndex(double [] A)

Remember that, for each method, a comment of the following form is needed:


    // method:  <blah blah blah>
    // inputs:  <blah blah blah>
    // outputs: <blah blah blah>

In total, these methods are worth about 15 of the problem's 25 points.

The main method: main should start with the code for inputting the initial data and storing it in an array, followed by a loop that: displays the menu using the printMenu method, gets the user's choice, and then processes it. If the user enters an invalid option, they should be prompted to try again.

Required methods that produce output to the screen for the user: printPrices and printMenu() are the only required methods (besides main) that print out text to the console:

public static void printPrices(double [] A) displays a nicely formatted report of the set of prices. Each day's price, starting from Day 0, is labeled and printed on its own line. For an example, see the Sample Run.
public static void printMenu() displays the text of the menu of choices. For an example, see the Sample Run. This method should not ask for the user's choice -- that gets done in main, where the choice needs to be processed!

Methods that do not interact with the user at all: the purpose of the following methods is to interact with the main program. As such, they should not interact with the user at all (rather, let main do that):

public static double sum(double[] A) should return the sum of the elements in array A. For instance, one place you'll want to use this method is in servicing Option 1. It should also be used by some of the other methods in this list --- sound advice that is also applicable to many of the other methods in this assignment --- in fact, for full credit, you'll want to reuse methods where ever you can.
public static double average(double[] A) should compute and return the average of the elements in array A. In main you'll want to format your answer to use 2 places of precision with H.fmt. For an example, see the Sample Run.
public static double stdev(double[] A) should compute and return the standard deviation of the elements in array A. Here's the formula to use for calculating the standard deviation:

where the symbol A_av stands for the average of array A. Note that the squaring happens before the summation, not after. The statistically savvy will recognize that this is the sample (as opposed to the full population) formula for standard deviation. The coolness of dividing by L-1 as opposed to L is that, in the limit of infinite data, this estimate will converge to the population's actual standard deviation---i.e. it is an unbiased estimate! In main you'll want to format your answer to use 2 places of precision with H.fmt. For an example, see the Sample Run.
public static double min(double[] A) should return the minimum value in array A. For an example, see the Sample Run.
public static int minIndex(double[] A) should return the index of the minimum value in array A. You may assume that the values will all be distinct so that there will never be more than one minimum (the same assumption can be made for the maximum). Again, for an example, see the Sample Run.
public static double max(double[] A) should return the maximum value in array A, and is analogous to min.
public static double maxIndex(double[] A) should return the index of the maximum value in array A, and is analogous to minIndex.

Option 8: All of the options should be clear except, perhaps, option 8. This option should print out the best investment strategy for the user, based on the fact that the user can time-travel back to Day 0, buy a stock on that day (or any day after that), and sell a stock on any day in which it has already been bought. Once this option has figured out the optimal strategy --- i.e. the maximum possible profit --- it should print out the day and the value of the stock price at which the user should buy, the day and the value at which the user should sell, and the total profit the user would make using that investment strategy.

A few clarifications:

The earliest day a stock that was purchased may be sold is on the day it was purchased (so even if a stock does nothing but go down --- a real possibility --- a user's minimum profit can always be non-negative).
Aside from buying and selling the same stock on the same day, users will have at most one transaction per day.
Over the entire time period, a user will buy and sell exactly one stock (after all, capital-to-brokers' fees can be substantial!).

Feel free to put the code for option 8 directly in main if you wish. For an example of how option 8 works and how its results should be displayed, see the Sample Run.

Sample Run: a single run from a sample program follows and serves as a guide to a suitable interface. The user's input is in blue. Notice that you don't have to type decimal points when entering input as long as you use H.nd().

Welcome to time-travel securities!

How many stocks would you like to analyze?
6

Please enter the prices:
90.0
10.0
60.0
42.0
75.0
70.0

Main Menu:
 (0) Print prices and days
 (1) Sum
 (2) Average
 (3) Standard Deviation
 (4) Print minimum price 
 (5) Print the minimum price's DAY
 (6) Print maximum price 
 (7) Print the maximum price's DAY
 (8) Print the best investment strategy!

 (9) Quit

Which choice would you like?  0

Day 0   Price is 90.0
Day 1   Price is 10.0
Day 2   Price is 60.0
Day 3   Price is 42.0
Day 4   Price is 75.0
Day 5   Price is 70.0

  < MENU HERE >

Which choice would you like?  1

The sum is 347.0

  < MENU HERE >

Which choice would you like?  2

The average price is 57.83

  < MENU HERE >

Which choice would you like?  3

The standard deviation of the prices is 28.36

  < MENU HERE >

Which choice would you like?  4

The minimum price is 10.0

  < MENU HERE >

Which choice would you like?  5

The minimum price occurs on day 1

  < MENU HERE >

Which choice would you like?  6

The maximum price is 90.0

  < MENU HERE >

Which choice would you like?  7

The maximum price occurs on day 0

  < MENU HERE >

Which choice would you like?  0

Day 0   Price is 90.0
Day 1   Price is 10.0
Day 2   Price is 60.0
Day 3   Price is 42.0
Day 4   Price is 75.0
Day 5   Price is 70.0

  < MENU HERE >

Which choice would you like?  8

You should  buy the stock on day #1 at a price of 10.0
You should sell the stock on day #4 at a price of 75.0

You will make a per-share profit of 65.0

  < MENU HERE >

Which choice would you like?  10

That is not a valid choice.

  < MENU HERE >

Which choice would you like?  9

Until yesterday, happy investing!

Submission:Be sure to submit your CS5App.java file under homework 8, problem 1.

Extra Credit: There is no extra credit for this problem.

Problem 2 Lights Out! (25 points) [topic: using arrays]

Problem 2 is this homework's Pair Programming problem and should be worked on in groups of two as described at http://www.cs.hmc.edu/cs5/pair_programming.html.

For this problem, you will implement a one-dimensional game of Lights Out. The one dimensional game is just like the two dimensional game---described here---except that the "light toggling" only happens in one dimension.

To re-cap, the game consists of a row of lights that can be either on or off. By choosing a particular light, you switch its state and the state of its neighbors. That is, you turn the chosen light from off to on or from on to off, and you turn each neighbor from off to on or from on to off, depending on their initial states. The game is won when all of the lights are turned off.

For example, if there were 6 lights in the game in the following state (dark squares indicate "off", light squares indicate "on"):

and the user selected light number 2, then the resulting state would be

If the user then selected light number 0, the resulting state would be

Your program should first prompt the user for a number of lights. This must be between 3 and 15 (inclusive). If it is not in that range, your program should enter a small loop in which it continues to prompt the user for an integer in the valid range until one is typed. (Feel free to use the get_int function provided in class a couple weeks ago for this purpose.)

Your program should create an array of the specified length and go through each value in the array and randomly set it to "on" or "off". This randomization is for each value separately -- we want a random pattern of lights to begin with. The one restriction is that your initial randomization should not allow for the possibility that the game is already won (i.e. all the lights are already off).

Notice: this problem does not force you to represent the lights in any particular manner -- you may use ints, doubles, booleans, chars, or whatever you would like. In addition, you are fee to choose a representation for "on" lights and "off" lights. Also, whether or not you want to use any methods is entirely up to you. While the first problem of this assignment is quite strict in what to do, for this problem, you are free to design the program as you wish!! And, please do not be shy --- ask the graders or I about your design choices if you'd like feedback.

Your program should then print out the pattern of lights so that each "on" light is a 4x4 block of *'s and each "off" light is a 4x4 block of spaces Each light should be separated by vertical bars (|). After printing the lights, you should include numbers beneath each light, starting from 0. Note: this specification is slightly different than what we did in class on the worksheet; use the specification described here when writing up your code!

For instance, the final state of the example above would look like

|    |****|****|****|    |****|
|    |****|****|****|    |****|
|    |****|****|****|    |****|
|    |****|****|****|    |****|
   0    1    2    3    4    5

To give another example, a full-sized, fifteen-light initial configuration might look like:

|****|****|    |    |    |****|    |****|****|****|    |    |    |    |****|
|****|****|    |    |    |****|    |****|****|****|    |    |    |    |****|
|****|****|    |    |    |****|    |****|****|****|    |    |    |    |****|
|****|****|    |    |    |****|    |****|****|****|    |    |    |    |****|
   0    1    2    3    4    5    6    7    8    9   10   11   12   13   14

Note that how many numbers are displayed below the lights depends on how many lights the user initially chose. Thus, when printing numbers above 9, you need less white space between them if they are to line up in the same part of their respective light's block (and you should aim for this level of care in your formatting). An appropriate if statement within the appropriate for block should do the trick here. You might also find a void printSpaces(int n) method helpful to write.

After printing the lights, you should ask the user what light they would like to select (it must be an integer). You should check to be sure that the light selected is actually valid for the current game -- if not, you should enter a small loop and continue prompting the user until a correct input is typed in. See the run below as an example.

Once a valid light number is input, your program should make the appropriate changes to the light array, and then continue by printing out the new array and prompting the user again. When the user wins the game by turning off all of the lights, the program should stop (make sure you've displayed the winning light configuration to the console) , print a congratulatory message, and quit. There is no need to prompt the user to play again (in that case, we'll let the user rerun the program if they'd like...).

Wacky Fact: For some numbers of lights and some initial states, the Lights Out puzzle isn't even solvable. (In fact, it's unsolvable 1/6 of the time.) Don't worry about this; it's simply to let you know... .

Here is a sample run of my program as a guide to an appropriate interface. The user's input is in blue:

Welcome to Lights Out!

How many lights would you like to have (3-15)?  10


|    |****|    |    |****|    |    |    |    |    |
|    |****|    |    |****|    |    |    |    |    | 
|    |****|    |    |****|    |    |    |    |    |  
|    |****|    |    |****|    |    |    |    |    |   
   0    1    2    3    4    5    6    7    8    9  


Which light do you select?  2



|    |    |****|****|****|    |    |    |    |    | 
|    |    |****|****|****|    |    |    |    |    |  
|    |    |****|****|****|    |    |    |    |    |   
|    |    |****|****|****|    |    |    |    |    |
   0    1    2    3    4    5    6    7    8    9   


Which light do you select?  1



|****|****|    |****|****|    |    |    |    |    |
|****|****|    |****|****|    |    |    |    |    | 
|****|****|    |****|****|    |    |    |    |    |  
|****|****|    |****|****|    |    |    |    |    |   
   0    1    2    3    4    5    6    7    8    9  


Which light do you select?  1



|    |    |****|****|****|    |    |    |    |    |
|    |    |****|****|****|    |    |    |    |    | 
|    |    |****|****|****|    |    |    |    |    |  
|    |    |****|****|****|    |    |    |    |    |   
   0    1    2    3    4    5    6    7    8    9  


Which light do you select?  3


|    |    |    |    |    |    |    |    |    |    | 
|    |    |    |    |    |    |    |    |    |    |  
|    |    |    |    |    |    |    |    |    |    |   
|    |    |    |    |    |    |    |    |    |    |
   0    1    2    3    4    5    6    7    8    9   


You win! Well done.

Submission: Be sure to submit your CS5App.java file under homework 8, problem 2.

Extra Credit: For extra credit (of up to 10%), include an "undo" feature in your lights out game. In this situation, if the user types -1 at the prompt, your program should undo the last move the user made. If the user types -1 again, it should undo the move before that, and so on, all the way back to the starting configuration of the lights. However, if the user types -1 when she or he is at the starting configuration of lights, your program should simply indicate that no more "undoing" is possible and redisplay the same starting configuration again. To process undos, you will want to keep track of the user's moves in (what else...) an array! You may assume the game will not go past 1000 moves, so that your array of moves can be of size 1000.

If you do the extra credit, simply add the "undo" feature to your Hw8Pr2, indicate that you've done the EC in the comment at the top of the file, and submit it as that problem (as you ordinarily would).

Problem 3 Many drunken walks... (5 EC points) [topic: using arrays and methods]

Extend your random walk, Hw6Pr1, which accepts a width w from the user, and allow it to run in two different ways:

absorbing: in this situation the walker stops whenever a wall is hit. The walker should take an arbitrary number of steps and report the number of steps taken before a wall is hit.
reflecting: in this situation the walker reverses their direction whenever a wall is hit. In this case, the walker takes a fixed number of steps (which it gets from the user).

You should write a different function for each of these modes. I recommend you write the following:

public static void absorb(int w, int [] stats, boolean debug)
public static int reflect(int w, int n, int [] stats, boolean debug)

The stats argument should contain 2*w+1 elements. Each time the user enters a lane (some position value between -w and w), the appropriate index in this array should increment by one. Thus stats reflects the frequencies with which the user was in different locations along the walk. The boolean argument should turn on and off the walk's corresponding ASCII printing (which can be useful for debugging, but a real drag when you're simulating 1000 walks in total). The n argument is only used in the reflect walk case (and indicates how many steps the user should take). In the absorb case, the integer returned should be the number of steps taken until a wall has been hit.

The main goal of this problem is to see what kind of distribution over lanes one could have with a random walk of this sort. To do this, you need to run the walk multiple times. Let t be the number of times the walk is repeated.

At the beginning of main, the user should be asked to enter values for w, t, and n, after which the user should be allowed to choose from among the following options:

Reset the stats array (set all its values to 0).
Print out the contents of the stats array.
Draw a histogram of the stats array (I've provided some code to help you get started on this).
Run an absorbing or reflecting walk once (with debugging on).
Run t absorbing or reflecting walks (with debugging off). In this case, you'll first reset stats, run the walks, and then display the histogram.
Quit, which leaves main.