naitsu: Day 3: Mull It Over – Advent of Code 2024 in Racket

Day 3: Mull It Over – Advent of Code 2024 in Racket

Published on 06 Dec 2024 by Ashpool.

Day three presents us with a couple of simple pattern-matching problems. Regular expressions should make these easy. Let’s dive into it.

As always, the solutions are available on GitHub and all Racket code is released into the Public Domain.

Part One

Problem Statement (in a Nutshell)

We need to find some patterns in a long string and evaluate them. The pattern we are looking for looks like mul(X,Y), where X and Y are 1-3 digit integers. Evaluating such a pattern simply means multiplying those numbers together. The answer to the problem is the sum of all products across all patterns found in the string. The string also contains some noise, which should simply be ignored.

Solution

We can use regular expressions to find patterns. Evaluating and adding the results together is trivial.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#lang at-exp racket

(require (prefix-in seq: seq)
         relation/type)

(define (read-mul)
  (regexp-try-match @pregexp{mul\((\d{1,3}),(\d{1,3})\)}
                    (current-input-port)))

(define bytes->number (compose string->number bytes->string/utf-8))

(define (eval-mul match-result)
  (apply * (map bytes->number (cdr match-result))))

(define (main)
  (seq:foldl + 0 (seq:map eval-mul (->stream (in-producer read-mul #f)))))

(with-input-from-file "input" main)

The first thing that should catch your eye is the new word in the #lang reader form.

1

#lang at-exp racket

This is to allow us to use an extension of Racket that supports @-expressions. They were originaly introduced to the Racket ecosystem as a part of Scribble, the Racket documentation DSL, but they found use outside of it. For the purposes of our program they allow us to avoid quoting strings, serving as a sort of a replacement for “raw strings” implemented in other languages.

With @-expressions, writing regular expression constants is more pleasant as we don’t need to escape any backslashes that are very prevalent in regexps. The following two syntaxes mean the same thing:

@pregexp{mul\((\d{1,3}),(\d{1,3})\)}

#px"mul\\((\\d{1,3}),(\\d{1,3})\\)"

The use of @-expressions will be typical for problems that require the use of regular expressions.

We broke up the program into several functions to make it easier to understand. Let’s begin with read-mul.

6
7
8


(define (read-mul)
  (regexp-try-match @pregexp{mul\((\d{1,3}),(\d{1,3})\)}
                    (current-input-port)))

read-mul simply tries to read a pattern that satisfies the hard-coded regular expression from the input port, which, remember, is pointed to a file named input using the function with-input-from-file. The regular expression tries to find the first occurrence of a string that that looks like mul(X,Y). X and Y are capture groups, each matching a string of 1-3 digits.

If there is no match, regexp-try-match consumes nothing from the input port. If there is a match in the input port, it is returned as a list of bytes values like '(#"mul(666,399)" #"666" #"399") where the first element is the entire match, and any subsequent elements are the matches of the capture groups.

12
13


(define (eval-mul match-result)
  (apply * (map bytes->number (cdr match-result))))

Now that we’ve matched something, let’s evaluate it. We are only interested in the values of the capture groups, thus the cdr. We map bytes->number onto the list of matches and then simply multiply everything together.

15
16


(define (main)
  (seq:foldl + 0 (seq:map eval-mul (->stream (in-producer read-mul #f)))))

Putting everything together, we first create a stream produced by repeatedly calling the function read-mul until it returns #f. We map eval-mul onto the stream, and fold it with + to sum up all the products.

Part Two

Problem Statement (in a Nutshell)

For the second part we similarly need to find the mul(X,Y) instructions and evaluate them, but this time we also need to pay attention to two other kinds of instructions that enable conditional evaluation: do() and don't(). After the program encounters a don't() instruction it should ignore subsequent mul’s until a do() is encountered.

Evalutation is enabled by default, and the objective is similar: find the sum of results of evaluating all mul’s that are not disabled by a don't.

Solution

Update the regular expression to match any of mul(X,Y), do() or don't(). Loop over the matches, keeping track of whether or not evalutaion is enabled and adding each result of a mul(X,Y) evaluation to an accumulator when it is.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


#lang at-exp racket

(define (read-op)
  (regexp-try-match
   @pregexp{do\(\)|don't\(\)|mul\((\d{1,3}),(\d{1,3})\)}
   (current-input-port)))

(define bytes->number (compose string->number bytes->string/utf-8))

(define (main)
  (let ([is-mul-enabled #t]
        [acc 0])
    (for ([m (in-producer read-op #f)])
      (match m
        [(list #"do()" #f #f)
         (set! is-mul-enabled #t)]
        [(list #"don't()" #f #f)
         (set! is-mul-enabled #f)]
        [(list _ (app bytes->number a) (app bytes->number b))
         (when is-mul-enabled (set! acc (+ acc (* a b))))]))
    acc))

(with-input-from-file "input" main)

read-op is similar to read-mul from the first part except it matches any instruction that is significant: do(), don't(), or mul(X,Y).

For the main function, instead of foldl we opt for a more imperative style using a for loop with side-effects that modify the state (enable-mul? and acc). Folding would also be idiomatic, but less to my taste: the accumulator variable would need to be a struct.

As we loop over the results of repeatedly calling read-op (until it returns #f), we try match each result against one of the three templates.

15
16
17
18


        [(list #"do()" #f #f)
         (set! is-mul-enabled #t)]
        [(list #"don't()" #f #f)
         (set! is-mul-enabled #f)]

The first two templates match either do() or don't() and enable or disable mul evaluation, respectively. Note the use of byte-strings instead of regular strings: this is the consequence of using regexp-try-match directly on an input port.

19
20


        [(list _ (app bytes->number a) (app bytes->number b))
         (when is-mul-enabled (set! acc (+ acc (* a b))))]))

If the matched instruction is neither do() nor don't(), it must be mul(X,Y). Because the value of the entire match will vary depending on the arguments to mul, we don’t validate it (_ accepts anything), although it would be required in a more complex program.

The cool thing here is the (app ...) syntax in the template. Not only does it bind the match to a local name (a or b), but it also applies an arbitrary function (bytes->number in our case) to it before binding. After binding, we can simply multiply a * b (since they are both numbers at that point) and add the result to acc.

After the for loop is done, acc contains the answer.

Conclusion

With the right tools at our disposal (regular expressions and pattern matching), day 3 problems could be the easiest yet this year. Nevertheless, I hope you’ve learned something and I will see you in a future post.

Last updated: 08 Dec 2024.

Day 3: Mull It Over – Advent of Code 2024 in Racket

Table of Contents

Part One

Problem Statement (in a Nutshell)

Solution

Code

Part Two

Problem Statement (in a Nutshell)

Solution

Code

Conclusion