Advent of Code 2022 - Day 6: Tuning Trouble

2022-12-06 :: programming, puzzle, racket

1 2	#lang iracket/lang #:require racket (require "../advent.rkt")

Day 6

Tuning Trouble

Today’s puzzle has very similar parts! For both parts, our input is a single string, and the task is to determine how many characters we need to consume before finding a contiguous group of N unique characters. The only difference is the value of N.

As always, our first task is to parse the input:

1	(define in (car (parse-aoc 6 string->list)))

----------------------------------------------------------------------------------------------------
day06.txt -> 4096 chars, 1 lines; first 1 lines; last 1 lines:
----------------------------------------------------------------------------------------------------
pjbjvjtjljplppjssvtvwtwptptztltbtrrjgrjrzrqrjrbrhbrhrlllbpbdbbzqqgsqsh ... lhlhjnnbpdvnnfjrdfbdqmvcb
...
pjbjvjtjljplppjssvtvwtwptptztltbtrrjgrjrzrqrjrbrhbrhrlllbpbdbbzqqgsqsh ... lhlhjnnbpdvnnfjrdfbdqmvcb
----------------------------------------------------------------------------------------------------
(parse 6) -> 1 entries:
----------------------------------------------------------------------------------------------------
((#\p #\j #\b #\j #\v #\j #\t #\j #\l #\j #\p #\l #\p #\p #\j #\s #\s # ...  #\d #\q #\m #\v #\c #\b))
----------------------------------------------------------------------------------------------------

By passing the string->list function to our parser, we’ll parse each line into a list of chars; however, since parse-aoc expects to be parsing multiple lines of input, it returns a list of parsed lines, but we only have one, so we’ll use the car function to return the first, and only, element, the list.

Next, we’ll need a function that searches for a group of N unique chars, and returns how many chars we had to consume to find it. This function is the entire solution, so I’ll present the function, and the invocation for both parts, and then break it down in detail afterward:

(define (unique-group-end n lst)
  (~> (windows n lst)
      (enumerate _ n)
      (findf (compose not check-duplicates car) _)
      cdr))

(unique-group-end 4 in)  ; Part 1

1275

1	(unique-group-end 14 in) ; Part 2

3605

Now let’s look at each of the four parts in detail. First we’ll define our N as 4, and provide an example list of chars:

1 2	(define N 4) (define example-list (string->list "abacbdef"))

First task

The first task is to form a list of sliding windows of length N from the input. Our advent.rkt module contains a windows function we can use. For example:

1 2	(define task1 (windows N example-list)) task1

’((#\a #\b #\a #\c) (#\b #\a #\c #\b) (#\a #\c #\b #\d) (#\c #\b #\d #\e) (#\b #\d #\e #\f))

Second task

Our second task is to enumerate (defined in advent.rkt) the windows so we’ll know the position of the group we find. enumerate usually begins counting at 0, but by passing in N as the optional second argument, we’ll start there instead:

1 2	(define task2 (enumerate task1 N)) task2

’(((#\a #\b #\a #\c) . 4) ((#\b #\a #\c #\b) . 5) ((#\a #\c #\b #\d) . 6) ((#\c #\b #\d #\e) . 7) ((#\b #\d #\e #\f) . 8))

Third task

Our third task is the meaty one - find the first group of unique chars. The findf function accepts a predicate and a list, and returns the first element of the list for which the predicate returns true. Remember, because of our call to enumerate, our list elements are pairs. The first element of each pair is our group of chars (a list), and the second element is our position. So, we’ll form our predicate as a composition of 3 functions.

First we’ll use car to grab the group of chars:

1	(car '((#\a #\b #\a #\c) . 4))

’(#\a #\b #\a #\c)

Second we’ll use Racket’s check-duplicates to indicate whether the list contains any duplicates. Note: in Racket, the value #f is false and all other values are true. The check-duplicates either returns the first duplicate element in the list, if there is one, or #f if there are no duplicates:

1	(check-duplicates '(#\a #\b #\a #\c))

#\a

Ok, we have a duplicate, the char #\a, so the result is a truthy value.

Third we’ll use the not function since we want to know which groups do not have duplicates:

(not #\a)

#f

To compose a single predicate out of these 3 functions, we use compose as follows:

1	((compose not check-duplicates car) '((#\a #\b #\a #\c) . 4))

#f

Here is the resulting third task:

1 2	(define task3 (findf (compose not check-duplicates car) task2)) task3

’((#\a #\c #\b #\d) . 6)

Fourth task

Our fourth task is simply to grab the second element of the resulting pair with the cdr function:

1 2	(define task4 (cdr task3)) task4

6

Or, using our actual function to perform the entire pipeline:

1	(unique-group-end 4 example-list)

6

Summary

In summary, we do the following:

Form sliding windows of length N
Enumerate these window elements with a position
Find the first window that meets our criteria
Extract the position of the resulting window

I’m pleased with how easily Racket allows me to express today’s solution. Looking forward to tomorrow!