-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathadventOfCode22d12.py
207 lines (166 loc) · 7.8 KB
/
adventOfCode22d12.py
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
207
# -*- coding: utf-8 -*-
"""
Created on Mon Dec 12 14:32:58 2022
@author: xBubblex
"""
import re
import numpy as np
import random as rd
import functools as ft
def load_files():
fContent = []
with open("input12.txt") as f:
for (lineIndex, line) in enumerate(f): #loading the file into an np.array
if bool(line):
fContent.append(list(line.strip("\n")))
return(fContent)
print(np.array(load_files()).shape)
class Map():
def __init__(self):
rd.seed()
self.raw = np.array(load_files())
self.map = self.raw.copy()
self.mapWBorders = np.array(load_files())
self.entrances = np.zeros(self.map.shape, dtype = object)
self.exits = np.zeros(self.map.shape, dtype = object)
self.enex = np.zeros(self.map.shape, dtype = object)
self.startStop = []
self.longestWalkL = self.map.shape[0] * self.map.shape[1]
self.pathLimit = self.longestWalkL
self.relH = np.zeros(self.map.shape, dtype = object)
self.walks = []
self.deadEnds = list([])
self.shortest = 0
self.visited = set([])
self.shortestW = []
self.shortestWDirs = []
self.stepsData = np.zeros(self.map.shape)
self.shortestList = []
def __set_start_stop(self):
while len(self.startStop) > 0:
self.startStop.pop()
self.startStop.append(np.where(self.map == "S"))
self.startStop.append(np.where(self.map == "E"))
self.map[self.startStop[0]] = "a"
self.map[self.startStop[1]] = "z"
self.pathLimit = ord("z") + 1 - ord("a")
# print(self.map.shape)
# print(len([inf for i in range((self.map.shape[0] + 2) * (self.map.shape[1] + 2))]))
self.mapWBorders = np.array([1000 for i in range((self.map.shape[0] + 2) * (self.map.shape[1] + 2))]).reshape((self.map.shape[0] + 2, -1))
self.map = np.array([ord(height) for height in self.map.flatten()]).reshape(self.map.shape)
self.mapWBorders[1 : -1, 1 : -1] = self.map
return self
def __rel_heights(self):
# print(self.map)
# print(self.mapWBorders[1 : -1, : -2])
l = self.map - self.mapWBorders[1 : -1, : -2]
r = self.map - self.mapWBorders[1 : -1, 2 : ]
u = self.map - self.mapWBorders[ : -2, 1 : -1]
d = self.map - self.mapWBorders[2 : , 1 : -1]
for rowIdx, row in enumerate(self.map):
for colIdx, col in enumerate(row):
self.relH[rowIdx, colIdx] = [r[rowIdx, colIdx], d[rowIdx, colIdx], l[rowIdx, colIdx], u[rowIdx, colIdx]]
return self
def __find_ent_ex(self):
conditionEnt = 1
conditionEx = -1
self.enex = map(lambda dirs: np.array([(dir_ <= conditionEnt) * "en" + (dir_ >= conditionEx) * "ex" for dir_ in dirs]), self.relH)
cond = [np.array(["enex", "", "", ""]), np.array(["enex", "", "", ""]), np.array(["", "", "enex", ""]), np.array(["", "", "", "enex"])]
deadEndsMatrix = (self.enex == cond[0]).astype(int) + (self.enex == cond[1]).astype(int) + (self.enex == cond[2]).astype(int) + (self.enex == cond[3]).astype(int)
self.deadEnds = np.where(deadEndsMatrix == 1)
return self
def find_path_lee(self, startIn = 0):
#Need to add something to avoid the path looping around.
self.__set_start_stop() if not startIn else 0
self.__rel_heights() if not startIn else 0
self.__find_ent_ex() if not startIn else 0
self.deadEnds = []
self.stepsData = np.zeros(self.map.shape)
start = [self.startStop[0][0][0], self.startStop[0][1][0]] if not startIn else startIn
# print(start)
finish = [self.startStop[1][0][0], self.startStop[1][1][0]]
self.shortest = 0
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
while self.stepsData[finish[0], finish[1]] == 0:
if self.shortest == 0:
self.shortest += 1
for direction in directions:
location = start
locCond = (direction[0] + location[0]) in range(self.map.shape[0]) and (direction[1] + location[1]) in range(self.map.shape[1])
if locCond:
valCond = self.map[direction[0] + location[0], direction[1] + location[1]] - self.map[location[0], location[1]] <= 1
notVisitedCond = self.stepsData[direction[0] + location[0], direction[1] + location[1]] == 0
else:
valCond = False
notVisitedCond = False
# print(locCond, valCond, notVisitedCond)
if valCond and notVisitedCond and locCond:
self.stepsData[direction[0] + start[0], direction[1] + start[1]] = self.shortest
currentStepLocRaw = np.where(self.stepsData == self.shortest)
currentStep = [location for location in zip(currentStepLocRaw[0], currentStepLocRaw[1])]
if currentStep == []:
self.shortest = float("inf")
break
self.shortest += 1
for location in currentStep:
for direction in directions:
# print([direction[0] + location[0], direction[1] + location[1]])
locCond = (direction[0] + location[0]) in range(self.map.shape[0]) and (direction[1] + location[1]) in range(self.map.shape[1])
if locCond:
valCond = self.map[direction[0] + location[0], direction[1] + location[1]] - self.map[location[0], location[1]] <= 1
notVisitedCond = self.stepsData[direction[0] + location[0], direction[1] + location[1]] == 0
else:
valCond = False
notVisitedCond = False
# print(locCond, valCond, notVisitedCond)
if valCond and notVisitedCond and locCond:
self.stepsData[direction[0] + location[0], direction[1] + location[1]] = self.shortest
return self
def find_path_lee_shortest(self):
self.__set_start_stop()
self.__rel_heights()
self.__find_ent_ex()
# print(self.map)
startsRaw = np.where(self.map == ord("a"))
starts = [[location[0], location[1]] for location in zip(startsRaw[0], startsRaw[1])]
# print(starts)
# print(len(starts))
for startIdx, start in enumerate(starts):
# print(startIdx)
self.find_path_lee(start)
self.shortestList.append(self.shortest)
# print(self.shortest)
self.shortest = min(self.shortestList)
return self
#use a sum and u product for each point with entries/exits in the format [pm1 or 0, pm1 or 0, pm1 or 0, pm1 or 0] for [r, d, l, u] directions.
#map relative heights in the same manner as line above.
def run():
maps = Map()
maps.find_path_lee_shortest()
return maps.shortest
print(run())
# a = np.array([i for i in range(25)]).reshape((5, -1))
# print(a)
# print(sum(abs(np.array(np.where(a == 0)) - np.array(np.where(a == 24)))))
# print(list(np.where(a == 12))[1])
# print(np.where(a == 12))
# print(np.where(a == 12)[0][0], np.where(a == 12)[1][0])
# b = True
# c = False
# print([b] + [c])
# a = np.array([inf for i in range(9)]).reshape((3, -1))
# a[1 : -1, 1 : -1] = np.array([-inf])
# print(a - 5)
# def fun(x):
# return x if x%2 else -x
# print(fun(2), fun(3))
# a = [1, 2, 3]
# b = [4]
# b.append(a.pop())
# print(a, b)
# a = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
# b = a.copy()
# a.pop()
# print(b)
# b = np.where(a > 4)
# print([a[i] for i in zip(b[0], b[1])])