import numpy as np
from copy import deepcopy
class Nod:
    def __init__(self, nrStare, stare, parinte, scor):
        self.nrStare = nrStare
        self.stare = stare
        self.parinte = parinte
        self.scor = scor
    def afisare(self):
        print("{} {} {} {}".format(self.nrStare, self.stare, self.parinte, self.scor))

frontiera = []
teritoriu = []
si = [0, 0, 0, 0, 0]
sf = [1, 2, 3, 4, 5]
nodInit = Nod(1, si, 0, 0)
frontiera.append(nodInit)
F=50
scorMax=0
nodMax=nodInit
ok=False
nr = 2
while not ok:
    if len(frontiera) == 0:
        print("Insucces")
        break
    nodCurent = frontiera.pop()
    # print(nodCurent.stare)

    if 0 in nodCurent.stare:
        teritoriu.append(Nod(nr, nodCurent.stare, nodCurent.nrStare, 0))
    else:
        nodCurent.scor = F
        if nodCurent.stare[0] == 3:
            nodCurent.scor+=5
        if nodCurent.stare[1] == 5:
            nodCurent.scor+=4
        for i in range(4):
            if nodCurent.stare[i] % 2 == nodCurent.stare[i+1] % 2:
                nodCurent.scor-=8
        if nodCurent.scor > scorMax:
            scorMax = nodCurent.scor
            nodMax = nodCurent
        teritoriu.append(Nod(nr, nodCurent.stare, nodCurent.nrStare, nodCurent.scor))

    for element in range(1,6):
        if element not in nodCurent.stare:
            poz = 0
            for x in nodCurent.stare:
                if x != 0:
                    poz +=1

            succesor = deepcopy(nodCurent)
            succesor.stare[poz] = element
            nr+=1
            if succesor not in frontiera and succesor not in teritoriu:
                if succesor.stare == sf:
                    print(nodMax.stare)
                    # afisare.Solutie()
                    ok=True
                    exit(0)
                frontiera.append(succesor)
    # print(frontiera)