You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
132 lines
3.9 KiB
132 lines
3.9 KiB
1 year ago
|
from queue import PriorityQueue
|
||
|
|
||
|
qu = PriorityQueue()
|
||
|
qu2 = PriorityQueue()
|
||
|
currentbest = None
|
||
|
timestamps = {}
|
||
|
solutions = 0
|
||
|
visted = []
|
||
|
|
||
|
class Vortex():
|
||
|
def __init__(self, y, x):
|
||
|
self.y = y
|
||
|
self.x = x
|
||
|
|
||
|
def givePosition(self, time):
|
||
|
return self.calcPosition(time)
|
||
|
|
||
|
|
||
|
class VortexRigth(Vortex):
|
||
|
def calcPosition(self, time):
|
||
|
current = (self.x + time) % width
|
||
|
return self.y, current
|
||
|
def __str__(self):
|
||
|
return 'Rigth'
|
||
|
|
||
|
class VortexLeft(Vortex):
|
||
|
def calcPosition(self, time):
|
||
|
current = self.x - time
|
||
|
while current < 0:
|
||
|
current = width + current
|
||
|
return self.y, current
|
||
|
def __str__(self):
|
||
|
return 'Left'
|
||
|
|
||
|
class VortexUp(Vortex):
|
||
|
def calcPosition(self, time):
|
||
|
current = self.y - time
|
||
|
while current < 0:
|
||
|
current = heigth + current
|
||
|
return current, self.x
|
||
|
def __str__(self):
|
||
|
return 'Up'
|
||
|
|
||
|
class VortexDown(Vortex):
|
||
|
def calcPosition(self, time):
|
||
|
current = (self.y + time) % heigth
|
||
|
return current, self.x
|
||
|
def __str__(self):
|
||
|
return 'Down'
|
||
|
|
||
|
def findPath(y, x, time):
|
||
|
#print(y, x, time)
|
||
|
global currentbest
|
||
|
global timestamps
|
||
|
global solutions
|
||
|
if y == heigth - 1 and x == width - 1:
|
||
|
solutions += 1
|
||
|
if currentbest is None or currentbest > time:
|
||
|
currentbest = time
|
||
|
#print('solution found', currentbest)
|
||
|
return
|
||
|
if currentbest is not None and time + ((width - 1 - x) + (heigth - 1 - y))>= currentbest - 1:
|
||
|
return
|
||
|
if time + 1 not in timestamps:
|
||
|
timeList = []
|
||
|
for vort in vorteces:
|
||
|
timeList.append(vort.givePosition(time + 1))
|
||
|
timestamps[time + 1] = timeList
|
||
|
for nextMove in [(y, x),(y - 1, x),(y + 1, x),(y, x- 1),(y, x + 1)]:
|
||
|
#print(timestamps[time + 1], nextMove)
|
||
|
if nextMove not in timestamps[time + 1] and 0 <= nextMove[0] < heigth and 0 <= nextMove[1] < width:
|
||
|
if nextMove + (time + 1,) not in visted:
|
||
|
visted.append(nextMove + (time + 1,))
|
||
|
if switch:
|
||
|
qu2.put((time + (heigth - nextMove[0]) + (width - nextMove[1]), (time + 1), -nextMove[0], -nextMove[1]))
|
||
|
else:
|
||
|
qu.put((-(time + 1), -((nextMove[0]+1)*(nextMove[1]+1)), -nextMove[0], -nextMove[1]))
|
||
|
|
||
|
#reading input
|
||
|
initialState = []
|
||
|
vorteces = []
|
||
|
with open('input24.txt', 'r') as f:
|
||
|
inp = f.read().splitlines(keepends=False)
|
||
|
|
||
|
for line in inp:
|
||
|
initialState.append(list(line))
|
||
|
|
||
|
heigth = len(initialState) - 2
|
||
|
width = len(initialState[0]) - 2
|
||
|
currentbest = heigth * width
|
||
|
|
||
|
for y in range(len(initialState)):
|
||
|
for x in range(len(initialState[0])):
|
||
|
if initialState[y][x] == '>':
|
||
|
newVortex = VortexRigth(y - 1, x - 1)
|
||
|
vorteces.append(newVortex)
|
||
|
if initialState[y][x] == '<':
|
||
|
newVortex = VortexLeft(y - 1, x - 1)
|
||
|
vorteces.append(newVortex)
|
||
|
if initialState[y][x] == '^':
|
||
|
newVortex = VortexUp(y - 1, x - 1)
|
||
|
vorteces.append(newVortex)
|
||
|
if initialState[y][x] == 'v':
|
||
|
newVortex = VortexDown(y - 1, x - 1)
|
||
|
vorteces.append(newVortex)
|
||
|
switch = False
|
||
|
n = 0
|
||
|
qu.put((-1, 0, 0, 0))
|
||
|
while not qu.empty():
|
||
|
if not switch and solutions > 0:
|
||
|
switch = True
|
||
|
time, _, y, x = qu.get()
|
||
|
n += 1
|
||
|
if n % 10000 == 0:
|
||
|
print(n, solutions, time, currentbest)
|
||
|
findPath(abs(y), abs(x), abs(time))
|
||
|
|
||
|
while not qu2.empty():
|
||
|
_, time, y, x = qu2.get()
|
||
|
n += 1
|
||
|
if n % 10000 == 0:
|
||
|
print('n=', n, 'solutions=', solutions, 'time=', time, 'currentbest=', currentbest+1, 'queue=', qu2.qsize())
|
||
|
findPath(abs(y), abs(x), abs(time))
|
||
|
|
||
|
print(currentbest + 1)
|
||
|
# for vort in vorteces:
|
||
|
# print(vort, '(', vort.y, vort.x, ')', vort.givePosition(3))
|
||
|
|
||
|
# for line in initialState:
|
||
|
# for point in line:
|
||
|
# print(point, end = ' ')
|
||
|
# print('\n')
|