# 2007 Open Response Solutions

(The formatting here will look more correct if you click the "hide" toolbar button)
1. A positive integer is called a "self-divisor" if every decimal digit of the number is a divisor of the number, that is, the number is evenly divisible by each and every one of its digits. For example, the number 128 is a self-divisor because it is evenly divisible by 1, 2, and 8. However, 26 is not a self-divisor because it is not evenly divisible by the digit 6. Note that 0 is not considered to be a divisor of any number, so any number containing a 0 digit is NOT a self-divisor. There are infinitely many self-divisors.
`public class SelfDivisor {   /** @param number `the number to be tested`    *         `Precondition: `number` > 0`    *  @return true `if every decimal digit of number is a divisor of number;`    *         false `otherwise`    */   public static boolean isSelfDivisor(int number) {      /* `to be implemented in part (a)` */   }      /** @param start `starting point for values to be checked`    *         `Precondition:` start > 0    *  @param num `the size of the array to be returned`    *         `Precondition:` num > 0    *  @return `an array containing the first `num` integers ≥ `start` that are self-divisors`    */   public static int[] firstNumSelfDivisors(int start, int num) {      /* `to be implemented in part (b)` */   }      // `There may be fields, constructors, and methods that are not shown.`}`
1. Write method `isSelfDivisor`, which takes a positive integer as its parameter. This method returns `true` if the number is a self-divisor; otherwise, it returns `false`.

Complete method `isSelfDivisor` below.
`/** @param number `the number to be tested` *         `Precondition: `number` > 0` *  @return true `if every decimal digit of number is a divisor of number;` *         false `otherwise` */public static boolean isSelfDivisor(int number) {`
Give me a hint?
Our goal is to ensure that a number is divisible by each and every one of its digits. In order to check this, we need to figure out how to do two things:
1. First, we need some way to loop through the digits.
2. Then, we need some way to figure out if the number is divisible by something.

Divisibility is a condition you should be familiar with coding. Finding all the digits is also something we have done before, although you may or may not remember. In both cases, you will be making a lot of use of the % modulus operator to find remainders.
OK, just tell me.
In order to search through every digit of a number, I will first think about what I would do to get just the ones digit of a number. It ought to occur to you that this can be found just by a modulus by 10. Once I've got the ones digit, I can shift the digits over one place just by dividing by ten; integer division will automatically discard the decimal part that was formerly the ones digit.
`while(n > 0) {   int digit = n % 10;   n /= 10;   ...}`
I keep repeating this until there are no digits left - that is, the number is 0.

Now I need to figure out what to do with the digit. There are two ways the number can fail - either the digit is 0, or it doesn't evenly divide the number. I'll be clever about short-circuit evaluation of conditions by checking if the number is 0 first - that way, if it is, the computer won't try to divide the number by it, which would cause an error.

The number passes (returns `true`) only if I get through looping and haven't yet returned false. So, that should happen after the loop, not in an `else`-branch of my `if`.
`public static boolean isSelfDivisor(int number) {   int n = number;   while(n > 0) {      int digit = n % 10;      n /= 10;      if(digit == 0 || number % digit != 0) {         return false;      }   }   return true;}`

2. Write method `firstNumSelfDivisors`, which takes two positive integers as parameters, representing a start value and a number of values. Method `firstNumSelfDivisors` returns an array of size `num` that contains the first `num` self-divisors that are greater than or equal to `start`.

For example, the call |firstNumSelfDivisors(10, 3) should return an array containing the values 11, 12, and 15, because the first three self-divisors that are greater than or equal to 10 are 11, 12, and 15.

In writing `firstNumSelfDivisors`, assume that `isSelfDivisor` wors as specified, regardless of what you wrote in part (a).

Complete method `firstNumSelfDivisors` below.
`/** @param start `starting point for values to be checked` *         `Precondition:` start > 0 *  @param num `the size of the array to be returned` *         `Precondition:` num > 0 *  @return `an array containing the first `num` integers ≥ `start` that are self-divisors` */public static int[] firstNumSelfDivisors(int start, int num) {`
Give me a hint?
There are several steps we must do here:
1. Create an array big enough to hold all the values to be returned
2. Starting from the number `start`, count upwards, adding to the array only numbers that are self-divisors (we can use `isSelfDivisor()` to check this)
3. Keep track of how many values we have stored into the array, and stop once it is full
4. Return the array

OK, just tell me.
It should be clear enough how to make and return the array:
`public static int[] firstNumSelfDivisors(int start, int num) {   int[] arr = new int[num];      ...         return arr;}`
So, the tricky bit is finding the numbers to fill it in with. This is tricky because we need to keep track of two things as we loop: what `number` we are looking at, and at what `index` in the array we will be storing the next number. The `number` will start with `start` and count up by one each time, in a pattern we have often used in loops before. However, there is no ending `number`; the `index`, instead, will tell us when we are done.

The `index` will start at 0, and count up until it reaches `num`, at which point the array is full and we are done. However, it shouldn't count up every time we look at a number; it should count up only when we find a value to store.

The code should look something like this:
`public static int[] firstNumSelfDivisors(int start, int num) {   int[] arr = new int[num];   for(int index = 0, number = start; index < num; number++) {      if(isSelfDivisor(number)) {         arr[index] = number;         index++;      }   }   return arr;}`

2. This question involves reasoning about the code from the Marine Biology Simulation case study. A copy of the code is provided as part of this exam.

A `PounceFish` is a type of fish that looks for prey and then "pounces" on it. A `PounceFish` can see only a limited distance in its forward direction. If the `PounceFish` sees another fish, it rushes forward and eats the nearest on that it sees, ending up in the location where its prey was originally located. If the `PounceFish` does not see another fish, it acts as a `Fish`.

The `PounceFish` class is shown below.
`public class PounceFish extends Fish {   private int range; // `the distance that a `PounceFish` can see; `range` > 0`      /** `Looks ahead `range` location in current direction`    *  @return `the nearest fish in that direction within range (if any);`    *          null` if no such fish is found`    */   private Fish findFish() {   /* `to be implemented in part (a)` */ }      /** `Acts for one step in the simulation`    */   public void act() {   /* `to be implemented in part (b)` */ }      // `There may be fields, constructors, and methods that are not shown`}`
The following diagrams show an example environment containing a `PounceFish` (represented by a `P`) and other fish (represented by `F1`, `F2`, etc.). The direction of the `PounceFish` is indicated by the character ">", showing that, in this example, the `PounceFish` is facing east. If the `PounceFish` can see 2 or more locations ahead in its forward direction, it will see fish `F3` as shown in the first diagram and will move to that location to eat it, causing `F3` to die as shown in the second diagram.
Environment before the `PounceFish` acts
North
West
 0 1 2 3 4 5 0 `F1` 1 `F2` `P>` `F3` `F4` 2 `F5` 3
East
South

Environment after the `PounceFish` acts
North
West
 0 1 2 3 4 5 0 `F1` 1 `F2` `P>` `F4` 2 `F5` 3
East
South

If the PounceFish in the diagram above could see only 1 location ahead, it would not see any prey and therefore would act as any ordinary fish.
1. Write the `PounceFish` method `findFish`. If any fish are located within `range` locations in the direction that the `PounceFish` is currently facing, the method returns the nearest of these. Otherwise, the method returns `null`.
`/** `Looks ahead `range` location in current direction` *  @return `the nearest fish in that direction within range (if any);` *          null` if no such fish is found` */private Fish findFish() {`
Give me a hint?
In order to write a Marine Biology Case Study method, a good first step is to look at the Quick Reference and remind yourself of what methods you have to do the things that method needs you to do.

In this case, think about how you would do this task if you were working it through yourself. You need to be able to find out what location is in front of the `PounceFish`. This means, first, that you need to know your current location and direction; then, you need to ask some other object (who?) to tell you what location is in that direction from your current location. Once you know how to find one location, it should be clear how to find the next location in line with reference to that first location.

The hard part, really, is figuring out how to write a loop that will repeat this process automatically. My suggestion is that you imagine the loop as walking forward from your current location, taking one step in your direction each time through, until you find a fish or have stepped beyond your range.

Another hint: I always get things like my location and direction and environment and store them in shorter-named variables to start out with. This gives me a better sense of what tools I have to use, and simplifies my later code.
OK, just tell me.
You should remember that the standard way to find a new location, given a direction, is with the `Environment` method `getNeighbor()`. So, the following code would find the location in front of me:
`Location loc = location();Direction dir = direction();Environment env = environment();Location front = env.getNeighbor(loc, dir);`
I want to do something slightly different: I want to step my `loc` forward one step at a time until I go beyond the range. I'll use the same logic, but put it all inside a loop counting the steps:
`Location loc = location();Direction dir = direction();Environment env = environment();for(int i = 0; i < range; i++) {   loc = env.getNeighbor(loc, dir);   ...}return null;`
Notice that now my loop changes `loc` each time - it is moving the location forward, rather than just calculating one forward location. I can return `null` at the end because the only way I can get there is if I didn't find and return a fish in the loop.

So, now I have a loop that will look at every location. What do I do next? Well, I should check whether there is a `Fish` there, and if so, return it. The whole method looks like this:
`private Fish findFish() {   Location loc = location();   Direction dir = direction();   Environment env = environment();      for(int i = 0; i < range; i++) {      loc = env.getNeighbor(loc, dir);      Fish f = env.objectAt(loc);      if(f != null) {         return f;      }   }   return null;}`
If you were really sharp it probably occurred to you to wonder what would happen if the location returned were invalid. Do we need to check for this? Fortunately for us, `getNeighbor()` just returns and invalid location in this case, not `null` as you might fear. And since there can't be a fish in an invalid location, going off the edge just automatically means we have nothing to pounce on and will get through the loop and return `null`.

2. Override the `act` method for the `PounceFish` class. A `PounceFish` attempts to find a fish that it can eat. If it finds such a fish, the `PouncerFish` eats it (causing it to die) and moves to its location. If the `PounceFish` does not find a fish that it can eat, it acts as an ordinary fish.

In writing `act`, assume that `findFish` works as specified, regardless of what you wrote in part (a).

Complete the method `act()` below.
`/** `Acts for one step in the simulation` */public void act() {   if(!isInEnv()) return;`
Give me a hint?
One big key here is realizing that to act as an ordinary fish is simple to do - and doesn't require copying out what `Fish.act()` normally does. How do you decide to just do what your superclass normally does for a method you overrode?

You'll need to remember how to kill a `Fish`, and how to move a `Fish`. Look at the Quick Reference if you're unsure.
OK, just tell me.
The solution to this part is very straightforward:
`public void act() {   if(!isInEnv()) return;      Fish f = findFish();   if(f == null) {      super.act();   } else {      Location loc = f.location();      f.die();      changeLocation(loc);   }`
I'm not sure how necessary it is to do those three steps in the order that I did. My reasoning here is like this: it's possible that an exception is thrown if a fish moves to the same space as another fish, and it's possible that a dead fish has no location, so I should get the location first, then kill the fish, then move.

3. Consider a system for processing student test scores. The following class will be used as part of this system and contains a student's name and the student's answers for a multiple-choice test. the answers are represented as strings of length one with an omitted answer being represented by a string containing a single question mark (`"?"`). These answers are stored in an `ArrayList` in which the position of the answer corresponds to the answer number on the test (question numbers start at 0). A student's score on the test is computed by comparing the student's answers with the corresponding answers in the answer key for the test. One point is awarded for each correct answer, and ¼ of a point is deducted for each incorrect answer. Omitted answers (indicated by a `"?"`) do not change a student's score.
`public class StudentAnswerSheet {   private ArrayList<String> answers; // `the list of student's answers`      /** @param key `the list of correct answers, represented as strings of length one`    *         `Precondition: `key.size()` is equal to the number of answers in this answer sheet`    *  @return `this student's test score`    */   public double getScore(ArrayList<String> key) {      /* `to be implemented in part (a)` */   }      /** @return `the name of the student`    */   public String getName() {      /* `implementation not shown` */   }}`
The following table shows an example of an answer key, a student's answers, and the corresponding point values that would be awarded for the student's answers. In this example, there are six correct answers, three incorrect answers, and one omitted answer. The student's score is ((6 * 1) - (3 * 0.25)) = 5.25.

 Question Number 0 1 2 3 4 5 6 7 8 9 key "A" "C" "D" "E" "B" "C" "E" "B" "B" "C" key "A" "B" "D" "E" "A" "C" "?" "B" "D" "C" Points Awarded 1 -0.25 1 1 -0.25 1 0 1 -0.25 1
1. Write the `StudentAnswerSheet` method `getScore`. The parameter passed to method `getScore` is an `ArrayList` of strings representing the correct answers for the test being scored. The method computes and returns a `double` that represents the score for the student's test answers when compared with the answer key. One point is awarded for each correct answer and ¼ of a point is deducted for each incorrect answer. Omitted answers (indicated by a `"?"`) do not change the student's score.

Complete method `getScore` below.
`/** @param key `the list of correct answers, represented as strings of length one` *         `Precondition: `key.size()` is equal to the number of answers in this answer sheet` *  @return `this student's test score` */public double getScore(ArrayList<String> key) {`
Give me a hint?
I'm sure that you've guessed already that this method will require using a `for` loop to search through an array. It's convenient for you that the student answer and the key answer are in the same index in the two different arrays. The only other complication I can think of is that you should be sure you are comparing correctly.

This is a chance to use the type-specific `ArrayList`, as we discussed on the day before the test. It's not a good place for the weird `for` loop, however, becasue you have to search two arrays at once. (This is why I suggested that you just not use the new `for` loops - their functionality is too limited)
OK, just tell me.
First, I need to figure out how to loop through the two arrays and get the student and key answers for each index. Perhaps checking the `ArrayList` methods in the Quick Reference, I come up with this:
`for(int i = 0; i < key.size(); i++) {   String s = answers.get(i);   String k = key.get(i);   ...}`
Remember, I don't have to typecast to `String` as I get values out of the `ArrayList`, because it is a type-specific `ArrayList` that only contains `String`s.

I'm trying to keep track of the student's current score and add or subtract from it for every answer I read. So, I'll need a `double` variable declared outside the loop, and I'll have a couple of `if` branches using `equals()` to compare my `s` and `k` variables. The completed code looks like this:
`public double getScore(ArrayList<String> key) {   double score = 0;   for(int i = 0; i < key.size(); i++) {      String s = answers.get(i);      String k = key.get(i);      if(s.equals(k)) {         score += 1;      } else if(!s.equals("?")) {         score -= 0.25;      }   }   return score;}`

2. Consider the following class that represents the test results of a group of students that took a multiple-choice test.
`public class TestResults {   private ArrayList<StudentAnswerSheet> sheets;      /** `Precondition: `sheets.size()` > 0`    *            `All answer sheets in `sheets` have the same number of answers`    *  @param key `the list of correct answers, represented as strings of length one`    *         `Precondition: `key.size()` is equal to the number of answers`    *         `in each of the answer sheets in `sheets    *  @return `the name of the student with the highest score`    */   public String highestScoringStudent(ArrayList<String> key) {      /* `to be implemented in part (b)` */   }}`
Write the `TestResults` method `highestScoringStudent`, which returns the name of the student who received the highest score on the test represented by the parameter `key`. If there is more than one student with the highest score, the name of any one of these highest-scoring students may be returned. You may assume that the size of each answer sheet represented in the `ArrayList sheets` is equal to the size of the `ArrayList key`.

In writing `highestScoringStudent`, assume that `getScore` works as specified, regardless of what you wrote in part (a).

Complete method `highestScoringStudent` below.
`/** `Precondition: `sheets.size()` > 0` *            `All answer sheets in `sheets` have the same number of answers` *  @param key `the list of correct answers, represented as strings of length one` *         `Precondition: `key.size()` is equal to the number of answers` *         `in each of the answer sheets in `sheets *  @return `the name of the student with the highest score` */public String highestScoringStudent(ArrayList<String> key) {`
Give me a hint?
Surprise, surprise - it's yet another array searching method! This time you're trying to find the largest value in a list, which should be something you hopefully remember how to do. My advice - make as many variables as you think you might want. It'll make your code easier to think about.
As in many problems we've done of this sort, I'm going to remember both what the best score so far is and who got it as I search through the list. If I find a better score, I change both the score and the name that I'm remembering.

The specification that you may return any one of the highest-scoring students in the case of a tie is actually very merciful on their part - it means that we don't need to worry about mistakes happening that relate to double precision. In other words, if one student got a 3.0000001 and another got a 2.9999999, (both are the computer's way to try to represent 3.) it doesn't matter that we return the first rather than the second.
OK, just tell me.
I think this is all more or less standard boilerplate that we've done before. The only one bit of cleverness I did was setting the starting `best` score to be more negative than any student could be. After all, I can't just start it at 0, because maybe all the students got a negative score.
`public String highestScoringStudent(ArrayList<String> key) {   double high = -key.size();   String name = null;   for(int i = 0; i < sheets.size(); i++) {      StudentAnswerSheet s = sheets.get(i);      if(s.getScore(key) > best) {         best = s.getScore(key);         name = s.getName();      }   }   return name;}`
An equally valid solution would be to remember just the `StudentAnswerSheet` that had the best score. Then I could rescore both it and the one I was comparing it to, every time through the loop, and change just that one variable if the one comparing was better. This would also require me to start it not null - probably `sheets.get(0)`. I think the added complexity of this method makes it less appealing.

4. In this question, you will complete methods in classes that can be used to represent a multi-player game. You will be able to implement those methods without knowing the specific game or the players' strategies.

The `GameState` interface describes the current state of the game. Different implementations of the interface can be used to play different games. For example, the state of a checkers game would include the positions of all the pieces on the board and which player should make the next move.

The `GameState` interface specifies these methods. The `Player` class will be described in part (a).
`public interface GameState {   /** @return true` if the game is in an ending state`    *        false` otherwise`    */   boolean isGameOver();      /** `Precondiiton: `isGameOver()` returns `true    *  @return` the player that won the game, or `null` if there was no winner`    */   Player getWinner();      /** `Precondiiton: `isGameOver()` returns `false    *  @return` the player who is to make the next move`    */   Player getCurrentPlayer();      /** @return` a list of valid moves for the current player;`    *        `the size of the returned list is 0 if there are no valid moves.`    */   ArrayList<String> isGameOver();      /** `Updates game state to reflect the effect of the specified move.`    *  @param move`a description of the move to be made`    */   void makeMove(String move);      /** @return` a string representing the current `GameState    */   String toString();}`
The `makeMove` method makes the move specified, updating the state of the game being played. Its parameter is a `String` that describes the move. The format of the string depends on the game. In tic-tac-toe, for example, the move might be something like `"X-1-1"`, indicating that an X is put in the position (1, 1).
1. The `Player` class provides a method for selecting the next move. By extending this class, different playing strategies can be modeled.
`public class Player {   private String name; // `name of this player`      public Player(String aName) {      name = aName;   }      public String getName() {      return name;   }      /** `This implementation chooses the first valid move.`    *  `Override this method in subclasses to define players with other strategies.`    *  @param state` the current state of the game; its current player is this player`    *  @return` a string representing the move chosen;`    *         "no move"` if no valid moves for the current player.`    */   public String getNextMove(GameState state) {   /* `implementation not shown` */ }}`
The method `getNextMove` returns the next move to be made as a string, using the same format as that used by `makeMove` in `GameState`. Depending on how the `getNextMove` method is implemented, a player can exhibit different game-playign strategies.

Write the complete class declaration for a `RandomPlayer` class that is a subclass of `Player`. The class should have a constructor whose `String` parameter is the player's name. It should override the `getNextMove` method to randomly select one of the valid moves in the given game state. If there are no valid moves available to the player, the string `"no move"` should be returned.
Give me a hint?
There is often a question of this nature on the AP test. The idea is to make sure you know what all goes into a complete class definition, and at the same time to assess your ability to make a new class to fit in with a complicated preexisting system. You will need to read carefully through the `GameState` class carefully and figure out how to use it.

You know from the problem that you need a constructor and a method, so I think the only potentially complex bit is how to generate random numbers. The way the AP board tends to like is to make a `Random` and then repeatedly call its `nextInt()` method; you also know of `Math.random()`, which returns a `double` from 0 to 1.
OK, just tell me.
One clever thing that I will do is to construct a single `Random` at the and assign it to a static variable so all `Player`s can share it. That way I will avoid any of the errors you may recall happening when I make a new `Random` generator for each random number I need (two `Random`s made at the same time give the same sequence of numbers).
`public class RandomPlayer extends Player {   private static Random rand = new Random();      public RandomPlayer(String n) {      super(n);   }      public String getNextMove(GameState state) {      ArrayList<String> moves = state.getCurrentMoves();      if(moves.size() == 0) {         return "no move";      } else {         return moves.get(rand.nextInt(moves.size()));      }   }`
It would work equally well to dispense with the whole `rand` variable and replace the salient line with:
`return moves.get((int)(Math.random() * moves.size()));`

2. The `GameDriver` class is used to manage the state of the game during game play. The `GameDriver` class can be written without knowing details of the game being played.
`public class GameDriver {   private GameState state; // `the current state of the game`      public GameDriver(GameState initial) {      state = initial;   }      /** `Plays an entire game, as described in the problem description`    */   public void play() {   /* `to be implemented in part (b)` */ }}`
Write the `GameDriver` method `play`. This method should first print the initial state of the game. It should then repeatedly determine the current player and that player's next move, print both the player's name and the chosen move, and make the move. When the game is over, it should stop making moves and print either the name of the winner and the word `"wins` or the message `"Game ends in a draw"` if there is no winner. You may assume that the `GameState makeMove` method has been implemented so that it will properly handle any move description returned by the `Player getNextMove` method, including `"no move"`.

Complete the method `play` below.
`/** `Plays an entire game, as described in the problem description` */public void play() {`
Give me a hint?
This is another problem that just requires you to figure out how to use the code given in the problem based on its specification. Go through the problem one sentence at a time, and try to figure out what method(s) in `GameState` are needed to do as you are asked.
OK, just tell me.
Just following the description a line at a time, I get something like this:
`public void play() {   // Print the initial game state   System.out.println(state);      // Repeat until game over   while(!state.isGameOver()) {      // Get the current player, and have him make a move      Player p = state.getCurrentPlayer();      state.makeMove(p.getMove(state));   }      // Game is finished - print victory information   if(state.getWinner() == null) {      System.out.println("Game ends in a draw");   } else {      System.out.println(state.getWinner().getName() + " wins");   }}`