part1 (5699B)
1--- Day 25: Sea Cucumber --- 2 3This is it: the bottom of the ocean trench, the last place the sleigh keys could be. Your 4submarine's experimental antenna [1m[97mstill isn't boosted enough[0m to detect the keys, but they 5[1m[97mmust[0m be here. All you need to do is [1m[97mreach the seafloor[0m and find them. 6 7At least, you'd touch down on the seafloor if you could; unfortunately, it's completely covered by 8two large herds of sea cucumbers, and there isn't an open space large enough for your submarine. 9 10You suspect that the Elves must have done this before, because just then you discover the phone 11number of a deep-sea marine biologist on a handwritten note taped to the wall of the submarine's 12cockpit. 13 14"Sea cucumbers? Yeah, they're probably hunting for food. But don't worry, they're predictable 15critters: they move in perfectly straight lines, only moving forward when there's space to do so. 16They're actually quite polite!" 17 18You explain that you'd like to predict when you could land your submarine. 19 20"Oh that's easy, they'll eventually pile up and leave enough space for-- wait, did you say 21submarine? And the only place with that many sea cucumbers would be at the very bottom of the 22Mariana--" You hang up the phone. 23 24There are two herds of sea cucumbers sharing the same region; one always moves [1m[97meast[0m (>), while the 25other always moves [1m[97msouth[0m (v). Each location can contain at most one sea cucumber; the remaining 26locations are [1m[97mempty[0m (.). The submarine helpfully generates a map of the situation (your puzzle 27input). For example: 28 29v...>>.vv> 30.vv>>.vv.. 31>>.>v>...v 32>>v>>.>.v. 33v>v.vv.v.. 34>.>>..v... 35.vv..>.>v. 36v.v..>>v.v 37....v..v.> 38 39Every [1m[97mstep[0m, the sea cucumbers in the east-facing herd attempt to move forward one location, then the 40sea cucumbers in the south-facing herd attempt to move forward one location. When a herd moves 41forward, every sea cucumber in the herd first simultaneously considers whether there is a sea 42cucumber in the adjacent location it's facing (even another sea cucumber facing the same direction), 43and then every sea cucumber facing an empty location simultaneously moves into that location. 44 45So, in a situation like this: 46 47...>>>>>... 48After one step, only the rightmost sea cucumber would have moved: 49 50...>>>>.>.. 51After the next step, two sea cucumbers move: 52 53...>>>.>.>. 54During a single step, the east-facing herd moves first, then the south-facing herd moves. So, given 55this situation: 56 57.......... 58.>v....v.. 59.......>.. 60.......... 61 62After a single step, of the sea cucumbers on the left, only the south-facing sea cucumber has moved 63(as it wasn't out of the way in time for the east-facing cucumber on the left to move), but both sea 64cucumbers on the right have moved (as the east-facing sea cucumber moved out of the way of the 65south-facing sea cucumber): 66 67.......... 68.>........ 69..v....v>. 70.......... 71 72Due to [1m[97mstrong water currents[0m in the area, sea cucumbers that move off the right edge of the map 73appear on the left edge, and sea cucumbers that move off the bottom edge of the map appear on the 74top edge. Sea cucumbers always check whether their destination location is empty before moving, even 75if that destination is on the opposite side of the map: 76 77Initial state: 78...>... 79....... 80......> 81v.....> 82......> 83....... 84..vvv.. 85 86After 1 step: 87..vv>.. 88....... 89>...... 90v.....> 91>...... 92....... 93....v.. 94 95After 2 steps: 96....v>. 97..vv... 98.>..... 99......> 100v>..... 101....... 102....... 103 104After 3 steps: 105......> 106..v.v.. 107..>v... 108>...... 109..>.... 110v...... 111....... 112 113After 4 steps: 114>...... 115..v.... 116..>.v.. 117.>.v... 118...>... 119....... 120v...... 121 122To find a safe place to land your submarine, the sea cucumbers need to stop moving. Again consider 123the first example: 124 125Initial state: 126v...>>.vv> 127.vv>>.vv.. 128>>.>v>...v 129>>v>>.>.v. 130v>v.vv.v.. 131>.>>..v... 132.vv..>.>v. 133v.v..>>v.v 134....v..v.> 135 136After 1 step: 137....>.>v.> 138v.v>.>v.v. 139>v>>..>v.. 140>>v>v>.>.v 141.>v.v...v. 142v>>.>vvv.. 143..v...>>.. 144vv...>>vv. 145>.v.v..v.v 146 147After 2 steps: 148>.v.v>>..v 149v.v.>>vv.. 150>v>.>.>.v. 151>>v>v.>v>. 152.>..v....v 153.>v>>.v.v. 154v....v>v>. 155.vv..>>v.. 156v>.....vv. 157 158After 3 steps: 159v>v.v>.>v. 160v...>>.v.v 161>vv>.>v>.. 162>>v>v.>.v> 163..>....v.. 164.>.>v>v..v 165..v..v>vv> 166v.v..>>v.. 167.v>....v.. 168 169After 4 steps: 170v>..v.>>.. 171v.v.>.>.v. 172>vv.>>.v>v 173>>.>..v>.> 174..v>v...v. 175..>>.>vv.. 176>.v.vv>v.v 177.....>>vv. 178vvv>...v.. 179 180After 5 steps: 181vv>...>v>. 182v.v.v>.>v. 183>.v.>.>.>v 184>v>.>..v>> 185..v>v.v... 186..>.>>vvv. 187.>...v>v.. 188..v.v>>v.v 189v.v.>...v. 190 191... 192 193After 10 steps: 194..>..>>vv. 195v.....>>.v 196..v.v>>>v> 197v>.>v.>>>. 198..v>v.vv.v 199.v.>>>.v.. 200v.v..>v>.. 201..v...>v.> 202.vv..v>vv. 203 204... 205 206After 20 steps: 207v>.....>>. 208>vv>.....v 209.>v>v.vv>> 210v>>>v.>v.> 211....vv>v.. 212.v.>>>vvv. 213..v..>>vv. 214v.v...>>.v 215..v.....v> 216 217... 218 219After 30 steps: 220.vv.v..>>> 221v>...v...> 222>.v>.>vv.> 223>v>.>.>v.> 224.>..v.vv.. 225..v>..>>v. 226....v>..>v 227v.v...>vv> 228v.v...>vvv 229 230... 231 232After 40 steps: 233>>v>v..v.. 234..>>v..vv. 235..>>>v.>.v 236..>>>>vvv> 237v.....>... 238v.v...>v>> 239>vv.....v> 240.>v...v.>v 241vvv.v..v.> 242 243... 244 245After 50 steps: 246..>>v>vv.v 247..v.>>vv.. 248v.>>v>>v.. 249..>>>>>vv. 250vvv....>vv 251..v....>>> 252v>.......> 253.vv>....v> 254.>v.vv.v.. 255 256... 257 258After 55 steps: 259..>>v>vv.. 260..v.>>vv.. 261..>>v>>vv. 262..>>>>>vv. 263v......>vv 264v>v....>>v 265vvv...>..> 266>vv.....>. 267.>v.vv.v.. 268 269After 56 steps: 270..>>v>vv.. 271..v.>>vv.. 272..>>v>>vv. 273..>>>>>vv. 274v......>vv 275v>v....>>v 276vvv....>.> 277>vv......> 278.>v.vv.v.. 279 280After 57 steps: 281..>>v>vv.. 282..v.>>vv.. 283..>>v>>vv. 284..>>>>>vv. 285v......>vv 286v>v....>>v 287vvv.....>> 288>vv......> 289.>v.vv.v.. 290 291After 58 steps: 292..>>v>vv.. 293..v.>>vv.. 294..>>v>>vv. 295..>>>>>vv. 296v......>vv 297v>v....>>v 298vvv.....>> 299>vv......> 300.>v.vv.v.. 301 302In this example, the sea cucumbers stop moving after [1m[97m58[0m steps. 303 304Find somewhere safe to land your submarine. [1m[97mWhat is the first step on which no sea cucumbers 305move?[0m 306 307