Skip to content

Instantly share code, notes, and snippets.

@ephbaum
Created December 21, 2023 18:28
Show Gist options
  • Save ephbaum/59bc2d1bba38fedf46bcab8b7d735e17 to your computer and use it in GitHub Desktop.
Save ephbaum/59bc2d1bba38fedf46bcab8b7d735e17 to your computer and use it in GitHub Desktop.
Advent of Code 2023 - Day 21
from collections import deque
def parse_map(map_data):
"""Parse the map data to find the starting position and create a grid."""
grid = []
start = None
for y, row in enumerate(map_data):
row_list = list(row.strip())
grid.append(row_list)
if 'S' in row:
start = (y, row.index('S'))
return grid, start
def bfs_revisited(grid, start, step_limit):
"""Perform BFS to count the reachable plots in exactly 'step_limit' steps, revisiting the logic."""
rows, cols = len(grid), len(grid[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # east, south, west, north
visited = set() # Keep track of visited positions with steps
queue = deque([(start, 0)]) # Queue of (position, steps), starting from 1
reachable_plots = set()
while queue:
(y, x), steps = queue.popleft()
# If exactly 'step_limit' steps, add to reachable plots
if steps == step_limit and grid[y][x] == '.':
reachable_plots.add((y, x))
# Proceed only if steps are less than or equal to the limit
if steps < step_limit:
for dy, dx in directions:
ny, nx = y + dy, x + dx
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == '.' and (ny, nx, steps+1) not in visited:
visited.add((ny, nx, steps+1))
queue.append(((ny, nx), steps+1))
return len(reachable_plots)
def read_map_file(file_path):
"""Read map data from a file."""
with open(file_path, 'r') as file:
return file.readlines()
# Path to the map file
# file_path = "map_example.txt"
file_path = "map.txt"
# Read the map data from the file
map_data = read_map_file(file_path)
# Now, you can use the read map data with the existing functions
grid, start = parse_map(map_data)
# reachable_plots_count = bfs_revisited(grid, start, 6)
reachable_plots_count = bfs_revisited(grid, start, 64)
print(f"Number of reachable plots in 64 steps: {reachable_plots_count + 1}")
with open('map.txt', 'r') as file:
input_data = file.read().strip()
# Parsing the grid from the input file
grid = list(map(list, input_data.split("\n")))
# Movement directions (up, left, down, right)
move_x = [0, -1, 0, 1]
move_y = [-1, 0, 1, 0]
# Grid dimensions
grid_height = len(grid)
grid_width = len(grid[0])
print(f"Grid dimensions: {grid_height}x{grid_width}")
# Finding the starting position (marked 'S')
start_positions = set()
for row in range(grid_height):
for col in range(grid_width):
if grid[row][col] == "S":
start_positions.add((row, col))
# Goal number of steps
goal_steps = 26501365
# Quadratic function to calculate the number of reachable plots
def file(num_steps, a0, a1, a2):
initial_plots = a0
linear_growth = a1 - a0
quadratic_growth = a2 - a1
return initial_plots + linear_growth * num_steps + (num_steps * (num_steps - 1) // 2) * (quadratic_growth - linear_growth)
# BFS to explore the grid
prev_len = 0
reachable_plots = []
for iteration in range(1, 100000):
next_positions = set()
for row, col in start_positions:
for k in range(4):
new_row, new_col = row + move_x[k], col + move_y[k]
if grid[new_row % grid_height][new_col % grid_width] != "#":
next_positions.add((new_row, new_col))
start_positions = next_positions
if iteration % grid_height == goal_steps % grid_height:
current_len = len(start_positions)
reachable_plots.append(current_len)
print(f"Iteration {iteration}: {current_len}, Growth: {current_len - prev_len}, Factor: {iteration // grid_height}")
prev_len = current_len
if len(reachable_plots) == 3: # We can calculate the quadratic function with 3 points
break
# Call f with the calculated a0, a1, and a2 values
if len(reachable_plots) >= 3:
estimated_reachable_plots = file(goal_steps // grid_height, reachable_plots[0], reachable_plots[1], reachable_plots[2])
print(f"Estimated reachable plots for {goal_steps} steps: {estimated_reachable_plots}")
# Final number of reachable plots
print(f"Number reachable plots used to get values for quadratic equation: {len(start_positions)}")
...................................................................................................................................
....#..#...##..##........#...#.#.........#.....#.#....................#..###.#.#...#........##......#.#.......#............#.......
.#...#........................#.....#.#..............#....................#..#....................#...............##..#...##.#.....
....#......#..#.#.....#...............#........#........#.#...............#....#..#..#..##........................#.#...#..........
......................................#...#......#....#..................#.#......................#.....#....#....#.#....#....#....
..#.....#....#....#.#....#...#...#..............##..#...........#..................#.......#.......#...#....##...#.........#.......
....##..........#.........#.....#...#.#.#.......#.#...#............................#..#.............#.#............................
............#.#...............................#.....#............................#......#.......#........#.......#.....#...#.#.....
....#.......#........#......................#....#............#....#..........................#....#......##.....#...........##....
...#.#.#..##...........................#........................#...#.........##.....#...#.#..............#.#.....#.#...##..#......
..#.....#..#.................................#...#...........##.....#...........#........#.#..#..........##....#..#.#..............
....##..#.#...#..#...................#...#...#...............#.....#......................................#............#.......#...
............#..#...##....#.#..#............#...#.........##.......#........................#..............###.#...........#......#.
.......#..#......#...#.##..#...#....#.#.......................#.#.####....#...................#...#.........##.....##...........#..
.....#..#..............#....##..#....#.................#.#....#.....#...............#....#...................................#.....
..#.......#..#....##......#.....##........#...........#.#...........................#.#.....#...................###...........#..#.
.#....###.....#......#......#.........#......................#.#..........................##...#..#.............##...#...#.#.......
...#..##..#...................#.....#.#..#..#.........##....#..............#.#...........##.....#.......##..............#....#...#.
........#..............#...................................##........#....#...........................#...............#.......#.##.
.......#......#.............#..........#.................#.....##....##...##............##....................#.#.#........#....##.
...............#...........#..#.....#...............#......#.......#...#..#.##.............#.#..............##....#.........###....
....#.....#..##.................................#.....##........#...................................#....#...#.........#..#......#.
............#.........#....#...#.......................#.##.....#...................................#....#.....#..#.......#.....#..
...##..........#.#.....#..#........##....................#...............#..#..#........................#....#............#..#.....
...................#.....#......................#.#............#...........##......................#..#............#.....##........
...#.......##......#......#....#.............#...#............#...............#...................#.#.##........................#..
..#..#........##..#.#...#..#..#..##........#.#...............#........................#............#...#.......#.........#..#......
..................#..#..#.....#..................#.#.#..#...............#...#..###..#........................#.....#...#.......#...
............#.......##..........#..............#.....#.#...........#........##...##..##.#..........#.............#..#.#............
..........................#....#...........#.............#...........#....#......##...............#....#.....#....#.##.....#.#...#.
.#........#.............#........................#.#........##.#......#...........#.....##............###.....#.....#.....#........
......#..........#......#..#.......................#......................##.....#..#.......#........#....#.#..#..#.......#......#.
.....#........#..#.....#..#.............#.................#.........#..................#...#..........##....#.#.#..#.##........###.
...#......#.#.............#..............#.............#...#..#...##.#..#..........##......##..............##..#.#...#.........#...
......##..#......#.#....#.##.......#......#.#...................#.......#.....#..........................#........#...........#....
...#...............##.............#.............................#.......#.............#....#....................................#..
..#.#....#.#.....#.#...#..........#..#................#.....#........#.#...............#........#........................#....#....
....#....#.......#...............#..........##.#..................#...#...............#.#....#..............#......#.......#....##.
..#..................#......................#...#..##.....##.###......#.###...........#..#.............................##.......##.
..#..##...#..#....................#....#.#.#..#.#.#..#.#...##......#.#.#....#..........##.#..##.#..#..............##...............
.....#..............#.........................###.....##...............#.....#.....#..#......###.....#.............................
.......##....................................#.........#..#...#...##......#......#.#.#...#......##...#.......................#.#...
.#....#....#.......#............##.....................#.......#...#..#.......#...#..#...#.....................................#...
.#...#.......#..#...............##...........#....#.....##...#..........#.....#...#.........##....#..#.....................#..#.##.
......##..................#.##...#....#.................#...#.#........##.......#.....#........#.......#...............#..#....#...
.#........##.#..............#.....#...........#...#...#.#..#.#...........#....#.......#.....#...##.....................#.#...##..#.
......#..#..#.#........#...#......#........#.#.........##...........#............#..........#......................#..#..#.....#...
.#.......#..#.........#.#....#.#.##...........##.....#........#.#..........#......#..............#...#..#..............#..#........
.....#....#............#.#...........#..#.#..#............#...........#......#.#...........#...#................................#..
....##.................#.....##.....#.....................#..........#.#.#...#.....#...............#.....#.#.............#.........
......#...............#.#.#......#...##..........#...........##....#.............#.........#......#......#...................#.##..
.....#............#.......#.#.............#....#.......#..........#.##.#...#........##......#.....#.#...#..........................
....#....................#................#..#....#....##..#...#.....#........#..#.........#....#.......#......#.............#...#.
.#...#................#...#....................#.....#.....#........##........#....#.#...#...#..#..#.#...#..#......................
....#.........................#.....#..#..............##......#.#.....#............................#.#.....#.....#.................
......................#...##.........##........#..#.........#.....#...##...#..#.#...#..........................#.................#.
..#..#........#...#.......#....................#....#.......#.#.......#....#.......#.#.#.................#.....................##..
.#................#....#...............#.#..........#.......#...........#.##.#...#.....#..............#...#....#..#................
.#....................#................##.......#####......#..........#........#.............#.#.........#.#......#..#.............
..#.......#....#...#.#.................#.......#................#..#..#.....##..#.....................#..#....#....................
.........#.......##...#.#.........#.....#.........#.....#.#.#..##...#...#.......#....................#..#...#..#....#.#............
..............#.........#.....#.###....##...#.....#........##...#......#..........#...........#..##...#.....#.#........#...........
.........#.#..........#..........#.........#........##....#..##.........##......#..#..#........#.....#.....#.......................
.......#.#...........#........##.......#............#........#.#...............#..#.......#..#.........#.....#..#..#..#..#.........
.......#............#.#............#...........##..#.........#.....#......#..#...#.............................#......#..#.........
.................................................................S.................................................................
.......##....#...#......#...........#.........#.....#..#...........#.##....#.##..#........................................###......
.....................#...............#....#.........#..........#.....#..#.......#.......#...............#.#.....#..#...............
.........##..........#.....#.............#...#.........##..........##........##......#............#.#...##...#...#..#....#.#.......
............#..##........#..........#.##..............#................#..#..#..#...#.##........#......#.......#.......#.##........
.......................#.....#..#..#.....#....................#.............###.....#..#....#.......#...#.......#......#...........
.#........#.#.....#...#.#......#..#.#.#..#......##..........##..#.....#...............#............................................
.....................##..........#.....#.........#....#.........................#..........#...#.#.....#.....#...#.................
.##................#.......##...........#...#.#.........##..#.......#.......##................#........#...##.......#............#.
....................#.#.....#...#...#..#..##...##...#..................#......................#....##........................#.....
..#.............#...#.......#...#....#..#............#..#.#......................#.................#.#...#..#.....#.........#.#....
...................#.#......##.............#...............#..#.#......................#...............###..###..#..........#......
........#............#...#...#.#....#..#..........#..................#.........#.......#.........#..##......#..............#...#...
..##.............##.......##.#.#.#....#....#.#...#....................#..........#...#.......#..#..........#.#...............#.....
...#..............#.....#..............###......#........#..#.....#.......#...#..#.................#.#........#..........#.....#...
....#....#............#.#....#..........#............#.........##...............#.#................#...#...................#..#.#..
........#.#.........#....#.....#.....#.#..#.........................#..#.#.......##.#.........#......#..##....#........##.#........
......................#......#...........#......#......#.#................#...##.#....#......#.....#.................#...#.#...#...
.....#..#...................#...............###..........#.............#..#.#.....#....#....................................#.#.#..
.#.#.........#.........#......#.#...............#.....#..#......#.....#.#..#...##.........#...#....#............................#..
..#.#......#..............#.##.#..##....#.............#.....#....................###.....#...#..#.....................#.......#.#..
.#.#.........#.................#.#........#..##.........#..#.......#...##....#...#..........#.#...#..#.#...........#......#.###.##.
.........##..................#...#......##...##...#.............#..........#.....###......#...#...#.#.#.................##.#...#...
..........#...#..#...................#..#....##........#..........##............#......#........#.#.................#............#.
..#.....#......#..............#............................##..##.............##.......#.#..#.........#..........##...##.....#..#..
.............#..............................#.#........................#......##...............#..#................#.##...#........
...#..#.....#..##...#..................................#.....................#...#.....#.........#..........#........#...#.#.#.....
....#......#.##.....#..........#.....##.........#.#..#.........................................................#......#..##.#....#.
...................#............................#........#..#.................#.....#..#.......#..............##.#.....#...........
......#......#..#................#........#...#..#..............#......#....#.......#.....................#...........#....#...##..
..#..#.....#...#..#...............##.............#.#........#...........#.............##....#.#...........#.#.........###....##....
..#......#.#...#.........#...................................#........#...................................................#..#.....
.............#......#.......#........#.........#...........#....#..#...................##..............#.#...#.#...........#..#..#.
....#............#.....#.............#...#..........#.......#.....#......................#..#..........#.#....#...........#........
..........#.......##.....................##....##......#.............##.##...#..........#.#...................#..............##.#..
....#....#.........#.#..#..##.#....................#..............#.......#............................#.......#..........##....#..
..##.#.........#.......#...#..........................#.#.....#....#.....##......#....#...#...................................#....
..........#.....#..#....#...................#.....#.#...##..#.#................#.#...................##.........#........#....##...
.............#.........#.....#.............#.............##.............#.....#....#.................#...#.......#.#..#..#...#.#...
........##...#....#..........#......................#..#.#...........#........#..#.#..............#............#......#........#...
...#.#..#.#...............#..##..#..#.........#........#.#..........#.......#.........#........#.......#.......#..#....##.......#..
..#.......###.........#.....##.......#....................#..#......##.......#....##..........##........#.....................#....
.........#..#.....#.....#......#.....#........#...............#...#...#......#.................................#.#.#............##.
.....#.........#..#.........#..##......#...................##.....##.....#.....#............#.......#.....#..#..#..#..........#.#..
..........#.#.........#.......#..#...##......................................#..............#....##.#..#....#....#.##..............
...........###.#..........##...........................................#.........#.......#.....................#......##...........
...#........#.....#...................#.......................##.......#......#...........#..###.....#..#.......#........#.........
..##.....#..#..#.....#.................#.#.............#...##.........#................#.......................##.......#.....###..
..............##.#...#............#......#...........#..#.........#..#......#...........##....#....#.............##.#..............
.#..##.#.............#.....#.............................#.....#.........#.................##.#...#.....#.....#..#..#............#.
.#.#...#.##..........#..........#.......#.....................#..........##..............#.............#........#.#......#....#....
....#...................#.......#.....#................#.....#.....#.....#.............#.#.#..#.................#........#..#......
.............#...#.......#.#..#...##....#..#..#.........##.............#.............#.#.#.........#..................#............
............#..#...#..##....##..#.....#..........#.......##.#.......................................#.#..........................#.
..#................#...##.....#..........#...#...............#........................#....##.....#..............#...##.##.#..#.#..
....#.#...#.#.#.....#..#.##.#.##....#.#.##..#..................................##.......................##........#.#......##...#..
...#.....#.#..#..#.#.......#.......#..##.#.....#............#.#......##..............#.#...#.....#...#.#....#.........#.....#....#.
....###.#..............#.#.....##..........#......................#.#...............#.##.....#........#.#...#..#.#............#..#.
.......#.....#.#..............#..#..#........##.#.#...............#.....................#...#..#.##...........#.....#....#.#..#....
.......##..........#.#....#..#..#.......##.......#..................................#..#..........#............#....#......#.##....
.###.##.##........#.....#......#....#...................#.........#..................#...#..............#..#......#..........#..#..
.....##.........................#.....#.......#...#.....#.................##..#........#...................###.#......#..#....#....
..#........#........##......#..#.#..............#.........................#...###.#...#....##.#........#.#......#........#....##...
..........#.....#........#................##...........#...............###.....##...........#..#...#...#..##......#........#.#.....
.....#....#......................#.##.............#..#...#.#.............#............#..#..#.....#.......................#...###..
...................................................................................................................................
...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment