Overview
Context
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)))
|
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |