This repository has been archived by the owner on May 28, 2023. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path17_set_and_forget.py
162 lines (126 loc) · 4.83 KB
/
17_set_and_forget.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
##################################
# --- Day 17: Set and Forget --- #
##################################
import AOCUtils
from intcodeVM import VM
class BotCam:
def __init__(self, cam):
self.cam = [list(line) for line in cam]
self.size = (len(cam), len(cam[0]))
self.botPos, self.botFacing = None, None
for x in range(self.size[0]):
for y in range(self.size[1]):
if self.cam[x][y] != "." and self.cam[x][y] != "#":
self.botPos, self.botFacing = (x, y), self.cam[x][y]
self.cam[x][y] = "#"
def sumIntersections(self):
total = 0
for x in range(1, self.size[0]-2):
for y in range(1, self.size[1]-2):
if self.cam[x][y] != "#": continue
if self.cam[x-1][y] == self.cam[x+1][y] == self.cam[x][y-1] == self.cam[x][y+1]:
total += x*y
return total
def _rotate(self, direction):
faces = "^>v<"
if direction == "R":
newFace = (faces.index(self.botFacing)+1) % len(faces)
elif direction == "L":
newFace = (faces.index(self.botFacing)-1) % len(faces)
return faces[newFace]
def getPath(self):
moves = {"^": (-1, 0), ">": (0, 1), "v": (1, 0), "<": (0, -1)}
path = []
while True:
nxtTile = {"fwd": moves[self.botFacing],
"left": moves[self._rotate("L")],
"right": moves[self._rotate("R")]}
nxtStep = {"fwd": None,
"left": None,
"right": None}
for k, v in nxtTile.items():
if not (0 <= self.botPos[0]+v[0] < self.size[0]): continue
if not (0 <= self.botPos[1]+v[1] < self.size[1]): continue
if self.cam[self.botPos[0]+v[0]][self.botPos[1]+v[1]] == "#":
nxtStep[k] = (self.botPos[0]+v[0], self.botPos[1]+v[1])
# Always go forward, if possible
if nxtStep["fwd"]:
self.botPos = nxtStep["fwd"]
path[-1] += 1
elif nxtStep["left"]:
self.botPos = nxtStep["left"]
self.botFacing = self._rotate("L")
path += ["L", 1]
elif nxtStep["right"]:
self.botPos = nxtStep["right"]
self.botFacing = self._rotate("R")
path += ["R", 1]
else:
return path
# def __repr__(self):
# s = ""
# for line in self.cam:
# s += "".join(line) + "\n"
# return s
def formatInput(s):
return ",".join(str(c) for c in s)
def findAndReplace(l, f, r):
nl = []
i = 0
while i < len(l):
if l[i:i+len(f)] == f:
nl.append(r)
i += len(f)
else:
nl.append(l[i])
i += 1
return nl
def compressPath(path):
funcNames = list("ABC")
# Recursive backtracking approach
def recursiveCompress(main, funcs):
# If we have three functions, do not recurse anymore
if len(funcs) == 3:
# If main is short enough and fully compressed, return answer
if len(formatInput(main)) <= 20 and all(c in funcNames for c in main):
main = formatInput(main)
A, B, C = [formatInput(f) for f in funcs]
return main, A, B, C
return None
# Skip to uncompressed portion of path
curPos = 0
while main[curPos] in funcNames: curPos += 1
# Find next function to consider
curFunc = []
while True:
# Next element to add to the current function
newElement = main[curPos]
# If the element is a function, then this is invalid
if newElement in funcNames: break
curFunc.append(newElement)
curPos += 1
# If formatted function is longer than 20, also invalid
if len(formatInput(curFunc)) > 20: break
# Replace in main, add to function list and recurse
newMain = findAndReplace(main, curFunc, funcNames[len(funcs)])
newFuncs = funcs + [curFunc]
solution = recursiveCompress(newMain, newFuncs)
if solution: return solution
return None
return recursiveCompress(path, [])
##################################
rawProgram = AOCUtils.loadInput(17)
memory = [int(i) for i in rawProgram.split(",")]
vm = VM(memory)
vm.run()
cam = "".join(chr(c) for c in vm.output).split()
botcam = BotCam(cam)
print("Part 1: {}".format(botcam.sumIntersections()))
path = botcam.getPath()
main, A, B, C = compressPath(path)
videoFeed = "n"
vm = VM(memory)
vm[0] = 2
vm.run("\n".join([main, A, B, C, videoFeed]) + "\n")
print("Part 2: {}".format(vm.output[-1]))
AOCUtils.printTimeTaken()