blob: 640dccab4b5891e423da99f8a49f12fb125418cb (
plain)
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
81
82
83
84
85
86
87
88
|
(define-module (day09)
#:use-module (ice-9 rdelim)
#:use-module (srfi srfi-9))
(define (check-spot disk-offset file-id times)
; n+(n+1)+...+(n+k-1)=k*(2*n+k-1)/2=k*(n+(k-1)/2)
(* file-id times (+ disk-offset (/ (- times 1) 2))))
(define (num-at s pos)
(- (char->integer (string-ref s pos))
(char->integer #\0)))
(define (compact-checksum s)
(define (iter-used offset sid eid etimes acc)
(if (= sid eid)
(+ acc (check-spot offset sid etimes))
(let ((times (num-at s (* 2 sid))))
(iter-free (+ offset times)
sid
(num-at s (+ 1 (* 2 sid)))
eid
etimes
(+ acc (check-spot offset sid times))))))
(define (iter-free offset sprevid stimes eid etimes acc)
(cond ((= sprevid eid) acc)
((>= stimes etimes)
(iter-free (+ offset etimes)
sprevid
(- stimes etimes)
(- eid 1)
(num-at s (* 2 (- eid 1)))
(+ acc (check-spot offset eid etimes))))
(else (iter-used (+ offset stimes)
(+ sprevid 1)
eid
(- etimes stimes)
(+ acc (check-spot offset eid stimes))))))
(define last-id (quotient (- (string-length s) 1) 2))
(iter-used 0 0 last-id (num-at s (* 2 last-id)) 0))
(define* (part1 #:optional (input (current-input-port)))
(compact-checksum (read-line input)))
(define-record-type <zone> (zone offset length id) zone?
(offset zone-offset)
(length zone-length)
(id zone-id))
(define (displace-free z n)
(zone (+ (zone-offset z) n)
(- (zone-length z) n)
(zone-id z)))
(define (string->free+revused s)
(define (iter id off free used)
(if (>= (* 2 id) (string-length s))
(values (reverse free) used)
(let ((freelen (num-at s (- (* 2 id) 1)))
(usedlen (num-at s (* 2 id))))
(iter (+ 1 id)
(+ off freelen usedlen)
(cons (zone off freelen #f) free)
(cons (zone (+ off freelen) usedlen id) used)))))
(iter 1 (num-at s 0) '() (list (zone 0 (num-at s 0) 0))))
(define (defrag-checksum free revused)
(define (iter-used lst sum)
(if (null? lst)
sum
(let ((off (zone-offset (car lst)))
(len (zone-length (car lst))))
(define (reserve-free! lst)
(cond ((null? lst) off)
((> (zone-offset (car lst)) off) off)
((>= (zone-length (car lst)) len)
(let ((new-off (zone-offset (car lst))))
(set-car! lst (displace-free (car lst) len))
new-off))
(else (reserve-free! (cdr lst)))))
(define new-off (reserve-free! free))
(iter-used (cdr lst) (+ sum (check-spot new-off (zone-id (car lst)) len))))))
(iter-used revused 0))
(define* (part2 #:optional (input (current-input-port)))
(call-with-values (lambda () (string->free+revused (read-line input)))
defrag-checksum))
|
