# -*- coding: utf-8 -*-
"""
Les  états  du   système  sont  représentés  par   une  liste  d'entiers
relatifs.  Les  4  premiers  éléments représentent  la  position  des  4
charriots (de  gauche à droite,  pui de  haut en bas).   Ensuite, chaque
élément représente une  caisse et indique sa position dans  la chaîne ou
alors  un nombre  négatif dont  la  valeur absolue  indique l'indice  du
charriot (de 1 à 4).

Voici un exemple (le charriot 1 est en train de déplacer la caisse 3):

 3  *
14-25    donne la liste (1,4,1,3, 0,3,-1,1,4) ou le texte "BEBDad1be"
 * *

"""

from collections import deque
from heapq import *


class Fringe:
    def __init__(self):
        self.arr = []
        self.size = 0

    def add(self, value, item):
        heappush(self.arr, (value, item))
        self.size += 1

    def pop(self):
        value, item = heappop(self.arr)
        self.size -= 1
        return item

    def empty(self):
        if self.size > 0:
            return False
        return True

    def length(self):
        return self.size


def find(config, heuristic):
    end = len(config) - 1
    actions = {
        ">": "#>-<",
        "<": "#<->",
        "#": "><-#",
        "-": "><#-"
    }
    fringe = Fringe()
    item = [("----", [0, end, 0, end] + config, 0)]
    fringe.add(0, item)
    cache = set()
    count = 0
    while not fringe.empty():
        count += 1
        item = fringe.pop()
        code, state, value = item[-1]
        if isGoal(state):
            print("Configurations examinees :", count)
            return item
        txt = stringify(state)
        if txt in cache:
            continue
        cache.add(txt)
        for a1 in actions[code[0]]:
            state1 = doAction(state, a1, 0)
            if state1 == None:
                continue
            for a2 in actions[code[1]]:
                state2 = doAction(state1, a2, 1)
                if state2 == None:
                    continue
                for a3 in actions[code[2]]:
                    state3 = doAction(state2, a3, 2)
                    if state3 == None:
                        continue
                    for a4 in actions[code[3]]:
                        state4 = doAction(state3, a4, 3)
                        if state4 == None:
                            continue
                        cache.add(txt)
                        nextCode = a1 + a2 + a3 + a4
                        nextValue = value + 10
                        for k in nextCode:
                            if k == "#":
                                nextValue += 2
                            elif k in "<>":
                                nextValue += 1
                        nextItem = item[:]
                        nextItem.append((nextCode, state4, nextValue))
                        fringe.add(heuristic(state4) + nextValue, nextItem)
    print("=" * 40)
    print("Pas de solution !!!")
    print("Cache :", len(cache))


def isGoal(state):
    for i in range(4, len(state)):
        if state[i] != i - 4:
            return False
    return True


def stringify(state):
    a = "abcdefghijklmnopqrstuvwxyz"
    A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    b = "0123456789"
    txt = ""
    for i in range(len(state)):
        n = state[i]
        if n < 0:
            txt += b[-n]
        elif i < 4:
            txt += A[n]
        else:
            txt += a[n]
    return txt


def doAction(state, action, index):
    """
    state  : état initial.
    action : code d'action du charriot.
    index  : index du charriot (0 à 3).
    """
    neighbours = (1, 0, 3, 2)
    pos = state[index]
    nextState = state[:]
    if action == "<":
        if pos == 0 or nextState[neighbours[index]] == pos - 1:
            return None
        nextState[index] -= 1
    elif action == ">":
        if pos == len(nextState) - 5 or nextState[neighbours[index]] == pos + 1:
            return None
        nextState[index] += 1
    elif action == "#":
        load = -1    # indice de la caisse chargée ou -1 si le charriot est à vide.
        for i in range(4, len(nextState)):
            if nextState[i] == -index - 1:
                load = i - 4
                break
        if load < 0:
            # Le charriot est à vide, peut-il charger une caisse ?
            for i in range(4, len(nextState)):
                if nextState[i] == pos:
                    nextState[i] = -index - 1
                    return nextState
            return None
        else:
            # Le charriot est chargé, peut-il déposer sa caisse ?
            for i in range(4, len(nextState)):
                if nextState[i] == pos:
                    # Il y a déjà une caisse à cet endroit.
                    return None
            nextState[load + 4] = pos
    return nextState


def doActions(state, actions):
    nextState = state[:]
    for i in range(len(actions)):
        nextState = doAction(nextState, actions[i], i)
        if nextState == None:
            return None
    return nextState