Source: Sea Cucumber
Part 1: Load a grid of empty cells (.), east movers (>), and south movers (v). Each step, move all east movers than all south movers (only if they can this iteration). Wrap east/west and north/south. How many steps does it take the movers to get stuck?
Let’s just do it!
@dataclass(frozen=True)
class Point:
x: int
y: int
def __repr__(self):
return f'<{self.x}, {self.y}>'
def __add__(self, other: 'Point') -> 'Point':
return Point(self.x + other.x, self.y + other.y)
def __mod__(self, bound: 'Point') -> 'Point':
return Point(self.x % bound.x, self.y % bound.y)
EAST = Point(1, 0)
SOUTH = Point(0, 1)
@dataclass(frozen=True)
class State:
bounds: Point
east_movers: FrozenSet[Point]
south_movers: FrozenSet[Point]
@staticmethod
def read(file: TextIO) -> 'State':
east_movers = set()
south_movers = set()
for y, line in enumerate(file):
for x, c in enumerate(line.strip()):
if c == '>':
east_movers.add(Point(x, y))
elif c == 'v':
south_movers.add(Point(x, y))
return State(Point(x + 1, y + 1), east_movers, south_movers)
def step(self) -> 'State':
new_east_movers = {
(p + EAST) % self.bounds if (
(p + EAST) % self.bounds not in self.east_movers
and (p + EAST) % self.bounds not in self.south_movers
) else p
for p in self.east_movers
}
new_south_movers = {
(p + SOUTH) % self.bounds if(
(p + SOUTH) % self.bounds not in new_east_movers
and (p + SOUTH) % self.bounds not in self.south_movers
) else p
for p in self.south_movers
}
return State(self.bounds, new_east_movers, new_south_movers)
I particularly like how p + p and p % p work and also how you can step them all pretty much in two lines. Pretty cool!
And to solve:
@app.command()
def solve(file: typer.FileText):
s = State.read(file)
for i in itertools.count(1):
logging.info(f'{i}\n{s}')
sp = s.step()
if s == sp:
break
else:
s = sp
logging.info('\n{s}\n')
print(f'{i} steps')
Quick enough:
--- Day 25: Sea Cucumber ---
$ python3 cucumbinator.py solve input.txt
419 steps
# time 14198676792ns / 14.20s
I did take some time to render it as a gif though!
$ python3 cucumbinator.py render input.txt 'aoc2021-25-input.gif' 556x548
Merry Christmas. :D
‘All’ solutions
As always with Advent of Code, there’s no part 2 on the last day. So instead, for better or for worse, here’s the current timing of all my answers this year!
$ python3 all.py
--- Day 1: Sonar Sweep ---
$ python3 depth-finder.py part1 input.txt
1393
# time 44893792ns / 0.04s
$ python3 depth-finder.py part2 input.txt 3
1359
# time 34075167ns / 0.03s
$ python3 depth-finder.py part2-simple input.txt 3
1359
# time 33592209ns / 0.03s
--- Day 2: Dive! ---
$ python3 submarine-simulator.py part1 input.txt
position=2007, depth=747, position*depth=1499229
# time 33215792ns / 0.03s
$ python3 submarine-simulator.py part2 input.txt
position=2007, depth=668080, position*depth=1340836560
# time 32647917ns / 0.03s
--- Day 3: Binary Diagnostic ---
$ python3 binary-contraption.py part1 input.txt
gamma='100100101010'=2346, epsilon='011011010101'=1749, product=4103154
# time 34595542ns / 0.03s
$ python3 binary-contraption.py part2 input.txt
potential_generators=['110101000111']=3399, potential_scrubbers=['010011100001']=1249, product=4245351
# time 33425041ns / 0.03s
--- Day 4: Giant Squid ---
$ python3 his-name-oh.py part1 input.txt
remaining_numbers=[99, 19, 9, 59, 92, 82, 69, 72, 2, 45, 93, 27], sum(remaining_numbers)=668, number=66, product=44088
# time 46472333ns / 0.05s
$ python3 his-name-oh.py part2 input.txt
remaining_numbers=[3, 78, 23, 79, 80], sum(remaining_numbers)=263, number=90, product=23670
# time 64237667ns / 0.06s
--- Day 5: Hydrothermal Venture ---
$ python3 linear-avoidinator.py part1 input.txt
5632
# time 160036875ns / 0.16s
$ python3 linear-avoidinator.py part2 input.txt
22213
# time 289326791ns / 0.29s
--- Day 6: Lanternfish ---
$ python3 we-all-glow-down-here.py 80 input.txt
395627
3.95e6
# time 32692042ns / 0.03s
$ python3 we-all-glow-down-here.py 256 input.txt
1767323539209
1.76e13
# time 32836333ns / 0.03s
--- Day 7: The Treachery of Whales ---
$ python3 brachyura-aligner.py part1 input.txt
target=323, fuel=336040
# time 134097542ns / 0.13s
$ python3 brachyura-aligner.py part2 input.txt
target=463, fuel=94813675
# time 265068000ns / 0.27s
--- Day 8: Seven Segment Search ---
$ python3 seven-segment-demystifier.py part1 input.txt
349
# time 704037791ns / 0.70s
$ python3 seven-segment-demystifier.py part2 input.txt
1070957
# time 722054125ns / 0.72s
$ python3 seven-segment-demystifier.py --fast part1 input.txt
349
# time 50202125ns / 0.05s
$ python3 seven-segment-demystifier.py --fast part2 input.txt
1070957
# time 50484291ns / 0.05s
--- Day 9: Smoke Basin ---
$ python3 local-minimum-deminifier.py part1 input.txt
total_risk=491
# time 41001958ns / 0.04s
$ python3 local-minimum-deminifier.py part2 input.txt
The largest basins are [112, 99, 97] with a size product of 1075536
# time 44843709ns / 0.04s
--- Day 10: Syntax Scoring ---
$ python3 chunkinator.py part1 input.txt
167379
# time 34562209ns / 0.03s
$ python3 chunkinator.py part2 input.txt
2776842859
# time 34596333ns / 0.03s
--- Day 11: Dumbo Octopus ---
$ python3 octopus-flashinator.py part1 input.txt
1679
# time 43026125ns / 0.04s
$ python3 octopus-flashinator.py part2 input.txt
519
# time 79435000ns / 0.08s
--- Day 12: Passage Passing ---
$ python3 submarine-spider.py part1 input.txt
4749
# time 69497166ns / 0.07s
$ python3 submarine-spider.py part2 input.txt
123054
# time 1182472583ns / 1.18s
$ python3 submarine-spider.py part2-fast input.txt
123054
# time 516106250ns / 0.52s
--- Day 13: Transparent Origami ---
$ python3 foldinator.py part1 input.txt
706
# time 35915167ns / 0.04s
$ python3 foldinator.py part2 input.txt
* *** **** ** *** ** **** * *
* * * * * * * * * * *
* * * *** * *** * *** ****
* *** * * * * * * * *
* * * * * * * * * * * * *
**** * * * ** *** ** **** * *
# time 37279250ns / 0.04s
--- Day 14: Extended Polymerization ---
$ python3 polymerizationinator.py direct input.txt 10
2797
# time 54387334ns / 0.05s
$ python3 polymerizationinator.py recursive input.txt 10
2797
# time 100416792ns / 0.10s
$ python3 polymerizationinator.py direct input.txt 15
85972
# time 795572458ns / 0.80s
$ python3 polymerizationinator.py recursive input.txt 15
85972
# time 2112865750ns / 2.11s
$ python3 polymerizationinator.py --cache recursive input.txt 15
85972
# time 39737625ns / 0.04s
$ python3 polymerizationinator.py --cache recursive input.txt 40
2926813379532
# time 48990125ns / 0.05s
--- Day 15: Chiton ---
$ python3 low-ceiling-simulator.py part1 input.txt
best_score=687
# time 1697947292ns / 1.70s
$ python3 low-ceiling-simulator.py --version 2 part1 input.txt
best_score=687
# time 88316334ns / 0.09s
$ python3 low-ceiling-simulator.py --version 3 part1 input.txt
best_score=687
# time 269650750ns / 0.27s
$ python3 low-ceiling-simulator.py --version 4 part1 input.txt
best_score=687
# time 93736375ns / 0.09s
$ python3 low-ceiling-simulator.py --version 4 part2 input.txt
best_score=2957
# time 1704585750ns / 1.70s
--- Day 16: Packet Decoder ---
$ python3 depacketinator.py part1 input.txt
981 005532447836402684AC7AB3801A800021F0961146B1007A1147C89440294D005C12D2A7BC992D3F4E50C72CDF29EECFD0ACD5CC016962099194002CE31C5D3005F401296CAF4B656A46B2DE5588015C913D8653A3A001B9C3C93D7AC672F4FF78C136532E6E0007FCDFA975A3004B002E69EC4FD2D32CDF3FFDDAF01C91FCA7B41700263818025A00B48DEF3DFB89D26C3281A200F4C5AF57582527BC1890042DE00B4B324DBA4FAFCE473EF7CC0802B59DA28580212B3BD99A78C8004EC300761DC128EE40086C4F8E50F0C01882D0FE29900A01C01C2C96F38FCBB3E18C96F38FCBB3E1BCC57E2AA0154EDEC45096712A64A2520C6401A9E80213D98562653D98562612A06C0143CB03C529B5D9FD87CBA64F88CA439EC5BB299718023800D3CE7A935F9EA884F5EFAE9E10079125AF39E80212330F93EC7DAD7A9D5C4002A24A806A0062019B6600730173640575A0147C60070011FCA005000F7080385800CBEE006800A30C023520077A401840004BAC00D7A001FB31AAD10CC016923DA00686769E019DA780D0022394854167C2A56FB75200D33801F696D5B922F98B68B64E02460054CAE900949401BB80021D0562344E00042A16C6B8253000600B78020200E44386B068401E8391661C4E14B804D3B6B27CFE98E73BCF55B65762C402768803F09620419100661EC2A8CE0008741A83917CC024970D9E718DD341640259D80200008444D8F713C401D88310E2EC9F20F3330E059009118019A8803F12A0FC6E1006E3744183D27312200D4AC01693F5A131C93F5A131C970D6008867379CD3221289B13D402492EE377917CACEDB3695AD61C939C7C10082597E3740E857396499EA31980293F4FD206B40123CEE27CFB64D5E57B9ACC7F993D9495444001C998E66B50896B0B90050D34DF3295289128E73070E00A4E7A389224323005E801049351952694C000
# time 43134500ns / 0.04s
$ python3 depacketinator.py part2 input.txt
299227024091 005532447836402684AC7AB3801A800021F0961146B1007A1147C89440294D005C12D2A7BC992D3F4E50C72CDF29EECFD0ACD5CC016962099194002CE31C5D3005F401296CAF4B656A46B2DE5588015C913D8653A3A001B9C3C93D7AC672F4FF78C136532E6E0007FCDFA975A3004B002E69EC4FD2D32CDF3FFDDAF01C91FCA7B41700263818025A00B48DEF3DFB89D26C3281A200F4C5AF57582527BC1890042DE00B4B324DBA4FAFCE473EF7CC0802B59DA28580212B3BD99A78C8004EC300761DC128EE40086C4F8E50F0C01882D0FE29900A01C01C2C96F38FCBB3E18C96F38FCBB3E1BCC57E2AA0154EDEC45096712A64A2520C6401A9E80213D98562653D98562612A06C0143CB03C529B5D9FD87CBA64F88CA439EC5BB299718023800D3CE7A935F9EA884F5EFAE9E10079125AF39E80212330F93EC7DAD7A9D5C4002A24A806A0062019B6600730173640575A0147C60070011FCA005000F7080385800CBEE006800A30C023520077A401840004BAC00D7A001FB31AAD10CC016923DA00686769E019DA780D0022394854167C2A56FB75200D33801F696D5B922F98B68B64E02460054CAE900949401BB80021D0562344E00042A16C6B8253000600B78020200E44386B068401E8391661C4E14B804D3B6B27CFE98E73BCF55B65762C402768803F09620419100661EC2A8CE0008741A83917CC024970D9E718DD341640259D80200008444D8F713C401D88310E2EC9F20F3330E059009118019A8803F12A0FC6E1006E3744183D27312200D4AC01693F5A131C93F5A131C970D6008867379CD3221289B13D402492EE377917CACEDB3695AD61C939C7C10082597E3740E857396499EA31980293F4FD206B40123CEE27CFB64D5E57B9ACC7F993D9495444001C998E66B50896B0B90050D34DF3295289128E73070E00A4E7A389224323005E801049351952694C000
# time 41857292ns / 0.04s
--- Day 17: Trick Shot ---
$ python3 pew-pewinator.py part1 input.txt
2850
# time 728209708ns / 0.73s
$ python3 pew-pewinator.py part2 input.txt
1117
# time 34003049541ns / 34.00s
--- Day 18: Snailfish ---
$ python3 pairs-of-pairs.py part1 input.txt
4433
# time 412309834ns / 0.41s
$ python3 pairs-of-pairs.py part2 input.txt
4559
# time 5496543584ns / 5.50s
--- Day 19: Beacon Scanner ---
$ python3 point-matchinator.py part1 input.txt
313
# time 420895747958ns / 420.90s
$ python3 point-matchinator.py part2 input.txt
10656
# time 403475587666ns / 403.48s
--- Day 20: Trench Map ---
$ python3 enhancinator.py part1 input.txt
5057
# time 288085792ns / 0.29s
$ python3 enhancinator.py part2 input.txt
18502
# time 10353347750ns / 10.35s
--- Day 21: Dirac Dice ---
$ python3 dicinator.py part1 input.txt
1 wins, 752247
# time 37687791ns / 0.04s
$ python3 dicinator.py part2 input.txt
221109915584112
# time 170310291ns / 0.17s
--- Day 22: Reactor Reboot ---
$ python3 cubinator.py part1 input.txt
590467
# time 32701100500ns / 32.70s
$ python3 cubinator.py part2 input.txt
1225064738333321
# time 9419514983155ns / 9419.51s
--- Day 23: Amphipods ---
$ python3 amphipodinator.py main input1.txt goal1.txt
Final solution:
State<13x5>{
#############
# #
###A#B#C#D###
#A#B#C#D#
#########
}
states examined: 896123
11608
# time 105522400083ns / 105.52s
$ python3 amphipodinator.py main input1.txt goal1.txt --heuristic
Final solution:
State<13x5>{
#############
# #
###A#B#C#D###
#A#B#C#D#
#########
}
states examined: 156876
11608
# time 18701982625ns / 18.70s
$ python3 amphipodinator.py main input2.txt goal2.txt --heuristic
Final solution:
State<13x7>{
#############
# #
###A#B#C#D###
#A#B#C#D#
#A#B#C#D#
#A#B#C#D#
#########
}
states examined: 784637
46754
# time 162205732958ns / 162.21s
--- Day 24: Arithmetic Logic Unit ---
$ python3 aluinator.py solve input.txt
part1: 99995969919326
part2: 48111514719111
# time 64456917ns / 0.06s
--- Day 25: Sea Cucumber ---
$ python3 cucumbinator.py solve input.txt
419 steps
# time 14853312250ns / 14.85s
There are some that could certainly be better… but overall, I’m pretty happy with it. Now, to go back and do the years I missed!