Untitled

 avatar
unknown
plain_text
5 months ago
5.5 kB
8
Indexable
def read_map(file_path): #gets map
    with open(file_path, "r") as file:
        raw_lines = file.readlines()
    map_grid = []
    for line in raw_lines:
        map_grid.append(list(line.strip()))
    return map_grid


def simulate_guard_with_tracking(grid):
    #               down    right    up      left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # Find guard starting position and direction
    for row in range(len(grid)): #search each row
        for col in range(len(grid[0])): #search each col
            if grid[row][col] in "^>v<": #look for guard
                guard_position = (row, col) #set coords for start position
                current_direction = "^>v<".index(grid[row][col]) #set direction
                break

    visited_positions = set([guard_position]) # set because we want unique elements unlike tuple.
    rows, cols = len(grid), len(grid[0]) #get rows/cols

    while True:
        # Calculate next position
        row, col = guard_position #current position
        dy, dx = directions[current_direction] #direction
        next_position = (row + dy, col + dx) #move guard based on direction

        # Stop if the guard leaves the grid
        if not (0 <= next_position[0] < rows and 0 <= next_position[1] < cols):
            break

        # Check if the next position is blocked.
        if grid[next_position[0]][next_position[1]] == "#": #check for obs
            current_direction = (current_direction + 1) % 4  # Turn right
        else:
            guard_position = next_position  # Move forward
            visited_positions.add(guard_position) #add new position to set

    return visited_positions #return all unique visited positions


def causes_loop_with_obstruction(grid, obstruction_pos, start_pos, start_direction):
    """Simulates the guard"s movement with a new obstruction and checks if it causes a loop."""
    #               down     right  up       left
    directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    direction_now = start_direction #guard direction
    guard_position = start_pos #guard position

    visited_with_direction = set() #generate a set for direction and position
    visited_with_direction.add((guard_position, direction_now)) #add start direction and position

    rows, cols = len(grid), len(grid[0]) #set map

    # No need to check if position already obstructed
    if(grid[obstruction_pos[0]][obstruction_pos[1]] == "#"):
        return False 

    # Place new obstruction
    grid[obstruction_pos[0]][obstruction_pos[1]] = "#" #add a new obstruction

    while True:
        y, x = guard_position #guard positiion
        dy, dx = directions[direction_now] #guard direction
        next_position = (y + dy, x + dx) #move guard to new position

        # Check boundry
        if not (0 <= next_position[0] < rows and 0 <= next_position[1] < cols):
            grid[obstruction_pos[0]][obstruction_pos[1]] = "."  # Remove obstruction for next iteration
            return False # No loop

        # Check if the next position is blocked
        if grid[next_position[0]][next_position[1]] == "#":
            direction_now = (direction_now + 1) % 4  # Turn right
        else:
            guard_position = next_position  # Move forward

        # Check if the guard revisits a position with the same direction
        state = (guard_position, direction_now) #set guard position and direction
        if state in visited_with_direction: #check if that matches one we've visited already
            grid[obstruction_pos[0]][obstruction_pos[1]] = "."  # Remove obstruction, loop found.
            return True #found 1 loop position

        visited_with_direction.add(state) #add to set if not already in


def find_all_loop_positions(grid, visited_positions):
    """Finds all positions where adding an obstruction causes the guard to get stuck in a loop."""


    # Find guard"s starting position and direction
    guard_position = None
    guard_direction = None
    for y, row in enumerate(grid): #make tuple loopable
        for x, cell in enumerate(row): #same for row
            # Debug: Check each cell
            if cell in "^>v<": #loop to find starting direction
                guard_position = (y, x) #set starting position
                guard_direction = "^>v<".index(cell)  # Map direction to index
                break
        if guard_position:
            break #pnce guard found stop loop

   
    loop_positions = [] #list of position

    # Test only visited positions
    for y, x in visited_positions: #for each visited positions coords
        # Skip the guard"s starting position
        if (y, x) == guard_position: #ignore starting position and continue
            continue

        # Check if placing an obstruction at x y causes a loop
        #pass in the map, the current position, the guard position and guard direction
        if causes_loop_with_obstruction(grid, (y, x), guard_position, guard_direction):
            loop_positions.append((y, x)) #add the return to loop positions

    return loop_positions


file_path = "Day 6\day6input.txt" #input file
grid = read_map(file_path) #generate map
visited_positions = simulate_guard_with_tracking(grid) #track guard, storing location and direction
loop_positions = find_all_loop_positions(grid, visited_positions) #find loop
print(len(loop_positions)) #print total positions for obstructions that causes loop
Editor is loading...
Leave a Comment