Lab 7
                 Counting Sheep and Ending the World

  Introduction
  ============
  In this lab we will be working with arrays.  In the guided part, you
  will be implementing an array sort of your choice.  In the self lab
  part you will be modifying the tower of Hanoi problem.  The guided
  lab is pretty easy, as you just have to translate a little
  pseudocode into C++.  The second part will seem very simple, however,
  you have to do a fair bit of thinking and design to make it work.
  This is one of those "easy" problems that have lots of details, so
  take your time and be careful.  Most of all, as always, have fun
  getting the machines to do your bidding!


  Lab 7.1 (Guided) Counting Sheep 
  ===============================
  Having discovered how to count numbers and convert currency the
  world over, Reg and Stan have become fabulously wealthy.  Not only
  have they managed to turn the patent settlement with Rome into the
  largest Etruscan sheep farm ever seen before or since, but they have
  also made many friends and enemies throughout the whole ancient
  world.  Realizing that the Italian peninsula does not have enough
  need of sheep to sustain their vast fields, they have decided to
  branch out, and ship sheep with ships to foreign shores.  (Try to
  say that 3 times fast!)  However, they have hit a bit of a problem.

  "Stan, I am having trouble determining the best order to send the
  sheep out in."  Reg lamented one day.  "We have dozens of orders
  leaving every day, and they are too vast to juggle around.  Not to
  mention that the crates are very heavy!"

  "Hmmm..." Stan though.  "Perhaps we should hand this off to the
  boffins* down in the CS department."

  "That sounds like a great idea!  Maybe they'll have a way of
  correctly sorting large lists of data!"

  When Reg and Stan presented the problem to their crack team of
  computer scientists (a group who was about 2500 years ahead of their
  time), they decided that what Reg and Stan needed was a way to
  sort orders by country and due date.  They decided that they would
  have to have some way to store an entire order, but that no such
  method  had been developed yet.

  "Hey Stan, do you get the feeling we'll be showing up in a later
  lab?"  Reg asked.  "Indeed I do!" said Stan.

  So now, the CS department (that's you) set out to work on Stan and
  Reg's problem.  Because they didn't yet know how to store a whole
  sheep in a computer, they decided instead to store a sequence number
  and then sort those numbers.  The idea being that if they develop
  the sorting technique, they will then be able to apply it once they
  know how to store complex objects.  

  * Note: "Boffin" is part of Anglican slang, and Reg and Stan are
    modern British people who somehow live in ancient Tuscany. Look up
    the meaning of "boffin" and amuse your friends!


  Procedure
  =========
  We are going to develop a simple program that allows the user to 
  enter 20 items into an array.  The program will then sort the items
  and then print the sorted list.  A skeleton of the code is provided
  below: 

  --- begin array.cpp ---
  #include <iostream>
  #include "arrayFun.h"
  
  using namespace std;
  
  void sort(int ar[], int n);
  
  
  int main(void) {
    int ar[20];
    int i;
    
    //read in the values
    cout << "Enter 20 values." << endl;
    for(i=0; i<20; i++) {
      cin >> ar[i];
    }
  
    //sort the values
    sort(ar, 20);
  
    //print the array
    cout << endl << "The sorted array." << endl;
    printArray(ar, 20);
  
    return 0;
  }
  
  
  
  void sort(int ar[], int n) {
    /* TODO: Write Sort */
  }
  --- end array.cpp ---

  Clearly, a key piece is missing.  Namely, we are not yet sorting
  anything.  So here's what I want you to do:

  1.  Copy the arrayFun.h and arrayFun.cpp files which we developed in
      class into your working folder.  These are in my home directory,
      just do:
        cp ~relowe/arrayFun.* .
      To get them.  If you typed along with me on Monday's class, you
      already have them.

  2.  Enter the array.cpp code exactly as it is above.

  3.  Compile the program.  You can either write a makefile or you can
      just do the single line:
        g++ -o array array.cpp arrayFun.cpp

  4.  Implement your favorite sort algorithm in the sort function,
      replacing my "todo" comment.  The pseudocode used in class is on
      D2L, or you are welcome to look up and use other algorithms if
      you are feeling adventurous.  If you want to produce more than
      one version of this program, I'll add some extra credit to your
      lab 6.2 score!  (you'll want to list multiple array.cpp files in
      your turnin script file.)

  5.  Generate your script file showing a listing of array.cpp, your
      compile line, and a single test.



  Lab 7.2 (Self) Ending the World
  ===============================
  In the far east, within the capital city of Vietnam stands the tower
  of Hanoi.  Within this tower monks work endlessly on a puzzle moving
  golden disks between 3 pegs.  When they started, the first peg
  contained 64 golden disks.  Each disk is of a unique size, and they
  move them so that a large disk is never placed on a smaller disk.
  They only move one at a time, and when they place the last disk on
  the last peg, the world will end.  

  Ok, so as we discussed this story isn't real.  There aren't any
  Vietnamese monks counting down to the Earth's destruction, and even
  if there were, solving this puzzle with 64 disks would take a
  considerable amount of time.  The puzzle was really created by a
  French mathematician in the late 19th century, and whenever it was
  published, it was given a tale of some far off exotic place where
  an extreme version of the puzzle was being solved.  Over the years,
  Hanoi has emerged as the most likely place for the mythical tower,
  and so we now know this problem as "The Tower of Hanoi".  To refresh
  your memory, here is the solution we discussed in class.

  Suppose we start the puzzle with the following configuration:


      |       |      |
      #       |      |
     ###      |      |
    #####     |      |
   #######    |      |
      A       B      C

  Remember the basic strategy to move 4 disks to peg c is to first
  move 3 to B, then 1 to C, then move 3 from B to C.  This problem
  was our demonstration of recursive thinking, and we wound up with
  the following code:


  -- Begin hanoi.cpp --
  #include <iostream>
  #include <cmath>
  
  using namespace std;
  
  void solve(int n, char src, char dest, char spare) {
    if(n==1) {
      cout << "(" << src << ", " << dest << ")" << endl;
      return;
    }
  
    solve(n-1, src, spare, dest);
    solve(1, src, dest, spare);
    solve(n-1, spare, dest, src);
  }
  
  
  int main(void) {
    int num=4;
  
  
    solve(num, 'A', 'C', 'B');
    
    return 0;
  }
  -- hanoi.cpp --
  
  Note that I have modified it slightly so that instead of getting the
  puzzle size from the user, it is statically defined to be 4.  The
  reason for this is we have not yet looked at how to dynamically
  allocate an array, and so we're going to be modifying this program
  to work with a fixed size puzzle.

  Now, what your task is is to modify this program so that it draws
  the board after each move.  For instance, suppose we had the above
  problem.  The first move it makes is it moves 1 disk from A to C.
  Thus the first move would look like this:
  
  (A, C)
        |       |       |
        |       |       |
       ###      |       |
      #####     |       |
     #######    |       #
        A       B       C

  In order to this, you will need to keep track of the whereabouts of
  all the disks in the puzzle.  My setup does this by using 3 arrays,
  one for each post, with 4 elements.  These elements represent the
  disk numbers which are on the post.  So you can solve this using 3
  arrays of integers.  (Though that is certainly not the only way to
  do it.)  

  You should design your code to neatly draw the posts and the disks.
  I see a fair bit of iomanip in your future, but really aside from
  setting widths and centering, it's really pretty simple.  The hard
  part will be in figuring out how to move the disks around.  I
  recommend that you implement a "moveDisk" function which does this,
  as it will make your code easier to deal with.  I also recommend
  that you create a "printBoard" function to print based on your
  arrays.  You will also want to create an "initializeBoard" function
  which initializes the arrays to the starting position of the
  puzzle.  Finally, you will need to modify the solve function to
  accept your arrays as parameters, and use them when it actually
  makes a move.  Recall that the cout line is where the move is
  actually made.  This will be where you use your moveDisk and
  printBoard functions.

  The key to this program is having a good design.  I will be
  weighting the pseudocode more heavily this time, as I believe it
  will take a fair bit of contemplation to get right.  The pseudocode
  will be worth 40% of the lab grade.  In your psuedocode, I want to
  see the following:

     - How you plan to represent your posts.  Remember there are 5
       possibilities at each post position (one of the 4 disks, or an
       empty spot).  

     - A design for your modified solve function.
     
     - The design for your printBoard function.

     - The design for your moveDisk function

     - The design for your initializeBoard function


  HINTS
    - Modular decomposition is key to getting this program to work.

    - Look at setw and how to center fields in the iomanip
      documentation. 

    - You will not have to change the logic of solve, you will only be
      adding to the function.

    - Disks are easier to center if they have an odd number of
      characters.  Take a look at my disks above.

    - I want you to think about this problem very hard as you design
      it.  Don't over think it though.  Try working at a nice calm
      pace, and if you get stuck, look at something else for a little
      while.  I am looking for the most elegant solution you can
      create, and that means detailed pseudocode, and lots of time
      spent in deep contemplation of the arrays on your board.


  Extra Credit
  ------------
  If you read ahead and figure out how to make a dynamically allocated
  array, then you can write this program in a way that can accept any
  number of disks.  If you do this, then I will give you 10 points
  extra credit.  Note that this is tricky, and it has a far reaching
  effect on your rendering and initialization functions.  Get the
  official lab done first, then do the challenge.  


  Enjoy!