first commit

1 files changed, 169 insertions, 0 deletions

diff --git a/gothpick.py b/gothpick.py
new file mode 100644
index 0000000..056514a
--- /dev/null
+++ b/gothpick.py
@@ -0,0 +1,169 @@
+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]
+	# 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
+		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.")
+
+
+
+'''
+# example 
+# scatty's chest in his house
+numOfBlocks = 5
+numOfPins = 7
+initialPositions = {
+0:6,
+1:3,
+2:2,
+3:1,
+4:7
+}
+
+edges = {
+0:[(1,0),(1,3)],
+1:[(1,1),(1,4)],
+2:[(1,2),(-1,4)],
+3:[(1,3),(-1,4),(-1,2),(1,1)],
+4:[(1,4)]
+}
+
+solvedpath = lockpick(numOfBlocks,numOfPins,initialPositions,edges)
+TranslateResults(solvedpath,False)
+PrintInput(initialPositions,edges)
+#'''
+
+if __name__ == "__main__":
+	print("Gothic 1 Remake - lockpick help")
+	print("_______________________________")
+	RunWithConsoleInput()
+