adventofcode/src/2019/day24.lisp at master · iamFIREcracker/adventofcode · GitHub

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
(defpackage :aoc/2019/24 #.cl-user::*aoc-use*)
(in-package :aoc/2019/24)

(defstruct (eris (:constructor make-eris%)
                 (:copier NIL)
                 (:conc-name NIL))
  tiles)

(defun make-eris (data &aux (tiles (make-hash-table)))
  (prog1 (make-eris% :tiles tiles)
    (loop
      :for str :in data
      :for i = 0 :then (1+ i)
      :do (loop
            :for c :across str
            :for j = 0 :then (1+ j)
            :do (hash-table-insert tiles (complex j (- i)) c)))))

(defun copy-eris (e)
  (make-eris% :tiles (copy-hash-table (tiles e))))

(defun bugp (c)
  (eql #\# c))

(defun emptyp (c)
  (eql #\. c))

(defun eris-neighbors (e pos)
  (loop
    :for delta :in (list #C(0 1) #C(1 0) #C(0 -1) #C(-1 0))
    :for pos-next = (+ pos delta)
    :for c = (gethash pos-next (tiles e))
    :when c :collect it))

(defun evolve (curr adj-bugs)
  (if (bugp curr)
    (if (= 1 adj-bugs) #\# #\.)
    (if (or (= 1 adj-bugs) (= 2 adj-bugs)) #\# #\.)))

(defun eris-evolve (e &aux (e-next (copy-eris e)))
  (prog1 e-next
    (loop
      :for pos :being :the :hash-keys :of (tiles e)
      :for c = (gethash pos (tiles e))
      :for adj-bugs = (count-if #'bugp (eris-neighbors e pos))
      :do (hash-table-insert (tiles e-next) pos (evolve c adj-bugs)))))

(defun biodiversity-rating (e)
  (loop
    :with pow = 1
    :for i :from 0 :upto 4
    :summing (loop
               :for j :from 0 :upto 4
               :for pos = (complex j (- i))
               :for c = (gethash pos (tiles e))
               :when (bugp c) :summing pow
               :do (setf pow (* pow 2)))))

(defstruct (recursive-eris (:constructor make-recursive-eris%)
                           (:copier NIL)
                           (:conc-name NIL))
  levels)

(defun make-recursive-eris (data &aux (levels (make-hash-table)))
  (let ((re (make-recursive-eris% :levels levels)))
    (prog1 re
      (hash-table-insert levels 0 (make-eris data))
      (recursive-eris-create-levelf re 1)
      (recursive-eris-create-levelf re -1))))

(defun copy-recursive-eris (re &aux (levels (make-hash-table)))
  (prog1 (make-recursive-eris% :levels levels)
    (dolist (k (hash-table-keys (levels re)))
      (hash-table-insert levels k (copy-eris (gethash k (levels re)))))))

(defun print-recursive-eris (re)
  (loop
    :with min-level = (recursive-eris-min-level re)
    :with max-level = (recursive-eris-max-level re)
    :for level :from min-level :upto max-level
    :for eris = (gethash level (levels re))
    :unless (not (some #'bugp (hash-table-values (tiles eris))))
    :do (format T "Depth ~d:~%" level)
    :and :do (print-hash-table-map (tiles (gethash level (levels re))))
    :do (format T "~%")))

(defun recursive-eris-min-level (re)
  (reduce #'min (hash-table-keys (levels re))))

(defun recursive-eris-max-level (re)
  (reduce #'max (hash-table-keys (levels re))))

(defun recursive-eris-create-levelf (re level &aux (tiles (make-hash-table)))
  (dorange (i 0 5)
    (dorange (j 0 5)
      (hash-table-insert tiles (complex j (- i)) #\.)))
  (hash-table-insert (levels re) level (make-eris% :tiles tiles)))

(defun recursive-eris-neighbors (re level pos)
  (flet ((get-eris (level)
           (or (gethash level (levels re))
               (recursive-eris-create-levelf re level))))
    (loop
      :until (= pos #C(2 -2))
      :with eris = (gethash level (levels re))
      :for delta :in (list #C(0 1) #C(1 0) #C(0 -1) #C(-1 0))
      :for pos-next = (+ pos delta)
      :for i = (imagpart pos-next)
      :for j = (realpart pos-next)
      :append (cond ((> i 0) (let ((eris-above (get-eris (1- level))))
                               (list (gethash #C(2 -1) (tiles eris-above)))))
                    ((> j 4) (let ((eris-above (get-eris (1- level))))
                               (list (gethash #C(3 -2) (tiles eris-above)))))
                    ((< i -4) (let ((eris-above (get-eris (1- level))))
                                (list (gethash #C(2 -3) (tiles eris-above)))))
                    ((< j 0) (let ((eris-above (get-eris (1- level))))
                               (list (gethash #C(1 -2) (tiles eris-above)))))
                    ((= pos-next #C(2 -2)) (cond ((= delta #C(0 1)) (let ((eris-below (get-eris (1+ level))))
                                                                      (list
                                                                        (gethash #C(0 -4) (tiles eris-below))
                                                                        (gethash #C(1 -4) (tiles eris-below))
                                                                        (gethash #C(2 -4) (tiles eris-below))
                                                                        (gethash #C(3 -4) (tiles eris-below))
                                                                        (gethash #C(4 -4) (tiles eris-below)))))
                                                 ((= delta #C(1 0)) (let ((eris-below (get-eris (1+ level))))
                                                                      (list
                                                                        (gethash #C(0  0) (tiles eris-below))
                                                                        (gethash #C(0 -1) (tiles eris-below))
                                                                        (gethash #C(0 -2) (tiles eris-below))
                                                                        (gethash #C(0 -3) (tiles eris-below))
                                                                        (gethash #C(0 -4) (tiles eris-below)))))
                                                 ((= delta #C(0 -1)) (let ((eris-below (get-eris (1+ level))))
                                                                       (list
                                                                         (gethash #C(0 0) (tiles eris-below))
                                                                         (gethash #C(1 0) (tiles eris-below))
                                                                         (gethash #C(2 0) (tiles eris-below))
                                                                         (gethash #C(3 0) (tiles eris-below))
                                                                         (gethash #C(4 0) (tiles eris-below)))))
                                                 ((= delta #C(-1 0)) (let ((eris-below (get-eris (1+ level))))
                                                                       (list
                                                                         (gethash #C(4  0) (tiles eris-below))
                                                                         (gethash #C(4 -1) (tiles eris-below))
                                                                         (gethash #C(4 -2) (tiles eris-below))
                                                                         (gethash #C(4 -3) (tiles eris-below))
                                                                         (gethash #C(4 -4) (tiles eris-below)))))))
                    (T (list (gethash pos-next (tiles eris))))))))

(defun recursive-eris-evolve (re &aux (re-next (copy-recursive-eris re)))
  (prog1 re-next
    (loop
      :for level :in (hash-table-keys (levels re))
      :for e = (gethash level (levels re))
      :for e-next = (gethash level (levels re-next))
      :do (loop
            :for pos :in (hash-table-keys (tiles e))
            :for c = (gethash pos (tiles e))
            :for adj-bugs = (count-if #'bugp (recursive-eris-neighbors re level pos))
            :do (hash-table-insert (tiles e-next) pos (evolve c adj-bugs))))
   (recursive-eris-create-levelf re-next (1- (recursive-eris-min-level re-next)))
   (recursive-eris-create-levelf re-next (1+ (recursive-eris-max-level re-next)))))

(defun recursive-eris-bugs (re)
  (loop
    :for eris :in (hash-table-values (levels re))
    :summing (count-if #'bugp (hash-table-values (tiles eris)))))

(define-solution (2019 24) (data)
  (values
    (destructuring-bind (cycles-at cycle-size e)
        (floyd #'eris-evolve
               (make-eris data)
               :key #'tiles
               :test 'equalp)
      (declare (ignore cycles-at cycle-size))
      (biodiversity-rating e))
    (loop
      :for n :from 0 :upto 200
      :for re = (make-recursive-eris data) :then (recursive-eris-evolve re)
      :finally (return (recursive-eris-bugs re)))))

(define-test (2019 24) (7543003 1975))