🎄⌨️ Advent of Code 2018

Check-in [711f70]
Overview
Comment:Add first and second tries at Day 9 solutions — too slow!
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 711f70fcf589408957343f260fd24008609525531b46a857c9627d525af04e72
User & Date: joel on 2018-12-13 19:01:52
Original Comment: Add first and second tries at Day 9 solutions -- too slow!
Other Links: manifest | tags
Context
2018-12-14
04:46
Add Day 9 solution finally! check-in: 3893cb user: joel tags: trunk
2018-12-13
19:01
Add first and second tries at Day 9 solutions — too slow! check-in: 711f70 user: joel tags: trunk
2018-12-10
01:05
Add Day 9 input check-in: 404a9b user: joel tags: trunk
Changes

Added day09-try1.rkt version [f8315f].

































































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#lang racket

(require sugar 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)

(define circle (list 0))

;; Note these number refers to the “nth“ spots in their lists;
;; they are not zero-based!
(define cur-marble 1)
(define cur-player 1)

(define players (make-list num-players 0))

(define (set-next-player!)
  (define n (add1 cur-player))
  (set! cur-player (if (> n (length players)) (- n (length players)) n)))

(define (add-to-current-player-score! score)
  (define new-score (+ score (list-ref players (sub1 cur-player))))
  (set! players (list-set players (sub1 cur-player) new-score)))

;; Inserts an item into the `circle` list after the element specified
(define (insert-into-circle! val after-nth)
  (set! circle (append (take circle after-nth)
                       (list val)
                       (drop circle after-nth)))
  (set! cur-marble (add1 after-nth)))

;; Returns the count of the element in `circle` after which the
;; next marble should be placed
(define (next-marble-after-nth)
  (define n (add1 cur-marble))
  (cond [(> n (length circle)) (- n (length circle))]
        [else n]))

(define (remove-nth-marble! n)
  (set! circle (append (take circle (sub1 n))
                       (drop circle n)))
  (set! cur-marble n))

(define (score! marble-val)
  (define 7th-marble-clockwise
    (cond [(> cur-marble 7) (- cur-marble 7)]
          [else (+ (length circle) (- cur-marble 7))]))
  (define 7th-marble-value (list-ref circle (sub1 7th-marble-clockwise)))
  (define turn-score (+ marble-val 7th-marble-value))
  (add-to-current-player-score! turn-score)
  (set-next-player!)
  (remove-nth-marble! 7th-marble-clockwise))

;; Place a marble in the correct spot
(define (place-marble! new-marble-val)
  (cond [(zero? (modulo new-marble-val 23))
         (score! new-marble-val)]
        [else
         (define after-nth (next-marble-after-nth))
         (insert-into-circle! new-marble-val after-nth)]))

(define (test n)
  (for ([i (in-range n)])
        (place-marble! (add1 i))))

;; Gets me the correct answer (374287)
(define (day09-part1)
  (for ([i (in-range last-marble-pts)])
       (place-marble! (add1 i)))
  (apply max players))


;; I left this running overnight and it did not finish!
(define (day09-part2)
  (set! last-marble-pts (* 100 last-marble-pts))
  (day09-part1))

Added day09-try2.rkt version [7a2374].





























































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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)))