from queue import deque
from itertools import zip_longest

def transpose(l):
    return list(zip_longest(*l, fillvalue=None))

def rot_left(grid):
    return list(reversed(transpose(grid)))

def rot_right(grid):
    return list(transpose(reversed(grid)))


lines = [line[:-1] for line in open("22.input")]

board = [line for line in lines[:-2]]
max_width = max(len(line) for line in board)
board = [line + " " * max(0, max_width - len(line)) for line in board]

def show(grid):
    for line in grid:
        for c in line:
            print(c, end='')
        print("")

def walk(steps, board, pos):
    for _ in range(steps):
        x, y = pos
        new_x = pos[0] + 1
        if new_x >= len(board[y]) or board[y][new_x] == " ":
            new_x = [x for x, c in enumerate(board[y]) if c != " "][0]
        if board[y][new_x] == '#':
            break
        else:
            pos = (new_x, y)
    return (board, pos)

def rotate(rot, board, pos, facing):
    if rot == "R":
        board = rot_left(board)

        x, y = pos
        pos = (y, len(board)-x-1)
        facing = (facing + 1) % 4
    elif rot == "L":
        x, y = pos
        new_x = len(board) - y - 1
        board = rot_right(board)
        pos = (new_x, x)
        facing = (facing - 1) % 4
    return (board, pos, facing)

def part1(board, pw):

    pw = deque(pw)

    pos = ([x for x, c in enumerate(board[0]) if c == '.'][0], 0)
    facing = 0

    num = ""

    while pw:
        char = pw.popleft()
        if char == 'R' or char == 'L':
            steps = int(num)

            board, pos = walk(steps, board, pos)

            board, pos, facing = rotate(char, board, pos, facing)

            num = ""
        else:
            num += char


    board, pos = walk(int(num), board, pos)

    final_facing = facing

    while facing != 0:
        board, pos, facing = rotate("R", board, pos, facing)

    pos = (pos[0] + 1, pos[1] + 1)

    print(pos[1] * 1000 + pos[0] * 4 + final_facing)

part1(board, lines[-1])

grid_sz = 50

def empty_side():
    return [" " * grid_sz] * grid_sz

def extract_side(board, pos):
    return [line[pos[0] * grid_sz : (pos[0] + 1) * grid_sz] for line in board[pos[1] * grid_sz : (pos[1] + 1) * grid_sz]]



dir_to_sym = [">", "v", "<", "^"]

def build_cube(board):
    neighbours = {}
    sides = set()

    side = ([x for x, c in enumerate(board[0]) if c == '.'][0] // grid_sz, 0)
    q = deque()
    q.append(side)

    while q:
        side = q.popleft()
        x, y = side
        if side not in neighbours:
            neighbours[side] = [None, None, None, None]
        for i, (dx, dy) in enumerate([(1, 0), (0, 1), (-1, 0), (0, -1)]):
            new_x, new_y = x + dx, y + dy
            new = (new_x, new_y)
            if new_x < 0:
                continue
            if new_y < 0:
                continue
            try:
                if board[new_y * grid_sz][new_x * grid_sz] != " ":
                    if new not in neighbours:
                        neighbours[new] = [None, None, None, None]
                    neighbours[side][i] = (new, (i + 2) % 4)
                    neighbours[new][(i+2) % 4] = (side, i % 4)
                    if (new_x, new_y) not in sides:
                        sides.add((new_x, new_y))
                        q.append((new_x, new_y))
            except IndexError:
                continue

    for _ in range(4):
        for pos, nbrs in neighbours.items():
            # Fold corners
            for i in range(4):
                left = nbrs[i]
                right = nbrs[(i+1) % 4]
                if left is not None and right is not None:
                    if neighbours[left[0]][(i+1)%4] is not None:
                        continue
                    if left[0] in [a[0] for a in neighbours[right[0]] if a is not None]:
                        continue
                    rel_left = (i - left[1]) % 4
                    rel_right = ((i + 1) - right[1]) % 4
                    rel = (rel_left - rel_right) % 4
                    print("Looking at", pos)
                    print("Relative direction:", rel_left, rel_right, rel)
                    if rel == 0:
                        print(left[0], "has", right[0], "to the", dir_to_sym[(i + 1)%4])
                        print(right[0], "has", left[0], "to the", dir_to_sym[(i + 0)%4])
                        print("-" * 20)
                        neighbours[left[0]][(i+1)%4] = (right[0], (i+0)%4)
                        neighbours[right[0]][(i+0)%4] = (left[0], (i+1)%4)
                    elif rel == 1:
                        print(left[0], "has", right[0], "to the", dir_to_sym[(i + 1)%4])
                        print(right[0], "has", left[0], "to the", dir_to_sym[(i + 1)%4])
                        print("-" * 20)
                        neighbours[left[0]][(i+1)%4] = (right[0], (i+1)%4)
                        neighbours[right[0]][(i+1)%4] = (left[0], (i+1)%4)
                    else:
                        raise ValueError("Weird grid?")

    for pair in neighbours.items():
        print(pair)
    # Finish the fold :DDD
    for i in range(2):
        for start in [(pos, nbrs) for (pos, nbrs) in neighbours.items() if None in nbrs]:
            print("Start:", start)
            pos, nbrs = start
            for direction in [(2 + i) % 4 for i, n in enumerate(nbrs) if n is None]:
                start_dir = direction
                print("Direction:", direction)
                for i in range(3):
                    if neighbours[pos][direction] is None:
                        break
                    pos, new_dir = neighbours[pos][direction]
                    direction = (2 + new_dir) % 4
                    print("pos:", pos, "Direction:", direction)
                else:
                    neighbours[start[0]][(2 + start_dir) % 4] = (pos, direction)
                    neighbours[pos][direction] = (start[0], (2 + start_dir) % 4)
    for pair in neighbours.items():
        print(pair)

    return neighbours


def part2(board, pw):
    #neighbours = build_cube(board)
    #print(neighbours)
    neighbours = {
            (1, 0): [((2, 0), 2), ((1, 1), 3), ((0, 2), 2), ((0, 3), 2)],
            (2, 0): [((1, 2), 0), ((1, 1), 0), ((1, 0), 0), ((0, 3), 1)],
            (1, 1): [((2, 0), 1), ((1, 2), 3), ((0, 2), 3), ((1, 0), 1)],
            (1, 2): [((2, 0), 0), ((0, 3), 0), ((0, 2), 0), ((1, 1), 1)],
            (0, 2): [((1, 2), 2), ((0, 3), 3), ((1, 0), 2), ((1, 1), 2)],
            (0, 3): [((1, 2), 1), ((2, 0), 3), ((1, 0), 3), ((0, 2), 1)]}
    if False:
        edges = set()
        for pos, nbrs in neighbours.items():
            for i, (n, d) in enumerate(nbrs):
                if (n, d) in edges:
                    print("Duplicate:", (n, d))
                    break
                edges.add((n, d))
                print(pos, "has", n, "to the", dir_to_sym[i])

        for side in neighbours.keys():
            for direction in range(4):
                current = side
                #print("Start:", current, "Direction:", direction)
                for i in range(4):
                    side, new_dir = neighbours[side][direction]
                    direction = (2 + new_dir) % 4
                    #print("side:", side, "Direction:", direction)
                print(side, current)
                assert current == side


    side = ([x for x, c in enumerate(board[0]) if c == '.'][0] // grid_sz, 0)
    grid = extract_side(board, side)
    pos = ([x for x, c in enumerate(grid[0]) if c == '.'][0], 0)
    facing = 0


    num = ""

    path = set()

    pw = deque(pw)
    pw.append('S')

    while pw:
        char = pw.popleft()
        if char == 'R' or char == 'L' or char == 'S':
            rot = char
            steps = int(num)

            #print("grid:", side, "pos:", pos, "face:", dir_to_sym[facing])
            #show(grid)

            for _ in range(steps):
                x, y = pos
                new_x = pos[0] + 1
                new_pos = (new_x, pos[1])
                new_grid = grid
                new_side = side
                new_facing = facing
                if new_x >= grid_sz:
                    # Find next side
                    new_side, entry_dir = neighbours[side][facing]
                    rel_dir = entry_dir - facing
                    new_facing = (entry_dir + 2) % 4
                    new_grid = extract_side(board, new_side)
                    for _ in range(new_facing):
                        new_grid = rot_left(new_grid)
                    new_x = 0
                    new_pos = (0, y)

                if new_grid[y][new_x] == '#':
                    break
                else:
                    side = new_side
                    pos = new_pos
                    grid = new_grid
                    facing = new_facing

            #print("grid:", side, "pos:", pos, "face:", dir_to_sym[facing])
            #show(grid)

            grid, pos, facing = rotate(rot, grid, pos, facing)

            num = ""
        else:
            num += char

    final_facing = facing

    while facing != 0:
        grid, pos, facing = rotate("R", grid, pos, facing)

    pos = (side[0] * grid_sz + pos[0] + 1, side[1] * grid_sz + pos[1] + 1)

    print(pos[1] * 1000 + pos[0] * 4 + final_facing)

part2(board, lines[-1])