#informatii despre un nod din arborele de parcurgere (nu din graful initial)
class NodParcurgere:
	def __init__(self, id, info, parinte):
		self.id=id # este indicele din vectorul de noduri
		self.info=info
		self.parinte=parinte #parintele din arborele de parcurgere

	def obtineDrum(self):
		l=[self.info]; #lista care incepe cu nodul dat
		nod=self
		while nod.parinte is not None: #parcurg toate nodurile din drum
			l.insert(0, nod.parinte.info)
			nod=nod.parinte
		return l

	def afisDrum(self): #returneaza si lungimea drumului
		l = self.obtineDrum()
		print("->".join(l)) #pt [a, b, f] o sa afiseze a->b->f
		return len(l)

	def contineInDrum(self, infoNodNou):
		nodDrum = self
		while nodDrum is not None:
			if infoNodNou == nodDrum.info:
				return True
			nodDrum=nodDrum.parinte

		return False

	def __repr__(self):
		sir=""
		sir+=self.info+"("
		sir+="id = {}, ".format(self.id)
		sir+="drum="
		drum=self.obtineDrum()
		sir+=("->").join(drum)
		sir+=")"
		return(sir)


class Graph: #graful problemei
	def __init__(self, start, scopuri):
		self.nrStive = len(start)
		self.start=start
		self.scopuri=scopuri

	#va genera succesorii sub forma de noduri in arborele de parcurgere
	def genereazaSuccesori(self, nodCurent):
		listaSuccesori = []  # pornesc cu lista vida de succesori
		# pentru fiecare stiva i vreau sa incerc sa iau un bloc
		for i in range(self.nrStive):
			# test sa vad daca pot extrage bloc
			if len(nodCurent.info[i]) > 0:
				# mai jos copiez informatia nodului curent in nodul intermediar
				infoIntermediar = copy.deepcopy(
					nodCurent.info)  # face exact ce face for-ul de pe tabla, dar e mai compact
				nodIntermediar = NodParcurgere(infoIntermediar,
											   nodCurent)  # fac un nod parcurgere nou daca vreau sa afisez si starea intermediara (fara bloc)
				# iau primul bloc din stiva i
				bloc = nodIntermediar.info[i].pop(0)
				# reparcurg stivele incercand sa pun blocul la loc
				# pentru fiecare stiva j diferita de stiva i (ca sa nu ajung la starea de dinainte)
				for j in range(self.nrStive):
					if i != j:
						# creez un NodParcurgere nou pentru punerea blocului
						infoNou = copy.deepcopy(nodIntermediar.info)
						nodSuccesor = NodParcurgere(infoNou,
													nodIntermediar)  # sau pot pune nodCurent ca parinte daca nu vreau sa afisez si pasii intermediari
						# actualizez nodul, punand blocul lipsa pe stiva j
						nodSuccesor.info[j].insert(0, bloc)
						# adaug nodul succesor in lista de succesori
						listaSuccesori.append(nodSuccesor)
		return listaSuccesori

	def __repr__(self):
		sir = ""
		for (k,v) in self.__dict__.items(): #creez un dictionar(metoda predefinita)
			sir+="{} = {}\n".format(k, v) # {} este echivalent cu %s din C
		return(sir)



##############################################################################################
#                                 Initializare problema                                      #
##############################################################################################

#pozitia i din vectorul de noduri da si numarul liniei/coloanei corespunzatoare din matricea de adiacenta


start=[["a"],["b","c"],["d"]]
scopuri=[["c","b"],[],["a","d"]]
gr=Graph(start, scopuri)



#### algoritm BF
#presupunem ca vrem mai multe solutii (un numar fix)
#daca vrem doar o solutie, renuntam la variabila nrSolutiiCautate
#si doar oprim algoritmul la afisarea primei solutii
nrSolutiiCautate=4

def breadth_first(gr):
	global nrSolutiiCautate #folosesc global pt a putea folosi variabila globala
	#in coada vom avea doar noduri de tip NodParcurgere (nodurile din arborele de parcurgere)
	c = [NodParcurgere(gr.noduri.index(start), start, None)]
	continua = True #variabila pe care o setez la false cand consider ca s-au afisat suficiente solutii
	while len(c) > 0 and continua:
		print("Coada actuala: " + str(c))
		input()
		nodCurent = c.pop(0)
		print("Se extinde nodul ", nodCurent.info, " din drumul ", end="")
		nodCurent.afisDrum()

		if nodCurent.info in scopuri:
			print("----> Solutie: ", end="")
			l = nodCurent.afisDrum()
			print("Lungime solutie:", l)
			nrSolutiiCautate -= 1
			if nrSolutiiCautate == 0:
				continua = False
		lSuccesori = gr.genereazaSuccesori(nodCurent)
		c.extend(lSuccesori) #adaug in finalul cozii
		print("Se adauga in coada: ", end="")
		if len(lSuccesori) > 0:
			for nod in lSuccesori:
				print(nod.info, end=" ")
		else:
			print("nimic")
		print("")


breadth_first(gr)
#bonus: sa afiseze solutia in momentu expandarii
#ca sa nu puna newline: print("fdsf", end="")