Advent of Code is an annual Advent calendar featuring small programming puzzles created by Eric Wastl, which has been running every December since 2015. Being the puzzle-lovers we are, a bunch of us at Jane Street participate in Advent of Code every year.

There’s a recurring tradition in the Advent of Code community known as “Upping the Ante” which entails solving or visualizing the puzzles in some unorthodox way, whether by code-golfing, using esoteric programming languages, or Excel, SQL—even implementing solutions entirely inside of video games.

For 2024, I spent a few weekends trying to solve some of the puzzles entirely on an FPGA. It’s an interesting challenge adapting classic algorithms like graph traversal, sorting, dynamic programming, and recursion to the unique capabilities of the FPGA. Choosing to target a relatively small FPGA part (84K LUTs, 4 Mbits of RAM) also requires some algorithmic optimizations which would not be a consideration if running on a regular computer.

Why use Hardcaml for this project?

I decided to implement this project in Hardcaml, which is an open-source Hardware Description Language embedded inside of OCaml that we maintain at Jane Street. Hardcaml includes a simulation backend as well as support for compiling down to RTL, so the entire project, from designing the hardware to validating the design to synthesizing it for an FPGA, is done in OCaml.

To get the advantages of implementing software algorithms in hardware, you usually have to “unroll” iterative or sequential operations into a hardware pipeline that can compute many things in parallel. Traditional HDLs offer only very primitive generation features, so this unrolling becomes unwieldy, and tends to result in code that’s hard to read and to reuse across projects.

Hardcaml’s strong type system and expressive metaprogramming capabilities allow us to implement highly flexible circuits concisely using OCaml. This also eliminates the risk of type-confusion bugs (in hardware, everything’s just a wire, but we can assign semantic meanings to those wires using OCaml’s type system), and makes the resultant code easier to understand and adapt. The ability to parametrize components using functors and higher-order functions lets us easily reuse them across designs and projects.

All of this also makes the development experience a lot more efficient and enjoyable, which are particularly imporant traits when working on a side-project.

Targeting a new FPGA platform

In keeping with the open source theme, I decided to target the Lattice ECP5 FPGA chip, using the open-source Yosys + NextPNR toolchain. The ECP5 provides a sufficient variety of resources for such a project, while still being small enough to make resource utilization an important consideration.

I defined an extensible OCaml interface, which would then be implemented by each puzzle’s solution. Along with a NextPNR build script and a top-level board wrapper (to set up the clock, UART and other peripherals), it made it very easy to add a new design to the project; I could write the top-level of each puzzle solution as a module that implemented the Ulx3s.Design module type, and then add it to the list defined in build.ml. I set up something similar for parsing the puzzle inputs as well, which meant that all of the parsing and setup code could be shared between the simulation tests as well as for interfacing with the actual FPGA board.

Day 4: Sliding window with higher-order functions

Day 4’s puzzle entails taking an ASCII word-search grid, and searching for occurrences of the string “XMAS” in any orientation: horizontal, vertical, diagonal, or reversed. This lends itself nicely to a “convolution” approach, where we use a shift register to store the most recent 4 rows of the grid, and compute an appropriately-sized sliding window on each cycle.

One tricky part is that we actually need several different-sized sliding windows (1x4, 4x1, 4x4) to match horizontal, vertical, and diagonal strings respectively. This is further complicated by the fact that part 2 requires searching for the string “MAS” in an X shape, while ignoring the squares that don’t overlap with the X.

Hardcaml makes this quite nice to implement, as we can implement a higher-order function to construct such a sliding window for any given dimensions, and then apply a provided function to check the sliding window against some condition and output a result. We can take advantage of OCaml types to represent the variable-dimension window as a nested array at build time, but still flatten it down to a fixed-width signal when generating the actual RTL.

(* For each possible orientation (horizontal, vertical, and both diagonals,
   build a sliding window to check for the XMAS. *)
let part1_count =
  let pattern = List.map [ 'X'; 'M'; 'A'; 'S' ] ~f:char_to_xmas in
  [ (* Horizontal *)
    make_sliding_window ~width:4 ~height:1 ~check_fn:(fun window ->
      window |> window_to_row |> list_match_reversible ~pattern)
    (* Vertical *)
  ; make_sliding_window ~width:1 ~height:4 ~check_fn:(fun window ->
      window |> window_to_col |> list_match_reversible ~pattern)
    (* Forward diagonal *)
  ; make_sliding_window ~width:4 ~height:4 ~check_fn:(fun window ->
      window |> window_to_diag |> list_match_reversible ~pattern)
    (* Reverse diagonal *)
  ; make_sliding_window ~width:4 ~height:4 ~check_fn:(fun window ->
      window |> window_to_rev_diag |> list_match_reversible ~pattern)
  ]
  |> reduce ~f:Uop.( +: )
in

(* There's several possible orientations in which the X-shaped MAS can match,
   check all of them. *)
let part2_count =
  let pattern = List.map [ 'S' ; 'M' ] ~f:char_to_xmas in
  make_sliding_window ~width:3 ~height:3 ~check_fn:(fun window ->
    match window with
    | [ [ c0; _; c1 ]; [ _; center; _ ]; [ c2; _; c3 ] ] ->
      let center_match = 
        center ==:. char_to_xmas 'A' in
      let pair1_match = 
        list_match_reversible ~pattern [ c0; c3 ] in
      let pair1_match =
        list_match_reversible ~pattern [ c1; c2 ] in
      center_match &: pair1_match &: pair2_match
    | ... )
in

Visualization of the sliding window search

Day 7’s puzzle involves filling operators into a provided sequence of numbers, to try to make an arithmetic expression that evaluates to some target number. This lends itself very nicely to a brute-force solution, iterating over every combination of operators and evaluating them to see if they match the goal. Fortunately, FPGAs are well-suited for such tasks, and Hardcaml makes it very easy to construct an extremely deep pipeline. Each pipeline stage takes the current accumulator, evaluates it against the next operator/operand, and then passes down the remaining input to the subsequent stage. This lets us average one attempt per clock cycle, allowing us to test hundreds of millions of operator combinations in a matter of seconds.

module Operator = struct
  module Cases = struct
    type t = Add | Mul | Cat | Nop
    [@@deriving sexp_of, compare, enumerate]
  end
  module Enum = Hardcaml.Enum.Make_enums (Cases)
  include Enum.Binary
end

(* Each stage of the pipeline contains the current accumulator, the goal value,
   and the remaining operands and operators *)
module Pipeline_state = struct
  type 'a t =
    { valid : 'a
    ; accum : 'a [@bits accum_bits]
    ; goal : 'a [@bits accum_bits]
    ; operands : 'a Operand.t list [@length max_seq_len - 1]
    ; operators : 'a Operator.t list [@length max_seq_len - 1]
    }
  [@@deriving hardcaml ~rtlmangle:"$"]
end

Engaging with the academic community

We love getting involved with the academic community and seeing all of the cutting-edge research happening in the space. Last year, a few of us presented Hardcaml and our work on accelerating MSM at the ISFPGA 2024 conference. We really enjoyed meeting everyone there, and attended again this year as a sponsor of the event. We demoed a visualization of one of the Advent of FPGA puzzle solutions at our table, which got quite a bit of interest and gave us a chance to talk further about why Hardcaml is so fundamental to our development process at Jane Street.

It was great to connect with the research community and hear about all of the exciting work going on in the FPGA space. We’ll also be at IEEE FCCM, FOSSi Latch-Up, and FPL this year. We’d love to chat with you, and you can even snag some limited-edition Hardcaml swag!

Our booth at ISFPGA 2025

How can I use Hardcaml?

If this piqued your interest in playing with Hardcaml, check out the Hardcaml GitHub page for all of our open-source Hardcaml libraries, tools, examples, and tutorials. Be sure to install the bleeding-edge opam repository to get all of our latest improvements and features.

Also check out this interview with Andy Ray (creator of Hardcaml) on Jane Street’s podcast Signals & Threads, as well as the “OCaml All the Way Down” tech talk on how we use OCaml to build our FPGAs and supporting software from the ground up.

Come work with us

We’re always looking to grow our team! If you’re excited about the idea of applying software development techniques and tools to design hardware more efficiently, and are interested in building FPGA accelerator systems with us at Jane Street, check out our experienced FPGA engineer and new grad FPGA engineer positions. We’ll also soon be hiring interns for Summer 2026, see this listing for more details and to be notified when the application opens.

If you’re currently pursuing or are soon starting a PhD in computer engineering or a related field, check out our Graduate Research Fellowship program as well!

An Open Challenge

Hardcaml isn’t the only Hardware Description Language of it’s kind. There’s many other open-source HDLs out there, but it’s not always easy to compare the usability of different languages against each other, especially when considering them for larger-scale projects. I think these Advent of Code puzzles are a great way to experiment with new languages: they involve both clever hardware optimizations (unrolling, heavy pipelining), but also more mundane things like sequencing, input parsing, and resource sharing. The relatively low complexity of the puzzles also makes it much easier to understand and compare implementations side-by-side.

I’ve also really enjoyed seeing others’ attempts at similar projects, such as this implementation of 2022 Day 1 in Clash (a Haskell-based hardware development language), and this design for 2024 Day 24 implemented in a 130nm silicon process, that the creator is actually working on getting manufactured into a physical chip through TinyTapeout!

So I’d like to issue a challenge: If you have a favorite HDL language (or even a High Level Synthesis framework) that you’d like to show off the capabilities of, try using it to solve some puzzles this December when Advent of Code 2025 rolls around, and share your results with the community!