import time
from collections import deque

def get_possible_moves(board_tuple, empty_r, empty_c):
    possible_moves = []
    for dr, dc in [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]:
        r, c = empty_r + dr, empty_c + dc
        if 0 <= r < 5 and 0 <= c < 5:
            board = [list(row) for row in board_tuple]
            if board[r][c] != 'E':
                next_board = [list(row) for row in board]
                next_board[empty_r][empty_c], next_board[r][c] = next_board[r][c], next_board[empty_r][empty_c]
                possible_moves.append((tuple("".join(row) for row in next_board), r, c, (r, c)))
    return possible_moves


def solve():
    initial_board_tuple = (
        "GBBBB",
        "GGBBB",
        "GGEBB",
        "GGGBB",
        "GGGGB"
    )

    target_board_tuple = (
       "BGGGG",
       "GBBGG",
       "GGEEG",
       "GGGBB",
       "GGGGB"
    )

    def check_target(current_board_tuple):
        return current_board_tuple == target_board_tuple

    max_estimated_states = 25 * (2**25)
    queue = deque([(initial_board_tuple, 0, 2, 2, [])])  # (board, moves, empty_r, empty_c, path)
    visited = {initial_board_tuple}
    best_moves_found = float('inf')
    nodes_checked = 0
    update_frequency = 100
    start_time = time.time()

    while queue:
        current_board_tuple, moves, empty_r, empty_c, path = queue.popleft()
        nodes_checked += 1

        if check_target(current_board_tuple):
            if moves < best_moves_found:
                best_moves_found = moves
                print(f"Found a solution in {moves} moves", end='\r')
                print("\nSolution Path:")
                for i, (board, move_r, move_c) in enumerate(path):
                    print_board(board, move_r, move_c, i)

            continue

        for next_board_tuple, next_empty_r, next_empty_c, move_pos in get_possible_moves(current_board_tuple, empty_r, empty_c):

             if next_board_tuple not in visited:
                visited.add(next_board_tuple)
                queue.append((next_board_tuple, moves + 1, next_empty_r, next_empty_c, path + [(current_board_tuple, move_pos[0], move_pos[1])]))

        if nodes_checked % update_frequency == 0:
            percentage = min(100, (nodes_checked / max_estimated_states) * 100)
            bar = "[" + "=" * int(percentage / 5) + " " * (20 - int(percentage / 5)) + "]"
            elapsed_time = time.time() - start_time
            if nodes_checked > 0:
                nodes_per_sec = nodes_checked / elapsed_time
                remaining_nodes = max_estimated_states - nodes_checked
                if nodes_per_sec > 0:
                  eta_sec = remaining_nodes / nodes_per_sec
                  eta_min = int(eta_sec / 60)
                  eta_sec = int(eta_sec % 60)
                  eta_str = f"{eta_min}m {eta_sec}s"
                else:
                   eta_str = "N/A"

            else:
                eta_str = "N/A"

            print(f"Progress: {bar} {percentage:.2f}%, Visited: {nodes_checked}, Best: {best_moves_found if best_moves_found != float('inf') else 'N/A'}, Depth: {moves}, ETA: {eta_str}", end="\r")

    return best_moves_found if best_moves_found != float('inf') else -1
def print_board(board_tuple, moved_r, moved_c, step):
    """Prints the board with a colored move indication."""
    colors = {
        'G': '\033[92mG\033[0m',   # Green
        'B': '\033[94mB\033[0m',    # Blue
        'E': 'E'   # Empty
    }
    print(f"Step {step}:")
    for r, row in enumerate(board_tuple):
      colored_row = ""
      for c, cell in enumerate(row):
          if r == moved_r and c == moved_c:
                colored_row += f'\033[93m{colors.get(cell, cell)}\033[0m'  #Yellow for the moved piece
          else:
            colored_row += colors.get(cell, cell)
      print(colored_row)


result = solve()
print(f"The smallest number of moves required is: {result}")