Day 12 Writeup

Note: This writeup was generated with assistance from GitHub Copilot to document the solution and pedagogical approach.

Summary

Day 12 involved determining how many regions under Christmas trees can fit oddly-shaped presents without overlapping. The presents can be rotated or flipped on a 2D grid to fit better. However, the “trick” in this problem is that no complex packing algorithms are needed. Instead, you can solve it by simply checking if the total area of the presents is less than or equal to the area of the region.

The problem demonstrated the value of starting with simple checks before diving into complex algorithms. It also highlighted optimization techniques for problems that appear to be NP-hard but turn out to have simpler solutions.

Key Concepts

  • 2D Bin Packing Feasibility: This refers to the challenge of determining whether a set of shapes can fit into a given rectangular area without any of the shapes overlapping each other. It’s like trying to pack items into a box without wasting space or having items stick out.
  • Backtracking: This is a recursive algorithm technique where you try different options step by step. If a choice leads to a dead end, you backtrack and try a different path. In this context, it involves trying to place shapes in various positions and orientations until a valid arrangement is found or all options are exhausted.
  • Area-Based Heuristic: A heuristic is a rule of thumb or shortcut for solving a problem. Here, it means stopping early if the total area of the remaining shapes to place is larger than the available space in the region. This prunes the search tree and speeds up the process.
  • Shape Transformations: Shapes can be rotated (turned 90 degrees) or flipped (mirrored horizontally or vertically) to find orientations that fit better in the available space.
  • Encapsulation: This is an object-oriented programming principle where data and related methods are bundled together in a class, hiding internal implementation details. The Shape class encapsulates the grid data and methods like area calculation and transformations.
  • Trivial Solution Insight: Sometimes, a problem that seems complex has a very simple solution once you recognize the key constraints. In this case, the insight was that area alone determines feasibility, making advanced methods unnecessary.

Approach

The Development Journey: From Confusion to Clarity

Day 12 started as a seemingly straightforward 2D bin packing problem, but it quickly became a lesson in over-engineering and recognizing “trick” problems. What began as simple parsing in the main class evolved into a full object-oriented design, only to be simplified back down. Here’s the detailed path we took, including all the wrong turns.

Initial Parsing: Building Directly in Day12

We started by parsing the input directly in the Day12 class. The input format was complex: shapes defined with indices and grid representations, followed by regions with dimensions and shape counts. Our first implementation read the input line by line, building shapes as 2D boolean arrays on the fly.

// Early parsing code (simplified)
ArrayList<boolean[][]> shapes = new ArrayList<>();
// Read shape grids directly into boolean arrays
for each shape block:
    boolean[][] grid = new boolean[height][width];
    // Parse # and . into true/false
    shapes.add(grid);

This worked for basic reading, but it was messy—parsing logic mixed with the main logic, and shapes had no methods. We realized we needed better abstraction.

Creating the Shape Class: Encapsulation and Methods

To clean up, we extracted shape handling into a dedicated Shape class. This was a key encapsulation step: bundling the grid data with methods for area calculation, rotations, and flips. The parsing moved to create Shape objects from the input grids.

public class Shape {
    private boolean[][] occupied;
    // Constructor from ArrayList<String> gridLines
    // Methods: getArea(), rotate90Clockwise(), flipHorizontal(), getAllOrientations()
}

Parsing now called new Shape(gridLines) for each shape block. This made the code more modular and reusable, aligning with OOP principles.

First Algorithm Attempt: ILP with ojAlgo

Confident in our parsing, we tackled the core problem. The user suggested starting with Integer Linear Programming using the ojAlgo library, since we had used it successfully in the past few days. We modeled variables for each possible shape placement (shape index, orientation, x, y) and constraints for no-overlap.

But this was a wrong turn: the real input had too many placements (thousands), causing memory overflow. ojAlgo couldn’t handle the scale, and we abandoned ILP after hours of debugging.

Backtracking: The Slow but Correct Path

Next, we implemented recursive backtracking. Generate all possible placements for each shape type, then recursively try placing them without overlap, using a grid to track occupied cells.

This worked for the sample (finding 2 feasible regions) but took 5 minutes—exponential time made it unusable for real input. We added sorting by area (largest first) and basic pruning, but it wasn’t enough.

CP-SAT with OR-Tools: Library Hell

Seeking efficiency, the user sought out Constraint Programming SAT with OR-Tools as an improvement over backtracking, and I agreed it was a better fit. This involved downloading jars, setting up JNA and Protobuf dependencies, and writing CP model code with boolean variables and no-overlap constraints.

Another wrong turn: OR-Tools requires native libraries, but macOS ARM64 binaries weren’t available. We spent time on failed downloads and classpath issues. The user got annoyed when I initially gave up and reimplemented backtracking, but ultimately we abandoned CP-SAT due to the unresolved library problems.

Optimized Backtracking with Heuristic: Partial Success

When we struggled with CP-SAT, the user looked again at the area-based heuristic through further web research. Returning to backtracking, we added this heuristic: if remaining shape area > available grid space, prune the branch. Due to overwriting the real input file with sample data, what we thought was the real input (taking 9 seconds) was actually the sample. The actual real input took 0.9 seconds.

It gave the correct answer, but we knew there had to be a better way.

The Trick Revelation: Simple Area Check

Testing the heuristic, we realized the area check alone matched the backtracking results. No overlaps needed checking—the problem was just “does total shape area fit in region area?” This trivial solution ran in 10 ms.

We had over-engineered for nothing, but learned valuable lessons about starting simple and recognizing constraints.

Attempts Made (Detailed):

  1. Direct Parsing in Day12: Quick start, but unmaintainable. Moved to Shape class for encapsulation.
  2. ILP with ojAlgo: Mathematically sound but memory-intensive. Failed on real input scale.
  3. Basic Backtracking: Correct but slow (5+ minutes). Exponential complexity doomed it.
  4. CP-SAT with OR-Tools: Promising but library issues (missing ARM64 natives) blocked it.
  5. Heuristic Backtracking: Added area pruning and sorting. Fast enough (0.9s) but overkill.
  6. Area Summation: The trick—sum areas ≤ region area. Instant and correct.

Final Solution

After all detours, the solution is embarrassingly simple: for each region, calculate total occupied cells of required shapes and check if ≤ W×H. No packing, no overlaps—just area math.

Code Implementation

Parsing Input

The input parsing reads the shape definitions and region requirements. Shapes are defined first, each starting with an index and colon, followed by the grid representation. Regions are listed as “WxH: count1 count2 …” where W and H are dimensions and counts are the number of each shape needed.

private void parseInput(ArrayList<String> input) {
    shapes = new ArrayList<>();
    regions = new ArrayList<>();
    
    int i = 0;
    // Parse shapes
    while (i < input.size()) {
        String line = input.get(i);
        if (line.contains("x") && line.contains(":")) break; // Start of regions
        
        if (line.endsWith(":")) {
            int shapeIndex = Integer.parseInt(line.substring(0, line.length()-1));
            i++;
            ArrayList<String> gridLines = new ArrayList<>();
            while (i < input.size() && !input.get(i).isEmpty() && !input.get(i).endsWith(":")) {
                gridLines.add(input.get(i));
                i++;
            }
            // Create shape from gridLines
            shapes.add(new Shape(gridLines));
        } else {
            i++;
        }
    }
    
    // Parse regions
    for (; i < input.size(); i++) {
        String line = input.get(i);
        if (line.isEmpty()) continue;
        String[] parts = line.split(": ");
        String[] size = parts[0].split("x");
        int width = Integer.parseInt(size[0]);
        int height = Integer.parseInt(size[1]);
        String[] quantities = parts[1].split(" ");
        int[] counts = new int[quantities.length];
        for (int j = 0; j < quantities.length; j++) {
            counts[j] = Integer.parseInt(quantities[j]);
        }
        regions.add(new Region(width, height, counts));
    }
}

Shape Class with Area Calculation

The Shape class represents each present shape. It includes methods for rotations and flips. The getArea() method counts the number of occupied cells, which represent the actual space the shape takes up.

public int getArea() {
    int count = 0;
    for (int r = 0; r < height; r++) {
        for (int c = 0; c < width; c++) {
            if (occupied[r][c]) count++;
        }
    }
    return count;
}

Simple Area Check

This method performs the final, trivial check for each region. It multiplies each shape’s area by the number of times it appears and sums them up. Then, it compares this total to the region’s total area (width times height).

private boolean simpleAreaCheck(Region region) {
    int W = region.getWidth();
    int H = region.getHeight();
    int[] counts = region.getShapeCounts();
    
    int totalArea = 0;
    for (int s = 0; s < counts.length; s++) {
        if (counts[s] > 0) {
            totalArea += shapes.get(s).getArea() * counts[s];
        }
    }
    
    return totalArea <= W * H;
}

Learning Objectives

  • AP CSA Alignment: This problem reinforces working with arrays and loops for calculations like area summing. It also introduces backtracking for search problems, which aligns with teaching recursion and managing program state.
  • CSTA Standards for Teachers: This aligns with CSTA 2-AP-10, which is about using abstractions to manage complexity in programs. It also matches 2-AP-13 for systematically testing and refining algorithms, and 2-AP-14 for debugging and improving solutions. Teachers can use this to discuss heuristic optimization and recognizing when a problem has a simpler solution than it appears.

Challenges

  • The problem appeared to be NP-hard, which led us to try overly complex solutions like ILP and CP-SAT.
  • Setting up external libraries like OR-Tools highlighted the challenges of dependency management in programming projects.
  • The initial slow performance of backtracking prompted us to develop heuristics, which demonstrated the importance of iterative optimization in problem-solving.

Results

  • For the sample input, there were 2 regions that could fit all their required presents.
  • For the real input, there were regions that could fit all their presents.
  • The final runtime for the simple area check was just 10 milliseconds.
  • The key lesson from this problem is to always consider simple solutions before jumping into complex algorithms!