Chapter Exercises

Why is the array structure a better choice than the vector for implementing the 2-D array?

Explain why a multi-dimensional array is considered an abstraction.

What is the difference between row-major order and column-major order?

We examined two different approaches for organizing the elements of a 2-D array. What is the advantage of each approach?

Complete the Matrix class by implementing the __sub__, __mul__, and __transpose__ methods.

Develop the index equation that computes the location within a 1-D array for element (i,j) of a 2-D array stored in column-major order.

The 2-D array described in the chapter is a simple rectangular structure consisting of the same number of elements in each row. Other layouts are possible and sometimes required by problems in computer science. For example, the lower triangular array shown below is organized such that the rows are staggered with each successive row consisting of one more element than the previous row.

1. Derive an equation that computes the total number of elements in the lower triangular table for a table of size $m\times m$.
2. Derive an index equation that maps an element of the lower triangular table onto a one-dimensional array stored in row-major order.

Define a new class named TriangleArray to implement the lower triangular table described in exercise E3. above.

A grayscale digital image is a two-dimensional raster image in which the picture elements, or pixels, store a single value representing a shade of gray that varies from black to white. In a discrete grayscale image, the shades of gray are represented by integer values in the range [0 ... 255], where 0 is black and 255 is white. We can define the Grayscale Image ADT for storing and manipulating discrete grayscale digital images. Given the description of the operations, provide a complete implementation of the ADT using a 2-D array.

• GrayscaleImage(nrows, ncols)
  Creates a new instance that consists of nrows and ncols of pixels each set to an initial value of 0.
• width()
  Returns the width of the image.
• height()
  Returns the height of the image.
• clear(value)
  Clears the entire image by setting each pixel to the given intensity value. The intensity value will be clamped to 0 or 255 if it is less than 0 or greater than 255, respectively.
• getitem(row, col)
  Returns the intensity level of the given pixel. The pixel coordinates must be within the valid range.
• setitem(row, col)
  Sets the intensity level of the given pixel to the given value. The pixel coordinates must be within the valid range. The intensity value is clamped to 0 or 255 if it is outside the valid range.

Playing board games on a computer is very common. We can use abstraction to aide in the design of a board game by separating the game logic from the actual user interaction required to play the game. No matter the type of user interface provided to play the game (i.e., text based, desktop windowing environment, or web browser), the underlying logic remains the same. Consider the game of Reversi, which was invented in 1893 but has a more modern set of rules dating back to the 1970s. Reversi is played by two players on a game board divided into 64 squares arranged in 8 rows and 8 columns and a set of 64 chips. Each chip is painted a dark color on one side and a light color on the other, with each color belonging to one of the two players. The players place their chips on the board and flip the chips of their opponent with the goal of having the most chips of their color on the board at the end of the game. The game starts with a configuration as shown

in part (a) of the figure below.

The players take turns placing chips on the board with their color facing up. A chip can only be played in a square that is adjacent to a chip of the other player and that forms a straight line of attack (vertical, horizontal, or diagonal). A line of attack is formed between two squares containing the player's own chips in which there is one or more of the opponent's chips in between the two. For example, if player 1 (black) goes first, he has four options as shown in part (b). Suppose player 1 places a chip in the square marked with an x. After placing his chip, player 1 flips all of the chips of player 2 (white) that are in the line of attack. In this case, he flips the chip immediately below the new chip as shown in part (c). Player 2 then places one of her chips. She has three options from which to choose as shown by the dark squares in part (c). If player 2 places her chip in the square marked x, she flips the black chip below the new chip as shown in part (d). If there are multiple lines of attack that result from the placement of a chip, then all of the opponent's chips that are in all of the lines of attack are flipped. For example, suppose player 1 places a chip in the square marked with an x as shown in part (d). Then he flips both white chips, the one to the left and the one diagonally down to the left as shown in part (e). Play alternates between the players until all of the squares are filled or neither player can move. If one player cannot move but the other can, play proceeds with the other player. The winner is the player with the most chips at the end of the game.

Given the following description of the operations, provide a complete implementation for the Reversi Game Logic ADT.

• ReversiGameLogic()
  Creates a new instance of the Reversi game logic with the initial configuration.
• whoseTurn()
  Returns the player number (1 or 2) for the current player or 0 if no player

  can move.

• numChips(player)
  Returns the number of chips on the board belonging to the indicated player. The value of player must be 1 or 2.
• numOpenSquares()
  Returns the number of squares still open and available for play.
• getWinner()
  Returns the player number (1 or 2) for the player who has won the game or 0 if the game is not finished.
• isLegalMove(row, col)
  Returns True or False to indicate if the current player can place their chip in the square at position (row, col).
• occupiedBy(row, col)
  Which player has a chip in the given square? Returns the player number (1 or 2) or 0 if the square is empty.
• makeMove(row, col)
  The current player places one of his chips in the square at position (row, col). All chips on the board that should be flipped based on the rules of Reversi are flipped.

Implement a text-based version of the Reversi game using your game logic ADT from the previous question.

Consider the game of Connect Four, which was first sold and marketed by the Milton Bradley company in 1974.

Connect Four is played by two players on a vertical game board divided into 7 columns in which each column has 6 rows of holes. Using two sets of chips, colored red and yellow, the players alternate turns dropping one of their chips into an unfilled column. The chip falls straight down the column to occupy the next available slot within the column. The objective of the game is to be the first player to form a straight line of four chips of one's own color in any direction: horizontally, vertically, or diagonally.

We can define an abstract data type to store and maintain the current state of the connect four game, including the pieces on the board and the current player. When a chip is dropped, the game logic makes sure the play is legal and performs the necessary action. As play progresses, the ADT also maintains which player is the current player and determines when the game is over. For simplicity, The individual squares are identified by a (row, column) index pair. Both indices start at 0 with (0, 0) corresponding to the square in the upper-left corner of the board. The two players are identified by number, with player 1 corresponding to the "yellow" chips and player 2 corresponding to the "red" chips. When fully implemented, this ADT can be used by a separate user-interface component to create a fully functioning computer game.

Given the following description of the operations, provide a complete implementation for the Connect Four Game Logic ADT.

• Connect4GameLogic()
  Creates a new instance of the Connect Four game logic with an empty board and the current player set to player 1.
• isOver()
  Returns a Boolean indicating if the game is over. That is, one of the players are filled, or no player can move.
• whoseTurn()
  Returns the player number (1 or 2) for the current player.
• getWinner()
  Returns the player number (1 or 2) for the player who has won the game or 0 if the game is a draw. If the game is not over, the returned value is undefined.
• getWinningSeq()
  Returns a list of 2-tuples that contain the (row, column) indices of the four chips that resulted in a win.
• occupiedBy(row, col)
  Returns the player number (1 or 2) for the player who has a chip in the given square or 0 if the square is empty. Both row and col must be valid indices.
• isLegalMove(col)
  Returns a Boolean indicating if the current player can drop one of their chips into the given column. When dropping a chip, the column can not be full. The col index must be within the valid range.
• dropChip(col)
  Performs the actual dropping of a chip into the indicated column, which must be a legal move.

Since the introduction of the original version of the game, variations have been introduced. One such variation is called "Pop Out". In this version, a player may choose to add a chip from the top as in the original game or remove ("pop out") one of their own colored chips from the bottom of a column. Removing a chip from the bottom causes all other chips in that column to drop down one row. Modify the game logic from the previous question to allow for the "pop out" option.

Define a game logic ADT, similar to that of the Reversi Game Logic ADT, for the game of checkers.