import heapq

# calculate how far away all pins are from the middle
# used for pathfinding 
def CalculateDistance(target, PinList):
	distance = 0;
	for pin in PinList:
		distance += abs(target - pin)
	return distance

# pathinding function
def lockpick(blocks, pinnumber, pinpos,connections):
	TargetPosition = 1+ pinnumber // 2; #middle pin slot
	initialpins = [0]*blocks
	for p in pinpos:
		initialpins[p]=pinpos[p]
	VisitedNodes=set()
	# queue items: 
	#	distance from solution
	#	pinpositions 
	#	takenpath
	queue = [(-1,initialpins,[])]
	while queue:
		dist,pins,path = heapq.heappop(queue)
		# all are in the middle?
		if dist == 0:
			return path
		
		if path:
			if (tuple(pins),path[-1]) in VisitedNodes: continue
			VisitedNodes.add((tuple(pins),path[-1]))
		subqueue = []
		#for each block
		for block in range(blocks):
			#in each direction
			for blockdir in [-1,1]:
				#check if all connected blocks can be moved
				CanMove = True
				PinsAfterMove = [pin for pin in pins]
				for conndir,connection in connections[block]:
					PinsAfterMove[connection] += conndir*blockdir
					CanMove *= PinsAfterMove[connection] in range(1,pinnumber+1)
					if not CanMove:
						break
				if CanMove:
					subqueue.append([block,blockdir,PinsAfterMove])
		
		for QueueBlock,QueueDirection,UpdatedPins in subqueue:
			#prevent going back and forth
			if len(path) > 0:
				if (QueueBlock,-QueueDirection) == path[-1]: 
					continue;
			
			UpdatedDistance = CalculateDistance(TargetPosition,UpdatedPins)
			UpdatedPath = [step for step in path]+[(QueueBlock,QueueDirection)]
			heapq.heappush(queue,(UpdatedDistance,UpdatedPins,UpdatedPath))
		
	return []		



# it's reversed from the pin point of view
verbosedict = {-1:"RIGHT",1:"LEFT "}

def TranslateResults(PathList,incremental=False):
	TotalStepCount = len(PathList)
	if TotalStepCount == 0:
			print("did not find a solution. Make sure the input is correct")
			return
	spacefillnum = len(str(TotalStepCount))
	step_i = 0
	for pathblock,pathmove in PathList:
		step_i += 1
		b = pathblock + 1
		s = verbosedict[pathmove]
		print(f'{str(step_i).zfill(spacefillnum)}/{TotalStepCount}:\t{b} -> {s}')
		if incremental:
			input()
		else:
			print()



def ParseInputs():
	increm = None
	while increm == None:
		decision = input("step-by-step [y] or complete list [n]? : ")
		decision = decision.casefold()
		if decision not in ["y","n"]:
			print("invalid input")
			continue
		increm = decision == "y"
		#if not increm:
	
	NumberOfBlocks = None
	NumberOfBlocks = input("How many blocks?: ") 
	NumberOfBlocks = int(NumberOfBlocks)
	NumberOfPinslots = None
	NumberOfPinslots = input("How many pin slots in a block?: ") 
	NumberOfPinslots = int(NumberOfPinslots)
	StartingPositions = {}
	BlockConnections = {}
	print("Initial State")
	for b in range(NumberOfBlocks):
		blockpinpos = input(f'enter initial pin position for block {b+1}: ')
		StartingPositions[b] = int(blockpinpos)
	print("connections")
	print("format: comma separated block IDs")
	print("if the connected block moves in opposite direction, prefix with -")
	print("basically positive and negative integers") 
	for b in range(NumberOfBlocks):
		BlockMapInput = input(f'enter connections for block {b+1}: ')
		BlockMap = [int(bm) for bm in BlockMapInput.replace("\n","").split(",")]
		BlockMap = [tuple([int(bm)//abs(int(bm)),abs(bm)-1]) for bm in BlockMap]
		BlockConnections[b] = [bl for bl in BlockMap]
	
	PrintInput(StartingPositions,BlockConnections)
	if increm:
		print("[step-by-step] the solution will be displayed one step at a time")
		print("To show next step, press any key")
	return increm, NumberOfBlocks, NumberOfPinslots, StartingPositions,BlockConnections


def PrintInput(pinpos,edges):
	print("========SETUP========")
	print("pins")
	for p_i,pin in enumerate(pinpos):
		print(f'  {p_i+1}: {pinpos[pin]}')
	
	print("connections")
	for p_i in range(len(pinpos)):
		edgeString = ",".join([ f'{e[0]*(1+e[1])}' for e in edges[p_i]])
		print(f'  {p_i+1}: {edgeString}')
	print("=====================")
		
def RunWithConsoleInput():
	FullPrint, BlockCount, PinCount, StartingPos, BlockGraph = ParseInputs()
	solution = lockpick(BlockCount, PinCount, StartingPos, BlockGraph)
	TranslateResults(solution,FullPrint)
	print("Done.")



if __name__ == "__main__":
	print("Gothic 1 Remake - lockpick help")
	print("_______________________________")
	RunWithConsoleInput()