🎄⌨️ Advent of Code 2018

day09-try2.rkt at trunk

File day09-try2.rkt artifact 7a2374 on branch trunk


#lang racket

(require rackunit)

(define input
  (map string->number
       (rest (regexp-match #px"(\\d+) players; last marble is worth (\\d+) points"
                           (file->string "day09-input.txt")))))

(match-define (list num-players last-marble-pts) input)

;; In this variation, the circle is stored as a list. The “current”
;; marble is always the first item in the list.
(define (insert-and-rotate circle val after-nth)
  (values (append (list val)
                  (drop circle (min after-nth (length circle)))
                  (take circle (min after-nth (length circle)))) 0))

;; Remove the marble in the Nth slot, rotating the “circle” so the marble
;; to the right of the removed one is now in the front.
;; Returns both the rotated list and the value of the removed marble
(define (remove-and-rotate circle nth)
  (values (append (drop circle nth) (take circle (sub1 nth))) (list-ref circle (sub1 nth))))

(define (add-to-spot lst pos val)
  (append (take lst pos)
          (list (+ val (list-ref lst pos)))
          (drop lst (add1 pos))))

(define (play-game num-players until-marble)
  (for/fold ([scores (make-list num-players 0)]
             [circle (list 0)])
            ([player (in-cycle (range num-players))]
             [cur-marble (in-naturals 1)])
    #:final (equal? cur-marble until-marble)
    (define-values (result-circle turn-score)
      (cond [(zero? (modulo cur-marble 23))
             (remove-and-rotate circle (- (length circle) 6))]
            [else
             (insert-and-rotate circle cur-marble 2)]))
    (values (add-to-spot scores player (* (+ cur-marble turn-score) (sgn turn-score))) result-circle)))

(define (high-score num-players until-marble)
  (let-values ([(scores _) (play-game num-players until-marble)])
    (apply max scores)))

; Finishes in 78 seconds on a 2015 Apple rMBP
(define (day09-part1)
  (high-score num-players last-marble-pts))

(module+ test
  ;(check-equal? (high-score 10 1618) 8317)
  ;(check-equal? (high-score 13 7999) 146373)
  ;(check-equal? (high-score 17 1104) 2764)
  ;(check-equal? (high-score 21 6111) 54718)
  ;(check-equal? (high-score 30 5807) 37305)

  (check-equal? (time (day09-part1)) 374287)) ; Correct answer for part 1

; Ran overnight — still didn’t finish!
(define (day09-part2)
  (high-score num-players (* 100 last-marble-pts)))