def parse_input(file):
    with open(file, 'r') as f:
        lines = f.readlines()
    
    # Separate the map and the movement sequence
    map_lines = []
    move_sequence = ""
    for line in lines:
        if line.startswith('#'):
            map_lines.append(line.strip())
        else:
            move_sequence += line.strip()
    
    return map_lines, move_sequence

def find_robot_and_boxes(map_lines):
    robot_pos = None
    boxes = set()
    for r, line in enumerate(map_lines):
        for c, char in enumerate(line):
            if char == '@':
                robot_pos = (r, c)
            elif char == 'O':
                boxes.add((r, c))
    return robot_pos, boxes

def move_robot_and_boxes(map_lines, robot_pos, boxes, move_sequence):
    directions = {'<': (0, -1), '>': (0, 1), '^': (-1, 0), 'v': (1, 0)}
    max_r = len(map_lines)
    max_c = len(map_lines[0])
    
    for move in move_sequence:
        dr, dc = directions[move]
        new_robot_pos = (robot_pos[0] + dr, robot_pos[1] + dc)
        
        if map_lines[new_robot_pos[0]][new_robot_pos[1]] == '#':
            continue  # Robot can't move into a wall
        
        if new_robot_pos in boxes:
            new_box_pos = (new_robot_pos[0] + dr, new_robot_pos[1] + dc)
            if map_lines[new_box_pos[0]][new_box_pos[1]] == '#' or new_box_pos in boxes:
                continue  # Box can't be pushed into a wall or another box
            boxes.remove(new_robot_pos)
            boxes.add(new_box_pos)
        
        robot_pos = new_robot_pos
    
    return robot_pos, boxes

def calculate_gps_sum(boxes, max_r, max_c):
    gps_sum = 0
    for r, c in boxes:
        gps_sum += 100 * r + c
    return gps_sum

def part_one(file):
    map_lines, move_sequence = parse_input(file)
    robot_pos, boxes = find_robot_and_boxes(map_lines)
    robot_pos, boxes = move_robot_and_boxes(map_lines, robot_pos, boxes, move_sequence)
    return calculate_gps_sum(boxes, len(map_lines), len(map_lines[0]))

def scale_map(map_lines):
    scaled_map = []
    for line in map_lines:
        scaled_line = ""
        for char in line:
            if char == '#':
                scaled_line += "##"
            elif char == 'O':
                scaled_line += "[]"
            elif char == '.':
                scaled_line += ".."
            elif char == '@':
                scaled_line += "@."
        scaled_map.append(scaled_line)
    return scaled_map

def find_robot_and_boxes_scaled(map_lines):
    robot_pos = None
    boxes = set()
    for r, line in enumerate(map_lines):
        for c in range(0, len(line), 2):
            char = line[c:c+2]
            if char == '@.':
                robot_pos = (r, c)
            elif char == '[]':
                boxes.add((r, c))
    return robot_pos, boxes

def move_robot_and_boxes_scaled(map_lines, robot_pos, boxes, move_sequence):
    directions = {'<': (0, -2), '>': (0, 2), '^': (-1, 0), 'v': (1, 0)}
    max_r = len(map_lines)
    max_c = len(map_lines[0])
    
    for move in move_sequence:
        dr, dc = directions[move]
        new_robot_pos = (robot_pos[0] + dr, robot_pos[1] + dc)
        
        if map_lines[new_robot_pos[0]][new_robot_pos[1]] == '#' or map_lines[new_robot_pos[0]][new_robot_pos[1]] == '#':
            continue  # Robot can't move into a wall
        
        if new_robot_pos in boxes:
            new_box_pos = (new_robot_pos[0] + dr, new_robot_pos[1] + dc)
            if map_lines[new_box_pos[0]][new_box_pos[1]] == '#' or new_box_pos in boxes:
                continue  # Box can't be pushed into a wall or another box
            boxes.remove(new_robot_pos)
            boxes.add(new_box_pos)
        
        robot_pos = new_robot_pos
    
    return robot_pos, boxes

def part_two(file):
    map_lines, move_sequence = parse_input(file)
    scaled_map_lines = scale_map(map_lines)
    robot_pos, boxes = find_robot_and_boxes_scaled(scaled_map_lines)
    robot_pos, boxes = move_robot_and_boxes_scaled(scaled_map_lines, robot_pos, boxes, move_sequence)
    return calculate_gps_sum(boxes, len(scaled_map_lines), len(scaled_map_lines[0]))

file = "input.txt"
result1 = part_one(file)
print(result1)

result2 = part_two(file)
print(result2)