-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDay_17.py
97 lines (88 loc) · 3.3 KB
/
Day_17.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
def part1():
frontier = [(0, 0, 0, "r", 0), (0, 0, 0, "d", 0)]
visited = set()
goal = (len(inputVals) - 1, len(inputVals[0]) - 1)
minDist = [[-1 for i in j] for j in inputVals]
while len(frontier) > 0:
frontier.sort()
cost, row, col, direction, movedAlready = frontier.pop(0)
minDist[row][col] = cost
if (row, col) == goal:
#for i in minDist:
# print(i)
print("Part 1:", cost)
break
if movedAlready < 3:
temp = getNext(cost, row, col, direction, movedAlready)
if temp and (temp[1], temp[2], temp[3], temp[4]) not in visited:
visited.add((temp[1], temp[2], temp[3], temp[4]))
frontier.append(temp)
otherOptions = getOptions(cost, row, col, direction)
for i in otherOptions:
if (i[1], i[2], i[3], i[4]) not in visited:
frontier.append(i)
visited.add((i[1], i[2], i[3], i[4]))
def part2():
frontier = [(0, 0, 0, "r", 0), (0, 0, 0, "d", 0)]
visited = set()
goal = (len(inputVals) - 1, len(inputVals[0]) - 1)
minDist = [[-1 for i in j] for j in inputVals]
while len(frontier) > 0:
frontier.sort()
cost, row, col, direction, movedAlready = frontier.pop(0)
minDist[row][col] = cost
if (row, col) == goal:
if movedAlready > 3:
#for i in minDist:
# print(i)
print("Part 2:", cost)
break
if movedAlready < 10:
temp = getNext(cost, row, col, direction, movedAlready)
if temp and (temp[1], temp[2], temp[3], temp[4]) not in visited:
visited.add((temp[1], temp[2], temp[3], temp[4]))
frontier.append(temp)
if movedAlready > 3:
otherOptions = getOptions(cost, row, col, direction)
for i in otherOptions:
if (i[1], i[2], i[3], i[4]) not in visited:
frontier.append(i)
visited.add((i[1], i[2], i[3], i[4]))
def getNext(cost, row, col, direction, movedAlready):
if direction == "l":
if col > 0:
return (cost + inputVals[row][col - 1], row, col - 1, direction, movedAlready + 1)
if direction == "r":
if col < len(inputVals[0]) - 1:
return (cost + inputVals[row][col + 1], row, col + 1, direction, movedAlready + 1)
if direction == "u":
if row > 0:
return (cost + inputVals[row - 1][col], row - 1, col, direction, movedAlready + 1)
if direction == "d":
if row < len(inputVals) - 1:
return (cost + inputVals[row + 1][col], row + 1, col, direction, movedAlready + 1)
return None
def getOptions(cost, row, col, direction):
temp = []
if direction in "lr":
x = getNext(cost, row, col, "u", 0)
if x:
temp.append(x)
x = getNext(cost, row, col, "d", 0)
if x:
temp.append(x)
else:
x = getNext(cost, row, col, "l", 0)
if x:
temp.append(x)
x = getNext(cost, row, col, "r", 0)
if x:
temp.append(x)
return temp
inputVals = []
f = open("Day_17_input.txt")
for line in f:
line = line.replace("\n", "")
inputVals.append([int(i) for i in line])
#part1()
part2()