generated from public/aoc_template
75 lines
2.3 KiB
Python
75 lines
2.3 KiB
Python
from collections import deque
|
|
from tools.aoc import AOCDay
|
|
from tools.coordinate import Coordinate
|
|
from tools.grid import Grid
|
|
from typing import Any
|
|
|
|
|
|
def walk(grid: Grid, start: tuple[Coordinate, tuple[int, int]]) -> int:
|
|
visited = set()
|
|
q = deque()
|
|
q.append(start)
|
|
while q:
|
|
cur = q.popleft()
|
|
if cur in visited:
|
|
continue
|
|
pos, direction = cur
|
|
if not grid.isWithinBoundaries(pos):
|
|
continue
|
|
visited.add(cur)
|
|
|
|
tile = grid.get(pos)
|
|
if not tile or (tile == '-' and direction[1] == 0) or (tile == '|' and direction[0] == 0):
|
|
q.append((pos + direction, direction))
|
|
elif tile == '|':
|
|
q.append((pos + (0, 1), (0, 1)))
|
|
q.append((pos + (0, -1), (0, -1)))
|
|
elif tile == '-':
|
|
q.append((pos + (1, 0), (1, 0)))
|
|
q.append((pos + (-1, 0), (-1, 0)))
|
|
elif tile == '\\':
|
|
q.append((pos + (direction[1], direction[0]), (direction[1], direction[0])))
|
|
elif tile == '/':
|
|
q.append((pos + (-direction[1], -direction[0]), (-direction[1], -direction[0])))
|
|
else:
|
|
assert False, tile
|
|
|
|
return len(set(x[0] for x in visited))
|
|
|
|
|
|
class Day(AOCDay):
|
|
inputs = [
|
|
[
|
|
(46, "input16_test"),
|
|
(8539, "input16_dennis"),
|
|
(7074, "input16"),
|
|
],
|
|
[
|
|
(51, "input16_test"),
|
|
(8674, "input16_dennis"),
|
|
(7530, "input16"),
|
|
]
|
|
]
|
|
|
|
def part1(self) -> Any:
|
|
grid = Grid.from_data(self.getInput(), translate={'.': False})
|
|
return walk(grid, start=(Coordinate(0, 0), (1, 0)))
|
|
|
|
def part2(self) -> Any:
|
|
grid = Grid.from_data(self.getInput(), translate={'.': False})
|
|
max_tiles = 0
|
|
for x in grid.rangeX():
|
|
max_tiles = max(max_tiles, walk(grid, start=(Coordinate(x, 0), (0, 1))))
|
|
max_tiles = max(max_tiles, walk(grid, start=(Coordinate(x, grid.maxY), (0, -1))))
|
|
|
|
for y in grid.rangeY():
|
|
max_tiles = max(max_tiles, walk(grid, start=(Coordinate(0, y), (1, 0))))
|
|
max_tiles = max(max_tiles, walk(grid, start=(Coordinate(grid.maxX, -y), (-1, 0))))
|
|
|
|
return max_tiles
|
|
|
|
|
|
if __name__ == '__main__':
|
|
day = Day(2023, 16)
|
|
day.run(verbose=True)
|