25.py

# --- Day 25: Sea Cucumber ---
#
# This is it: the bottom of the ocean trench, the last place the
# sleigh keys could be.  Your submarine's experimental antenna still
# isn't boosted enough to detect the keys, but they must be here.  All
# you need to do is reach the seafloor and find them.
#
# At least, you'd touch down on the seafloor if you could;
# unfortunately, it's completely covered by two large herds of sea
# cucumbers, and there isn't an open space large enough for your
# submarine.
#
# You suspect that the Elves must have done this before, because just
# then you discover the phone number of a deep-sea marine biologist on
# a handwritten note taped to the wall of the submarine's cockpit.
#
# "Sea cucumbers?  Yeah, they're probably hunting for food.  But don't
# worry, they're predictable critters: they move in perfectly straight
# lines, only moving forward when there's space to do so.  They're
# actually quite polite!"
#
# You explain that you'd like to predict when you could land your
# submarine.
#
# "Oh that's easy, they'll eventually pile up and leave enough space
# for-- wait, did you say submarine?  And the only place with that
# many sea cucumbers would be at the very bottom of the Mariana--"
# You hang up the phone.
#
# There are two herds of sea cucumbers sharing the same region; one
# always moves east (>), while the other always moves south (v).  Each
# location can contain at most one sea cucumber; the remaining
# locations are empty (.).  The submarine helpfully generates a map of
# the situation (your puzzle input).  For example:
#
# v...>>.vv>
# .vv>>.vv..
# >>.>v>...v
# >>v>>.>.v.
# v>v.vv.v..
# >.>>..v...
# .vv..>.>v.
# v.v..>>v.v
# ....v..v.>
#
# Every step, the sea cucumbers in the east-facing herd attempt to
# move forward one location, then the sea cucumbers in the
# south-facing herd attempt to move forward one location.  When a herd
# moves forward, every sea cucumber in the herd first simultaneously
# considers whether there is a sea cucumber in the adjacent location
# it's facing (even another sea cucumber facing the same direction),
# and then every sea cucumber facing an empty location simultaneously
# moves into that location.
#
# So, in a situation like this:
#
# ...>>>>>...
#
# After one step, only the rightmost sea cucumber would have moved:
#
# ...>>>>.>..
#
# After the next step, two sea cucumbers move:
#
# ...>>>.>.>.
#
# During a single step, the east-facing herd moves first, then the
# south-facing herd moves.  So, given this situation:
#
# ..........
# .>v....v..
# .......>..
# ..........
#
# After a single step, of the sea cucumbers on the left, only the
# south-facing sea cucumber has moved (as it wasn't out of the way in
# time for the east-facing cucumber on the left to move), but both sea
# cucumbers on the right have moved (as the east-facing sea cucumber
# moved out of the way of the south-facing sea cucumber):
#
# ..........
# .>........
# ..v....v>.
# ..........
#
# Due to strong water currents in the area, sea cucumbers that move
# off the right edge of the map appear on the left edge, and sea
# cucumbers that move off the bottom edge of the map appear on the top
# edge.  Sea cucumbers always check whether their destination location
# is empty before moving, even if that destination is on the opposite
# side of the map:
#
# Initial state:
# ...>...
# .......
# ......>
# v.....>
# ......>
# .......
# ..vvv..
#
# After 1 step:
# ..vv>..
# .......
# >......
# v.....>
# >......
# .......
# ....v..
#
# After 2 steps:
# ....v>.
# ..vv...
# .>.....
# ......>
# v>.....
# .......
# .......
#
# After 3 steps:
# ......>
# ..v.v..
# ..>v...
# >......
# ..>....
# v......
# .......
#
# After 4 steps:
# >......
# ..v....
# ..>.v..
# .>.v...
# ...>...
# .......
# v......
#
# To find a safe place to land your submarine, the sea cucumbers need
# to stop moving.  Again consider the first example:
#
# Initial state:
# v...>>.vv>
# .vv>>.vv..
# >>.>v>...v
# >>v>>.>.v.
# v>v.vv.v..
# >.>>..v...
# .vv..>.>v.
# v.v..>>v.v
# ....v..v.>
#
# After 1 step:
# ....>.>v.>
# v.v>.>v.v.
# >v>>..>v..
# >>v>v>.>.v
# .>v.v...v.
# v>>.>vvv..
# ..v...>>..
# vv...>>vv.
# >.v.v..v.v
#
# After 2 steps:
# >.v.v>>..v
# v.v.>>vv..
# >v>.>.>.v.
# >>v>v.>v>.
# .>..v....v
# .>v>>.v.v.
# v....v>v>.
# .vv..>>v..
# v>.....vv.
#
# After 3 steps:
# v>v.v>.>v.
# v...>>.v.v
# >vv>.>v>..
# >>v>v.>.v>
# ..>....v..
# .>.>v>v..v
# ..v..v>vv>
# v.v..>>v..
# .v>....v..
#
# After 4 steps:
# v>..v.>>..
# v.v.>.>.v.
# >vv.>>.v>v
# >>.>..v>.>
# ..v>v...v.
# ..>>.>vv..
# >.v.vv>v.v
# .....>>vv.
# vvv>...v..
#
# After 5 steps:
# vv>...>v>.
# v.v.v>.>v.
# >.v.>.>.>v
# >v>.>..v>>
# ..v>v.v...
# ..>.>>vvv.
# .>...v>v..
# ..v.v>>v.v
# v.v.>...v.
#
# ...
#
# After 10 steps:
# ..>..>>vv.
# v.....>>.v
# ..v.v>>>v>
# v>.>v.>>>.
# ..v>v.vv.v
# .v.>>>.v..
# v.v..>v>..
# ..v...>v.>
# .vv..v>vv.
#
# ...
#
# After 20 steps:
# v>.....>>.
# >vv>.....v
# .>v>v.vv>>
# v>>>v.>v.>
# ....vv>v..
# .v.>>>vvv.
# ..v..>>vv.
# v.v...>>.v
# ..v.....v>
#
# ...
#
# After 30 steps:
# .vv.v..>>>
# v>...v...>
# >.v>.>vv.>
# >v>.>.>v.>
# .>..v.vv..
# ..v>..>>v.
# ....v>..>v
# v.v...>vv>
# v.v...>vvv
#
# ...
#
# After 40 steps:
# >>v>v..v..
# ..>>v..vv.
# ..>>>v.>.v
# ..>>>>vvv>
# v.....>...
# v.v...>v>>
# >vv.....v>
# .>v...v.>v
# vvv.v..v.>
#
# ...
#
# After 50 steps:
# ..>>v>vv.v
# ..v.>>vv..
# v.>>v>>v..
# ..>>>>>vv.
# vvv....>vv
# ..v....>>>
# v>.......>
# .vv>....v>
# .>v.vv.v..
#
# ...
#
# After 55 steps:
# ..>>v>vv..
# ..v.>>vv..
# ..>>v>>vv.
# ..>>>>>vv.
# v......>vv
# v>v....>>v
# vvv...>..>
# >vv.....>.
# .>v.vv.v..
#
# After 56 steps:
# ..>>v>vv..
# ..v.>>vv..
# ..>>v>>vv.
# ..>>>>>vv.
# v......>vv
# v>v....>>v
# vvv....>.>
# >vv......>
# .>v.vv.v..
#
# After 57 steps:
# ..>>v>vv..
# ..v.>>vv..
# ..>>v>>vv.
# ..>>>>>vv.
# v......>vv
# v>v....>>v
# vvv.....>>
# >vv......>
# .>v.vv.v..
#
# After 58 steps:
# ..>>v>vv..
# ..v.>>vv..
# ..>>v>>vv.
# ..>>>>>vv.
# v......>vv
# v>v....>>v
# vvv.....>>
# >vv......>
# .>v.vv.v..
#
# In this example, the sea cucumbers stop moving after 58 steps.
#
# Find somewhere safe to land your submarine.  What is the first step
# on which no sea cucumbers move?

from common import lfilter
from itertools import takewhile, count

grid = [list(l.strip()) for l in open("25.in")]
R, C = len(grid), len(grid[0])  # grid dimensions

def step():
    n = 0
    for r in range(R):
        for c in lfilter(
            lambda c: grid[r][c] == ">" and grid[r][(c+1)%C] == ".",
            range(C)
        ):
            grid[r][c] = "."
            grid[r][(c+1)%C] = ">"
            n += 1
    for c in range(C):
        for r in lfilter(
            lambda r: grid[r][c] == "v" and grid[(r+1)%R][c] == ".",
            range(R)
        ):
            grid[r][c] = "."
            grid[(r+1)%R][c] = "v"
            n += 1
    return n

print(list(takewhile(lambda _: step() > 0, count(1)))[-1] + 1)

# --- Part Two ---
#
# Suddenly, the experimental antenna control console lights up:
#
# Sleigh keys detected!
#
# According to the console, the keys are directly under the submarine.
# You landed right on them!  Using a robotic arm on the submarine, you
# move the sleigh keys into the airlock.
#
# Now, you just need to get them to Santa in time to save Christmas!
# You check your clock - it is Christmas.  There's no way you can get
# them back to the surface in time.
#
# Just as you start to lose hope, you notice a button on the sleigh
# keys: remote start.  You can start the sleigh from the bottom of the
# ocean!  You just need some way to boost the signal from the keys so
# it actually reaches the sleigh.  Good thing the submarine has that
# experimental antenna!  You'll definitely need 50 stars to boost it
# that far, though.
#
# The experimental antenna control console lights up again:
#
# Energy source detected.
# Integrating energy source from device "sleigh keys"...done.
# Installing device drivers...done.
# Recalibrating experimental antenna...done.
# Boost strength due to matching signal phase: 1 star
#
# Only 49 stars to go.

print("DONE!")