Computer Science A

Course Progress 0/0
Sprint View
Week 19 2017 FRQ 4

2017 FRQ 4

7 min read

FRQ Question 4: Successors Class - 2D Array Processing

This question involves reasoning about a two-dimensional (2D) array of integers. You will write two static methods, both of which are in a single enclosing class named Successors (not shown). These methods process a 2D integer array that contains consecutive values.

Each of these integers may be in any position in the 2D integer array. For example, the following 2D integer array with 3 rows and 4 columns contains the integers 5 through 16, inclusive.

2D Integer Array

  0 1 2 3
0 15 5 9 10
1 12 16 11 6
2 14 8 13 7

The following Position class is used to represent positions in the integer array. The notation (r,c) will be used to refer to a Position object with row r and column c.

Part (a): findPosition Method

Write a static method findPosition that takes an integer value and a 2D integer array and returns the position of the integer in the given 2D integer array. If the integer is not an element of the 2D integer array, the method returns null.

For example, assume that array arr is the 2D integer array shown at the beginning of the question.

  • The call findPosition(8, arr) would return the Position object (2,1) because the value 8 appears in arr at row 2 and column 1.

  • The call findPosition(17, arr) would return null because the value 17 does not appear in arr.

Part (b): getSuccessorArray Method

A successor is the next consecutive value in the 2D array. For example, in the 2D array shown at the beginning of the question, the successor of 8 is 9, and the successor of 16 is not in the array.

Write a static method getSuccessorArray that takes a 2D integer array and returns a 2D array of Position objects that represent the positions of the successors for each value in the given 2D integer array.

The returned 2D array has the same dimensions as the given 2D integer array. The value stored in the returned 2D array at position (r,c) is:

  • The Position of the successor of the element at position (r,c) in the given array, if the successor exists in the array
  • null if the successor does not exist in the array

For example, assume that array arr is the 2D integer array shown at the beginning of the question. The following shows the result of calling getSuccessorArray(arr).

  0 1 2 3
0 (1,2) (0,2) (0,3) (1,2)
1 (0,3) null (1,0) (2,3)
2 (15,0) (0,2) (2,2) null

Requirements:

  • You must use findPosition appropriately to receive full credit.
  • The method creates and returns a new 2D array of Position objects with the same dimensions as the input array.

Complete method getSuccessorArray below.

Code Runner Challenge

Position

View IPYNB Source 
// CODE_RUNNER: Position

public class Main {
    
    // Inner Position class
    class Position {
        private int row;
        private int col;
        
        public Position(int r, int c) {
            row = r;
            col = c;
        }
        
        public String toString() {
            return "(" + row + "," + col + ")";
        }
    }
    
    /** Returns the position of num in intArr;
     *  returns null if no such element exists in intArr.
     *  Precondition: intArr contains at least one row.
     */
    public Position findPosition(int num, int[][] intArr) {
        // Part (a): Nested loop structure - iterate through rows
        for (int r = 0; r < intArr.length; r++) {
            // Part (a): Nested loop structure - iterate through columns
            for (int c = 0; c < intArr[r].length; c++) {
                // Part (a): Accessing array elements and comparing to num
                if (intArr[r][c] == num) {
                    // Part (a): Return Position when found
                    return new Position(r, c);
                }
            }
        }
        // Part (a): Return null when not found (after all loops complete)
        return null;
    }
    
    /** Returns a 2D array of positions of the successors of each element
     *  in intArr; null is stored in each position where the successor
     *  does not exist in intArr.
     *  Precondition: intArr contains at least one row.
     */
    public Position[][] getSuccessorArray(int[][] intArr) {
        // Part (b): Create result array with same dimensions as intArr
        Position[][] result = new Position[intArr.length][];
        
        // Part (b): Nested loop structure - iterate through rows
        for (int r = 0; r < intArr.length; r++) {
            // Part (b): Initialize each row with correct column length
            result[r] = new Position[intArr[r].length];
            
            // Part (b): Nested loop structure - iterate through columns
            for (int c = 0; c < intArr[r].length; c++) {
                // Part (b): Call findPosition with successor value (element + 1)
                // and store result in corresponding position of result array
                result[r][c] = findPosition(intArr[r][c] + 1, intArr);
            }
        }
        
        // Part (b): Return the completed result array
        return result;
    }
    
    public void driver() {
        int[][] arr = {
            {15, 5, 9, 10},
            {12, 16, 11, 6},
            {14, 8, 13, 7}
        };
        
        System.out.println("Testing getSuccessorArray:");
        System.out.println("Original array:");
        for (int r = 0; r < arr.length; r++) {
            for (int c = 0; c < arr[r].length; c++) {
                System.out.print(arr[r][c] + "\t");
            }
            System.out.println();
        }
        System.out.println();
        
        Position[][] result = getSuccessorArray(arr);
        System.out.println("Successor positions:");
        for (int r = 0; r < result.length; r++) {
            for (int c = 0; c < result[r].length; c++) {
                System.out.print(result[r][c] + "\t");
            }
            System.out.println();
        }
        System.out.println();
        
        System.out.println("Expected:");
        System.out.println("(1,1)\t(1,3)\t(0,3)\t(1,2)");
        System.out.println("(1,0)\tnull\t(1,0)\t(2,3)");
        System.out.println("(0,0)\t(0,2)\t(2,0)\t(2,1)");
    }
    
    public static void main(String[] args) {
        Main successors = new Main();
        successors.driver();
    }
}

Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Scoring Guidelines Part (a)

Part (a): findPosition - 4 points

Nested loop structure - 1 point

  • Uses nested loops to traverse the 2D array
  • Outer loop iterates through rows, inner loop iterates through columns

Accessing array elements correctly - 1 point

  • Correctly accesses elements using intArr[r][c] or equivalent notation

Comparing and returning Position when found - 1 point

  • Compares intArr[r][c] to num
  • Returns new Position(r, c) when a match is found

Returning null when not found - 1 point

  • Returns null after completing the search without finding num
  • null is returned outside the loops

Sample Solution:

public static Position findPosition(int num, int[][] intArr) {
    for (int r = 0; r < intArr.length; r++) {
        for (int c = 0; c < intArr[r].length; c++) {
            if (intArr[r][c] == num) {
                return new Position(r, c);
            }
        }
    }
    return null;
}

Scoring Guidelines Part (b)

Part (b): getSuccessorArray - 5 points

Creating the result array with correct dimensions - 1 point

  • Creates a new 2D Position array
  • Array has the same dimensions as intArr (same number of rows, same length for each row)

Nested loop structure - 1 point

  • Uses nested loops to traverse the 2D array
  • Outer loop iterates through rows, inner loop iterates through columns

Calling findPosition appropriately - 2 points

  • 1 point: Calls findPosition with the successor value (intArr[r][c] + 1)
  • 1 point: Calls findPosition with intArr as the second parameter

Storing results in correct positions - 1 point

  • Stores the result from findPosition in the corresponding position of the result array
  • Uses result[r][c] = findPosition(...) or equivalent

Sample Solution:

public static Position[][] getSuccessorArray(int[][] intArr) {
    Position[][] result = new Position[intArr.length][];
    
    for (int r = 0; r < intArr.length; r++) {
        result[r] = new Position[intArr[r].length];
        for (int c = 0; c < intArr[r].length; c++) {
            result[r][c] = findPosition(intArr[r][c] + 1, intArr);
        }
    }
    
    return result;
}

Alternative Solution:

public static Position[][] getSuccessorArray(int[][] intArr) {
    Position[][] result = new Position[intArr.length][intArr[0].length];
    
    for (int r = 0; r < intArr.length; r++) {
        for (int c = 0; c < intArr[r].length; c++) {
            int successor = intArr[r][c] + 1;
            result[r][c] = findPosition(successor, intArr);
        }
    }
    
    return result;
}

Course Timeline