Your answers to these questions should be reasonable C++ code; minor syntactic errors are acceptable, but the intent of the code should be clear from what is written.

1. Create a tic-tac-toe class. There should be four public member functions:

   1. clear - clear the board and start a new game; clear accepts no arguments and returns no value. Either player (X or O) may go first after the board has been cleared; after that moves strictly alternates between the two players.

   2. move - put an X or an O on the board; move accepts two arguments, one indicating the marker to place (X or O) and the other indicating a square on the board receiving the marker. move should return true if the move was legal and false if the move is not legal. A move is illegal if the square already has a marker or if the move is out of turn (for example, O moving twice in a row).

   3. winner - if the game is over, return the winner's marker. If the game is not over, return an indication that there is yet no winner.

   4. The default constructor - this should leave the board cleared for a new game.

   You may use whatever representation for markers and board squares you find convenient; you may also use whatever private members you feel necessary.

   ---

   class ttt {
   
     public:
   
       ttt() {
         clear();
         next_move = empty;
         }
   
       void clear(void) {
         for (int i = 0; i < 3; i++)
           for (int j = 0; j < 3; j++)
             borad[i][j] = empty;
         }
   
       char winner(void) {
         if (check_board(0, 0,  1, 1,  2, 2)) return board[0][0];
         if (check_board(0, 2,  1, 1,  2, 0)) return board[0][2];
         for (int i = 0; i < 3; i++) {
           if (check_board(i, 0, i, 1, i, 2)) return board[i][0];
           if (check_board(0, i, 1, i, 2, i)) return board[0][i];
   	}
         }
   
       bool move(char mover, int square) {
   
         if ((mover != cross) && (mover != nought))
           return false;
         if ((next_move != empty) && (next_move != mover))
           return false;
         if ((square < 1) || (9 < square))
           return false;
   
         const int x = (square - 1)/3;
         const int y = (square - 1) % 3;
         if (board[x][y] != empty)
           return false;
   
         board[x][y] = mover;
         return true;
   
         if (mover == cross)
           next_move = nought;
         else
           next_move = cross;
         }
   
     private:
   
       bool check_board(int x1, int y1, int x1, int y1, int x1, int y1) {
        return (board[x1][y1] == board[x2][y2]) && 
   	    (board[x2][y2] == board[x3][y3]) && (board[x1][x1] != empty)
        }
   
       const char empty = ' ';
       const char cross = 'x';
       const char nought = '0';
   
       char board[3][3];
     };
   
   

   ---

2. The function

   void largest_square(int mtx[][], int m, int n);
   

   accepts an m-by-n matrix mtx and finds the largest square it could find in mtx. A square is defined by a square of mtx elements that contain 1s; the values in the elements inside the square don't matter. Write the body of the function largest_square().

   ---

   // The largest size for a matrix in either dimension.
   
      static const int mtx_size = 25;
   
   
   // Represents a square.
   
      struct square {
        int upperleft_x, upperleft_y;	// The square's upper-left corner.
        int size;				// The square's size.
        };
   
   
   
   static int find_largest_square_size(
     const int mtx[][mtx_size], int x, int y, int X, int Y) {
   
     // Given the X-by-Y matrix mtx, return the size of the largest square with an
     // upper left corner at mtx[x, y].  Return 0 if there's no such square.
   
     if (mtx[x][y] != 1)
       return 0;
   
     int size = 1;
     while ((x + size < X) && (y + size < Y)) {
       for (int i = 0; i <= size; i++) {
         if (mtx[x + size][y + i] != 1)
   	return size;
         if (mtx[x + i][y + size] != 1)
           return size;
         }
       size++;
       }
   
     return size;
     }
   
   
   square find_largest_square(const int mtx[][mtx_size], int X, int Y) {
   
     square s;
     s.upperleft_x = s.upperleft_y = s.size = 0;
   
     for (int x = 0; x < X; x++)
       for (int y = 0; y < Y; y++) {
         int size = find_largest_square_size(mtx, x, y, X, Y);
         if (size > s.size) {
           s.size = size;
           s.upperleft_x = x;
           s.upperleft_y = y;
           }
         }
   
     return s;
     }    
   
   
   
   

   ---

3. The function

   void merge_files(const string file_names[], int n)
   

   accepts a list of n text-file names and merges the text in each file into a single text-file named merged-files.txt. merge_files() merges by reading a line of text from file_names[i] and writing it to the output file merge-files.txt for 0 <= i < n. The input files do not have the same number of lines; as each input file end-of-file, it is dropped from the merge. When all input files are empty the merge is over.

   For example, if merge_files() is called with the three input files

   file-1:		  file-2:	   file-3:
   
     file 1 line 1	    file 2 line 1    file 3 line 1
     file 1 line 2			     file 3 line 2
   				     file 3 line 3
   

   then it will create the output file

   merged-files.txt:
   
     file 1 line 1
     file 2 line 1
     file 3 line 1
     file 1 line 2
     file 3 line 2
     file 3 line 3
   

   Write the body of merge_files().

   ---

   #include <fstream>
   #include <string>
   #include <cstdlib>
   
   void merge_files(const string filenames[], int filename_cnt) {
   
     ifstream * if_streams = new ifstream[filename_cnt];
     int i;
   
     for (i = 0; i < filename_cnt; i++) {
       if_streams[i].open(filenames[i].c_str());
       if (!if_streams[i]) {
         cerr << "Error during " << filenames[i] << " open.\n";
         exit(EXIT_FAILURE);
         }
       }
   
     const string of_name = "merged.files";
     ofstream ofs(of_name.c_str());
     if (!ofs) {
       cerr << "Error during " << of_name << " open.\n";
       exit(EXIT_FAILURE);
       }
   
     int files_left = filename_cnt;
     do {
       files_left = filename_cnt;
       for (i = 0; i < filename_cnt; i++) {
         string line;
         if (getline(if_streams[i], line))
   	ofs << line << "\n";
         else
   	files_left--;
         }      
       }
     while (files_left > 0);
   
     ofs.close();
     if (!ofs)
       cerr << "Error during " << of_name << " close.\n";
   
     for (i = 0; i < filename_cnt; i++)
       if_streams[i].close();
   
     delete [] if_streams;
     }
   

   ---

4. The function sort_shelf()

   void sort_shelf(
     const book shelf[], int cnt, book * by_author[], book * by_call_number[]);
   

   accepts an array of cnt books and sorts them in two ways: by author and by call number. Because a book contains a lot of information, the sorted arrays do not contain the books themselves, but rather pointers to the books in shelf.

   Write the function sort_shelf(). You may assume that author and call_number are public string members of the class book, and that by_author and by_call_number contain at least cnt elements.

   ---

   #include <string>
   #include <cassert>
   
   struct book {
     string author;
     string call_number;
     };
   
   
   void sort_shelf(
     const book shelf[], int cnt, book * by_author[], book * by_call_number[]) {
   
     int i;
   
     for (i = 0; i < cnt; i++) 
       by_call_number[i] = by_author[i] = &shelf[i];
   
     for (i = 0; i < cnt; i++) {
       int smallest = i;
       for (int j = i + 1; j < cnt; j++)
         if (by_author[smallest]->author > by_author[j]->author)
   	smallest = j;
       book * bp = by_author[smallest];
       by_author[smallest] = by_author[i];
       by_author[i] = bp;
       }
   
     for (i = 0; i < cnt; i++) {
       int smallest = i;
       for (int j = i + 1; j < cnt; j++)
         if (by_call_number[smallest]->call_number > by_call_number[j]->call_number)
   	smallest = j;
       book * bp = by_call_number[smallest];
       by_call_number[smallest] = by_call_number[i];
       by_call_number[i] = bp;
       }
   
     }
   
   
   int main() {
   
     string authors[] = { 
       string("zola, emile"), string("atwood, margaret"), string("melville, herman")
        };
     string call_numbers[] = {
       string("a 1"), string("z 1"), string("m 1")
       };
   
     book shelf[3];
     for (int i = 0; i < 3; i++) {
       shelf[i].author = authors[i];
       shelf[i].call_number = call_numbers[i];
       }
   
     book * by_author[3];
     book * by_call_number[3];
     
     sort_shelf(shelf, 3, by_author, by_call_number);
   
     assert(by_author[0]->author == authors[1]);
     assert(by_author[1]->author == authors[2]);
     assert(by_author[2]->author == authors[0]);
   
     assert(by_call_number[0]->call_number == call_numbers[0]);
     assert(by_call_number[1]->call_number == call_numbers[2]);
     assert(by_call_number[2]->call_number == call_numbers[1]);
     }
   

   ---

This page last modified on 27 August 2001.