1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
|
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()
|
