Advent of Code 2023-Day 2: Cube Conundrum
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:
We usedparallel-combine there because we need to both retain the id, which we do with cadr:
2
And we also need to create a list of pairs of numbers and colors. Which we do with:
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.:'(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:
'(8 "green" 3 "red" 7 "blue" 6 "red")
We then use curry to create a partially applied function so we can compose it:
'(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:
'((8 "green") (3 "red") (7 "blue") (6 "red"))
Composing those two functions gives us the function with which we can map over the input:
(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 with the line, and we'll call g with the line, and then combine those two results with h:
The resulting combinator is:
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>):
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 _)))
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 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:
'(2 3 4 8 9)
And sum them:
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:
67363