Programming Exercises for Chapter 7
This page contains several exercises for Chapter 7 in Introduction to Programming Using Java. For each exercise, a link to a possible solution is provided. Each solution includes a discussion of how a programmer might approach the problem and interesting points raised by the problem or its solution, as well as complete source code of the solution.
Exercise 7.1:
Write a subroutine that creates an ArrayList containing several different random integers in the range from 1 up to some specified maximum. The number of integers and the maximum allowed value for the integers should be parameters to the subroutine. Write a main() routine to test your subroutine.
Exercise 7.2:
Suppose that M is a two-dimensional array that has R rows and C columns. The transpose of M is defined to be an array T that has C rows and R columns such that T[i][j] = M[j][i] for each i and j. Write a function that takes an array of type int[][] as a parameter, and returns the transpose of that array. (Assume that the parameter is a typical 2D array in which all the rows have the same length.) Also write a subroutine to print a 2D array of integers in neat rows and columns, and include a main() routine to test your work.
Exercise 7.3:
In Subsection 7.4.4, it is mentioned that the standard sorting method Arrays.sort() is much faster and efficient than selection sort. Write a program to test this claim. To be specific, your program should create a large array filled with random real numbers. It should use both Arrays.sort() and selectionSort() to sort the array, and it should time how long it takes to perform each sort. Furthermore, it should do the same thing for a large array of random Strings. To find the times, you can use System.currentTimeMillis() (see Subsection 2.3.1 and the example TimedComputation.java).
Exercise 7.4:
In Exercise 6.1, you wrote a program SimpleStamperWithDrag that allows the user to place red rectangles and blue ovals in a panel by clicking and dragging the mouse. However, that program does not store any information about what has been drawn, so the panel cannot repaint itself correctly. Revise the program to use an ArrayList to store data about the contents of the panel. All drawing should be done in a paintComponent() method.
Exercise 7.5:
Write a program that will read a sequence of positive real numbers entered by the user and will print the same numbers in sorted order from smallest to largest. The user will input a zero to mark the end of the input. Assume that at most 100 positive numbers will be entered. Do not use any built-in function such as Arrays.sort(). Do the sorting yourself.
Exercise 7.6:
The sample program RandomArt.java from Subsection 6.4.1 shows a different random "artwork" every four seconds. There are three types of "art", one made from lines, one from circles, and one from filled squares. However, the program does not save the data for the picture that is shown on the screen. As a result, the picture cannot be redrawn when necessary. In fact, every time paintComponent() is called, a new picture is drawn.
Write a new version of RandomArt.java that saves the data needed to redraw its pictures. The paintComponent() method should simply use the data to draw the picture. New data should be recomputed only every four seconds, in response to an event from the timer that drives the program.
To make this interesting, write a separate class for each of the three different types of art. Also write an abstract class to serve as the common base class for the three classes. Since all three types of art use a random gray background, the background color can be defined in their superclass. The superclass also contains a draw() method that draws the picture; this is an abstract method because its implementation depends on the particular type of art that is being drawn. The abstract class can be defined as:
private abstract class ArtData {
Color backgroundColor; // The background color for the art.
ArtData() { // Constructor sets background color to be a random gray.
int x = (int)(256*Math.random());
backgroundColor = new Color( x, x, x );
}
abstract void draw(Graphics g); // Draws this artwork.
}
Each of the three subclasses of ArtData must define its own draw() method. It must also define instance variables to hold the data necessary to draw the picture. I suggest that you should create random data for the picture in the constructor of the class, so that constructing the object will automatically create the data for the random artwork. (One problem with this is that you can't create the data until you know the size of the panel, so you can't create an ArtData object in the constructor of the panel. One solution is to create an ArtData object at the beginning of the paintComponent() method, if the object has not already been created.) In each of the three subclasses, you will need to use one or more arrays or ArrayLists to store the data.
Exercise 7.7:
Write a program that will read a text file selected by the user, and will make an alphabetical list of all the different words in that file. All words should be converted to lower case, and duplicates should be eliminated from the list. The list should be written to an output file selected by the user. As discussed in Subsection 2.4.4, you can use TextIO to read and write files. Use a variable of type ArrayList<String> to store the words. It is not easy to separate a file into words as you are reading it. You can use the following method:
/**
* Read the next word from TextIO, if there is one. First, skip past
* any non-letters in the input. If an end-of-file is encountered before
* a word is found, return null. Otherwise, read and return the word.
* A word is defined as a sequence of letters. Also, a word can include
* an apostrophe if the apostrophe is surrounded by letters on each side.
* @return the next word from TextIO, or null if an end-of-file is
* encountered
*/
private static String readNextWord() {
char ch = TextIO.peek(); // Look at next character in input.
while (ch != TextIO.EOF && ! Character.isLetter(ch)) {
// Skip past non-letters.
TextIO.getAnyChar(); // Read the character.
ch = TextIO.peek(); // Look at the next character.
}
if (ch == TextIO.EOF) // Encountered end-of-file
return null;
// At this point, we know the next character is a letter, so read a word.
String word = ""; // This will be the word that is read.
while (true) {
word += TextIO.getAnyChar(); // Append the letter onto word.
ch = TextIO.peek(); // Look at next character.
if ( ch == '\'' ) {
// The next character is an apostrophe. Read it, and
// if the following character is a letter, add both the
// apostrophe and the letter onto the word and continue
// reading the word. If the character after the apostrophe
// is not a letter, the word is done, so break out of the loop.
TextIO.getAnyChar(); // Read the apostrophe.
ch = TextIO.peek(); // Look at char that follows apostrophe.
if (Character.isLetter(ch)) {
word += "\'" + TextIO.getAnyChar();
ch = TextIO.peek(); // Look at next char.
}
else
break;
}
if ( ! Character.isLetter(ch) ) {
// If the next character is not a letter, the word is
// finished, so break out of the loop.
break;
}
// If we haven't broken out of the loop, next char is a letter.
}
return word; // Return the word that has been read.
}
Note that this method will return null when the file has been entirely read. You can use this as a signal to stop processing the input file.
Exercise 7.8:
The game of Go Moku (also known as Pente or Five Stones) is similar to Tic-Tac-Toe, except that it is played on a much larger board and the object is to get five squares in a row rather than three. Players take turns placing pieces on a board. A piece can be placed in any empty square. The first player to get five pieces in a row -- horizontally, vertically, or diagonally -- wins. If all squares are filled before either player wins, then the game is a draw. Write a program that lets two players play Go Moku against each other.
Your program will be simpler than the Checkers program from Subsection 7.5.3. Play alternates strictly between the two players, and there is no need to highlight the legal moves. You will only need two classes, a short panel class to set up the interface and a Board class to draw the board and do all the work of the game. Nevertheless, you will probably want to look at the source code for the checkers program, Checkers.java, for ideas about the general outline of the program.
The hardest part of the program is checking whether the move that a player makes is a winning move. To do this, you have to look in each of the four possible directions from the square where the user has placed a piece. You have to count how many pieces that player has in a row in that direction. If the number is five or more in any direction, then that player wins. As a hint, here is part of the code from my program. This code counts the number of pieces that the user has in a row in a specified direction. The direction is specified by two integers, dirX and dirY. The values of these variables are 0, 1, or -1, and at least one of them is non-zero. For example, to look in the horizontal direction, dirX is 1 and dirY is 0.
int ct = 1; // Number of pieces in a row belonging to the player.
int r, c; // A row and column to be examined
r = row + dirX; // Look at square in specified direction.
c = col + dirY;
while ( r >= 0 && r < 13 && c >= 0 && c < 13
&& board[r][c] == player ) {
// Square is on the board, and it
// contains one of the players' pieces.
ct++;
r += dirX; // Go on to next square in this direction.
c += dirY;
}
r = row - dirX; // Now, look in the opposite direction.
c = col - dirY;
while ( r >= 0 && r < 13 && c >= 0 && c < 13
&& board[r][c] == player ) {
ct++;
r -= dirX; // Go on to next square in this direction.
c -= dirY;
}
Here is a picture of my program, just after black has won the game.
