Lab 9: Image Manipulation

Part 1: Recurse a Bit

  1. Compile and run the following program
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    double harm(int i, int N) {
      if( i > N )
        return 0;
      return 1.0/i + harm(i+1, N);
    int main() {
      int n;
      cin >> n;
      cout << "harm(" << n << ") = " << harm(1,n) << endl;
      return 0;
    ... that computes the first n terms of the harmonic series, 1/1 + 1/2 + ... 1/n using a recursive function. Try it out on a few values, then try it on a big value. The program crashed, eh? Why? A running program has some fixed amount of space allocated to the stack of function calls. If you force a whole bunch of recursive calls like this, you exceed that space. That's called "blowing the stack". So we tend not to use recursion for things like this. But it's good practice for us!
  2. Write a recursive (no loops allowed!) definition of the function printSpaced in the program below. Keep an eye on the previous example. This function prints out its input array elements from index i to N. Elements should be separated by spaces!

    Note: You'll see that "main" looks different and the first line inside of it references "argc", "argv" and "atoi", which are all things we haven't covered. We're using these here so that you can optionally run the program with a number as the command-line argument that will be used to seed the random number generator.

    Here's how the command-line argument thing works:
    1. define main with prototype
      int main(int argc, char** argv);
    2. when the program is run, parameter argc will be the total number of strings on the command line (including the program name itself, e.g. "./a.out")
    3. when the program is run, parameter argv is an array of c-style strings containing the strings that appeared on the command line

    So, if you compile this program as the executable lab09 and run it

    ~/$ ./lab09 281
    ... then
    • argc is 2,
    • argv[0] is "./lab09", and
    • argv[1] is "281".

    The function atoi (defined in cstdlib) takes a c-style string and returns the integer that string represents.
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    // prints the elements of array A (that has N elements) from index i to the end
    // should be space separated, and there should be a newline at the end.
    void printSpaced(int* A, int i, int N);
    int main(int argc, char** argv) {
      // if run with a command-line argument x, seed with x (else use current time)
      srand(argc < 2 ? time(0) : atoi(argv[1]));
      // Create a randomish array to use as input to printSpaced
      int N = 10 + rand() % 20, K = N / (2 + rand() % 5);
      int *A = new int[N];
      for( int i = 0; i < N; i++ )
        A[i] = i % K;
      // Call printSpaced (and cross fingers!)
      return 0;
    Call your program part1.cpp. If you've done this right, printspaced should print out the array nicely, like this:
    ~/$ ./part1 2017
    0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 
    ~/$ ./part1 2019
    0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 0 

    Submit as: ~/bin/submit -c=SI204 -p=Lab09 part1.cpp

  3. Going further (if you've finished Parts 2 and 3): make it print comma-separated!
  4. Going still further (if you've finished Parts 2 and 3): write a recursive (no loops allowed!) version of search (assume arrays of strings). I recommend starting with the following prototype:
    // In : array A of N elements, i such that 0<=i<=N, and search string x
    // Out: index k, i<= k < N, such that A[k] matches x, or N if no such k exists  
    int search(string* A, int i, int N, string x);

Part 2: sorting fish ... more cards? Really?

Check out this program, which is a start at implementing a game of Go Fish. Right now, the game simply deals out seven cards to two players, and prints out those players' hands. Modify the program so that the hands are printed out sorted by face value (smallest to largest) with ties broken by suit (clubs before diamonds before hearts before spades). Call your program part2.cpp. Here are some sample runs:
~/$ ./part2 2017
Player1:  2♣  3♥  4♥  9♠ 10♥  K♣  K♥
Player2:  5♣  6♠  8♣  9♥  J♠  Q♥  Q♠  
~/$ ./part2 2019
Player1:  5♦  6♥  6♠  7♠  9♥  K♠  A♠
Player2:  4♥  7♦  9♦  Q♦  Q♠  K♦  A♥  

Submit as: ~/bin/submit -c=SI204 -p=Lab09 part1.cpp part2.cpp

Part 3: searching for fish ... yep, more cards!

Add on to your Part 2 solution (call the new program part3.cpp) so that the program alternately asks player1 and player2 to choose a face to ask for (2,3,...,10,J,Q,K,A are the possible responses), and responds with either "yes" or "go fish", depending on whether there is a card having the chosen face. No matter which response, have the game simply deal the asking player another card, reprint (in sorted order of course), and continue. This should of course stop when the deck is empty, and it should also stop if X is entered as a card choice.
~/$ ./part3 2019
Player1:  5♦  6♥  6♠  7♠  9♥  K♠  A♠
Player2:  4♥  7♦  9♦  Q♦  Q♠  K♦  A♥
Player1 choose card: A

Player1:  5♦  6♥  6♠  7♠  9♥  J♣  K♠  A♠
Player2:  4♥  7♦  9♦  Q♦  Q♠  K♦  A♥
Player2 choose card: 3
go fish

Player1:  5♦  6♥  6♠  7♠  9♥  J♣  K♠  A♠
Player2:  4♥  7♦  9♦  J♥  Q♦  Q♠  K♦  A♥
Player1 choose card: 10
go fish

Player1:  3♣  5♦  6♥  6♠  7♠  9♥  J♣  K♠  A♠
Player2:  4♥  7♦  9♦  J♥  Q♦  Q♠  K♦  A♥
Player2 choose card: J

Player1:  3♣  5♦  6♥  6♠  7♠  9♥  J♣  K♠  A♠
Player2:  4♥  7♦  9♦  J♥  Q♦  Q♠  K♦  A♣  A♥
Player1 choose card: X
To make your life a bit easier, and to allow you to concentrate on search, which is what this is really about, I'm gifting you the following function:

// In:  string s representing a face value or a full card (e.g. "10" or "J")
// Out: the facevalue (2-14) represented by the string 
int stringToFaceValue(string s);

int stringToFaceValue(string s)
  char c = s[0];
  int fv = c - '0';
  if (c == '1') fv = 10;
  if (c == 'J') fv = 11;
  if (c == 'Q') fv = 12;
  if (c == 'K') fv = 13;
  if (c == 'A') fv = 14;
  return fv;

Submit as: ~/bin/submit -c=SI204 -p=Lab09 part1.cpp part2.cpp part3.cpp

Part 4: (optional) Going Further ... Go Fish

Now make a full Go Fish game. In the complete game you could have player2's cards not printed out, and have player2 just randomly choose a card from his deck to ask for. If you were really ambitious, you could write it so player 2 followed a sophisticated strategy!