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
    012345
    0 F1
    1F2P> F3F4
    2 F5
    3
    East
    South

    Environment after the PounceFish acts
    North
    West
    012345
    0 F1
    1F2 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 Number0123456789
    key"A""C""D""E""B""C""E""B""B""C"
     
    key"A""B""D""E""A""C""?""B""D""C"
    Points Awarded1-0.2511-0.25101-0.251
    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 Strings.

      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 Players 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 Randoms 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");
         }
      }