# Input: Map of "#", ".", "^", "v", "<", ">"
# Output: Starting in "." in top row,
#         with each arrow moving one step per minute in its direction
#           (if it hits # then it wraps around),
#         and you simultaneously moving orthogonally or waiting,
#         how many minutes does it take to reach "." in bottom row
#           without overlapping any arrows, then return to start,
#           then return to end?

# By inspection, there are no ^ or v arrows in starting or ending columns,
# thus arrow pattern repeats every lcm(r, c) minutes
#   (r = # rows between first/last, c = # columns between first/last)
# so we can compute and store each of those states

import math
from functools import cache

initial_grid = []

input_data = open(r"c:\users\edward\desktop\personal\aoc2022\24_input.txt")
for input_line in input_data.read().splitlines():
    input_line = input_line.replace("\n", "")
    initial_grid.append(input_line)

number_interior_rows = len(initial_grid) - 2
number_interior_columns = len(initial_grid[0]) - 2
number_minutes = math.lcm(number_interior_rows, number_interior_columns)

initial_row = initial_grid[0]
initial_column = -1
for c in range(0, len(initial_row)):
    if initial_row[c] == ".":
        initial_column = c
        break

final_row = initial_grid[len(initial_grid) - 1]
final_column = -1
for c in range(0, len(final_row)):
    if final_row[c] == ".":
        final_column = c
        break

grids = []
for minute in range(0, number_minutes):
    blocked_positions = []
    for r in range(1, number_interior_rows + 1):
        for c in range(1, number_interior_columns + 1):
            character = initial_grid[r][c]
            if character == ".":
                continue
            nr, nc = r, c
            if character == "^":
                nr -= minute
                while nr < 1:
                    nr += number_interior_rows
            if character == "v":
                nr += minute
                while nr > number_interior_rows:
                    nr -= number_interior_rows
            if character == "<":
                nc -= minute
                while nc < 1:
                    nc += number_interior_columns
            if character == ">":
                nc += minute
                while nc > number_interior_columns:
                    nc -= number_interior_columns
            if not ([nr, nc] in blocked_positions):
                blocked_positions.append([nr, nc])
    grids.append(blocked_positions)

# Backtrack from each variation of final position

final_positions = []
for minute in range(0, number_minutes):
    final_positions.append([number_interior_rows + 1, final_column, minute])

positions = []
positions.append(final_positions)

# Is (r, c) at minute-state (m) a valid position to be?
@cache
def valid_position(r, c, m):
    # Bottom row and not at end
    if r > number_interior_rows and c != final_column:
        return False
    # Top row and not at start
    if r < 1 and c != initial_column:
        return False
    # Too far left or right
    if c < 1 or c > number_interior_columns:
        return False
    # Position occupied by blizzard
    if [r, c] in grids[m]:
        return False
    # Otherwise OK
    return True

# Minimum possible steps from current position to goal
#   (Manhattan distance, if any such path avoids a collision at each step)
@cache
def minimum_steps(r, c, reached_end_once, returned_to_start_once):
    if returned_to_start_once:
        return (number_interior_rows + 1 - r) + abs(c - final_column)
    if reached_end_once:
        return r + abs(c - initial_column) + (number_interior_rows + 1) + abs(initial_column - final_column)
    return (number_interior_rows + 1 - r) + abs(c - final_column) + (2 * (number_interior_rows + 1) + abs(initial_column - final_column))

# Perform best-first search
# Begin at the beginning
# Key of paths = minutes elapsed + minimum number of minutes still needed

paths = {}
initial_state = [0, initial_column, 0, False, False] # row, column, minutes elapsed, reached end once, returned to start once
initial_minimum_steps = minimum_steps(0, initial_column, False, False)
paths[initial_minimum_steps] = [initial_state]

minimum_length = -1
while minimum_length == -1:
    key_of_paths_to_extend = min(paths.keys())
    paths_to_extend = paths[key_of_paths_to_extend]
    del paths[key_of_paths_to_extend]
    for path in paths_to_extend:
        r, c, m, reached_end_once, returned_to_start_once = path[0], path[1], path[2], path[3], path[4]

        if r == number_interior_rows + 1 and c == final_column and returned_to_start_once:
            if minimum_length == -1 or minimum_length > m:
                minimum_length = m
            continue

        nm = (m + 1) % number_minutes

        # Consider going south
        nr, nc = r + 1, c
        if valid_position(nr, nc, nm):
            new_path = [nr, nc, m + 1, reached_end_once, returned_to_start_once]
            if (not reached_end_once) and nr == number_interior_rows + 1 and c == final_column:
                new_path[3] = True
            new_minimum_steps = m + minimum_steps(nr, nc, reached_end_once, returned_to_start_once)
            if not (new_minimum_steps in paths.keys()):
                paths[new_minimum_steps] = [new_path]
            else:
                if not (new_path in paths[new_minimum_steps]):
                    paths[new_minimum_steps].append(new_path)

        # Consider going east
        nr, nc = r, c + 1
        if valid_position(nr, nc, nm):
            new_path = [nr, nc, m + 1, reached_end_once, returned_to_start_once]
            new_minimum_steps = m + minimum_steps(nr, nc, reached_end_once, returned_to_start_once)
            if not (new_minimum_steps in paths.keys()):
                paths[new_minimum_steps] = [new_path]
            else:
                if not (new_path in paths[new_minimum_steps]):
                    paths[new_minimum_steps].append(new_path)

        # Consider going west
        nr, nc = r, c - 1
        if valid_position(nr, nc, nm):
            new_path = [nr, nc, m + 1, reached_end_once, returned_to_start_once]
            new_minimum_steps = m + minimum_steps(nr, nc, reached_end_once, returned_to_start_once)
            if not (new_minimum_steps in paths.keys()):
                paths[new_minimum_steps] = [new_path]
            else:
                if not (new_path in paths[new_minimum_steps]):
                    paths[new_minimum_steps].append(new_path)

        # Consider going north
        nr, nc = r - 1, c
        if valid_position(nr, nc, nm):
            new_path = [nr, nc, m + 1, reached_end_once, returned_to_start_once]
            if reached_end_once and (not returned_to_start_once) and nr == 0 and c == initial_column:
                new_path[4] = True
            new_minimum_steps = m + minimum_steps(nr, nc, reached_end_once, returned_to_start_once)
            if not (new_minimum_steps in paths.keys()):
                paths[new_minimum_steps] = [new_path]
            else:
                if not (new_path in paths[new_minimum_steps]):
                    paths[new_minimum_steps].append(new_path)

        # Consider standing still
        nr, nc = r, c
        if valid_position(nr, nc, nm):
            new_path = [nr, nc, m + 1, reached_end_once, returned_to_start_once]
            new_minimum_steps = m + minimum_steps(nr, nc, reached_end_once, returned_to_start_once)
            if not (new_minimum_steps in paths.keys()):
                paths[new_minimum_steps] = [new_path]
            else:
                if not (new_path in paths[new_minimum_steps]):
                    paths[new_minimum_steps].append(new_path)

print (minimum_length)