import queue
#green marble is a 1 bit
#5 bits empty coordinate, 25 bits bitmap of marbles
#                12   |bitmap
start_state =  0b011001000011000110001110011110
target_state = 0b011000111100111000110001100001
target_board = 0b0111100111000110001100001

def decompose_state_int(state):
    empty = (state >> 25)%25
    board = (state & 0x1ffffff)
    return (empty, board)

def compose_state_int(empty, board):
    return (empty << 25) | board

def decompose_pos_int(empty):
    return (4-empty//5,4-empty%5)

def compose_pos_int(x,y):
    return (4-y)*5+(4-x)

def metric(state):
    empty, board = decompose_state_int(state)
    empty_adjust = 1 if empty!=12 else 0
    board_score = (board ^ target_board).bit_count() #this wrongly prefers blue over green, but should be irrelevant since the problem is symmetric
    return board_score+empty_adjust

def get_possible_next_states(state):
    offsets = [(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1),(-2,1),(-1,2)]
    empty, board = decompose_state_int(state)
    empty_pos = decompose_pos_int(empty)
    results = []
    for offset in offsets:
        ny = empty_pos[0]+offset[0]
        nx = empty_pos[1]+offset[1]
        if nx<0 or nx>4 or ny<0 or ny>4:
            continue
        new_empty = compose_pos_int(nx,ny)
        new_mask = 1<<new_empty
        target_bit = 1 if (new_mask&board) != 0 else 0
        new_board = (board & ~new_mask) | target_bit<<empty #unset bit at new coordinate, set that bit in old empty coordinate
        results.append(compose_state_int(new_empty,new_board))
    return results

def debug_print(state):
    empty, board = decompose_state_int(state)
    y,x = decompose_pos_int(empty)
    print(x,y,hex(board))
    for py in range(5):
        row_num = (board >> (20-5*py))&0x1f
        row = "".join(["X" if py==y and px==x else str((row_num>>(4-px)&1)) for px in range(5)])
        print(row)

def search():
    todo = queue.PriorityQueue()
    todo.put((metric(start_state),start_state))
    done = {}
    parent = {start_state:None}

    while not todo.empty():
        val, curr = todo.get()
        real_dist = val - metric(curr) #remove metric from final value
        if curr == target_state:
            print("found")
            s=curr
            counter = 0
            while s:
                debug_print(s)
                print(counter)
                counter += 1
                s=parent[s]
            return counter
        done[curr] = real_dist
        next_states = get_possible_next_states(curr)
        for state in next_states:
            if state in done:
                continue
            estimate = real_dist+metric(state)+1
            #print(metric(state))
            #debug_print(state)
            todo.put((estimate, state)) #append next state if we haven't seen it before
            done[state] = estimate #add to done dictionary to avoid repeatedly adding states we've already reached
            parent[state] = curr
    return -1



print(metric(start_state))
print(search())