day12/summary.txt

   1 --- Day 12: The N-Body Problem ---
   2 The space near Jupiter is not a very safe place; you need to be careful of a big distracting red spot, extreme radiation, and a whole lot of moons swirling around. You decide to start by tracking the four largest moons: Io, Europa, Ganymede, and Callisto.
   3
   4 After a brief scan, you calculate the position of each moon (your puzzle input). You just need to simulate their motion so you can avoid them.
   5
   6 Each moon has a 3-dimensional position (x, y, and z) and a 3-dimensional velocity. The position of each moon is given in your scan; the x, y, and z velocity of each moon starts at 0.
   7
   8 Simulate the motion of the moons in time steps. Within each time step, first update the velocity of every moon by applying gravity. Then, once all moons' velocities have been updated, update the position of every moon by applying velocity. Time progresses by one step once all of the positions are updated.
   9
  10 To apply gravity, consider every pair of moons. On each axis (x, y, and z), the velocity of each moon changes by exactly +1 or -1 to pull the moons together. For example, if Ganymede has an x position of 3, and Callisto has a x position of 5, then Ganymede's x velocity changes by +1 (because 5 > 3) and Callisto's x velocity changes by -1 (because 3 < 5). However, if the positions on a given axis are the same, the velocity on that axis does not change for that pair of moons.
  11
  12 Once all gravity has been applied, apply velocity: simply add the velocity of each moon to its own position. For example, if Europa has a position of x=1, y=2, z=3 and a velocity of x=-2, y=0,z=3, then its new position would be x=-1, y=2, z=6. This process does not modify the velocity of any moon.
  13
  14 For example, suppose your scan reveals the following positions:
  15
  16 <x=-1, y=0, z=2>
  17 <x=2, y=-10, z=-7>
  18 <x=4, y=-8, z=8>
  19 <x=3, y=5, z=-1>
  20 Simulating the motion of these moons would produce the following:
  21
  22 After 0 steps:
  23 pos=<x=-1, y=  0, z= 2>, vel=<x= 0, y= 0, z= 0>
  24 pos=<x= 2, y=-10, z=-7>, vel=<x= 0, y= 0, z= 0>
  25 pos=<x= 4, y= -8, z= 8>, vel=<x= 0, y= 0, z= 0>
  26 pos=<x= 3, y=  5, z=-1>, vel=<x= 0, y= 0, z= 0>
  27
  28 After 1 step:
  29 pos=<x= 2, y=-1, z= 1>, vel=<x= 3, y=-1, z=-1>
  30 pos=<x= 3, y=-7, z=-4>, vel=<x= 1, y= 3, z= 3>
  31 pos=<x= 1, y=-7, z= 5>, vel=<x=-3, y= 1, z=-3>
  32 pos=<x= 2, y= 2, z= 0>, vel=<x=-1, y=-3, z= 1>
  33
  34 After 2 steps:
  35 pos=<x= 5, y=-3, z=-1>, vel=<x= 3, y=-2, z=-2>
  36 pos=<x= 1, y=-2, z= 2>, vel=<x=-2, y= 5, z= 6>
  37 pos=<x= 1, y=-4, z=-1>, vel=<x= 0, y= 3, z=-6>
  38 pos=<x= 1, y=-4, z= 2>, vel=<x=-1, y=-6, z= 2>
  39
  40 After 3 steps:
  41 pos=<x= 5, y=-6, z=-1>, vel=<x= 0, y=-3, z= 0>
  42 pos=<x= 0, y= 0, z= 6>, vel=<x=-1, y= 2, z= 4>
  43 pos=<x= 2, y= 1, z=-5>, vel=<x= 1, y= 5, z=-4>
  44 pos=<x= 1, y=-8, z= 2>, vel=<x= 0, y=-4, z= 0>
  45
  46 After 4 steps:
  47 pos=<x= 2, y=-8, z= 0>, vel=<x=-3, y=-2, z= 1>
  48 pos=<x= 2, y= 1, z= 7>, vel=<x= 2, y= 1, z= 1>
  49 pos=<x= 2, y= 3, z=-6>, vel=<x= 0, y= 2, z=-1>
  50 pos=<x= 2, y=-9, z= 1>, vel=<x= 1, y=-1, z=-1>
  51
  52 After 5 steps:
  53 pos=<x=-1, y=-9, z= 2>, vel=<x=-3, y=-1, z= 2>
  54 pos=<x= 4, y= 1, z= 5>, vel=<x= 2, y= 0, z=-2>
  55 pos=<x= 2, y= 2, z=-4>, vel=<x= 0, y=-1, z= 2>
  56 pos=<x= 3, y=-7, z=-1>, vel=<x= 1, y= 2, z=-2>
  57
  58 After 6 steps:
  59 pos=<x=-1, y=-7, z= 3>, vel=<x= 0, y= 2, z= 1>
  60 pos=<x= 3, y= 0, z= 0>, vel=<x=-1, y=-1, z=-5>
  61 pos=<x= 3, y=-2, z= 1>, vel=<x= 1, y=-4, z= 5>
  62 pos=<x= 3, y=-4, z=-2>, vel=<x= 0, y= 3, z=-1>
  63
  64 After 7 steps:
  65 pos=<x= 2, y=-2, z= 1>, vel=<x= 3, y= 5, z=-2>
  66 pos=<x= 1, y=-4, z=-4>, vel=<x=-2, y=-4, z=-4>
  67 pos=<x= 3, y=-7, z= 5>, vel=<x= 0, y=-5, z= 4>
  68 pos=<x= 2, y= 0, z= 0>, vel=<x=-1, y= 4, z= 2>
  69
  70 After 8 steps:
  71 pos=<x= 5, y= 2, z=-2>, vel=<x= 3, y= 4, z=-3>
  72 pos=<x= 2, y=-7, z=-5>, vel=<x= 1, y=-3, z=-1>
  73 pos=<x= 0, y=-9, z= 6>, vel=<x=-3, y=-2, z= 1>
  74 pos=<x= 1, y= 1, z= 3>, vel=<x=-1, y= 1, z= 3>
  75
  76 After 9 steps:
  77 pos=<x= 5, y= 3, z=-4>, vel=<x= 0, y= 1, z=-2>
  78 pos=<x= 2, y=-9, z=-3>, vel=<x= 0, y=-2, z= 2>
  79 pos=<x= 0, y=-8, z= 4>, vel=<x= 0, y= 1, z=-2>
  80 pos=<x= 1, y= 1, z= 5>, vel=<x= 0, y= 0, z= 2>
  81
  82 After 10 steps:
  83 pos=<x= 2, y= 1, z=-3>, vel=<x=-3, y=-2, z= 1>
  84 pos=<x= 1, y=-8, z= 0>, vel=<x=-1, y= 1, z= 3>
  85 pos=<x= 3, y=-6, z= 1>, vel=<x= 3, y= 2, z=-3>
  86 pos=<x= 2, y= 0, z= 4>, vel=<x= 1, y=-1, z=-1>
  87 Then, it might help to calculate the total energy in the system. The total energy for a single moon is its potential energy multiplied by its kinetic energy. A moon's potential energy is the sum of the absolute values of its x, y, and z position coordinates. A moon's kinetic energy is the sum of the absolute values of its velocity coordinates. Below, each line shows the calculations for a moon's potential energy (pot), kinetic energy (kin), and total energy:
  88
  89 Energy after 10 steps:
  90 pot: 2 + 1 + 3 =  6;   kin: 3 + 2 + 1 = 6;   total:  6 * 6 = 36
  91 pot: 1 + 8 + 0 =  9;   kin: 1 + 1 + 3 = 5;   total:  9 * 5 = 45
  92 pot: 3 + 6 + 1 = 10;   kin: 3 + 2 + 3 = 8;   total: 10 * 8 = 80
  93 pot: 2 + 0 + 4 =  6;   kin: 1 + 1 + 1 = 3;   total:  6 * 3 = 18
  94 Sum of total energy: 36 + 45 + 80 + 18 = 179
  95 In the above example, adding together the total energy for all moons after 10 steps produces the total energy in the system, 179.
  96
  97 Here's a second example:
  98
  99 <x=-8, y=-10, z=0>
 100 <x=5, y=5, z=10>
 101 <x=2, y=-7, z=3>
 102 <x=9, y=-8, z=-3>
 103 Every ten steps of simulation for 100 steps produces:
 104
 105 After 0 steps:
 106 pos=<x= -8, y=-10, z=  0>, vel=<x=  0, y=  0, z=  0>
 107 pos=<x=  5, y=  5, z= 10>, vel=<x=  0, y=  0, z=  0>
 108 pos=<x=  2, y= -7, z=  3>, vel=<x=  0, y=  0, z=  0>
 109 pos=<x=  9, y= -8, z= -3>, vel=<x=  0, y=  0, z=  0>
 110
 111 After 10 steps:
 112 pos=<x= -9, y=-10, z=  1>, vel=<x= -2, y= -2, z= -1>
 113 pos=<x=  4, y= 10, z=  9>, vel=<x= -3, y=  7, z= -2>
 114 pos=<x=  8, y=-10, z= -3>, vel=<x=  5, y= -1, z= -2>
 115 pos=<x=  5, y=-10, z=  3>, vel=<x=  0, y= -4, z=  5>
 116
 117 After 20 steps:
 118 pos=<x=-10, y=  3, z= -4>, vel=<x= -5, y=  2, z=  0>
 119 pos=<x=  5, y=-25, z=  6>, vel=<x=  1, y=  1, z= -4>
 120 pos=<x= 13, y=  1, z=  1>, vel=<x=  5, y= -2, z=  2>
 121 pos=<x=  0, y=  1, z=  7>, vel=<x= -1, y= -1, z=  2>
 122
 123 After 30 steps:
 124 pos=<x= 15, y= -6, z= -9>, vel=<x= -5, y=  4, z=  0>
 125 pos=<x= -4, y=-11, z=  3>, vel=<x= -3, y=-10, z=  0>
 126 pos=<x=  0, y= -1, z= 11>, vel=<x=  7, y=  4, z=  3>
 127 pos=<x= -3, y= -2, z=  5>, vel=<x=  1, y=  2, z= -3>
 128
 129 After 40 steps:
 130 pos=<x= 14, y=-12, z= -4>, vel=<x= 11, y=  3, z=  0>
 131 pos=<x= -1, y= 18, z=  8>, vel=<x= -5, y=  2, z=  3>
 132 pos=<x= -5, y=-14, z=  8>, vel=<x=  1, y= -2, z=  0>
 133 pos=<x=  0, y=-12, z= -2>, vel=<x= -7, y= -3, z= -3>
 134
 135 After 50 steps:
 136 pos=<x=-23, y=  4, z=  1>, vel=<x= -7, y= -1, z=  2>
 137 pos=<x= 20, y=-31, z= 13>, vel=<x=  5, y=  3, z=  4>
 138 pos=<x= -4, y=  6, z=  1>, vel=<x= -1, y=  1, z= -3>
 139 pos=<x= 15, y=  1, z= -5>, vel=<x=  3, y= -3, z= -3>
 140
 141 After 60 steps:
 142 pos=<x= 36, y=-10, z=  6>, vel=<x=  5, y=  0, z=  3>
 143 pos=<x=-18, y= 10, z=  9>, vel=<x= -3, y= -7, z=  5>
 144 pos=<x=  8, y=-12, z= -3>, vel=<x= -2, y=  1, z= -7>
 145 pos=<x=-18, y= -8, z= -2>, vel=<x=  0, y=  6, z= -1>
 146
 147 After 70 steps:
 148 pos=<x=-33, y= -6, z=  5>, vel=<x= -5, y= -4, z=  7>
 149 pos=<x= 13, y= -9, z=  2>, vel=<x= -2, y= 11, z=  3>
 150 pos=<x= 11, y= -8, z=  2>, vel=<x=  8, y= -6, z= -7>
 151 pos=<x= 17, y=  3, z=  1>, vel=<x= -1, y= -1, z= -3>
 152
 153 After 80 steps:
 154 pos=<x= 30, y= -8, z=  3>, vel=<x=  3, y=  3, z=  0>
 155 pos=<x= -2, y= -4, z=  0>, vel=<x=  4, y=-13, z=  2>
 156 pos=<x=-18, y= -7, z= 15>, vel=<x= -8, y=  2, z= -2>
 157 pos=<x= -2, y= -1, z= -8>, vel=<x=  1, y=  8, z=  0>
 158
 159 After 90 steps:
 160 pos=<x=-25, y= -1, z=  4>, vel=<x=  1, y= -3, z=  4>
 161 pos=<x=  2, y= -9, z=  0>, vel=<x= -3, y= 13, z= -1>
 162 pos=<x= 32, y= -8, z= 14>, vel=<x=  5, y= -4, z=  6>
 163 pos=<x= -1, y= -2, z= -8>, vel=<x= -3, y= -6, z= -9>
 164
 165 After 100 steps:
 166 pos=<x=  8, y=-12, z= -9>, vel=<x= -7, y=  3, z=  0>
 167 pos=<x= 13, y= 16, z= -3>, vel=<x=  3, y=-11, z= -5>
 168 pos=<x=-29, y=-11, z= -1>, vel=<x= -3, y=  7, z=  4>
 169 pos=<x= 16, y=-13, z= 23>, vel=<x=  7, y=  1, z=  1>
 170
 171 Energy after 100 steps:
 172 pot:  8 + 12 +  9 = 29;   kin: 7 +  3 + 0 = 10;   total: 29 * 10 = 290
 173 pot: 13 + 16 +  3 = 32;   kin: 3 + 11 + 5 = 19;   total: 32 * 19 = 608
 174 pot: 29 + 11 +  1 = 41;   kin: 3 +  7 + 4 = 14;   total: 41 * 14 = 574
 175 pot: 16 + 13 + 23 = 52;   kin: 7 +  1 + 1 =  9;   total: 52 *  9 = 468
 176 Sum of total energy: 290 + 608 + 574 + 468 = 1940
 177 What is the total energy in the system after simulating the moons given in your scan for 1000 steps?
 178
 179 Your puzzle answer was 10189.
 180
 181 --- Part Two ---
 182 All this drifting around in space makes you wonder about the nature of the universe. Does history really repeat itself? You're curious whether the moons will ever return to a previous state.
 183
 184 Determine the number of steps that must occur before all of the moons' positions and velocities exactly match a previous point in time.
 185
 186 For example, the first example above takes 2772 steps before they exactly match a previous point in time; it eventually returns to the initial state:
 187
 188 After 0 steps:
 189 pos=<x= -1, y=  0, z=  2>, vel=<x=  0, y=  0, z=  0>
 190 pos=<x=  2, y=-10, z= -7>, vel=<x=  0, y=  0, z=  0>
 191 pos=<x=  4, y= -8, z=  8>, vel=<x=  0, y=  0, z=  0>
 192 pos=<x=  3, y=  5, z= -1>, vel=<x=  0, y=  0, z=  0>
 193
 194 After 2770 steps:
 195 pos=<x=  2, y= -1, z=  1>, vel=<x= -3, y=  2, z=  2>
 196 pos=<x=  3, y= -7, z= -4>, vel=<x=  2, y= -5, z= -6>
 197 pos=<x=  1, y= -7, z=  5>, vel=<x=  0, y= -3, z=  6>
 198 pos=<x=  2, y=  2, z=  0>, vel=<x=  1, y=  6, z= -2>
 199
 200 After 2771 steps:
 201 pos=<x= -1, y=  0, z=  2>, vel=<x= -3, y=  1, z=  1>
 202 pos=<x=  2, y=-10, z= -7>, vel=<x= -1, y= -3, z= -3>
 203 pos=<x=  4, y= -8, z=  8>, vel=<x=  3, y= -1, z=  3>
 204 pos=<x=  3, y=  5, z= -1>, vel=<x=  1, y=  3, z= -1>
 205
 206 After 2772 steps:
 207 pos=<x= -1, y=  0, z=  2>, vel=<x=  0, y=  0, z=  0>
 208 pos=<x=  2, y=-10, z= -7>, vel=<x=  0, y=  0, z=  0>
 209 pos=<x=  4, y= -8, z=  8>, vel=<x=  0, y=  0, z=  0>
 210 pos=<x=  3, y=  5, z= -1>, vel=<x=  0, y=  0, z=  0>
 211 Of course, the universe might last for a very long time before repeating. Here's a copy of the second example from above:
 212
 213 <x=-8, y=-10, z=0>
 214 <x=5, y=5, z=10>
 215 <x=2, y=-7, z=3>
 216 <x=9, y=-8, z=-3>
 217 This set of initial positions takes 4686774924 steps before it repeats a previous state! Clearly, you might need to find a more efficient way to simulate the universe.
 218
 219 How many steps does it take to reach the first state that exactly matches a previous state?
 220
 221 Your puzzle answer was 469671086427712.
 222
 223 Both parts of this puzzle are complete! They provide two gold stars: **
 224
 225 At this point, you should return to your Advent calendar and try another puzzle.
 226
 227 If you still want to see it, you can get your puzzle input.
 228
 229 You can also [Share] this puzzle.