Skip to main content

Day 25: Code Chronicle

by @merlinorg

Puzzle description​

https://adventofcode.com/2024/day/25

Solution summary​

  1. Parse and partition the locks and keys.
  2. Find all lock and key combinations that could fit.
  3. Return the count of potential matches.

Parsing​

It's the last day of Advent of Code so we'll keep it simple. The input consists of a sequence of grids, separated by blank lines. Each grid is a sequence of lines consisting of the # and . characters. Locks have # characters in the first row, where keys have . characters. To parse this we'll just use simple string splitting.

First, we split the input into grids by matching on the blank lines. This gives us an array of strings, each grid represented by a single string. Then we partition this into two arrays; one the keys, and the other locks. For this, we use the partition method that takes a predicate; every grid that matches this predicate will be placed in the first array of the resulting tuple, the rest in the second.

val (locks, keys) = input.split("\n\n").partition(_.startsWith("#"))

In general, arrays are not the most ergonomic data structures to use, but for this final puzzle they are more than sufficient.

Matching​

To find all potential matches we will use a for comprehension to loop through all the locks, and then for each lock, through all the keys. For each pair of a lock and key, we want to determine whether there is any overlap that would prevent the key fitting the lock. We can perform this test by simply zipping the key and the lock strings; this gives us a collection of every corresponding character from each string. The key can fit the lock if there is no location containing a # character in both grids.

val matches = for
  lock <- locks
  key  <- keys
  if lock.zip(key).forall: (lockChar, keyChar) =>
    lockChar != '#' || keyChar != '#'
yield lock -> key

This returns all of the matching lock and key combinations; the solution to the puzzle is the size of this array.

Final code​

def part1(input: String): Int =
  val (locks, keys) = input.split("\n\n").partition(_.startsWith("#"))

  val matches = for
    lock <- locks
    key  <- keys
    if lock.zip(key).forall: (lockChar, keyChar) =>
      lockChar != '#' || keyChar != '#'
  yield lock -> key

  matches.length

Run it in the browser​

Part 1​

Solutions from the community​

Share your solution to the Scala community by editing this page. You can even write the whole article! See here for the expected format