Day 12: Shape Counting

Problem

Count regions where the total shape area fits in the grid.

Each shape is 9 cells (3×3), so the condition is:

total_count * 9 <= width * height

Example

Given problems:

• width=10, height=10, total_count=11 → 11 * 9 = 99 ≤ 100 ✓
• width=5, height=5, total_count=3 → 3 * 9 = 27 ≤ 25 ✗
• width=10, height=10, total_count=12 → 12 * 9 = 108 > 100 ✗

Count = 1 (only the first one fits)

Circuit Interface

module I = struct
  type 'a t =
    { clock : 'a
    ; clear : 'a
    ; start : 'a
    ; problem_valid : 'a
    ; width : 'a [@bits 7]        (* Grid width up to 127 *)
    ; height : 'a [@bits 7]       (* Grid height up to 127 *)
    ; total_count : 'a [@bits 10]  (* Total count up to 1023 *)
    }
  [@@deriving hardcaml]
end

module O = struct
  type 'a t =
    { possible_count : 'a [@bits 16]  (* Result counter *)
    }
  [@@deriving hardcaml]
end

Key Implementation Details

Area Computation

Compute both areas with sufficient bit width:

let compute_width = 14 in  (* max 127 * 127 = 16129 *)

(* Grid area: width * height *)
let width_ext = uresize ~width:compute_width width in
let height_ext = uresize ~width:compute_width height in
let grid_area = width_ext *: height_ext in

(* Shape area: total_count * 9 *)
let count_ext = uresize ~width:compute_width total_count in
let nine = of_int_trunc ~width:compute_width 9 in
let shape_area = count_ext *: nine in

Comparison

Check if shapes fit:

let fits = shape_area <=: grid_area in

State Machine

compile
  [ when_ start
      [ possible_count <-- zero result_bits
      ]
  ; when_ problem_valid
      [ when_ fits [ possible_count <-- possible_count.value +: one result_bits ]
      ]
  ];

Testing

The test harness provides problems one at a time:

(* Start counting *)
inputs.start := Bits.vdd;
Cyclesim.cycle sim;

(* Problem 1: width=10, height=10, count=11 → fits *)
inputs.width := Bits.of_int ~width:7 10;
inputs.height := Bits.of_int ~width:7 10;
inputs.total_count := Bits.of_int ~width:10 11;
inputs.problem_valid := Bits.vdd;
Cyclesim.cycle sim;
(* possible_count = 1 *)

(* Problem 2: width=5, height=5, count=3 → doesn't fit *)
inputs.width := Bits.of_int ~width:7 5;
inputs.height := Bits.of_int ~width:7 5;
inputs.total_count := Bits.of_int ~width:10 3;
inputs.problem_valid := Bits.vdd;
Cyclesim.cycle sim;
(* possible_count = 1 (unchanged) *)

Key Concepts

Bit Width Selection

Choose bit widths carefully:

• width and height: 7 bits (0-127)
• total_count: 10 bits (0-1023)
• compute_width: 14 bits (for 127 * 127 = 16129)
• result_bits: 16 bits (for counting up to 65535 problems)

Multiplication

Hardware multipliers are expensive but necessary here. The circuit computes:

• grid_area = width * height
• shape_area = total_count * 9

Comparison

The comparison shape_area <= grid_area is straightforward in hardware - just a comparator circuit.

Try it in IDE →