Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
Where do I participate?: https://adventofcode.com/
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
The data today has a special property, which allows for a fast solution. This won't work on other data, including the example data in the problem description.
1645 line-seconds.
import collections
import math
from .solver import Solver
classDay21(Solver):
first_star_steps: int
second_star_steps: int
lines: list[str]
def__init__(self):
super().__init__(21)
self.first_star_steps = 64
self.second_star_steps = 26501365defpresolve(self, input: str):
self.lines = input.splitlines()
defsolve_first_star(self) -> int | str:
positions = {(i, j) for i, line inenumerate(self.lines) for j, c inenumerate(line) if c == 'S'}
for _ inrange(self.first_star_steps):
next_positions = set()
for i, j in positions:
for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
ifnot0 <= i + di < len(self.lines):
continueifnot0 <= j + dj < len(self.lines[i]):
continueif self.lines[i + di][j + dj] == '#':
continue
next_positions.add((i + di, j + dj))
positions = next_positions
returnlen(positions)
defsolve_second_star(self) -> int:
positions = {(i, j) for i, line inenumerate(self.lines) for j, c inenumerate(line) if c == 'S'}
modulus = self.second_star_steps % len(self.lines)
points_to_extrapolate = (modulus, modulus + len(self.lines), modulus + len(self.lines) * 2)
values = []
for step_count inrange(modulus + len(self.lines) * 2 + 1):
if step_count in points_to_extrapolate:
values.append(len(positions))
next_positions = set()
for i, j in positions:
for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
ni = i + di
nj = j + dj
if self.lines[ni % len(self.lines)][nj % len(self.lines)] == '#':
continue
next_positions.add((ni, nj))
positions = next_positions
a = (values[2] - values[1] *2 + values[0]) // 2
b = values[1] - values[0] - 3 * a
c = values[0] - b - a
cycles = math.ceil(self.second_star_steps / len(self.lines))
return a * cycles * cycles + b * cycles + c
Python
The data today has a special property, which allows for a fast solution. This won't work on other data, including the example data in the problem description.
1645 line-seconds.
import collections import math from .solver import Solver class Day21(Solver): first_star_steps: int second_star_steps: int lines: list[str] def __init__(self): super().__init__(21) self.first_star_steps = 64 self.second_star_steps = 26501365 def presolve(self, input: str): self.lines = input.splitlines() def solve_first_star(self) -> int | str: positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'} for _ in range(self.first_star_steps): next_positions = set() for i, j in positions: for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)): if not 0 <= i + di < len(self.lines): continue if not 0 <= j + dj < len(self.lines[i]): continue if self.lines[i + di][j + dj] == '#': continue next_positions.add((i + di, j + dj)) positions = next_positions return len(positions) def solve_second_star(self) -> int: positions = {(i, j) for i, line in enumerate(self.lines) for j, c in enumerate(line) if c == 'S'} modulus = self.second_star_steps % len(self.lines) points_to_extrapolate = (modulus, modulus + len(self.lines), modulus + len(self.lines) * 2) values = [] for step_count in range(modulus + len(self.lines) * 2 + 1): if step_count in points_to_extrapolate: values.append(len(positions)) next_positions = set() for i, j in positions: for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)): ni = i + di nj = j + dj if self.lines[ni % len(self.lines)][nj % len(self.lines)] == '#': continue next_positions.add((ni, nj)) positions = next_positions a = (values[2] - values[1] *2 + values[0]) // 2 b = values[1] - values[0] - 3 * a c = values[0] - b - a cycles = math.ceil(self.second_star_steps / len(self.lines)) return a * cycles * cycles + b * cycles + c