| CPSC 124 | Introduction to Programming | Spring 2024 |
This week's lab focuses on arrays. The power of arrays comes from the ability to refer to a particular slot using an integer index - because that index can be calculated as the program runs. This lab will give you some practice with two major ways in which arrays are used: "sequential access" applications where arrays are used to conveniently manipulate collections of things (such as in the Reverser example from class), and "random access" applications where the ability to calculate array indexes is exploited (such as in the DiceCounter example from class).
Labs and projects are for practice and learning. While it can be very productive to work on problems with your peers, it is also easy to underestimate how much you yourself understand and can do in such situations — so often something looks easy when someone else does it! With this in mind, you should always make the first attempt on a problem or programming task yourself using only the resources provided for the course (textbook, slides and examples posted on the schedule page, other resources linked on the course webpages). After that point, you are encouraged to come to office hours and/or go to Teaching Fellows. You may not collaboratively write solutions or code, and you may not copy solutions or code written by others, even if you contributed ideas.
You can discuss specific exercises with other students in general terms — such as how you might get started on that problem, or how or when to use various programming constructs, or strategies for debugging — but how to use a particular programming construct to solve a specific problem or debugging a particular program should only be discussed in office hours or with the Teaching Fellows.
Arrays are variables rather than statements like if statements and for/while, so in most cases you need to first recognize that you need to store information (what variables are for) and then the question is whether you have many values of the same kind (both Java type and in terms of meaning). If so, an array is appropriate; if not, you should have separate variables.
Once you have determined that an array is appropriate, identify the pattern of usage:
If you are working with a collection of things as a collection, you will fill up the slots of the array from the beginning and will typically write loops to do something to each slot of the array (initialize it, update it, print it, etc). (This is "sequential access".) Recall the "for each slot of the array" pattern from class to get you started when you have a "for each slot of the array" task in your program.
If you are doing clever indexing (i.e. "random access"), consider how you will use the slots of the array - what values will go where? For example, in DiceCounter, the count of the number of times the sum sum was rolled was stored in slot sum. In the birthday example in the reading, the days of the year were numbered 0 to 364 and the corresponding slot in the array held whether or not someone with that day as a birthday had been found already. Once you have what values are stored where worked out, usage of the array in the program boils down to computing the right index when you need to refer to a slot.
Note that these patterns are not mutually exclusive. For example, you will often use a "for each slot of the array" loop to initialize the array in a clever indexing application. DiceCounter has this, and a modified version of the "for each slot" loop to print out the counts at the end.
While most of the time an array is used to facilitate management of what would otherwise be a bunch of separate but similar variables, an array can also be used to facilitate sequential or random access to what would otherwise be a bunch of separate values.
In the sequential case, an array can be used to allow loops when the change between repetitions doesn't have a nice pattern, such as in the ColorSpots example from class. An example of the random access case will be seen in the exercises.
As this usage of arrays doesn't stem from needing to store information, it needs to be recognized on its own.
For all exercises:
Utilize incremental development, keeping in mind two key strategies: use placeholder variables so you can implement (simpler) parts of the task before tackling the computation of those values, and tackle more complex tasks by first solving a slightly modified (and simpler) version of the problem first.
Employ good programming style, including choosing descriptive variable names and autoformatting your code.
Include your name and a description of the program in each program.
A histogram is a graph that shows the frequency of numerical data.
Write a program called Histogram which creates an array containing 10 random numbers between 0 and 20 (inclusive) to simulate frequency data, then prints out a histogram using those values as shown below.
For example, for an array { 17, 8, 0, 5, 14, 9, 6, 6, 3, 6 }:
(17) ################# ( 8) ######## ( 0) ( 5) ##### (14) ############## ( 9) ######### ( 6) ###### ( 6) ###### ( 3) ### ( 6) ######
Each line should start with the number in the array in parens, followed by a space and a number of # symbols equal to that value. (Use formatted output as described in section 2.4.1 to pad 1-digit numbers with spaces so that things line up nicely.)
A Magic 8 Ball can be used to answer life's difficult questions: simply ask it a yes-no question, and it will reply.
Write a program called Magic8Ball to simulate a Magic 8 Ball: it should get a question from the user, then randomly select and print a response.
The possible responses are:
(Note that the program doesn't actually do anything with the question the user types in — it reads it in, but no use is made of that value later in the program.)
Your program must be reasonably compact and elegant — use an array in order to avoid a big if statement to choose a response, and write it so that if you wanted to change the possible responses (either the number of responses or what the responses are), you'd only have to change the array initialization.
But how to use an array? Think about this before revealing what is below.
This is a version of the clever indexing pattern. Use an array to store the possible responses. (Use the initializer list syntax to conveniently initialize the array; see the ColorSpots example from class for an example.) To pick a random response, randomly pick an array index and print the response stored at that slot in the array.
In the dice game Pig, a player's turn consists of rolling a single die until either a 1 is rolled or the player chooses to stop rolling. If a 1 is rolled, the player scores nothing for that turn. If the player chooses to stop rolling, the sum of all of the values rolled on that turn is added to the player's score. Players take turns, and the first player to accumulate 100 points wins.
Write a program called Pig which prompts the user for the number of players (two or more) and then carries out a game of Pig.
Your program's output should be similar to the following: (user input is indicated with bold underline)
enter the number of players (at least 2): 1 invalid number! enter the number of players (at least 2): 3 player 0, do you want to roll? [y/n] y you rolled: 6 player 0, do you want to roll? [y/n] y you rolled: 1 end of turn current scores: player 0: 0 player 1: 0 player 2: 0 player 1, do you want to roll? [y/n] y you rolled: 6 player 1, do you want to roll? [y/n] y you rolled: 6 player 1, do you want to roll? [y/n] n you scored 12 points on this turn current scores: player 0: 0 player 1: 12 player 2: 0 player 2, do you want to roll? [y/n] y you rolled: 3 player 2, do you want to roll? [y/n] y you rolled: 1 end of turn current scores: player 0: 0 player 1: 12 player 2: 0 player 0, do you want to roll? [y/n] y you rolled: 5 player 0, do you want to roll? [y/n] y you rolled: 1 end of turn current scores: player 0: 0 player 1: 12 player 2: 0
(...the game goes on for a while...)
player 2, do you want to roll? [y/n] y you rolled: 3 player 2, do you want to roll? [y/n] y you rolled: 2 player 2, do you want to roll? [y/n] y you rolled: 4 player 2, do you want to roll? [y/n] y you rolled: 5 player 2, do you want to roll? [y/n] n you scored 14 points on this turn current scores: player 0: 95 player 1: 60 player 2: 78 player 0, do you want to roll? [y/n] y you rolled: 4 player 0, do you want to roll? [y/n] y you rolled: 6 player 0, do you want to roll? [y/n] n you scored 10 points on this turn player 0 has won with 105 points!
Be sure to include all of the elements shown:
As with other more complex programs, start by outlining the necessary steps in English first. Also consider how arrays are useful and what array usage pattern is applicable before revealing what is below.
Each player has their own score, so the array stores the collection of player scores. This is really a "clever indexing" pattern as player i's score will be stored in slot i, but there are a number of places where a "for each slot in the array" loop is needed.
As you start to translate the English steps into code, keep in mind the idea of solving smaller, simpler problems first. For example, you could start with getting a valid number of players. When that works, do player 0's turn. When that works, update player 0's score and print all the player scores. Then repeat the turn and score printing until the game is over. Finally, detect and congratulate the winner. An alternative approach is to start with a single-player version of the game: take turn, print score, take turn, print score, etc until the one player's score gets to 100. When that works, expand to multiple players by repeating the one player actions for each player.
Imagine a promotion in which every time you buy a product, you get one of 8 different prizes. On average, how many products do you have to buy in order to collect a full set of the prizes?
Armed with an understanding of probability, you could derive a formula giving the answer. You can also solve the problem by writing a program to simulate the prize-collection process: generate random numbers to represent which prize is obtained each time you make a purchase, and count how many times that is done before you get all the prizes. Then repeat the whole process many times and compute the average number of purchases made to obtain the final answer.
Write a program called PrizeCollectorSim which asks the user for the number of different prizes available (8 in the example given in the first paragraph), then uses the simulation method described above to compute the average number of purchases needed to obtain a complete set of prizes.
How are arrays useful here? (What do you need to store that you have many of? Can you think of an example of a similar situation and how the problem was solved in that case?) What array usage pattern is this? Develop the pseudocode for the program and think about these answers before revealing what is below.
You need to keep track of which prizes have been obtained so far, so you can tell when you have the full set. However, instead of keeping a list of the prizes obtained and adding to that list each time a new prize is gotten, an alternative (which is easier to implement) is to start with a list of all of the possible prizes and then check each prize off as it is obtained — all prizes remain on the list, but some will be crossed off. Thus, the "many values" is keeping track of the crossed off/not crossed off status for each prize.
This is the "clever indexing" pattern, since we need to be able to locate the crossed off/not crossed off status for a particular prize. Since "crossed off/not crossed off" is two possible values, a boolean array is appropriate for keeping track of which prizes have been obtained — let slot i of the array store the value true if prize i has been obtained, and false if not. (This might remind you of the birthday problem. While it isn't exactly the same — in the birthday problem we go until we get the first repeated date, while here we go until we get all of the prizes — the idea of boolean values to track the status of a bunch of somethings is common.)
When a new random number is generated, consult the array — if that slot of the array holds the value true, that prize has already been obtained; if it is false, this is a new prize. Change the slot's value to true to reflect that that prize has now been obtained, then repeat until all of the prizes have been obtained.
As with other more complex programs, start by outlining the necessary steps in English first. Cover the whole program at a broad level, then work on writing the code for a simpler version of the problem: get one round working (choose random prizes until all of the prizes have been obtained, then print the number of purchases needed) first. Once that works, repeat one round the desired number of times (still printing the number of purchases each time), then finally add in what is needed to compute the average.
For extra credit, create a separate program PrizeCollectionSimGrapher which combines this exercise with #1: ask the user for a number N, compute the average number of purchases needed for each number of prizes between 2 and N, and then show these values using a histogram. Scale the number of # symbols printed — if x purchases are needed, print 2x # symbols.
Don't forget to hand in your work when you are done!
As in lab 2 (and all labs), grading will be based on both functionality and style. Style means following the good programming style conventions outlined in lab 2, as well as producing reasonably compact and elegant solutions. "Reasonably compact and elegant" means that your program is not significantly longer or more complex than it needs to be. In particular, you must use loops when loops are appropriate — achieving repetition by copying-and-pasting a bunch of code will not earn credit.