Mercurial > hg > aoc

comparison 2017/day22/problem @ 34:049fb8e56025

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add problem statements and inputs
author Jordi Gutiérrez Hermoso <jordigh@octave.org>
date Tue, 09 Jan 2018 21:51:44 -0500
parents
children
comparison
equal deleted inserted replaced
33:bc652fa0a645 34:049fb8e56025
1 --- Day 22: Sporifica Virus ---
2
3 Diagnostics indicate that the local grid computing cluster has been
4 contaminated with the Sporifica Virus. The grid computing cluster is a
5 seemingly-infinite two-dimensional grid of compute nodes. Each node is
6 either clean or infected by the virus.
7
8 To prevent overloading the nodes (which would render them useless to
9 the virus) or detection by system administrators, exactly one virus
10 carrier moves through the network, infecting or cleaning nodes as it
11 moves. The virus carrier is always located on a single node in the
12 network (the current node) and keeps track of the direction it is
13 facing.
14
15 To avoid detection, the virus carrier works in bursts; in each burst,
16 it wakes up, does some work, and goes back to sleep. The following
17 steps are all executed in order one time each burst:
18
19 If the current node is infected, it turns to its right. Otherwise,
20 it turns to its left. (Turning is done in-place; the current node
21 does not change.)
22
23 If the current node is clean, it becomes infected. Otherwise, it
24 becomes cleaned. (This is done after the node is considered for
25 the purposes of changing direction.)
26
27 The virus carrier moves forward one node in the direction it is
28 facing.
29
30 Diagnostics have also provided a map of the node infection status
31 (your puzzle input). Clean nodes are shown as .; infected nodes are
32 shown as #. This map only shows the center of the grid; there are many
33 more nodes beyond those shown, but none of them are currently
34 infected.
35
36 The virus carrier begins in the middle of the map facing up.
37
38 For example, suppose you are given a map like this:
39
40 ..#
41 #..
42 ...
43
44 Then, the middle of the infinite grid looks like this, with the virus
45 carrier's position marked with [ ]:
46
47 . . . . . . . . .
48 . . . . . . . . .
49 . . . . . . . . .
50 . . . . . # . . .
51 . . . #[.]. . . .
52 . . . . . . . . .
53 . . . . . . . . .
54 . . . . . . . . .
55
56 The virus carrier is on a clean node, so it turns left, infects the
57 node, and moves left:
58
59 . . . . . . . . .
60 . . . . . . . . .
61 . . . . . . . . .
62 . . . . . # . . .
63 . . .[#]# . . . .
64 . . . . . . . . .
65 . . . . . . . . .
66 . . . . . . . . .
67
68 The virus carrier is on an infected node, so it turns right, cleans
69 the node, and moves up:
70
71 . . . . . . . . .
72 . . . . . . . . .
73 . . . . . . . . .
74 . . .[.]. # . . .
75 . . . . # . . . .
76 . . . . . . . . .
77 . . . . . . . . .
78 . . . . . . . . .
79
80 Four times in a row, the virus carrier finds a clean, infects it,
81 turns left, and moves forward, ending in the same place and still
82 facing up:
83
84 . . . . . . . . .
85 . . . . . . . . .
86 . . . . . . . . .
87 . . #[#]. # . . .
88 . . # # # . . . .
89 . . . . . . . . .
90 . . . . . . . . .
91 . . . . . . . . .
92
93 Now on the same node as before, it sees an infection, which causes it
94 to turn right, clean the node, and move forward:
95
96 . . . . . . . . .
97 . . . . . . . . .
98 . . . . . . . . .
99 . . # .[.]# . . .
100 . . # # # . . . .
101 . . . . . . . . .
102 . . . . . . . . .
103 . . . . . . . . .
104
105 After the above actions, a total of 7 bursts of activity had taken
106 place. Of them, 5 bursts of activity caused an infection.
107
108 After a total of 70, the grid looks like this, with the virus carrier
109 facing up:
110
111 . . . . . # # . .
112 . . . . # . . # .
113 . . . # . . . . #
114 . . # . #[.]. . #
115 . . # . # . . # .
116 . . . . . # # . .
117 . . . . . . . . .
118 . . . . . . . . .
119
120 By this time, 41 bursts of activity caused an infection (though most
121 of those nodes have since been cleaned).
122
123 After a total of 10000 bursts of activity, 5587 bursts will have
124 caused an infection.
125
126 Given your actual map, after 10000 bursts of activity, how many bursts
127 cause a node to become infected? (Do not count nodes that begin
128 infected.)
129
130 Your puzzle answer was 5399.
131
132 --- Part Two ---
133
134 As you go to remove the virus from the infected nodes, it evolves to
135 resist your attempt.
136
137 Now, before it infects a clean node, it will weaken it to disable your
138 defenses. If it encounters an infected node, it will instead flag the
139 node to be cleaned in the future. So:
140
141 Clean nodes become weakened.
142
143 Weakened nodes become infected.
144
145 Infected nodes become flagged.
146
147 Flagged nodes become clean.
148
149 Every node is always in exactly one of the above states.
150
151 The virus carrier still functions in a similar way, but now uses the
152 following logic during its bursts of action:
153
154 Decide which way to turn based on the current node:
155
156 If it is clean, it turns left.
157
158 If it is weakened, it does not turn, and will continue moving
159 in the same direction.
160
161 If it is infected, it turns right.
162
163 If it is flagged, it reverses direction, and will go back the
164 way it came.
165
166 Modify the state of the current node, as described above.
167
168 The virus carrier moves forward one node in the direction it is
169 facing.
170
171
172 Start with the same map (still using . for clean and # for infected)
173 and still with the virus carrier starting in the middle and facing up.
174
175 Using the same initial state as the previous example, and drawing
176 weakened as W and flagged as F, the middle of the infinite grid looks
177 like this, with the virus carrier's position again marked with [ ]:
178
179 . . . . . . . . .
180 . . . . . . . . .
181 . . . . . . . . .
182 . . . . . # . . .
183 . . . #[.]. . . .
184 . . . . . . . . .
185 . . . . . . . . .
186 . . . . . . . . .
187
188 This is the same as before, since no initial nodes are weakened or
189 flagged. The virus carrier is on a clean node, so it still turns left,
190 instead weakens the node, and moves left:
191
192 . . . . . . . . .
193 . . . . . . . . .
194 . . . . . . . . .
195 . . . . . # . . .
196 . . .[#]W . . . .
197 . . . . . . . . .
198 . . . . . . . . .
199 . . . . . . . . .
200
201 The virus carrier is on an infected node, so it still turns right,
202 instead flags the node, and moves up:
203
204 . . . . . . . . .
205 . . . . . . . . .
206 . . . . . . . . .
207 . . .[.]. # . . .
208 . . . F W . . . .
209 . . . . . . . . .
210 . . . . . . . . .
211 . . . . . . . . .
212
213 This process repeats three more times, ending on the
214 previously-flagged node and facing right:
215
216 . . . . . . . . .
217 . . . . . . . . .
218 . . . . . . . . .
219 . . W W . # . . .
220 . . W[F]W . . . .
221 . . . . . . . . .
222 . . . . . . . . .
223 . . . . . . . . .
224
225 Finding a flagged node, it reverses direction and cleans the node:
226
227 . . . . . . . . .
228 . . . . . . . . .
229 . . . . . . . . .
230 . . W W . # . . .
231 . .[W]. W . . . .
232 . . . . . . . . .
233 . . . . . . . . .
234 . . . . . . . . .
235
236 The weakened node becomes infected, and it continues in the same
237 direction:
238
239 . . . . . . . . .
240 . . . . . . . . .
241 . . . . . . . . .
242 . . W W . # . . .
243 .[.]# . W . . . .
244 . . . . . . . . .
245 . . . . . . . . .
246 . . . . . . . . .
247
248 Of the first 100 bursts, 26 will result in infection. Unfortunately,
249 another feature of this evolved virus is speed; of the first 10000000
250 bursts, 2511944 will result in infection.
251
252 Given your actual map, after 10000000 bursts of activity, how many
253 bursts cause a node to become infected? (Do not count nodes that begin
254 infected.)
255
256 Your puzzle answer was 2511776.
257
258 Both parts of this puzzle are complete! They provide two gold stars: **