2019-12-11 - Space Police
(original .ipynb)
Day 11 puzzle input is an IntCode program which is supposed to control a little robot that paints the surface of a ship (mine is here). Part 1 involves running the program and keeping track of the number of panels it paints. Part 2 involves running the program over a panel coloured white, keeping track of what the robot paints - which should spell out a registration number.
Note: this is one of the ones I disliked because a few instructions were rather vague and weirdly worded, like this:
The panel under the robot (not visible here because a ^ is shown instead) is also black, and so any input instructions at this point should be provided
0.
This "provided N" appears a few times in the text.
opcode_add = 1
opcode_mul = 2
opcode_read = 3
opcode_write = 4
opcode_jump_true = 5
opcode_jump_false = 6
opcode_lt = 7
opcode_eq = 8
opcode_rebase = 9
opcode_terminate = 99
mode_position = 0
mode_immediate = 1
mode_relative = 2
class IntCodeCpu:
def __init__(self, memory_image):
self.memory = [ x for x in memory_image ] # copy memory image, in case it's reused
self.stalled = True
self.input_buffer = None
self.output_buffer = None
self.pc = 0
self.initialise_opcodes()
self.offset = 0
self.done = False
def start(self, input_buffer, output_buffer, noun=None, verb=None):
self.input_buffer = input_buffer
self.output_buffer = output_buffer
if noun:
self.memory[1] = noun
if verb:
self.memory[2] = verb
return self.run()
def run(self):
instr = self.memory[self.pc]
self.stalled = False
while int(instr) != opcode_terminate and not self.stalled:
(op, modes) = self.decode_instr(instr)
self.pc = op(modes)
instr = self.memory[self.pc]
return self.memory[0]
#-HELPERS-----------------------------
def try_pop_mode(self, modes):
if len(modes) == 0:
return 0
return modes.pop()
def resize_memory(self, target_addr):
self.memory += ([0] * (1 + target_addr - len(self.memory)))
#-DECODE-INSTRUCTIONS-----------------
def initialise_opcodes(self):
self.opcodes = {
opcode_add: self.op_add,
opcode_mul: self.op_mul,
opcode_read: self.op_read,
opcode_write: self.op_write,
opcode_jump_true: self.op_jump_true,
opcode_jump_false: self.op_jump_false,
opcode_lt: self.op_lt,
opcode_eq: self.op_eq,
opcode_rebase: self.op_rebase
}
def decode_instr(self, instr):
instr = str(instr)
opcode = self.decode_op(instr)
modes = self.decode_modes(instr)
if not (opcode in self.opcodes):
raise Exception(f"Invalid opcode {opcode}")
return (self.opcodes[opcode], modes)
def decode_op(self, instr):
if len(instr) > 2:
return int(instr[-2:])
return int(instr)
def decode_modes(self, instr):
if len(instr) > 2:
return [ int(d) for d in instr[:-2]]
return []
#-MICRO-OPS---------------------------
def uop_read(self, value, mode):
if mode == mode_position:
if value >= len(self.memory):
self.resize_memory(value)
return int(self.memory[value])
elif mode == mode_relative:
if self.offset + value >= len(self.memory):
self.resize_memory(self.offset + value)
return int(self.memory[self.offset + value])
elif mode == mode_immediate:
return int(value)
else:
raise Exception("UNKNOWN MODE")
def uop_write(self, dst, value, mode):
if mode == mode_position:
if dst >= len(self.memory):
self.resize_memory(dst)
self.memory[dst] = value
elif mode == mode_relative:
if self.offset + dst >= len(self.memory):
self.resize_memory(self.offset + dst)
self.memory[self.offset + dst] = value
elif mode == mode_immediate:
raise Exception(f"cannot write {value} to literal {dst}")
def uop_cond_jump(self, modes, cond):
param_mode = self.try_pop_mode(modes)
param_raw = int(self.memory[self.pc + 1])
param = self.uop_read(param_raw, param_mode)
dest_mode = self.try_pop_mode(modes)
dest_raw = int(self.memory[self.pc + 2])
dest = self.uop_read(dest_raw, dest_mode)
if cond(param):
return dest
return self.pc + 3
def uop_cmp(self, modes, cmp):
param0_mode = self.try_pop_mode(modes)
param0_raw = int(self.memory[self.pc + 1])
param0 = self.uop_read(param0_raw, param0_mode)
param1_mode = self.try_pop_mode(modes)
param1_raw = int(self.memory[self.pc + 2])
param1 = self.uop_read(param1_raw, param1_mode)
dest_mode = self.try_pop_mode(modes)
dest = int(self.memory[self.pc + 3])
if cmp(param0, param1):
self.uop_write(dest, 1, dest_mode)
else:
self.uop_write(dest, 0, dest_mode)
return self.pc + 4
#-OPCODES-----------------------------
def op_add(self, modes):
arg0_mode = self.try_pop_mode(modes)
arg1_mode = self.try_pop_mode(modes)
dest_mode = self.try_pop_mode(modes)
arg0_raw = int(self.memory[self.pc + 1])
arg1_raw = int(self.memory[self.pc + 2])
dest = int(self.memory[self.pc + 3])
arg0 = self.uop_read(arg0_raw, arg0_mode)
arg1 = self.uop_read(arg1_raw, arg1_mode)
self.uop_write(dest, str(int(arg0) + int(arg1)), dest_mode)
return self.pc + 4
def op_mul(self, modes):
arg0_mode = self.try_pop_mode(modes)
arg1_mode = self.try_pop_mode(modes)
dest_mode = self.try_pop_mode(modes)
arg0_raw = int(self.memory[self.pc + 1])
arg1_raw = int(self.memory[self.pc + 2])
dest = int(self.memory[self.pc + 3])
arg0 = self.uop_read(arg0_raw, arg0_mode)
arg1 = self.uop_read(arg1_raw, arg1_mode)
self.uop_write(dest, str(int(arg0) * int(arg1)), dest_mode)
return self.pc + 4
def op_read(self, modes):
dest_mode = self.try_pop_mode(modes)
dest = int(self.memory[self.pc + 1])
# if the input buffer is empty, we should "stall" and
# resume later
if not self.input_buffer:
self.stalled = True
return self.pc
val = self.input_buffer.pop()
self.uop_write(dest, str(val), dest_mode)
return self.pc + 2
def op_write(self, modes):
src_mode = self.try_pop_mode(modes)
src_raw = int(self.memory[self.pc + 1])
src = self.uop_read(src_raw, src_mode)
self.output_buffer.append(src)
return self.pc + 2
def op_jump_true(self, modes):
return self.uop_cond_jump(modes, lambda x: x != 0)
def op_jump_false(self, modes):
return self.uop_cond_jump(modes, lambda x: x == 0)
def op_lt(self, modes):
return self.uop_cmp(modes, lambda x, y: x < y)
def op_eq(self, modes):
return self.uop_cmp(modes, lambda x, y: x == y)
def op_rebase(self, modes):
param_mode = self.try_pop_mode(modes)
param_raw = int(self.memory[self.pc + 1])
param = self.uop_read(param_raw, param_mode)
self.offset += param
return self.pc + 2
raw_code = open("puzzle_input/day11.txt").read()
code = raw_code.split(",")
turn_left = 0
turn_right = 1
color_black = 0
color_white = 1
direction_up = (0, 1)
direction_right = (1, 0)
direction_down = (0, -1)
direction_left = (-1, 0)
def find_next_direction(current_direction, turn):
if current_direction == direction_up:
if turn == turn_left:
return direction_left
else:
return direction_right
elif current_direction == direction_right:
if turn == turn_left:
return direction_up
else:
return direction_down
elif current_direction == direction_down:
if turn == turn_left:
return direction_right
else:
return direction_left
elif current_direction == direction_left:
if turn == turn_left:
return direction_down
else:
return direction_up
raise Exception(f"Could not determine next direction, {current_direction} is not valid")
assert direction_up == find_next_direction(direction_right, turn_left)
assert direction_up == find_next_direction(direction_left, turn_right)
assert direction_down == find_next_direction(direction_right, turn_right)
assert direction_down == find_next_direction(direction_left, turn_left)
assert direction_left == find_next_direction(direction_up, turn_left)
assert direction_left == find_next_direction(direction_down, turn_right)
assert direction_right == find_next_direction(direction_up, turn_right)
assert direction_right == find_next_direction(direction_down, turn_left)
def next_position(current_position, current_direction, turn):
current_x, current_y = current_position
next_direction = find_next_direction(current_direction, turn)
move_x, move_y = next_direction
next_position = (current_x + move_x, current_y + move_y)
return (next_position, next_direction)
assert (-1, 0) == next_position((0, 0), direction_up, turn_left)[0]
assert ( 1, 0) == next_position((0, 0), direction_up, turn_right)[0]
assert ( 1, 0) == next_position((0, 0), direction_down, turn_left)[0]
assert (-1, 0) == next_position((0, 0), direction_down, turn_right)[0]
assert ( 0, -1) == next_position((0, 0), direction_left, turn_left)[0]
assert ( 0, 1) == next_position((0, 0), direction_left, turn_right)[0]
assert ( 0, 1) == next_position((0, 0), direction_right, turn_left)[0]
assert ( 0, -1) == next_position((0, 0), direction_right, turn_right)[0]
def parse_output_instructions(outputs):
instructions = []
while outputs:
color = outputs.pop(0)
turn = outputs.pop(0)
instructions.append((color, turn))
return instructions
def color_at_position(painted_panels, position):
if position not in painted_panels:
return color_black
return painted_panels[position]
def solve(starting_color):
cpu = IntCodeCpu(code)
input_buffer = [starting_color]
output_buffer = []
cpu.start(input_buffer, output_buffer)
current_direction = direction_up
current_position = (0, 0)
painted_panels = {}
while cpu.stalled:
output_instructions = parse_output_instructions(output_buffer)
for color, turn in output_instructions:
painted_panels[current_position] = color
(current_position, current_direction) = next_position(current_position, current_direction, turn)
input_buffer.append(color_at_position(painted_panels, current_position))
cpu.run()
return painted_panels
print(len(solve(color_black)))
1863
from PIL import Image, ImageDraw
from IPython.display import Image as IPythonImage
from IPython.display import display
panels = solve(color_white)
min_x = min(x for (x,y) in panels if panels[(x,y)])
max_x = max(x for (x,y) in panels if panels[(x,y)])
min_y = min(y for (x,y) in panels if panels[(x,y)])
max_y = max(y for (x,y) in panels if panels[(x,y)])
offset_x = 0 - min_x
offset_y = 0 - min_y
img = Image.new("RGB", (max_y + offset_y + 20, max_x + offset_x + 20), "black")
draw = ImageDraw.Draw(img)
color_lookup = {
0: "black",
1: "white"
}
for point in panels:
x, y = point
color = panels[point]
draw.point((y + offset_y + 10, x + offset_x + 10), fill=color_lookup[color])
img.save('img/day11.png')
display(IPythonImage(url="./img/day11.png"))
