TileGame: 2009 FRQ 4

Snapping numbered puzzle tiles together so their touching edges always match is the premise of this AP Computer Science A free-response question — the twist is that a tile that doesn't fit right away might still fit after being spun in place a few times.

What This FRQ Tests

• AP CSA units: Unit 7 (ArrayList) and Unit 4 (Iteration)
• Core skill: searching an ArrayList for a valid insertion point by comparing a new item against its would-be neighbors on both sides
• Secondary skill: retrying an operation across a fixed, small number of states (here, a tile's four possible rotations) until one works or all have been tried
• Official category: this year's FRQ 4 tests ArrayList (Unit 7) rather than the 2D-array slot used in today's fixed FRQ-number-to-category pattern. 2009 predates the 2019–2020 CED redesign that formalized that ordering, and this particular year's exam doesn't include a 2D-array question at all — the exam's own printed "4." next to this question is what actually determines the "FRQ 4" label here, not the category.

The Setup

• The given NumberTile class provides methods you call but never modify:
  • void rotate() — rotates the tile 90 degrees clockwise (calling it 4 times returns a tile to its original orientation)
  • int getLeft() — the value on the tile's current left edge
  • int getRight() — the value on the tile's current right edge
• TileGame holds:
  • private ArrayList<NumberTile> board — the tiles currently placed, left to right, in order; guaranteed never null
• Tiles are meant to line up so that the touching edges of any two neighbors show the same number — the tile at a given position's right edge must equal the next tile's left edge.
• You're asked to write two methods:
  • private int getIndexForFit(NumberTile tile) — finds a valid ArrayList index for the tile in its current orientation only (no rotating here); returns -1 if it doesn't fit anywhere
  • public boolean insertTile(NumberTile tile) — tries to actually place the tile, rotating it as needed and checking all four orientations before giving up

Part (a): Writing getIndexForFit

The Rule, Broken Down

1. If the board is empty, any tile fits — at position 0.
2. The tile fits at the front if its right edge matches the current first tile's left edge.
3. The tile fits at the end if its left edge matches the current last tile's right edge.
4. The tile fits between two existing tiles at positions i and i + 1 if the tile's left edge matches position i's right edge, and the tile's right edge matches position i + 1's left edge — both have to hold at once.
5. If none of the above match anywhere, the tile doesn't fit in this orientation, and the method returns -1.

Step-by-Step Approach

1. Handle the empty-board case immediately: if board.size() == 0, return 0 right away.
2. Check the front-of-board case: compare the new tile's right edge to the first tile's left edge.
3. Loop through every adjacent pair of existing tiles, checking whether the new tile fits snugly between them.
4. Check the end-of-board case: compare the new tile's left edge to the last tile's right edge.
5. If none of these checks succeeded, return -1.

The Code

private int getIndexForFit(NumberTile tile)
{
    if (board.size() == 0)
    {
        return 0;
    }

    if (tile.getRight() == board.get(0).getLeft())
    {
        return 0;
    }

    for (int i = 0; i < board.size() - 1; i++)
    {
        if (board.get(i).getRight() == tile.getLeft()
                && tile.getRight() == board.get(i + 1).getLeft())
        {
            return i + 1;
        }
    }

    if (tile.getLeft() == board.get(board.size() - 1).getRight())
    {
        return board.size();
    }

    return -1;
}

Why Each Piece Matters

• The empty-board check comes first and returns immediately. Every other check in the method calls board.get(...), which would throw an exception on an empty list — so this case has to be handled before anything else runs.
• The "between" check tests both edges at once with &&. A tile could easily match one neighboring edge without matching the other; both conditions have to hold for the insertion point to actually work.
• The loop returns i + 1, not i. Inserting "between position i and position i + 1" means the new tile ends up occupying position i + 1 (and everything from the old i + 1 onward shifts right) — this is exactly how ArrayList.add(int index, E obj) behaves.
• The front and end checks are separate from the loop, since "before the first tile" and "after the last tile" only involve one existing neighbor, not two.

Tracing the Example

Using the question's own game board (edges shown as left/right only, since those are the only two exposed by NumberTile):

For tile1 (left 2, right 2, in its original orientation):

• Front check: tile1.getRight() (2) vs. board.get(0).getLeft() (4) — no match.
• Loop i = 0: board.get(0).getRight() (3) vs. tile1.getLeft() (2) — no match.
• Loop i = 1: board.get(1).getRight() (4) vs. tile1.getLeft() (2) — no match.
• Loop i = 2: board.get(2).getRight() (2) equals tile1.getLeft() (2), and tile1.getRight() (2) equals board.get(3).getLeft() (2) — both match! Returns i + 1 = 3.

That matches the question directly: "the call getIndexForFit(tile1) can return either 3 or 4." The loop happens to find the position-3 fit first and returns it immediately, which is one of the two accepted answers — the position-4 fit (between positions 3 and 4) also exists, but the method never needs to check further once a valid match is found.

For tile2 (left 8, right 2): the front check fails (2 ≠ 4), every loop iteration fails because no board tile's right edge is 8, and the end check also fails (8 ≠ 9). The method falls through to return -1; — matching the question's stated result exactly.

Common Mistakes to Avoid

• Calling board.get(0) before checking whether the board is empty. This throws an IndexOutOfBoundsException the moment the board has no tiles at all.
• Checking only one edge of a "between" fit. A tile matching the left neighbor but not the right one (or vice versa) is not a valid fit — both comparisons need &&, not two separate if statements that each return on their own.
• Returning i instead of i + 1 from the loop — this points at the existing tile being compared against, not the slot the new tile will actually occupy after insertion.
• Looping all the way to board.size() - 1 instead of stopping at board.size() - 2 (i.e., using i < board.size() - 1). Comparing position i to position i + 1 only makes sense while i + 1 is still a valid index.

Part (b): Writing insertTile

The Idea

• getIndexForFit (from part (a), assumed to work correctly regardless of what was written above) only checks the tile's current orientation — it never rotates anything itself.
• insertTile is responsible for trying all four possible orientations of the tile (its original orientation, plus after 1, 2, and 3 rotations) until one of them fits somewhere, or all four have failed.
• Since rotate() always turns the tile 90 degrees clockwise, calling it 4 times in a row returns the tile to exactly the orientation it started in — a detail that makes the "try every orientation" loop clean to write.

Step-by-Step Approach

1. Repeat up to 4 times (once per possible orientation).
2. On each attempt, call getIndexForFit on the tile in whatever orientation it's currently in.
3. If a valid index comes back (anything other than -1), insert the tile there with board.add(index, tile) and return true immediately.
4. If it didn't fit, rotate the tile once and try again.
5. If all 4 orientations have been tried and none worked, return false.

The Code

public boolean insertTile(NumberTile tile)
{
    for (int attempt = 0; attempt < 4; attempt++)
    {
        int index = getIndexForFit(tile);

        if (index != -1)
        {
            board.add(index, tile);
            return true;
        }

        tile.rotate();
    }

    return false;
}

Why Each Piece Matters

• The loop checks the tile's orientation before rotating, every time. This guarantees the tile's original orientation gets checked first (on attempt = 0), matching the natural expectation that a tile which already fits shouldn't need to be spun at all.
• board.add(index, tile) is the exact method listed on the AP Quick Reference sheet for inserting into an ArrayList at a specific position — it automatically shifts every tile from index onward one position to the right, which is exactly the postcondition the problem describes ("the order of the other tiles on the board relative to each other is not changed").
• Returning immediately after a successful add. The problem states the tile should be placed "at most 1 time" — stopping as soon as one orientation works prevents ever inserting it a second time in a different orientation.
• Four full rotations, not fewer. A tile has exactly 4 distinct orientations (0, 1, 2, or 3 rotations); checking fewer than that could miss an orientation that actually would have fit.

Tracing the Example

Placing the question's tile1 (left 2, right 2 originally) onto the same 5-tile board from part (a):

• Attempt 0 (no rotation yet): getIndexForFit(tile1) returns 3, exactly as traced above. Since this isn't -1, the method calls board.add(3, tile1) and returns true immediately — the tile never needs to rotate at all.

This matches the scenario the question walks through: "Assume that the new tile, in its original orientation, is inserted between the tiles at positions 2 and 3." Because the very first orientation checked already fits, insertTile places it there without ever calling rotate().

The question separately notes that if this same tile were rotated once, it would fit either before position 0 or after position 4 instead — since the original orientation already succeeds first, that rotated possibility is simply never reached in this particular trace. (The question doesn't give the tile's exact left/right values after a rotation, so that alternate placement isn't independently re-verified here — only the original-orientation placement that the worked example actually walks through.)

Common Mistakes to Avoid

• Rotating the tile before the first check. This would skip testing the tile's original orientation entirely, potentially missing a fit that didn't need any rotation.
• Forgetting to actually rotate on a failed attempt — an infinite loop isn't possible here since the loop is bounded at 4 iterations, but omitting tile.rotate() means every attempt after the first checks the exact same (failing) orientation over and over.
• Calling getIndexForFit a 5th time or rotating a 5th time. Only 4 distinct orientations exist; a 5th attempt would just repeat the first one.
• Not returning true immediately after a successful add. Continuing to loop afterward risks inserting the same tile again in a different orientation, violating "the tile should be placed at most 1 time."

Key Takeaways

• Inserting into a sorted or matched sequence almost always means checking three separate cases — fits at the front, fits at the end, and fits between two existing elements — with the "between" case needing both neighboring comparisons to hold at once.
• ArrayList.add(int index, E obj) does the position-shifting work automatically; once a valid index is found, placing the item is a single call.
• "Try every possible state until one works" is a bounded loop over a known, small number of variations (here, a tile's 4 rotations) — check the current state first, then transform and retry, and stop as soon as something succeeds.