Day 2: Red-Nosed Reports – Advent of Code 2024 in Racket

Published on 06 Dec 2024 by Ashpool.

Welcome back to Advent of Code 2024. Today we will be taking a look at day 2 problems.

Feel free to check out and star the solutions on GitHub. All Racket code snippets in this article are released into the Public Domain.

Table of Contents

Part One

Problem Statement (in a Nutshell)

Each line of the input data represents a report which consists of a few whitespace-separated integers called levels. A report is considered safe if both of the following conditions are met.

1. The sequence of levels in the report is either strictly increasing or strictly decreasing.
2. The absolute difference between each two consecutive levels is not greater than three.

The task for the first part is simply to calculate how many reports among the input data are safe.

Solution

The overall plan is as follows.

1. Define a function to tell if a report is safe. This is straightforward to do by analyzing the differences between consecutive levels either iteratively or recursively.
2. Use the predicate to filter for and count safe reports.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#lang racket

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

(define (string->numbers str)
  (map string->number (string-split str)))

(define (levels-safe? levels [trend-before 'trend-unknown])
  (match levels
    [(list) #t]
    [(list _) #t]
    [(cons head tail)
     (let*
         ([next (first tail)]
          [step (- next head)]
          [trend (cond [(positive? step) 'trend-up]
                       [(negative? step) 'trend-down]
                       [else 'trend-constant])])
       (and (not (eq? trend 'trend-constant))
            (or (eq? trend-before 'trend-unknown)
                (eq? trend-before trend))
            (<= (abs step) 3)
            (levels-safe? tail trend)))]))

(define (main)
  (seq:length (seq:filter (compose levels-safe? string->numbers)
                          (type:->stream (in-lines)))))

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

Let’s write a function to find out if a given report is safe by thinking recusively. We will name this predicate levels-safe?. Note the question mark in the function name, which is a convention when naming predicates in Racket.

Ignore the second (optional) argument for now. The first thing the function does is try and match the levels argument against a few templates.

12
13

    [(list) #t]
    [(list _) #t]

The first two templates together establish the base case for the recursion, i.e. the (remaining) levels sequence having less than two levels. The first template matches an empty list, and the second template matches a single-element list. As there is no more differences to analyze in either of this cases, the function returns true.

14

    [(cons head tail)

The third template defines the main case – a list consisting of two or more elements. Note the cons matching syntax used to deconstruct the list into its first element (head) and the list of remaining elements (tail) – this is a fundamental concept to understand in Racket and all Lisps, since a list in these languages is a series of linked cons cells.

15
16
17
18
19
20

     (let*
         ([next (first tail)]
          [step (- next head)]
          [trend (cond [(positive? step) 'trend-up]
                       [(negative? step) 'trend-down]
                       [else 'trend-constant])])

Once we have the head and the tail, we can calculate the difference (called step in the function) and the local trend. In another language it would be idiomatic use an enum or an optional integer for trend, however in Racket using symbols is more prevalent.

21
22
23
24
25

       (and (not (eq? trend 'trend-constant))
            (or (eq? trend-before 'trend-unknown)
                (eq? trend-before trend))
            (<= (abs step) 3)
            (levels-safe? tail trend)))]))

Here we arrive at the core logic of the function. It’s a 4-step and statement.

First, the function will return false if the current trend is constant (i.e. the difference is zero), because this is not allowed in a safe report.

Otherwise, the function will make sure that the trend here continues the trend that was observed before. This is where the optional argument trend-before comes into play. The function will check if trend-before is either 'trend-unknown (which is supposed to be the case during the outermost call when no trend has been observed yet) or the same as trend.

Next, if the trend condition is satisfied, the function will check if the absolute value of the step is not greater than 3, as per the problem statement.

Finally, if all other conditions are met, the function calls itself with the remainder of the list of levels, supplying the present trend as trend-before.

The main function is self-explanatory. We simply count how many lines satisfy levels-safe?, doing the necessary conversions along the way.

Part Two

Problem Statement (in a Nutshell)

For the second problem the notion of safety for a report is relaxed a bit. A report is still safe if it meets both conditions set forth in the first part. However, if we can make the report satisfy those conditions by removing any one level from it, it is now considered safe, also.

The task is, just like in the first part, to count the number of reports that are safe according to the new definition.

Solution

We only need to update the definition of safety. If the report is safe without changes, it is safe, period. Otherwise simply try to make it safe by consecutively removing each level and seeing if any such operation yeilds a safe sequence of levels.

A more efficient solution is possible, however, since reports are not very long, we decide not to complicate things.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#lang racket

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

(define (string->numbers str)
  (map string->number (string-split str)))

(define (levels-safe? levels [trend-before 'trend-unknown])
  (match levels
    [(list) #t]
    [(list _) #t]
    [(cons head tail)
     (let*
         ([next (first tail)]
          [step (- next head)]
          [trend (cond [(positive? step) 'trend-up]
                       [(negative? step) 'trend-down]
                       [else 'trend-constant])])
       (and (not (eq? trend 'trend-constant))
            (or (eq? trend-before 'trend-unknown)
                (eq? trend-before trend))
            (<= (abs step) 3)
            (levels-safe? tail trend)))]))

(define (levels-dampened-safe? levels)
  (or (levels-safe? levels)
      (for/or ([index (in-range (length levels))])
        (levels-safe? (type:->list (seq:remove-at index levels))))))

(define (main)
  (seq:length (seq:filter (compose levels-dampened-safe? string->numbers)
                          (type:->stream (in-lines)))))

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

The code remains the same for the most part. We only introduce one new function – levels-dampened-safe? – and use it instead of levels-safe? in the final calculation.

27
28
29
30

(define (levels-dampened-safe? levels)
  (or (levels-safe? levels)
      (for/or ([index (in-range (length levels))])
        (levels-safe? (type:->list (seq:remove-at index levels))))))

levels-dampened-safe? uses levels-safe? under the hood. First, if the given sequence of levels is already safe, it will return true. Otherwise, for each level index try to remove the level at that index from the list. If the new levels sequence is safe at any point, return true. Note the use of for/or for the iteration over indices: it will break as soon as any iteration returns a non-#f result.

Conclusion

Day 2 problems were not very complicated to solve or implement. I used them as an opportunity to bolster my command of recusion and pattern matching in Racket. As always, I hope you learned something!

Last updated: 08 Dec 2024.

Except where otherwise noted, the contents of this page are available under CC BY 4.0.
Built with Hugo. Theme by Ashpool. No cookies for you.