P1. Using Array Lists to Collect Objects

Array Lists can hold collections of objects that may be quite large. In the following lab program, generate random circle objects and store them in an array. If a circle does not intersect any of the previously stored circles, add it to the array. Finally, display all circles that you collected in the array. The result should look something like the image below. (Note that none of the circles intersect.)

If you don't know how to draw the circles, then you will need to print out them out, which is less fun.

Use the code of the circleIntersect method that is given below to test whether two circles intersect. To randomly generate a circle, simply pick random x- and y- positions between 0 and 300 for the center and a random radius between 0 and 30. Compare each newly generated circle with all other circles before you add it. If the new circle passes the test, add it to the end of the array. Note that the array will have fewer elements than the number of generated circles since you are rejecting some of the circles. Keep track of the actual number of circles in the array.

public class Circles extends Applet
  public Circles()  
     // fill circles array list with circles
     for (int i = 1; i <= 300; i++)
        . . .

     Test if two circles intersect
     (distance between centers is less than sum of radii)
     @param c1 the first circle
     @param c2 the second circle

  public static boolean circlesIntersect(Ellipse2D.Double c1,
     Ellipse2D.Double c2)
     double radius1 = c1.getWidth() / 2;
     double radius2 = c2.getWidth() / 2;
     double dx = c1.getX() + radius1 - c2.getX() - radius2;
     double dy = c1.getY() + radius1 - c2.getY() - radius2;
     double distance = Math.sqrt(dx * dx + dy * dy);
     return distance < radius1 + radius2;

  public void paint(Graphics g)
     Graphics2D g2 = (Graphics2D)g;
     for (. . .)
        Ellipse2D.Double c = . . .;

  private ArrayList circles;

What is the code for your test program?



Using the debugger or a print statement, find out what percentage of circles was rejected.

Run your program five times. What rejection percentages do you get?



P2. Array Subscripts

In the text, we have frequently used the Random.nextInt method to generate random integers. For example, 1 + generator.nextInt(6)
generates random numbers between 1 and 6, simulating the throw of a die. In this lab assignment, use an array to test whether the random generator is fair, that is, whether each possible value is generated approximately the same number of times.

Your program should ask the user:

   How many random numbers should be generated?
   What is the number of values for each random draw? (e.g., 6)

Make an array with one element for each possible outcome. Set each element to 0. Then keep calling the random number generator. If it returns a value v, then increment the counter belonging to v.

After all numbers have been generated, print the counters. Here is a typical program run:

How many numbers do you want to generate? 1000
What is the number of values? 10.

0    78
1   101
2   118
3    97
4   103
5   102
6   112
7    91
8    94
9   104

What is the code for your program?



P3. Array Parameters and Return Values

Here is a method that receives an array of integers and creates a new array, with the entries reversed. For example, if the input array contains 1 2 3 4, the output array contains 4 3 2 1. Note that this method has an array parameter and an array return value.

  compute the reverse of an array
  @param intValues an array of integer values
  @return a copy of the array, with the elements reversed
  public static int[] reverse(int[] intValues)
  int[] result = new int[intValues.length];

  int i;    
  for(i = 0 ; i < intValues.length; i++)
     result[intValues.length - i - 1] = intValues[i];

     return result;

Note that this method does not change the intValues array. Rewrite this method so that it reverses the intValues array in place, without computing a new array.



Supply a program that tests your method.



P4. Simple Array Algorithms

Consider finding an average score from a sequence of scores where the lowest two scores are discarded. Write a class

public class ScoreSet
  public void add(int score) { . . . }
  public double averageWithoutLowest2() { . . . }
  private . . .

Use either an int[] array or an ArrayList of Integer objects.

What is the code for your ScoreSet class?



How does your class process duplicate scores? For example, how does it process 95, 90, 90, 80, 78, 68, 68, 68? What do you think it should do?



P5. Avoiding Parallel Arrays

Write a program that reads in the names and scores of students and then computes and displays the names of the students with the highest and lowest scores.

A simple method of carrying out this task would be to have two parallel arrays.

String[] names;
int[] scores;

However, you should avoid parallel arrays in your solution.

Give a test program that uses a single array or array list to solve this problem.



P6. Arrays as Object Data

You probably solved the preceding exercise by implementing a class Student with two instance variables, String name and int score. Now suppose that you want to store multiple scores for each student. That is, to have a class like this:

class Student
  . . .
  private String name;
  private int[] scores;
  private int scoresSize;
  private static final int SCORES_LENGTH = 20;

Alternatively, if you prefer, use an array list of Integer objects.

Supply the following methods:

   a constructor that sets the student name and initializes the scores array
   a method add that adds a score to the array
   a method getAverageWithoutLowest2 that returns the average score, with the lowest two discarded. (Just compute the average if you did
       not complete lab P3.)
What is the code for your class?



P7. Two-dimensional Arrays

Arrays store a linear arrangement of values, accessed by a single index. Two-dimensional arrays or matrices store a tabular arrangement of values, accessed by two indexes, for example matrix[i][j], where i is the row index, and j is the column index.

Crosswords are a type of puzzle where the "pieces" of the puzzle have letters in common. For example, these pieces share the letter 'o'.


Write a program that will accept a list of words into an array list of strings, then make a 20 x 20 array of char that contains a crossword puzzle with these words.

For example, when given the list addle, apple, clowning, incline, plan, burr your program should display:

   e   n

You may want to use the following method: Place the first word horizontally in the center of the grid. Place the next word vertically. Check if there is a common letter already on the grid, and if all the squares into which you want to place that word are still empty. (If you can't place it on any of the common letters, skip the word.) Then switch back to horizontal, place the next word if possible, and so on.