diff options
| -rw-r--r-- | example.py | 245 | ||||
| -rw-r--r-- | gothpick.py | 80 |
2 files changed, 213 insertions, 112 deletions
@@ -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?: ") |