def parse_input(filename):
    with open(filename, 'r') as f:
        lines = f.read().strip().split('\n')
    
    # Find empty line that separates map and moves
    split_idx = lines.index('')
    map_lines = lines[:split_idx]
    moves = ''.join(lines[split_idx+1:]).strip()
    
    return map_lines, moves

def find_robot_and_boxes(grid):
    robot = None
    boxes = set()
    for y in range(len(grid)):
        for x in range(len(grid[y])):
            if grid[y][x] == '@':
                robot = (x, y)
            elif grid[y][x] == 'O':
                boxes.add((x, y))
    return robot, boxes

def find_robot_and_boxes_wide(grid):
    robot = None
    boxes = set()
    for y in range(len(grid)):
        for x in range(len(grid[y])-1):
            if grid[y][x:x+2] == '[]':
                boxes.add((x, y))
            elif grid[y][x] == '@':
                robot = (x, y)
    return robot, boxes

def move_direction(direction):
    if direction == '^': return (0, -1)
    if direction == 'v': return (0, 1)
    if direction == '<': return (-1, 0)
    if direction == '>': return (1, 0)
    return (0, 0)

def is_wall(grid, x, y):
    return grid[y][x] == '#'

def simulate_move(grid, robot, boxes, dx, dy):
    new_x, new_y = robot[0] + dx, robot[1] + dy
    
    # Check if moving into wall
    if is_wall(grid, new_x, new_y):
        return robot, boxes
    
    # Check if moving into box
    if (new_x, new_y) in boxes:
        box_new_x, box_new_y = new_x + dx, new_y + dy
        # Check if box would move into wall or another box
        if is_wall(grid, box_new_x, box_new_y) or (box_new_x, box_new_y) in boxes:
            return robot, boxes
        # Move box
        boxes.remove((new_x, new_y))
        boxes.add((box_new_x, box_new_y))
    
    return (new_x, new_y), boxes

def simulate_move_wide(grid, robot, boxes, dx, dy):
    new_x, new_y = robot[0] + dx, robot[1] + dy
    
    # Check if moving into wall
    if is_wall(grid, new_x, new_y):
        return robot, boxes
    
    # Check if moving into box
    box_pos = None
    for box in boxes:
        if new_x in (box[0], box[0] + 1) and new_y == box[1]:
            box_pos = box
            break
    
    if box_pos:
        box_new_x, box_new_y = box_pos[0] + dx, box_pos[1] + dy
        # Check if box would move into wall or another box
        if (is_wall(grid, box_new_x, box_new_y) or 
            is_wall(grid, box_new_x + 1, box_new_y) or
            any(b[0] in (box_new_x, box_new_x + 1) and b[1] == box_new_y for b in boxes if b != box_pos)):
            return robot, boxes
        # Move box
        boxes.remove(box_pos)
        boxes.add((box_new_x, box_new_y))
    
    return (new_x, new_y), boxes

def calculate_gps_sum(boxes, height):
    return sum((box[1] + 1) * 100 + (box[0] + 1) for box in boxes)

def calculate_gps_sum_wide(boxes, height):
    return sum((box[1] + 1) * 100 + (box[0] + 1) for box in boxes)

def scale_map(map_lines):
    scaled = []
    for line in map_lines:
        new_line = ''
        for c in line:
            if c == '#':
                new_line += '##'
            elif c == 'O':
                new_line += '[]'
            elif c == '.':
                new_line += '..'
            elif c == '@':
                new_line += '@.'
        scaled.append(new_line)
    return scaled

def solve_part1(map_lines, moves):
    grid = map_lines
    robot, boxes = find_robot_and_boxes(grid)
    
    for move in moves:
        dx, dy = move_direction(move)
        robot, boxes = simulate_move(grid, robot, boxes, dx, dy)
    
    return str(calculate_gps_sum(boxes, len(grid)))

def solve_part2(map_lines, moves):
    grid = scale_map(map_lines)
    robot, boxes = find_robot_and_boxes_wide(grid)
    
    for move in moves:
        dx, dy = move_direction(move)
        robot, boxes = simulate_move_wide(grid, robot, boxes, dx, dy)
    
    return str(calculate_gps_sum_wide(boxes, len(grid)))

def main():
    map_lines, moves = parse_input('./input.txt')
    
    # Part 1
    print(solve_part1(map_lines, moves))
    
    # Part 2
    print(solve_part2(map_lines, moves))

if __name__ == "__main__":
    main()