blob: a8f0e6702976800740444546e1c502b72d99db1f (
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
|
#lang racket
(require "../lib/utils.rkt")
(define lines
(call-with-input-file "input"
(λ (fp) (get-lines fp))))
(set! lines (list->vector lines))
(define (transpose linesvec)
(define lines (vector->list linesvec))
(define width (string-length (vector-ref linesvec 0)))
(define new-lines (make-vector width))
(let loop ((i 0))
(if (>= i width)
new-lines
(let ()
(define char-list (map (λ (l) (string-ref l i)) lines))
(vector-set! new-lines i (list->string char-list))
(loop (+ i 1))))))
(define (get-rows-to-expand lines)
(let loop ((i 0) (ret '()))
(if (>= i (vector-length lines))
(reverse (cons 9999999 ret))
(let ()
(define str (vector-ref lines i))
(if (andmap (λ (c) (char=? #\. c))
(string->list str))
(loop (+ 1 i) (cons i ret))
(loop (+ 1 i) ret))))))
(define rows-to-expand (get-rows-to-expand lines))
(define columns-to-expand (get-rows-to-expand (transpose lines)))
(define height (vector-length lines))
(define width (string-length (vector-ref lines 0)))
(define expand-param 1000000)
(define (build-expand-map num rows-to-expand)
(define map (make-vector num))
(let loop ((i 0) (cur 0) (rows rows-to-expand))
(if (>= i num)
map
(begin
(vector-set! map i cur)
(if (= i (car rows))
(loop (+ 1 i) (+ expand-param cur) (cdr rows))
(loop (+ 1 i) (+ 1 cur) rows))))))
(define row-expand-map (build-expand-map height rows-to-expand))
(define column-expand-map (build-expand-map width columns-to-expand))
(define (get-galaxies universe)
(define (char-at x y) (string-ref (vector-ref universe y) x))
(let loop ((x 0) (y 0) (ret '()))
(if (>= y height)
(list->vector (reverse ret))
(if (>= x width)
(loop 0 (+ y 1) ret)
(if (char=? #\# (char-at x y))
(loop (+ x 1) y (cons (cons x y) ret))
(loop (+ x 1) y ret))))))
(define galaxies (get-galaxies lines))
(define (gen-pairs n)
(let loop ((i 0) (j 1) (ret '()))
(if (>= i n)
(reverse ret)
(if (>= j n)
(loop (+ 1 i) (+ 2 i) ret)
(loop i (+ 1 j) (cons (cons i j) ret))))))
(define (distance n1 n2)
(define x1 (vector-ref column-expand-map (car (vector-ref galaxies n1))))
(define x2 (vector-ref column-expand-map (car (vector-ref galaxies n2))))
(define y1 (vector-ref row-expand-map (cdr (vector-ref galaxies n1))))
(define y2 (vector-ref row-expand-map (cdr (vector-ref galaxies n2))))
(+ (abs (- x1 x2)) (abs (- y1 y2))))
(apply
+
(map (λ (x) (distance (car x) (cdr x)))
(gen-pairs (vector-length galaxies))))
|
