Mercurial > hg > aoc
comparison 2017/day20/problem @ 34:049fb8e56025
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 20: Particle Swarm --- | |
| 2 | |
| 3 Suddenly, the GPU contacts you, asking for help. Someone has asked it | |
| 4 to simulate too many particles, and it won't be able to finish them | |
| 5 all in time to render the next frame at this rate. | |
| 6 | |
| 7 It transmits to you a buffer (your puzzle input) listing each particle | |
| 8 in order (starting with particle 0, then particle 1, particle 2, and | |
| 9 so on). For each particle, it provides the X, Y, and Z coordinates for | |
| 10 the particle's position (p), velocity (v), and acceleration (a), each | |
| 11 in the format <X,Y,Z>. | |
| 12 | |
| 13 Each tick, all particles are updated simultaneously. A particle's | |
| 14 properties are updated in the following order: | |
| 15 | |
| 16 Increase the X velocity by the X acceleration. | |
| 17 | |
| 18 Increase the Y velocity by the Y acceleration. | |
| 19 | |
| 20 Increase the Z velocity by the Z acceleration. | |
| 21 | |
| 22 Increase the X position by the X velocity. | |
| 23 | |
| 24 Increase the Y position by the Y velocity. | |
| 25 | |
| 26 Increase the Z position by the Z velocity. | |
| 27 | |
| 28 Because of seemingly tenuous rationale involving z-buffering, the GPU | |
| 29 would like to know which particle will stay closest to position | |
| 30 <0,0,0> in the long term. Measure this using the Manhattan distance, | |
| 31 which in this situation is simply the sum of the absolute values of a | |
| 32 particle's X, Y, and Z position. | |
| 33 | |
| 34 For example, suppose you are only given two particles, both of which | |
| 35 stay entirely on the X-axis (for simplicity). Drawing the current | |
| 36 states of particles 0 and 1 (in that order) with an adjacent a number | |
| 37 line and diagram of current X positions (marked in parenthesis), the | |
| 38 following would take place: | |
| 39 | |
| 40 p=< 3,0,0>, v=< 2,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4 | |
| 41 p=< 4,0,0>, v=< 0,0,0>, a=<-2,0,0> (0)(1) | |
| 42 | |
| 43 p=< 4,0,0>, v=< 1,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4 | |
| 44 p=< 2,0,0>, v=<-2,0,0>, a=<-2,0,0> (1) (0) | |
| 45 | |
| 46 p=< 4,0,0>, v=< 0,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4 | |
| 47 p=<-2,0,0>, v=<-4,0,0>, a=<-2,0,0> (1) (0) | |
| 48 | |
| 49 p=< 3,0,0>, v=<-1,0,0>, a=<-1,0,0> -4 -3 -2 -1 0 1 2 3 4 | |
| 50 p=<-8,0,0>, v=<-6,0,0>, a=<-2,0,0> (0) | |
| 51 | |
| 52 At this point, particle 1 will never be closer to <0,0,0> than | |
| 53 particle 0, and so, in the long run, particle 0 will stay closest. | |
| 54 | |
| 55 Which particle will stay closest to position <0,0,0> in the long term? | |
| 56 | |
| 57 Your puzzle answer was 150. | |
| 58 | |
| 59 --- Part Two --- | |
| 60 | |
| 61 To simplify the problem further, the GPU would like to remove any | |
| 62 particles that collide. Particles collide if their positions ever | |
| 63 exactly match. Because particles are updated simultaneously, more than | |
| 64 two particles can collide at the same time and place. Once particles | |
| 65 collide, they are removed and cannot collide with anything else after | |
| 66 that tick. | |
| 67 | |
| 68 For example: | |
| 69 | |
| 70 p=<-6,0,0>, v=< 3,0,0>, a=< 0,0,0> | |
| 71 p=<-4,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3 | |
| 72 p=<-2,0,0>, v=< 1,0,0>, a=< 0,0,0> (0) (1) (2) (3) | |
| 73 p=< 3,0,0>, v=<-1,0,0>, a=< 0,0,0> | |
| 74 | |
| 75 p=<-3,0,0>, v=< 3,0,0>, a=< 0,0,0> | |
| 76 p=<-2,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3 | |
| 77 p=<-1,0,0>, v=< 1,0,0>, a=< 0,0,0> (0)(1)(2) (3) | |
| 78 p=< 2,0,0>, v=<-1,0,0>, a=< 0,0,0> | |
| 79 | |
| 80 p=< 0,0,0>, v=< 3,0,0>, a=< 0,0,0> | |
| 81 p=< 0,0,0>, v=< 2,0,0>, a=< 0,0,0> -6 -5 -4 -3 -2 -1 0 1 2 3 | |
| 82 p=< 0,0,0>, v=< 1,0,0>, a=< 0,0,0> X (3) | |
| 83 p=< 1,0,0>, v=<-1,0,0>, a=< 0,0,0> | |
| 84 | |
| 85 ------destroyed by collision------ | |
| 86 ------destroyed by collision------ -6 -5 -4 -3 -2 -1 0 1 2 3 | |
| 87 ------destroyed by collision------ (3) | |
| 88 p=< 0,0,0>, v=<-1,0,0>, a=< 0,0,0> | |
| 89 | |
| 90 In this example, particles 0, 1, and 2 are simultaneously destroyed at | |
| 91 the time and place marked X. On the next tick, particle 3 passes | |
| 92 through unharmed. | |
| 93 | |
| 94 How many particles are left after all collisions are resolved? | |
| 95 | |
| 96 Your puzzle answer was 657. | |
| 97 | |
| 98 Both parts of this puzzle are complete! They provide two gold stars: ** |