Untitled
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