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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
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):
distance = 0;
for pin in 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
initialpins = [0]*blocks
for p in pinpos:
initialpins[p]=pinpos[p]
VisitedNodes=set()
SolvedPath = None
# queue items:
# priority ( distance * path length
# pinpositions
# takenpath
queue = [(-1,initialpins,[])]
while queue:
priority,pins,path = heapq.heappop(queue)
# all are in the middle?
dist = CalculateDistance(TargetPosition,pins)
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)]
UpdatedPriority = CalculatePriority(TargetPosition,UpdatedPins,UpdatedPath)
heapq.heappush(queue,(UpdatedPriority,UpdatedPins,UpdatedPath))
return []
# 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,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}',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:
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"
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()
|
