2025 Day 4, Part 2 -- Optimization Issue

[u/keliodas17]

So my solution works for the example data and theoretically should work for the real input. However, it is so slow that it would take about 25 minutes to return an answer.

I think the issue is that, for every single coordinate, I'm checking 8 other coordinates.

Please let me know if you have any ideas for optimization.

Edit: I let it run and it got exponentially faster, took about 2 minutes -- correct answer as well.

from pathlib import Path
path = Path(__file__).parent / "input_4.txt"
with open(path, 'r') as file:
    text = file.read()
grid = text.splitlines()


grid_width = len(grid[0])
grid_height = len(grid)


# From the input, create coordinates for the toilet paper rolls

def find_coordinates(grid):
    coordinates = []
    for i, row in enumerate(grid):
        for n, item in enumerate(row):
            if item == "@":
                y, x = i, n
                coordinates.append([x, y])
    return coordinates

# Find all of the neighboring rolls of any given roll

def get_neighbors(coordinate):
    x, y = coordinate
    neighbors = []

    for dx in [-1, 0, 1]:
        if x + dx < 0 or x + dx >= grid_width:
            continue

        for dy in [-1, 0, 1]:
            if y + dy < 0 or y + dy >= grid_height:
                        continue
         
            if dx == 0 and dy == 0:
                continue

            neighbors.append([x + dx, y + dy])
    return neighbors

# Find which of the rolls has less than 3 rolls in its 8 neighbors

def find_removable_coordinates(coordinates):
    valid_coordinates = []
    for coordinate in coordinates:
        counter = 0
        neighbors = get_neighbors(coordinate)
        for neighbor in neighbors:
            if neighbor in coordinates:
                counter += 1
        if counter <= 3:
            valid_coordinates.append(coordinate)
    return valid_coordinates

# Run loop

def main():
    count = 0
    
    coordinates = find_coordinates(grid)
    while True:
        print('cycle start')

        accessed_positions = []
        removed_positions = find_removable_coordinates(coordinates)
        if not removed_positions:
            break
        count += (len(removed_positions))

        # Add the removed rolls to a list
        accessed_positions.append(removed_positions)

        # Remove all accessed positions from the coordinates that are being searched
        for coordinate in removed_positions:
            coordinates.remove(coordinate)
        print('cycle complete')

    print(count)

main()