diff options
Diffstat (limited to 'gothpick.py')
| -rw-r--r-- | gothpick.py | 80 |
1 files changed, 69 insertions, 11 deletions
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?: ") |