1  from lib import *
  2  
  3  input = read_input(2019, 15)
  4  
  5  
  6  class IntCode:
  7      def __init__(self, mem):
  8          self.mem = {i: e for i, e in enumerate(mem)}
  9          self.pc = 0
 10          self.running = False
 11          self.inp = []
 12          self.out = []
 13          self.rel = 0
 14  
 15      def start(self):
 16          self.running = True
 17          self.cont()
 18  
 19      def get_arg(self, i):
 20          mode = self.mem[self.pc] // (10 ** (i + 1)) % 10
 21          out = self.mem[self.pc + i]
 22          if mode == 1:
 23              return out
 24          elif mode == 2:
 25              out += self.rel
 26          return self.mem.get(out, 0)
 27  
 28      def write_arg(self, i, value):
 29          mode = self.mem[self.pc] // (10 ** (i + 1)) % 10
 30          pos = self.mem[self.pc + i]
 31          assert mode != 1
 32          if mode == 2:
 33              pos += self.rel
 34          self.mem[pos] = value
 35  
 36      def cont(self):
 37          while True:
 38              opcode = self.mem[self.pc] % 100
 39  
 40              if opcode == 1:
 41                  self.write_arg(3, self.get_arg(1) + self.get_arg(2))
 42                  self.pc += 4
 43              elif opcode == 2:
 44                  self.write_arg(3, self.get_arg(1) * self.get_arg(2))
 45                  self.pc += 4
 46              elif opcode == 3:
 47                  if not self.inp:
 48                      return
 49                  self.write_arg(1, self.inp.pop(0))
 50                  self.pc += 2
 51              elif opcode == 4:
 52                  self.out.append(self.get_arg(1))
 53                  self.pc += 2
 54              elif opcode == 5:
 55                  if self.get_arg(1):
 56                      self.pc = self.get_arg(2)
 57                  else:
 58                      self.pc += 3
 59              elif opcode == 6:
 60                  if not self.get_arg(1):
 61                      self.pc = self.get_arg(2)
 62                  else:
 63                      self.pc += 3
 64              elif opcode == 7:
 65                  self.write_arg(3, int(self.get_arg(1) < self.get_arg(2)))
 66                  self.pc += 4
 67              elif opcode == 8:
 68                  self.write_arg(3, int(self.get_arg(1) == self.get_arg(2)))
 69                  self.pc += 4
 70              elif opcode == 9:
 71                  self.rel += self.get_arg(1)
 72                  self.pc += 2
 73              elif opcode == 99:
 74                  self.running = False
 75                  return
 76  
 77  
 78  NORTH, SOUTH, WEST, EAST = range(1, 5)
 79  DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]
 80  BACK = {NORTH: SOUTH, SOUTH: NORTH, WEST: EAST, EAST: WEST}
 81  HIT_WALL, MOVED, REACHED_GOAL = range(3)
 82  UNKNOWN, EMPTY, WALL, GOAL = range(4)
 83  grid = {(0, 0): EMPTY}
 84  
 85  
 86  def get(x, y):
 87      return grid.get((x, y), 0)
 88  
 89  
 90  def put(x, y, v):
 91      grid[(x, y)] = v
 92  
 93  
 94  def explore(x, y):
 95      for direction, (dx, dy) in enumerate(DIRECTIONS):
 96          if get(x + dx, y + dy):
 97              continue
 98  
 99          intcode.inp.append(direction + 1)
100          intcode.cont()
101          result = intcode.out.pop(0)
102          if result == HIT_WALL:
103              put(x + dx, y + dy, WALL)
104              continue
105          elif result == MOVED:
106              put(x + dx, y + dy, EMPTY)
107          elif result == REACHED_GOAL:
108              put(x + dx, y + dy, GOAL)
109          explore(x + dx, y + dy)
110          intcode.inp.append(BACK[direction + 1])
111          intcode.cont()
112          intcode.out.pop(0)
113  
114  
115  (*mem,) = map(int, input.split(","))
116  intcode = IntCode(mem)
117  intcode.start()
118  explore(0, 0)
119  
120  Q = [(0, 0, 0)]
121  visited = set()
122  while Q:
123      d, x, y = heapq.heappop(Q)
124  
125      if (x, y) in visited:
126          continue
127      visited.add((x, y))
128  
129      if get(x, y) == GOAL:
130          print(d)
131          break
132  
133      for dx, dy in DIRECTIONS:
134          if get(x + dx, y + dy) != WALL:
135              heapq.heappush(Q, (d + 1, x + dx, y + dy))
136  
137  NORTH, SOUTH, WEST, EAST = range(1, 5)
138  DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]
139  BACK = {NORTH: SOUTH, SOUTH: NORTH, WEST: EAST, EAST: WEST}
140  HIT_WALL, MOVED, REACHED_GOAL = range(3)
141  UNKNOWN, EMPTY, WALL, GOAL = range(4)
142  grid = {(0, 0): EMPTY}
143  goal = None
144  
145  
146  def get(x, y):
147      return grid.get((x, y), 0)
148  
149  
150  def put(x, y, v):
151      global goal
152      if v == GOAL:
153          goal = x, y
154      grid[(x, y)] = v
155  
156  
157  def explore(x, y):
158      for direction, (dx, dy) in enumerate(DIRECTIONS):
159          if get(x + dx, y + dy):
160              continue
161  
162          intcode.inp.append(direction + 1)
163          intcode.cont()
164          result = intcode.out.pop(0)
165          if result == HIT_WALL:
166              put(x + dx, y + dy, WALL)
167              continue
168          elif result == MOVED:
169              put(x + dx, y + dy, EMPTY)
170          elif result == REACHED_GOAL:
171              put(x + dx, y + dy, GOAL)
172          explore(x + dx, y + dy)
173          intcode.inp.append(BACK[direction + 1])
174          intcode.cont()
175          intcode.out.pop(0)
176  
177  
178  (*mem,) = map(int, input.split(","))
179  intcode = IntCode(mem)
180  intcode.start()
181  explore(0, 0)
182  
183  Q = [(0, *goal)]
184  visited = set()
185  max_dist = 0
186  while Q:
187      d, x, y = heapq.heappop(Q)
188  
189      if (x, y) in visited:
190          continue
191      visited.add((x, y))
192  
193      max_dist = max(d, max_dist)
194  
195      for dx, dy in DIRECTIONS:
196          if get(x + dx, y + dy) != WALL:
197              heapq.heappush(Q, (d + 1, x + dx, y + dy))
198  print(max_dist)