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.
181 lines
5.1 KiB
181 lines
5.1 KiB
from queue import PriorityQueue |
|
|
|
qu = PriorityQueue() |
|
qu2 = PriorityQueue() |
|
currentbest = None |
|
timestamps = {} |
|
solutions = 0 |
|
visted = [] |
|
total = 0 |
|
|
|
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 == goal[0] and x == goal[1]: |
|
solutions += 1 |
|
if currentbest is None or currentbest > time: |
|
currentbest = time |
|
#print('solution found', currentbest) |
|
return |
|
if currentbest is not None and time + (abs(goal[1] - x) + abs(goal[0] - 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) or (nextMove[0] == heigth and nextMove[1] == width - 1) or (nextMove[0] == -1 and nextMove[1] == 0)): |
|
if nextMove + (time + 1,) not in visted: |
|
visted.append(nextMove + (time + 1,)) |
|
if switch: |
|
qu2.put((time + abs(goal[0] - nextMove[0]) + abs(goal[1] - 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)) |
|
goal = (heigth - 1, width - 1) |
|
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, 'queue=', qu2.qsize()) |
|
findPath(abs(y), abs(x), abs(time)) |
|
|
|
print(currentbest + 1) |
|
total = currentbest + 1 |
|
currentbest = None |
|
goal = (0, 0) |
|
solutions = 0 |
|
switch = True |
|
n = 0 |
|
qu.put((-(total), 0, heigth, width - 1)) |
|
visted = [] |
|
timestamps = {} |
|
|
|
while not qu.empty(): |
|
if not switch and solutions > 0: |
|
switch = True |
|
time, _, y, x = qu.get() |
|
n += 1 |
|
if n % 10 == 0: |
|
print(n, solutions, time, currentbest, y, x) |
|
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, 'queue=', qu2.qsize()) |
|
findPath(abs(y), abs(x), abs(time)) |
|
|
|
print(currentbest + 1) |
|
total = currentbest + 1 |
|
currentbest = None |
|
goal = (heigth -1, width - 1) |
|
solutions = 0 |
|
switch = True |
|
n = 0 |
|
qu.put((-(total), 0, -1, 0)) |
|
visted = [] |
|
timestamps = {} |
|
|
|
while not qu.empty(): |
|
if not switch and solutions > 0: |
|
switch = True |
|
time, _, y, x = qu.get() |
|
n += 1 |
|
if n % 10 == 0: |
|
print(n, solutions, time, currentbest, y, x) |
|
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, 'queue=', qu2.qsize()) |
|
findPath(abs(y), abs(x), abs(time)) |
|
|
|
print(currentbest + 1) |