Advent of Code 2023 - Day 21

main.py

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}")

main_p2.py

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)}")

map.txt

...................................................................................................................................
....#..#...##..##........#...#.#.........#.....#.#....................#..###.#.#...#........##......#.#.......#............#.......
.#...#........................#.....#.#..............#....................#..#....................#...............##..#...##.#.....
....#......#..#.#.....#...............#........#........#.#...............#....#..#..#..##........................#.#...#..........
......................................#...#......#....#..................#.#......................#.....#....#....#.#....#....#....
..#.....#....#....#.#....#...#...#..............##..#...........#..................#.......#.......#...#....##...#.........#.......
....##..........#.........#.....#...#.#.#.......#.#...#............................#..#.............#.#............................
............#.#...............................#.....#............................#......#.......#........#.......#.....#...#.#.....
....#.......#........#......................#....#............#....#..........................#....#......##.....#...........##....
...#.#.#..##...........................#........................#...#.........##.....#...#.#..............#.#.....#.#...##..#......
..#.....#..#.................................#...#...........##.....#...........#........#.#..#..........##....#..#.#..............
....##..#.#...#..#...................#...#...#...............#.....#......................................#............#.......#...
............#..#...##....#.#..#............#...#.........##.......#........................#..............###.#...........#......#.
.......#..#......#...#.##..#...#....#.#.......................#.#.####....#...................#...#.........##.....##...........#..
.....#..#..............#....##..#....#.................#.#....#.....#...............#....#...................................#.....
..#.......#..#....##......#.....##........#...........#.#...........................#.#.....#...................###...........#..#.
.#....###.....#......#......#.........#......................#.#..........................##...#..#.............##...#...#.#.......
...#..##..#...................#.....#.#..#..#.........##....#..............#.#...........##.....#.......##..............#....#...#.
........#..............#...................................##........#....#...........................#...............#.......#.##.
.......#......#.............#..........#.................#.....##....##...##............##....................#.#.#........#....##.
...............#...........#..#.....#...............#......#.......#...#..#.##.............#.#..............##....#.........###....
....#.....#..##.................................#.....##........#...................................#....#...#.........#..#......#.
............#.........#....#...#.......................#.##.....#...................................#....#.....#..#.......#.....#..
...##..........#.#.....#..#........##....................#...............#..#..#........................#....#............#..#.....
...................#.....#......................#.#............#...........##......................#..#............#.....##........
...#.......##......#......#....#.............#...#............#...............#...................#.#.##........................#..
..#..#........##..#.#...#..#..#..##........#.#...............#........................#............#...#.......#.........#..#......
..................#..#..#.....#..................#.#.#..#...............#...#..###..#........................#.....#...#.......#...
............#.......##..........#..............#.....#.#...........#........##...##..##.#..........#.............#..#.#............
..........................#....#...........#.............#...........#....#......##...............#....#.....#....#.##.....#.#...#.
.#........#.............#........................#.#........##.#......#...........#.....##............###.....#.....#.....#........
......#..........#......#..#.......................#......................##.....#..#.......#........#....#.#..#..#.......#......#.
.....#........#..#.....#..#.............#.................#.........#..................#...#..........##....#.#.#..#.##........###.
...#......#.#.............#..............#.............#...#..#...##.#..#..........##......##..............##..#.#...#.........#...
......##..#......#.#....#.##.......#......#.#...................#.......#.....#..........................#........#...........#....
...#...............##.............#.............................#.......#.............#....#....................................#..
..#.#....#.#.....#.#...#..........#..#................#.....#........#.#...............#........#........................#....#....
....#....#.......#...............#..........##.#..................#...#...............#.#....#..............#......#.......#....##.
..#..................#......................#...#..##.....##.###......#.###...........#..#.............................##.......##.
..#..##...#..#....................#....#.#.#..#.#.#..#.#...##......#.#.#....#..........##.#..##.#..#..............##...............
.....#..............#.........................###.....##...............#.....#.....#..#......###.....#.............................
.......##....................................#.........#..#...#...##......#......#.#.#...#......##...#.......................#.#...
.#....#....#.......#............##.....................#.......#...#..#.......#...#..#...#.....................................#...
.#...#.......#..#...............##...........#....#.....##...#..........#.....#...#.........##....#..#.....................#..#.##.
......##..................#.##...#....#.................#...#.#........##.......#.....#........#.......#...............#..#....#...
.#........##.#..............#.....#...........#...#...#.#..#.#...........#....#.......#.....#...##.....................#.#...##..#.
......#..#..#.#........#...#......#........#.#.........##...........#............#..........#......................#..#..#.....#...
.#.......#..#.........#.#....#.#.##...........##.....#........#.#..........#......#..............#...#..#..............#..#........
.....#....#............#.#...........#..#.#..#............#...........#......#.#...........#...#................................#..
....##.................#.....##.....#.....................#..........#.#.#...#.....#...............#.....#.#.............#.........
......#...............#.#.#......#...##..........#...........##....#.............#.........#......#......#...................#.##..
.....#............#.......#.#.............#....#.......#..........#.##.#...#........##......#.....#.#...#..........................
....#....................#................#..#....#....##..#...#.....#........#..#.........#....#.......#......#.............#...#.
.#...#................#...#....................#.....#.....#........##........#....#.#...#...#..#..#.#...#..#......................
....#.........................#.....#..#..............##......#.#.....#............................#.#.....#.....#.................
......................#...##.........##........#..#.........#.....#...##...#..#.#...#..........................#.................#.
..#..#........#...#.......#....................#....#.......#.#.......#....#.......#.#.#.................#.....................##..
.#................#....#...............#.#..........#.......#...........#.##.#...#.....#..............#...#....#..#................
.#....................#................##.......#####......#..........#........#.............#.#.........#.#......#..#.............
..#.......#....#...#.#.................#.......#................#..#..#.....##..#.....................#..#....#....................
.........#.......##...#.#.........#.....#.........#.....#.#.#..##...#...#.......#....................#..#...#..#....#.#............
..............#.........#.....#.###....##...#.....#........##...#......#..........#...........#..##...#.....#.#........#...........
.........#.#..........#..........#.........#........##....#..##.........##......#..#..#........#.....#.....#.......................
.......#.#...........#........##.......#............#........#.#...............#..#.......#..#.........#.....#..#..#..#..#.........
.......#............#.#............#...........##..#.........#.....#......#..#...#.............................#......#..#.........
.................................................................S.................................................................
.......##....#...#......#...........#.........#.....#..#...........#.##....#.##..#........................................###......
.....................#...............#....#.........#..........#.....#..#.......#.......#...............#.#.....#..#...............
.........##..........#.....#.............#...#.........##..........##........##......#............#.#...##...#...#..#....#.#.......
............#..##........#..........#.##..............#................#..#..#..#...#.##........#......#.......#.......#.##........
.......................#.....#..#..#.....#....................#.............###.....#..#....#.......#...#.......#......#...........
.#........#.#.....#...#.#......#..#.#.#..#......##..........##..#.....#...............#............................................
.....................##..........#.....#.........#....#.........................#..........#...#.#.....#.....#...#.................
.##................#.......##...........#...#.#.........##..#.......#.......##................#........#...##.......#............#.
....................#.#.....#...#...#..#..##...##...#..................#......................#....##........................#.....
..#.............#...#.......#...#....#..#............#..#.#......................#.................#.#...#..#.....#.........#.#....
...................#.#......##.............#...............#..#.#......................#...............###..###..#..........#......
........#............#...#...#.#....#..#..........#..................#.........#.......#.........#..##......#..............#...#...
..##.............##.......##.#.#.#....#....#.#...#....................#..........#...#.......#..#..........#.#...............#.....
...#..............#.....#..............###......#........#..#.....#.......#...#..#.................#.#........#..........#.....#...
....#....#............#.#....#..........#............#.........##...............#.#................#...#...................#..#.#..
........#.#.........#....#.....#.....#.#..#.........................#..#.#.......##.#.........#......#..##....#........##.#........
......................#......#...........#......#......#.#................#...##.#....#......#.....#.................#...#.#...#...
.....#..#...................#...............###..........#.............#..#.#.....#....#....................................#.#.#..
.#.#.........#.........#......#.#...............#.....#..#......#.....#.#..#...##.........#...#....#............................#..
..#.#......#..............#.##.#..##....#.............#.....#....................###.....#...#..#.....................#.......#.#..
.#.#.........#.................#.#........#..##.........#..#.......#...##....#...#..........#.#...#..#.#...........#......#.###.##.
.........##..................#...#......##...##...#.............#..........#.....###......#...#...#.#.#.................##.#...#...
..........#...#..#...................#..#....##........#..........##............#......#........#.#.................#............#.
..#.....#......#..............#............................##..##.............##.......#.#..#.........#..........##...##.....#..#..
.............#..............................#.#........................#......##...............#..#................#.##...#........
...#..#.....#..##...#..................................#.....................#...#.....#.........#..........#........#...#.#.#.....
....#......#.##.....#..........#.....##.........#.#..#.........................................................#......#..##.#....#.
...................#............................#........#..#.................#.....#..#.......#..............##.#.....#...........
......#......#..#................#........#...#..#..............#......#....#.......#.....................#...........#....#...##..
..#..#.....#...#..#...............##.............#.#........#...........#.............##....#.#...........#.#.........###....##....
..#......#.#...#.........#...................................#........#...................................................#..#.....
.............#......#.......#........#.........#...........#....#..#...................##..............#.#...#.#...........#..#..#.
....#............#.....#.............#...#..........#.......#.....#......................#..#..........#.#....#...........#........
..........#.......##.....................##....##......#.............##.##...#..........#.#...................#..............##.#..
....#....#.........#.#..#..##.#....................#..............#.......#............................#.......#..........##....#..
..##.#.........#.......#...#..........................#.#.....#....#.....##......#....#...#...................................#....
..........#.....#..#....#...................#.....#.#...##..#.#................#.#...................##.........#........#....##...
.............#.........#.....#.............#.............##.............#.....#....#.................#...#.......#.#..#..#...#.#...
........##...#....#..........#......................#..#.#...........#........#..#.#..............#............#......#........#...
...#.#..#.#...............#..##..#..#.........#........#.#..........#.......#.........#........#.......#.......#..#....##.......#..
..#.......###.........#.....##.......#....................#..#......##.......#....##..........##........#.....................#....
.........#..#.....#.....#......#.....#........#...............#...#...#......#.................................#.#.#............##.
.....#.........#..#.........#..##......#...................##.....##.....#.....#............#.......#.....#..#..#..#..........#.#..
..........#.#.........#.......#..#...##......................................#..............#....##.#..#....#....#.##..............
...........###.#..........##...........................................#.........#.......#.....................#......##...........
...#........#.....#...................#.......................##.......#......#...........#..###.....#..#.......#........#.........
..##.....#..#..#.....#.................#.#.............#...##.........#................#.......................##.......#.....###..
..............##.#...#............#......#...........#..#.........#..#......#...........##....#....#.............##.#..............
.#..##.#.............#.....#.............................#.....#.........#.................##.#...#.....#.....#..#..#............#.
.#.#...#.##..........#..........#.......#.....................#..........##..............#.............#........#.#......#....#....
....#...................#.......#.....#................#.....#.....#.....#.............#.#.#..#.................#........#..#......
.............#...#.......#.#..#...##....#..#..#.........##.............#.............#.#.#.........#..................#............
............#..#...#..##....##..#.....#..........#.......##.#.......................................#.#..........................#.
..#................#...##.....#..........#...#...............#........................#....##.....#..............#...##.##.#..#.#..
....#.#...#.#.#.....#..#.##.#.##....#.#.##..#..................................##.......................##........#.#......##...#..
...#.....#.#..#..#.#.......#.......#..##.#.....#............#.#......##..............#.#...#.....#...#.#....#.........#.....#....#.
....###.#..............#.#.....##..........#......................#.#...............#.##.....#........#.#...#..#.#............#..#.
.......#.....#.#..............#..#..#........##.#.#...............#.....................#...#..#.##...........#.....#....#.#..#....
.......##..........#.#....#..#..#.......##.......#..................................#..#..........#............#....#......#.##....
.###.##.##........#.....#......#....#...................#.........#..................#...#..............#..#......#..........#..#..
.....##.........................#.....#.......#...#.....#.................##..#........#...................###.#......#..#....#....
..#........#........##......#..#.#..............#.........................#...###.#...#....##.#........#.#......#........#....##...
..........#.....#........#................##...........#...............###.....##...........#..#...#...#..##......#........#.#.....
.....#....#......................#.##.............#..#...#.#.............#............#..#..#.....#.......................#...###..
...................................................................................................................................

map_example.txt

...........
.....###.#.
.###.##..#.
..#.#...#..
....#.#....
.##..S####.
.##..#...#.
.......##..
.##.#.####.
.##..##.##.
...........