1  from lib import *
  2  
  3  input = read_input(2019, 25)
  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      def output(self):
 78          out = "".join(map(chr, self.out))
 79          self.out.clear()
 80          return out
 81  
 82      def input(self, inp):
 83          self.inp += map(ord, inp + "\n")
 84          self.cont()
 85  
 86  
 87  class Bot(IntCode):
 88      def __init__(self, mem):
 89          super().__init__(mem)
 90  
 91          self.directions = []
 92          self.items = []
 93          self.room = None
 94  
 95      def start(self):
 96          super().start()
 97  
 98          self.parse_new_room()
 99  
100      def parse_new_room(self):
101          out = self.output().split("\n")
102          for line in out:
103              match = re.match(r"^== (.+) ==$", line)
104              if match:
105                  self.room = match.group(1)
106                  break
107          out = out[out.index("Doors here lead:") + 1 :]
108          self.directions = [d[2:] for d in out[: out.index("")]]
109          if "Items here:" not in out:
110              self.items.clear()
111              return
112          out = out[out.index("Items here:") + 1 :]
113          self.items = [i[2:] for i in out[: out.index("")]]
114  
115      def move(self, direction):
116          self.input(direction)
117          self.parse_new_room()
118  
119      def take(self, item):
120          self.input("take " + item)
121          self.out.clear()
122  
123      def drop(self, item):
124          self.input("drop " + item)
125          self.out.clear()
126  
127      def inv(self):
128          self.input("inv")
129          out = self.output().split("\n")
130          if "Items in your inventory:" not in out:
131              return []
132          out = out[out.index("Items in your inventory:") + 1 :]
133          return [i[2:] for i in out[: out.index("")]]
134  
135      def test(self, direction):
136          assert self.room == "Security Checkpoint"
137          self.input(direction)
138  
139          orig = out = self.output().split("\n")
140          out = out[out.index("Doors here lead:") + 1 :]
141          out = out[out.index("") + 1 :]
142          res = "ejected back" not in out[0]
143          if res:
144              print(re.match(r"^.*?(\d+).*$", out[2]).group(1))
145          return res
146  
147  
148  BACK = {"north": "south", "south": "north", "east": "west", "west": "east"}
149  
150  (*mem,) = map(int, input.split(","))
151  bot = Bot(mem)
152  bot.start()
153  
154  items = []
155  maze = {}
156  
157  
158  def explore(r=None, came_from=None, indent=0):
159      room = bot.room
160      if r:
161          maze.setdefault(r, {})[BACK[came_from]] = room
162      if room == "Security Checkpoint":
163          for direction in bot.directions:
164              if direction != came_from:
165                  maze.setdefault(room, {})[direction] = "TEST"
166          return
167      for item in bot.items:
168          if item not in {"escape pod", "giant electromagnet", "molten lava", "photons", "infinite loop"}:
169              items.append(item)
170              bot.take(item)
171  
172      for direction in bot.directions:
173          if came_from == direction:
174              continue
175          bot.move(direction)
176          explore(room, BACK[direction], indent + 1)
177          bot.move(BACK[direction])
178  
179  
180  explore()
181  
182  
183  def make_path(room, dest, f=None):
184      if room == dest:
185          return []
186  
187      for d, r in maze.get(room, {}).items():
188          if r == f:
189              continue
190          res = make_path(r, dest, room)
191          if res is not None:
192              return [d] + res
193  
194  
195  for d in make_path(bot.room, "Security Checkpoint"):
196      bot.move(d)
197  (dire,) = maze[bot.room]
198  
199  
200  def test_combination(i):
201      for e in bot.inv():
202          bot.drop(e)
203      for j, e in enumerate(items):
204          if i & (1 << j):
205              bot.take(e)
206      return bot.test(dire)
207  
208  
209  for i in range(1 << len(items)):
210      if test_combination(i):
211          break