APCS Workshop, First Day

Introduction

This document is meant be be read both as a stand-alone document and as a hypertext document. Thus some of the code will be accessible in an appendix to the material you receive, but will also be immediately accessible by following links if the document is viewed online.

Classes and libraries used include:

• apstring The AP string class, based on the standard C++ string class, declared in apstring.h and implemented in apstring.cpp.

• apvector The AP vector/array class, a templated, growable, safely indexable class, based on the standard C++/STL (standard template library) vector class, declared in apvector.h and implemented in apvector.cpp.

• Dice A class that encapsulates simple random number generation (between 1 and the number of 'sides' on a die), declared in dice.h and implemented in dice.cpp.

• RandGen A class used by the Dice class, that generates random integers and reals (int and double), declared in rando.h and implemented in the rando.cpp

• A standard library of functions to manipulate characters declared in <ctype.h> (this library is not part of the APCS subset.)

• A library of prompting functions declared in prompt.h and defined in prompt.cpp

Vectors, Strings, Dice, and C++

We'll discuss two programs as a springboard to the syntax and semantics of C++. These two programs are:

• dicevec.cpp a program to roll two dice thousands of times and track the number of times each roll occurs.

• letters.cpp, a program for tracking how many times every alphabetic character occurs in a text file.

Sample Runs

        how many rolls 10000
        roll            # of occurrences
        2               247
        3               548
        4               800
        5               1180
        6               1364
        7               1672
        8               1381
        9               1105
        10              838
        11              563
        12              302

Here is a run of letters.cpp using a data file that stores The Scarlet Letter by Nathaniel Hawthorne.

   enter name of input file: data\hawthorne.txt

   a  29380   7.6%
   b   5672   1.5%
   c   9571   2.5%
   d  15972   4.2%
   e  50853  13.2%
   f   9317   2.4%
   g   7091   1.8%
   h  26624   6.9%
   i  26445   6.9%
   j    282   0.1%
   k   2351   0.6%
   l  16336   4.2%
   m  10312   2.7%
   n  25435   6.6%
   o  27513   7.2%
   p   6840   1.8%
   q    337   0.1%
   r  24075   6.3%
   s  24265   6.3%
   t  36509   9.5%
   u   9861   2.6%
   v   3680   1.0%
   w   8839   2.3%
   x    461   0.1%
   y   6534   1.7%
   z    152   0.0%

Group Activity

1. Modify letters.cpp so that a vector of 26 entries is used rather than a vector of CHAR_MAX entries. Try to isolate dependencies on a particular character set, e.g., ASCII, Unicode, etc.

2. Modify letters.cpp so that different word-lengths are tracked rather than character occurrences. The output of the program should be the number of 2 letter words, 3 letter words, etc.

3. show-me Modify dicevec.cpp to track how many times each sum occurs when three twelve-sided dice are rolled. Try to design the program to make it simple to change the number of sides and the number of dice used.

Lab Activity

Because this first morning's lab may be short, we suggest picking a small program to start with from among the group programs above (suggestions are given below). An additional problem is also suggested.

1. You should first use one of the project templates (see the write-up for your system) to get the program dicevec.cpp running.

2. When you've figured out how to make dicevec.cpp run, modify the program to roll three 12-sided dice and print the number of times each possible sum occurs.

3. Change the program used in the project so that letters.cpp is the active program. Run the program on poe.txt and hawthorne.txt (both in the subdirectory data).

   Modify the program so that it tracks both lower case letters and upper case letters separately. Print the output in a format like the one below (or use another format if you prefer).

      enter name of input file: data/hawthorne.txt
      a  28647   7.4%                 A    733  0.2%
      b   5350   1.4%                 B    322  0.1%
      c   9119   2.4%                 C    452  0.1%
      d  15697   4.1%                 D    275  0.1%
      e  49691  12.9%                 E   1162  0.3%
      f   9212   2.4%                 F    105  0.0%
   

4. In the dice game Yahtzee, five 6-sided dice are rolled (in the actual game the player can re-roll some of the dice during each "turn".) Write a program that simulates the rolling of five six-sided dice and determines how many times all five dice show the same number --- five of a kind --- in a large number of rolls (entered by the user). Think (you don't write code, think of how) about how you could modify the program to track how many times 3 of a kind, 4 of a kind, and a full house (2 of one kind, 3 of another) occur in addition to five of a kind.

Lunch

Random Walks, Dice, Classes, and C++

We'll go over any issues that came up from the morning lab session. Then we'll begin to work on turning the random walk program frogwalk.cpp into a class-based program. In addition to providing experience with classes, this will let you modify the program to have several "frogs" walking randomly at the same time. The group activities will center on language issues and class issues (changing a program to be class-based).

The program frogwalk.cpp simulates a one-dimensional random walk. The output is the final position of a "frog" that takes n steps (where n is a value entered by the user). The class Frog is declared (the declaration is not complete) in the header file frog.h. Three member functions are declared (in addition to the constructor) and no private instance variables are included in the declaration.

Group Activity

1. Modify frogwalk.cpp so that instead of walking for a fixed number of steps, the user is prompted for a distance from the origin. The frog should walk until it is that distance from the origin (in either the positive or negative direction). The output of the program is the total number of steps taken by the frog.

2. Track how many times all locations from -15 to +15 are visited, and use two extra variables to represent negative and positive infinity (all locations less than -15 and greater than +15, respectively.) Think about how you'd modify the program to track all locations, not just those in the range [-15 .. 15].

   When the random walk is finished, print/graph/output the number of times each location is visited.

3. Using the class Frog declared in frog.h, decide what additional member functions (if any) are needed and what private variables are needed to implement the member functions. You should think about how the Frog class will be used in programs. At the very least, it should be possible to have two Frog objects "walking" in one program, with the program tracking how many times the frogs occupy the same location during the walk. The member functions you specify will depend to a large extent on how you envision the Frog class being used. You should also think about what modifications are needed to have a Frog class that walks in two dimensions (x and y) but that is restricted to staying on lattice points, i.e., points with integer coordinates.

   You may design a basic Frog class that can be extended for particular frog "experiments". You might consider, for example, how a frog could be constrained to engage in a random walk in the range [-N..N], and walk until all 2N+1 locations have been visited, reporting the time needed until this happens.

4. show-me Design public and private member functions and private/instance variables for a complete Frog class. Provide the implementation of member function Frog::TakeTurn that tracks at least the locations in the range [-N..N] (for some constant N) visited by a Frog object.

Lab Activity

As a first step, implement your frog class by creating a frog.h header file and a frog.cpp implementation file (make sure that frog.cpp is in your project.) You can include a main function in frog.cpp as a first step, but you'll need to create a separate file/program at some point so that frog.cpp consists only of member functions of the class Frog. However, for many of the problems below, it will be easier to include the Frog member functions and main (and supporting functions) in the same file.

Your Frog class may have more functionality than needed to work on the problems below. Please feel free to embellish these exercises using your fertile imagination. No order is implied after the first of the programs outlined below, you can implement those that seem intriguing or interesting.

1. Write a program that creates two frog objects, both of which walk for some specified number of steps. The output of the program should be the final position of both frogs and the number times the two frogs occupy the same position.

2. Write a program that creates three frogs and tracks how many times all three frogs occupy the same location as well as how many times two frogs occupy the same location.

3. Modify the Frog class and write supporting functions to derive a relationship for how many steps are needed for one frog to visit all 2n+1 locations where a walk is constrained to take place in the range [-n .. n] on the x-axis. When a frog hits an endpoint (-n or n) you should try a few alternatives and see if the different behavior affects the relationship you derive from your program:
   • A frog at an endpoint steps around to the other end as needed, e.g., the walk is a circle with 2n+1 points on the circle (think how integers wrap from INT_MIN to INT_MAX).

   • A frog at an endpoint always moves in the other direction (away from the endpoint) when taking a step.

   • A frog either moves back (away from the endpoint) or stays where it is, with equal probability.

4. Repeat the previous experiments, but for two-dimensional walking frogs where the frogs are constrained to walk on a square (2N+1) x (2N+1) grid, e.g., x and y coordinates might be restricted to be between -10 and 10 for a 21 x 21 grid. Use one (or all three) of the options in the previous problem for when a frog reaches an "edge" of the world. You'll probably want to use the apmatrix.h class.

5. Write the results of a one, two, or three frog walk to a file in a format that can be easily graphed using Excel (or some other spreadsheet). Generate colorful and illuminating (both physically and intellectually) graphs for the walk.

Extra Activities

1. Write a program to play a non-graphical, interactive version of the word-game hangman. The user should guess a word "picked" by the computer. You can start by storing a few words as constants in an array initialized when the program is run, or read words from a file (or just use one word to get the program running, then add more words).

2. Write a program (using a class-based or non-class based) approach to solve the flatworld problem from the internet programming contest. A description of flatworld is accessible. You'll want to develop your own test files, but you an also test and verify with the files used in the internet contest.
   1. flat.dat the data file
   2. flat.out the output file for flat.dat