Rules: no spoilers.

The other rules are made up as we go along.

Share code by link to a forge, home page, pastebin (Eric Wastl has one here) or code section in a comment.

  • datarama@awful.systems
    link
    fedilink
    English
    arrow-up
    5
    ·
    edit-2
    1 year ago

    Day 4: Scratchcards

    Scheme code and explanations

    This problem feels a bit more Scheme-shaped. To keep things interesting, I have chosen to stick to pure functional programming.

    A card consists of three components – a card number (which turned out to be completely unnecessary), a list of winning numbers, and a list of numbers. Here’s a function to parse a card from a string, turning it into a 3-element list:

    (define (parse-card card)
      (let* ((parts (string-split card ":"))
             (numlists (string-split (cadr parts) "|")))
        (list (string->number (string-drop (car parts) 5))
              (map string->number (string-split (car numlists) " "))
              (map string->number (string-split (cadr numlists) " "))
    

    The value of a card is easy enough to compute. The first matched winning number sets the value to 1, every subsequent one doubles it.

    (define (card-value card)
      (let* ((card-parts (parse-card card))
             (winning-numbers (cadr card-parts)))
        (let loop ((nums (caddr card-parts)) (val 0))
          (cond ((null? nums) val)
                ((and (= val 0) (memq (car nums) winning-numbers)) (loop (cdr nums) 1))
                ((memq (car nums) winning-numbers) (loop (cdr nums) (* val 2)))
                (else (loop (cdr nums) val))))))
    

    Solving part 1 is now straightforward:

    (define (solve-part-1 cards)
      (apply + (map card-value cards)))
    

    But oh no! Turns out I (or the elf) got the rules wrong, and apparently the game requires so many dead trees to play that I think it was probably designed by Jair Bolsonaro.

    A function to count the card matches (eg. how many numbers match a winning number) is easily adapted from the above:

    (define (card-matches card)
      (let* ((card-parts (parse-card card))
             (winning-numbers (cadr card-parts)))
        (let loop ((nums (caddr card-parts)) (val 0))
          (cond ((null? nums) val)
                ((memq (car nums) winning-numbers) (loop (cdr nums) (+ val 1)))
                (else (loop (cdr nums) val))))))
    

    My strategy here is to have two lists: One of the card matches of all cards, the other of how many instances I have of each card. The second list will start as (1 1 1 1 ... ), and I need to be able to add some number x to the first n cards in the list. For example, if I have 4 instances of the first card, and it has 2 matches, then I’ll want to add 4 to however many instances I have of the next 2 cards. Here’s a function that reaches into a list and does just that:

    (define (reach x n l)
      (if (or (= n 0) (null? l))
        l
        (cons (+ x (car l)) (reach x (- n 1) (cdr l)))))
    

    Using this, here’s a recursive function that counts cards, given the two aforementioned lists:

    (define (count-cards matches cards)
      (if (null? cards) 0
        (+ (car cards)
           (count-cards (cdr matches)
                        (reach (car cards) (car matches) (cdr cards))))))
    

    Solving part 2 is now easy:

    (define (solve-part-2 lines)
      (count-cards (map card-matches lines) (map (lambda (x) 1) lines)))
    

    There you have it. It’d have been shorter if I had allowed myself some side effects, but pure functional programming is terrific fun.