Advent of Code 2023 - Day 2: Cube Conundrum

2023-12-02 :: programming, puzzle, racket

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

Our data today is as follows:

Game 1: 3 blue, 4 red; 1 red, 2 green, 6 blue; 2 green
Game 2: 1 blue, 2 green; 3 green, 4 blue, 1 red; 1 green, 1 blue
Game 3: 8 green, 6 blue, 20 red; 5 blue, 4 red, 13 green; 5 green, 1 red
Game 4: 1 green, 3 red, 6 blue; 3 green, 6 red; 3 green, 15 blue, 14 red
Game 5: 6 red, 1 blue, 3 green; 2 blue, 1 red, 2 green

For today’s task, I found it helpful to make use of the parallel-combine combinator from Hanson & Sussman’s “Software Design for Flexibility”. This combinator applies f and g to the input, in parallel, and combines their output using h. Pictorially, it looks like this:

                   ┌───────────────────┐
                   │ parallel-combine  │
                   └───────────────────┘
        ┌──────────────────────────────────────────┐
        │                                          │
        │         ┌───────┐                        │
        │     n   │       │   1                    │
        │  ┌─────▶│   f   │──────┐                 │
        │  │      │       │      │      ┌───────┐  │
        │  │      └───────┘      │      │       │  │
  n  ───┼──┤                     ├─────▶│   h   │──┼───▶
        │  │      ┌───────┐      │      │       │  │
        │  │      │       │      │      └───────┘  │
        │  └─────▶│   g   │──────┘                 │
        │     n   │       │   1    ┌────────────┐  │
        │         └───────┘        │ h o (f, g) │  │
        │                          └────────────┘  │
        └──────────────────────────────────────────┘

I added the following function to the advent.rkt support module:

;; (parallel-combine h f g) -> any
;; h : procedure?
;; f : procedure?
;; g : procedure?
;;
;; Functions f and g take the same number of arguments. The input to
;; parallel-combine is passed to both of them. Their outputs are
;; combined by the function h, of two arguments.
;;
;; For example:
;; ((parallel-combine cons car (compose1 (curry map add1) cdr)) '(1 2 3))
;; -> '(1 3 4)
;;
;; A combinator from "Software Design for Flexibility" by Hanson &
;; Sussman
(define (parallel-combine h f g)
  (define (the-combination . args)
    (h (apply f args) (apply g args)))

  the-combination)

((parallel-combine cons car (compose1 (curry map add1) cdr)) '(1 2 3))

’(1 3 4)

As always, first we’ll parse the data:

(define in (map (parallel-combine cons cadr (compose1 (curry chunk 2) (curry (flip drop) 2)))
                (parse-aoc 2 atoms)))

(car in)

----------------------------------------------------------------------------------------------------
day02.txt -> 10377 chars, 100 lines; first 3 lines; last 2 lines:
----------------------------------------------------------------------------------------------------
Game 1: 7 blue, 5 red; 10 red, 7 blue; 5 blue, 4 green, 15 red; 4 gree ... d; 5 red, 4 blue, 3 green
Game 2: 8 green, 3 red; 7 blue, 6 red, 8 green; 7 blue, 3 green, 6 red ... ; 6 blue, 3 green, 12 red
Game 3: 6 blue, 3 red, 7 green; 3 red, 3 green, 8 blue; 8 blue, 11 red ... n; 9 blue, 7 green, 1 red
...
Game 99: 6 blue, 11 red, 7 green; 9 red, 6 green, 1 blue; 9 red, 2 blue
Game 100: 1 red, 4 blue, 2 green; 6 red, 2 green, 11 blue; 1 red, 1 blue, 2 green; 1 red, 7 blue
----------------------------------------------------------------------------------------------------
(parse 2) -> 100 entries:
----------------------------------------------------------------------------------------------------
(("Game" 1 7 "blue" 5 "red" 10 "red" 7 "blue" 5 "blue" 4 "green" 15 "re ... "red" 4 "blue" 3 "green")
("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red" 8 "green" 7 "blue" 3 "gre ... blue" 3 "green" 12 "red")
...
("Game" 100 1 "red" 4 "blue" 2 "green" 6 "red" 2 "green" 11 "blue" 1 " ... "green" 1 "red" 7 "blue"))
----------------------------------------------------------------------------------------------------

’(1 (7 “blue”) (5 “red”) (10 “red”) (7 “blue”) (5 “blue”) (4 “green”) (15 “red”) (4 “green”) (6 “red”) (7 “blue”) (5 “green”) (8 “blue”) (4 “red”) (5 “red”) (4 “blue”) (3 “green”))

As shown in that last line, we now have a list of lines where each line is of the form:

(<id> (<n> <color) (<n> <color>) ...)

We used parallel-combine there because we need to both retain the id, which we do with cadr:

1 2	(define f cadr) (f '("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red"))

2

And we also need to create a list of pairs of numbers and colors. Which we do with:

(compose1 (curry chunk 2) (curry (flip drop) 2))

That’s a lot, so let’s break it down. First we just want to drop the first two items of the list, e.g.:

1	(drop '("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red") 2)

’(8 “green” 3 “red” 7 “blue” 6 “red”)

Unfortunately, the parameter order for drop doesn’t lend itself to partial application, so we use flip to flip the parameter order to have the list come last:

1	((flip drop) 2 '("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red"))

’(8 “green” 3 “red” 7 “blue” 6 “red”)

We then use curry to create a partially applied function so we can compose it:

1	((curry (flip drop) 2) '("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red"))

’(8 “green” 3 “red” 7 “blue” 6 “red”)

That provides the list we want to group into chunks. Again, we’ll use curry to partially apply chunk with the argument 2:

1	((curry chunk 2) '(8 "green" 3 "red" 7 "blue" 6 "red"))

’((8 “green”) (3 “red”) (7 “blue”) (6 “red”))

Composing those two functions gives us the function with which we can map over the input:

1 2	(define g (compose1 (curry chunk 2) (curry (flip drop) 2))) (g '("Game" 2 8 "green" 3 "red" 7 "blue" 6 "red"))

’((8 “green”) (3 “red”) (7 “blue”) (6 “red”))

We now have our f and g functions as follows:

f = cadr
g = (compose1 (curry chunk 2) (curry (flip drop) 2))

We’ll call f with the line, and we’ll call g with the line, and then combine those two results with h:

h = cons

The resulting combinator is:

(parallel-combine cons
                  cadr
                  (compose1 (curry chunk 2) (curry (flip drop) 2)

And the end result will be single list where the first element is the id and the rest of the list is pairs of (<n> <color>):

'(1 (7 "blue") (5 "red") (10 "red") (7 "blue") ...)

Our main function for today’s task is max-pixel. It will process a line, and return a 3-tuple of (red green blue) representing the maximum number for each of those colors:

(define (max-pixel lst [red 0] [green 0] [blue 0])
  (if (null? lst)
      (list red green blue)
      (match (car lst)
        [ (list n "red")   (max-pixel (cdr lst) (max n red) green blue) ]
        [ (list n "green") (max-pixel (cdr lst) red (max n green) blue) ]
        [ (list n "blue")  (max-pixel (cdr lst) red green (max n blue)) ])))

(max-pixel '((7 "green") (3 "blue") (9 "red") (4 "blue") (1 "green") (10 "red")))

’(10 7 4)

With the above in place, we can now solve both parts. Here’s the part1 function:

(define (part1)
  (define max-rgb '(12 13 14))
  (~> (map (parallel-combine cons car (compose1 max-pixel cdr)) in)
      (filter (compose1 (curry andmap >= max-rgb) cdr) _)
      (map car _)
      (list-sum _)))

Let’s break that down. We’ll make use of parallel-combine again, and convert the input lines into lines of the form '(id red green blue) where red, green and blue are the maximum values for those colors.

1
2
3

(define lst (map (parallel-combine cons car (compose1 max-pixel cdr)) in))

(take lst 10)

’((1 15 5 8) (2 12 8 7) (3 11 7 9) (4 5 4 1) (5 17 8 10) (6 13 6 8) (7 6 14 5) (8 9 3 9) (9 8 9 8) (10 14 12 5))

We then filter the list to retain only lines where the max color values don’t exceed the specified limits:

(define max-rgb '(12 13 14))

(define lst (filter (compose1 (curry andmap >= max-rgb) cdr) lst))

(take lst 3)

’((2 12 8 7) (3 11 7 9) (4 5 4 1))

Next, we extract the ids:

1
2
3

(define lst (map car lst))

(take lst 5)

’(2 3 4 8 9)

And sum them:

1	(list-sum lst)

2528

Part 2 is simpler, we just need to compute the max (red green blue) values for all of the lines, multiply those values together for each line, and sum all of those products:

(define (part2)
  (~> (map (compose1 max-pixel cdr) in)
      (map list-prod _)
      (list-sum)))

(part2)

67363