small optimization in heapexperimental

2 files changed, 213 insertions, 112 deletions

diff --git a/example.py b/example.py
index 7fb2dbe..8f96663 100644
--- a/example.py
+++ b/example.py
@@ -22,106 +22,71 @@ edges = {
 
 gothpick.PrintInput(initialPositions,edges)
 solvedpath = gothpick.lockpick(numOfBlocks,numOfPins,initialPositions,edges)
-gothpick.TranslateResults(solvedpath,False)
+gothpick.TranslateResults(solvedpath,False,edges, initialPositions)
 
 '''
-Gothic 1 Remake - lockpick help
-_______________________________
-step-by-step [y] or complete list [n]? : n
-How many blocks?: 5
-How many pin slots in a block?: 7
-Initial State
-enter initial pin position for block 1: 6
-enter initial pin position for block 2: 3
-enter initial pin position for block 3: 2
-enter initial pin position for block 4: 1
-enter initial pin position for block 5: 7
-connections
-format: comma separated block IDs
-if the connected block moves in opposite direction, prefix with -
-basically positive and negative integers
-enter connections for block 1: 1,4
-enter connections for block 2: 2,5
-enter connections for block 3: 3,-5
-enter connections for block 4: 4,-5,-3,2
-enter connections for block 5: 5
-========SETUP========
-pins
-  1: 6
-  2: 3
-  3: 2
-  4: 1
-  5: 7
-connections
-  1: 1,4
-  2: 2,5
-  3: 3,-5
-  4: 4,-5,-3,2
-  5: 5
-=====================
-01/31:	3 -> LEFT 
+01/31:	2 -> RIGHT	[0, -1, 0, 0, -1]	[6, 2, 2, 1, 6]
 
-02/31:	3 -> LEFT 
+02/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[6, 2, 3, 1, 5]
 
-03/31:	4 -> LEFT 
+03/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[6, 2, 4, 1, 4]
 
-04/31:	1 -> RIGHT
+04/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[6, 2, 5, 1, 3]
 
-05/31:	3 -> LEFT 
+05/31:	4 -> LEFT 	[0, 1, -1, 1, -1]	[6, 3, 4, 2, 2]
 
-06/31:	5 -> LEFT 
+06/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 3, 4, 2, 3]
 
-07/31:	5 -> LEFT 
+07/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 3, 4, 2, 4]
 
-08/31:	2 -> RIGHT
+08/31:	4 -> LEFT 	[0, 1, -1, 1, -1]	[6, 4, 3, 3, 3]
 
-09/31:	4 -> LEFT 
+09/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 4, 3, 3, 4]
 
-10/31:	5 -> LEFT 
+10/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[6, 4, 4, 3, 3]
 
-11/31:	1 -> RIGHT
+11/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 4, 4, 3, 4]
 
-12/31:	3 -> LEFT 
+12/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 4, 4, 3, 5]
 
-13/31:	5 -> LEFT 
+13/31:	2 -> RIGHT	[0, -1, 0, 0, -1]	[6, 3, 4, 3, 4]
 
-14/31:	5 -> LEFT 
+14/31:	4 -> LEFT 	[0, 1, -1, 1, -1]	[6, 4, 3, 4, 3]
 
-15/31:	2 -> RIGHT
+15/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[6, 4, 3, 4, 4]
 
-16/31:	4 -> LEFT 
+16/31:	1 -> RIGHT	[-1, 0, 0, -1, 0]	[5, 4, 3, 3, 4]
 
-17/31:	5 -> LEFT 
+17/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[5, 4, 4, 3, 3]
 
-18/31:	3 -> LEFT 
+18/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[5, 4, 4, 3, 4]
 
-19/31:	5 -> LEFT 
+19/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[5, 4, 4, 3, 5]
 
-20/31:	5 -> LEFT 
+20/31:	2 -> RIGHT	[0, -1, 0, 0, -1]	[5, 3, 4, 3, 4]
 
-21/31:	2 -> RIGHT
+21/31:	4 -> LEFT 	[0, 1, -1, 1, -1]	[5, 4, 3, 4, 3]
 
-22/31:	4 -> LEFT 
+22/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[5, 4, 3, 4, 4]
 
-23/31:	5 -> LEFT 
+23/31:	1 -> RIGHT	[-1, 0, 0, -1, 0]	[4, 4, 3, 3, 4]
 
-24/31:	3 -> LEFT 
+24/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[4, 4, 4, 3, 3]
 
-25/31:	5 -> LEFT 
+25/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[4, 4, 4, 3, 4]
 
-26/31:	5 -> LEFT 
+26/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[4, 4, 4, 3, 5]
 
-27/31:	2 -> RIGHT
+27/31:	2 -> RIGHT	[0, -1, 0, 0, -1]	[4, 3, 4, 3, 4]
 
-28/31:	4 -> LEFT 
+28/31:	4 -> LEFT 	[0, 1, -1, 1, -1]	[4, 4, 3, 4, 3]
 
-29/31:	5 -> LEFT 
+29/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[4, 4, 3, 4, 4]
 
-30/31:	3 -> LEFT 
+30/31:	3 -> LEFT 	[0, 0, 1, 0, -1]	[4, 4, 4, 4, 3]
 
-31/31:	5 -> LEFT 
+31/31:	5 -> LEFT 	[0, 0, 0, 0, 1]	[4, 4, 4, 4, 4]
 
-Done.
 
 '''
 
@@ -146,76 +111,154 @@ edges = {
 3:[(1,3),(-1,1),(-1,0)],
 4:[(1,4),(1,3),(-1,1)]
 }
+
 gothpick.PrintInput(initialPositions,edges)
 solvedpath = gothpick.lockpick(numOfBlocks,numOfPins,initialPositions,edges)
-gothpick.TranslateResults(solvedpath,False)
+gothpick.TranslateResults(solvedpath,False,edges, initialPositions)
 
 '''
 expected output:
-01/33:	5 -> LEFT 
+01/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[1, 7, 2, 1, 6]
+
+02/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[2, 6, 1, 1, 6]
+
+03/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[2, 7, 2, 1, 6]
+
+04/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[3, 6, 1, 1, 6]
+
+05/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 7, 2, 1, 6]
+
+06/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 6, 1, 1, 6]
+
+07/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[4, 7, 2, 1, 6]
+
+08/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[3, 6, 2, 2, 6]
+
+09/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 5, 1, 2, 6]
+
+10/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[3, 4, 1, 3, 6]
+
+11/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 5, 2, 3, 6]
+
+12/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[2, 4, 2, 4, 6]
+
+13/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[2, 5, 3, 4, 6]
+
+14/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[3, 4, 2, 4, 6]
+
+15/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 5, 3, 4, 6]
+
+16/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 4, 2, 4, 6]
+
+17/31:	5 -> RIGHT	[0, 1, 0, -1, -1]	[4, 5, 2, 3, 5]
+
+18/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[3, 4, 2, 4, 5]
+
+19/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 5, 3, 4, 5]
+
+20/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 4, 2, 4, 5]
+
+21/31:	5 -> RIGHT	[0, 1, 0, -1, -1]	[4, 5, 2, 3, 4]
+
+22/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[3, 4, 2, 4, 4]
+
+23/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 5, 3, 4, 4]
 
-02/33:	2 -> LEFT 
+24/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[3, 6, 4, 4, 4]
 
-03/33:	3 -> RIGHT
+25/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 5, 3, 4, 4]
 
-04/33:	4 -> LEFT 
+26/31:	1 -> RIGHT	[-1, 0, 1, -1, 0]	[3, 5, 4, 3, 4]
 
-05/33:	2 -> LEFT 
+27/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 4, 3, 3, 4]
 
-06/33:	3 -> RIGHT
+28/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[4, 5, 4, 3, 4]
 
-07/33:	2 -> LEFT 
+29/31:	4 -> LEFT 	[-1, -1, 0, 1, 0]	[3, 4, 4, 4, 4]
 
-08/33:	4 -> LEFT 
+30/31:	3 -> RIGHT	[1, -1, -1, 0, 0]	[4, 3, 3, 4, 4]
 
-09/33:	2 -> LEFT 
+31/31:	2 -> LEFT 	[0, 1, 1, 0, 0]	[4, 4, 4, 4, 4]
+
+
+'''
+
+
+
+numOfBlocks = 5
+numOfPins = 7
+
+initialPositions = {
+0:1,
+1:4,
+2:6,
+3:2,
+4:1
+}
+
+edges = {
+0:[(1,0),(1,3)],
+1:[(1,1),(-1,0)],
+2:[(1,2)],
+3:[(1,3),(1,4),(1,2),(-1,1)],
+4:[(1,4),(1,3),(-1,2)]
+}
+
+
+gothpick.PrintInput(initialPositions,edges)
+solvedpath = gothpick.lockpick(numOfBlocks,numOfPins,initialPositions,edges)
+gothpick.TranslateResults(solvedpath,False,edges, initialPositions)
+
+'''
+expected output:
 
-10/33:	3 -> RIGHT
+01/25:	2 -> RIGHT	[1, -1, 0, 0, 0]	[2, 3, 6, 2, 1]
 
-11/33:	2 -> LEFT 
+02/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[2, 3, 5, 3, 2]
 
-12/33:	3 -> RIGHT
+03/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[2, 3, 4, 4, 3]
 
-13/33:	2 -> LEFT 
+04/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[2, 3, 5, 4, 3]
 
-14/33:	3 -> RIGHT
+05/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[2, 3, 4, 5, 4]
 
-15/33:	2 -> LEFT 
+06/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[2, 3, 5, 5, 4]
 
-16/33:	4 -> LEFT 
+07/25:	4 -> RIGHT	[0, 1, -1, -1, -1]	[2, 4, 4, 4, 3]
 
-17/33:	5 -> RIGHT
+08/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[2, 4, 3, 5, 4]
 
-18/33:	3 -> RIGHT
+09/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[2, 4, 4, 5, 4]
 
-19/33:	2 -> LEFT 
+10/25:	2 -> RIGHT	[1, -1, 0, 0, 0]	[3, 3, 4, 5, 4]
 
-20/33:	4 -> LEFT 
+11/25:	4 -> RIGHT	[0, 1, -1, -1, -1]	[3, 4, 3, 4, 3]
 
-21/33:	5 -> RIGHT
+12/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[3, 4, 4, 4, 3]
 
-22/33:	3 -> RIGHT
+13/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[3, 4, 3, 5, 4]
 
-23/33:	2 -> LEFT 
+14/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[3, 4, 4, 5, 4]
 
-24/33:	4 -> LEFT 
+15/25:	2 -> RIGHT	[1, -1, 0, 0, 0]	[4, 3, 4, 5, 4]
 
-25/33:	5 -> RIGHT
+16/25:	4 -> RIGHT	[0, 1, -1, -1, -1]	[4, 4, 3, 4, 3]
 
-26/33:	3 -> RIGHT
+17/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[4, 4, 4, 4, 3]
 
-27/33:	2 -> LEFT 
+18/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[4, 4, 5, 4, 3]
 
-28/33:	4 -> LEFT 
+19/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[4, 4, 4, 5, 4]
 
-29/33:	1 -> RIGHT
+20/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[4, 4, 5, 5, 4]
 
-30/33:	3 -> RIGHT
+21/25:	1 -> RIGHT	[-1, 0, 0, -1, 0]	[3, 4, 5, 4, 4]
 
-31/33:	2 -> LEFT 
+22/25:	2 -> RIGHT	[1, -1, 0, 0, 0]	[4, 3, 5, 4, 4]
 
-32/33:	3 -> RIGHT
+23/25:	4 -> RIGHT	[0, 1, -1, -1, -1]	[4, 4, 4, 3, 3]
 
-33/33:	2 -> LEFT 
+24/25:	5 -> LEFT 	[0, 0, -1, 1, 1]	[4, 4, 3, 4, 4]
 
+25/25:	3 -> LEFT 	[0, 0, 1, 0, 0]	[4, 4, 4, 4, 4]
 '''
diff --git a/gothpick.py b/gothpick.py
index 8aa8e73..7b5e474 100644
--- a/gothpick.py
+++ b/gothpick.py
@@ -1,5 +1,21 @@
 import heapq
 
+
+# global variables
+verbosedict = {-1:"RIGHT",1:"LEFT "} # it's reversed from the pin point of view
+
+##### Notes
+#try making optimize path function
+#	takes path, starting pinslots and connections as input
+#	trimms away useless steps
+#	first idea: 
+#		if if the changes made m-steps before were reverted by current step, discard the (n-m) step
+#		repeat recursively
+#	VisitedNodes in lockpick() function might need a change
+#data structure of connections is a bit complicated, 
+#	I don't know why I didn't just make it neg/pos integers like in input
+
+
 # calculate how far away all pins are from the middle
 # used for pathfinding 
 def CalculateDistance(target, PinList):
@@ -8,21 +24,29 @@ def CalculateDistance(target, PinList):
 		distance += abs(target - pin)
 	return distance
 
+#experimental priority for heap queue (05-20% more efficient)
+def CalculatePriority(target, PinList,PathList):
+	distance = CalculateDistance(target, PinList)
+	return distance*len(PathList)
+
 # pathinding function
 def lockpick(blocks, pinnumber, pinpos,connections):
-	TargetPosition = 1+ pinnumber // 2; #middle pin slot
+	TargetPosition = 1 + pinnumber // 2; #middle pin slot
 	initialpins = [0]*blocks
 	for p in pinpos:
 		initialpins[p]=pinpos[p]
 	VisitedNodes=set()
+	
+	SolvedPath = None
 	# queue items: 
-	#	distance from solution
+	#	priority ( distance * path length
 	#	pinpositions 
 	#	takenpath
 	queue = [(-1,initialpins,[])]
 	while queue:
-		dist,pins,path = heapq.heappop(queue)
+		priority,pins,path = heapq.heappop(queue)
 		# all are in the middle?
+		dist = CalculateDistance(TargetPosition,pins)
 		if dist == 0:
 			return path
 		
@@ -53,27 +77,62 @@ def lockpick(blocks, pinnumber, pinpos,connections):
 			
 			UpdatedDistance = CalculateDistance(TargetPosition,UpdatedPins)
 			UpdatedPath = [step for step in path]+[(QueueBlock,QueueDirection)]
-			heapq.heappush(queue,(UpdatedDistance,UpdatedPins,UpdatedPath))
-		
-	return []		
+			
+			UpdatedPriority = CalculatePriority(TargetPosition,UpdatedPins,UpdatedPath)
+			
+			heapq.heappush(queue,(UpdatedPriority,UpdatedPins,UpdatedPath))
+	return []
+
 
 
 
-# it's reversed from the pin point of view
-verbosedict = {-1:"RIGHT",1:"LEFT "}
+# arguments:
+# pathlist -> solution from lockpick function
+# incremental -> you have to click to display next step
+# conndict -> connections, used for printout of the changes in pin positions
+# pindict -> pinslot positions, used for printout of current pin position after each step's changes
 
-def TranslateResults(PathList,incremental=False):
+def TranslateResults(PathList,incremental=False,conndict=None, pindict=None):
 	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
+	pinlist = None
+	
+	if conndict:
+		conns = len(conndict.keys())
+	
+		if pindict:
+			pinlist = [0]*conns
+			for p in pindict:
+				pinlist[p]=pindict[p]
+			#print(pinlist)
+	
 	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}')
+		print(f'{str(step_i).zfill(spacefillnum)}/{TotalStepCount}:\t{b} -> {s}',end="")
+		if conndict:
+			connlist = [0]*conns
+			for i in range(conns):
+				if (-1,i) in conndict[pathblock]: 
+					connlist[i] += -1*pathmove
+				elif (1,i) in conndict[pathblock]:
+					connlist[i] += 1*pathmove
+			print(f'\t{connlist}',end="")
+			
+			if pinlist:
+				for di,d in enumerate(connlist):
+					pinlist[di] += d
+				print(f'\t{pinlist}')
+			else:
+				print()
+		else: 
+			print()
+		
 		if incremental:
 			input()
 		else:
@@ -90,7 +149,6 @@ def ParseInputs():
 			print("invalid input")
 			continue
 		increm = decision == "y"
-		#if not increm:
 	
 	NumberOfBlocks = None
 	NumberOfBlocks = input("How many blocks?: ")