Advent of Code 2023-Day 4: Scratchcards

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

I always enjoy recursive list processing in Racket :) Here's our input today:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

For each card, the numbers before the | are "winning" numbers. The numbers after the | are "our" numbers. Our goal is to obtain a list where each element is the number indicating how many of "our" numbers matched a "winning" number. First let's get the raw input lines after splitting on " | ":

(define lines (parse-aoc 4 (λ (s) (string-split s " | ")) #:print-sample #f))

(for ([ line lines])
    (println line))

'("Card 1: 41 48 83 86 17" "83 86  6 31 17  9 48 53")
'("Card 2: 13 32 20 16 61" "61 30 68 82 17 32 24 19")
'("Card 3:  1 21 53 59 44" "69 82 63 72 16 21 14  1")
'("Card 4: 41 92 73 84 69" "59 84 76 51 58  5 54 83")
'("Card 5: 87 83 26 28 32" "88 30 70 12 93 22 82 36")
'("Card 6: 31 18 13 56 72" "74 77 10 23 35 67 36 11")

To reduce those lines to a single number indicating the number of matches, we'll:

Split each of the two strings on white space
For the first string, drop the 1st two strings, since we don't need them
Compute the set intersection of the two resulting lists
Count the number of elements in the set intersection

(define cards (map (λ (l)
                     (set-count (set-intersect (drop (string-split (car l)) 2)
                                               (string-split (cadr l)))))
                   lines))

cards

'(4 2 2 1 0 0)

Now we can solve the parts. For Part 1:

Filter the cards to only the ones with positive values
For each of those, compute the score with 2 ^ (n-1)
Sum all of the scores

(define (part1 cards)
  (list-sum (map (λ (n) (expt 2 (sub1 n))) (filter positive? cards))))

(part1 cards)

13

Part 2 is a little more difficult, but lends itself to a straightforward recursive solution. We'll create a function that excepts n (the number of elements to process) and cards (a list of scores). The function simply sums two numbers - n and the sum of recursively calling itself for each of the sublists.

(define (part2 n cards)
  (+ n (let loop ([ n n ][ cards cards ][ total 0 ])
         (cond [ (= n 0) total ]
               [ else (let ([ sub-total (part2 (car cards) (cdr cards)) ])
                        (loop (sub1 n) (cdr cards) (+ total sub-total))) ]))))

(part2 (length cards) cards)

30

Concluding Thoughts

There are a couple of things I like about the part 2 solution.

First: the solution is functional i.e. there is no mutation involved. I've found that an immutable, functional solution is almost always easier to both create and reason about.

Second: it's very efficient because once we create the initial list of cards, we're not allocating any additional data structures - we're simply traversing the same list repeatedly with calls to cdr, which returns the tail of the list via a pointer. The part2 function takes about 20 ms on my computer.