Computer Science A

Course Progress 0/0
Sprint View
Week 19 2016 FRQ 3

2016 FRQ 3

6 min read

FRQ Question Context

Overview

A crossword puzzle grid is a two-dimensional rectangular array of black and white squares. Some of the white squares are labeled with a positive number according to the crossword labeling rule.

Crossword Labeling Rule

A square is labeled with a positive number if and only if:

  • The square is white, and
  • The square does not have a white square immediately above it, or
  • The square does not have a white square immediately to its left, or
  • Both conditions are true.

The squares identified by these criteria are labeled with consecutive numbers in row-major order, starting at 1.

Class Descriptions

This question uses two classes: Square and Crossword.

Square Class

public class Square
{
    // Constructs one square of a crossword puzzle grid.
     // Postcondition:
     // - The square is black if and only if isBlack is true.
     // - The square has number num.
     
    public Square(boolean isBlack, int num)
    { /* implementation not shown */ }

    // There may be instance variables, constructors,
    // and methods that are not shown.
}

Crossword Class

public class Crossword
{
  // Each element is a Square object with a color (black or white) and a number.
    // puzzle[r][c] represents the square in row r, column c.
    // There is at least one row in the puzzle.
  
  private Square[][] puzzle;

  //Constructs a crossword puzzle grid.
    // Precondition: There is at least one row in blackSquares.
    // Postcondition:
    // - The crossword puzzle grid has the same dimensions as blackSquares.
    // - The Square object at row r, column c in the crossword puzzle grid is black
    // if and only if blackSquares[r][c] is true.
    // - The squares in the puzzle are labeled according to the crossword labeling rule.

  public Crossword(boolean[][] blackSquares)
  { /* to be implemented in part (b) */ }

  // Returns true if the square at row r, column c should be labeled with a positive number;
    // false otherwise.
    // The square at row r, column c is black if and only if blackSquares[r][c] is true.
    // Precondition: r and c are valid indexes in blackSquares.
    
  private boolean toBeLabeled(int r, int c, boolean[][] blackSquares)
  { /* to be implemented in part (a) */ }

    // There may be instance variables, constructors, and methods that are not shown.
}

FRQ Question Part A

Write the Crossword method toBeLabeled.

  • The method returns true if the square at row r, column c should be labeled with a positive number according to the crossword labeling rule.
  • Otherwise, it returns false.
  • The parameter blackSquares indicates which squares are black.

// CODE_RUNNER: <challenge text>

Code Runner Challenge

2D Arrays — Crossword toBeLabeled (Starter Code)

View IPYNB Source 
// CODE_RUNNER: 2D Arrays — Crossword toBeLabeled (Starter Code)

public class Main {

    /** Returns true if the square at row r, column c should be labeled
     *  with a positive number; false otherwise.
     *  The square at row r, column c is black if and only if
     *  blackSquares[r][c] is true.
     *  Precondition: r and c are valid indexes in blackSquares.
     */
    private boolean toBeLabeled(int r, int c, boolean[][] blackSquares) 
    {
        return (!(blackSquares[r][c]) &&
            (r == 0 || c == 0 || blackSquares[r - 1][c] ||
                blackSquares[r][c - 1]));
    } 

    // Driver (do not modify)
    public void driver() {
        boolean[][] grid = {
            {true, false, false},
            {false, false, true},
            {false, true, false}
        };

        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                System.out.println(
                    "Square (" + r + "," + c + ") labeled? " +
                    toBeLabeled(r, c, grid)
                );
            }
        }
    }

    public static void main(String[] args) {
        Main tester = new Main();
        tester.driver();
    }
}
Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

FRQ Question Part B

Write the Crossword constructor.

  • Initialize the puzzle grid to have the same dimensions as blackSquares.
  • Each element in the grid should be initialized with a Square object.

  • The Square object should have:

    • The correct color (black or white)
    • A positive number if the square is labeled
    • A number of 0 if the square is not labeled

Important Note

You may assume that toBeLabeled works as specified, regardless of what you wrote in part (a).

You must use toBeLabeled appropriately to receive full credit.

// CODE_RUNNER: <challenge text>

Code Runner Challenge

2D Arrays and Objects — Crossword Constructor (Starter Code)

View IPYNB Source 
// CODE_RUNNER: 2D Arrays and Objects — Crossword Constructor (Starter Code)

class Square {
    private boolean isBlack;
    private int num;

    public Square(boolean isBlack, int num) {
        this.isBlack = isBlack;
        this.num = num;
    }

    public String toString() {
        return isBlack ? "BLACK" : String.valueOf(num);
    }
}

public class Main {

    private Square[][] puzzle;

    // Assume this method works correctly (given in Part a)
    private boolean toBeLabeled(int r, int c, boolean[][] blackSquares) 
    {
        return (!(blackSquares[r][c]) &&
            (r == 0 || c == 0 || blackSquares[r - 1][c] ||
                blackSquares[r][c - 1]));
    } 

    /** Constructs a crossword puzzle grid.
     *  Precondition: There is at least one row in blackSquares.
     *  Postcondition:
     *  - The crossword puzzle grid has the same dimensions as blackSquares.
     *  - The Square object at row r, column c is black if and only if
     *    blackSquares[r][c] is true.
     *  - The squares in the puzzle are labeled according to the crossword labeling rule.
     */
    public Main(boolean[][] blackSquares) 
    {
        puzzle = new Square[blackSquares.length][blackSquares[0].length];
        int num = 1;

        for (int r = 0; r < blackSquares.length; r++)
        {
            for (int c = 0; c < blackSquares[0].length; c++)
            {
                if (blackSquares[r][c])
                {
                    puzzle[r][c] = new Square(true, 0);
                }
                else
                {
                    if (toBeLabeled(r, c, blackSquares))
                    {
                        puzzle[r][c] = new Square(false, num);
                        num++;
                    }
                    else
                    {
                        puzzle[r][c] = new Square(false, 0);
                    }
                }
            }
        } 
    }

    // Driver (do not modify)
    public void driver() {
        for (Square[] row : puzzle) {
            for (Square s : row) {
                System.out.print(s + "\t");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        boolean[][] grid = {
            {true, false, false},
            {false, false, true},
            {false, true, false}
        };

        Main crossword = new Main(grid);
        crossword.driver();
    }
}
Main.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Scoring Guidelines (AP Official)

Part (a): toBeLabeled — 3 points

Intent: Return a boolean indicating whether a crossword grid square should be labeled with a positive number.

  • +1 Checks blackSquares[r][c]
  • +1 Checks for a black square or grid border above and to the left (no bounds errors)
  • +1 Returns correct boolean result

Part (b): Crossword Constructor — 6 points

Intent: Initialize each square in the crossword puzzle grid with the correct color and number.

  • +1 Initializes puzzle with correct dimensions
  • +1 Accesses all locations in puzzle
  • +1 Calls toBeLabeled correctly
  • +1 Creates and assigns Square objects
  • +1 Labels squares consecutively in row-major order starting at 1
  • +1 Final grid has correct color and numbers

Question-Specific Penalties

  • −2 Uses incorrect variable name instead of puzzle
  • −1 Uses array[].length instead of array[row].length

Course Timeline