Day 15: Oxygen System

Of course, the nature of this problem makes it possible to search manually, which I seriously considered before deciding to actually do coding.

We're going to make the robot BFS the graph.

In particular, to make the robot go to any previously explored position, we essentially make the computer replay all the moves that got the robot to that position. This is less memory intensive than storing the exact computer state at that position (which would also work), but does mean that we're executing a lot more instructions.

Once we have the ability to set the robot in an arbitrary position, we just use a queue to explore positions and be careful to deal with the robot's output properly.

In particular, we keep our own graph representation with walls and distances from the start (which thanks to BFS is always the shortest) and always try to visit new nodes in BFS order until we can't (or until we find the oxygen tank).

Once done, output the distance from the oxygen tank.

Other than that, most of the code is already done Part 1 and now we don't even need to deal with the robot.

Just BFS the full graph from the oxygen tank with a new distance array, and return the greatest distance from that.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<int,int> ii;
typedef vector<ll> vl;
class Comp {
	vl w,oc;
	queue<ll> ins,outs;
	ll reb;
	ll pc;
	bool term;
	public:
	Comp() {
	}
	Comp(vl init) {
		oc = init;
		w = oc;
		w.resize(1000000);
		term = false;
		reb = 0;
		pc = 0;
	}
	void feed(ll val) {
		ins.push(val);
	}
	bool empty_ins() {
		return ins.empty();
	}
	bool empty_outs() {
		return outs.empty();
	}
	ll poll() {
		ll res = outs.front();
		outs.pop();
		return res;
	}
	void reset(){
		w = oc;
		term = false;
		pc = 0;
		reb = 0;
		ins = queue<ll>();
		outs = queue<ll>();
	}
	ll get(ll id) {
		return w[id];
	}
	bool run() {
		while(!term) {
			if(pc >= w.size()) {
				term = true;
				cout << "dropout termination\n";
				return term;
			}
			ll raw = w[pc];
			ll id = w[pc];
			if(id == 99) {
				term = true;
				return term;
			}
			ll params = id/100;
			id %= 100;
			ll pr[3];
			for(int i=0;i<3;i++) {
				pr[i] = (params%10);
				params /= 10;
			}
			ll pt[3] = {-1,-1,-1};
			ll nx[3] = {-1,-1,-1};
			for(int i=0;i<3;i++) {
				if(i+pc+1 >= w.size()) {
					break;
				} else {
					pt[i] = nx[i] = w[i+pc+1];
					if(pr[i] == 0) {
						if(nx[i] < w.size()) {
							nx[i] = w[nx[i]];
						} else {
						}
					} else if(pr[i] == 2) {
						pt[i] += reb;
						if(nx[i]+reb < w.size()) {
							nx[i] = w[nx[i]+reb];
						} else {
						}
					} else {
						//immediate mode
					}
				}
			}
			if(id == 3) {
				if(ins.empty()) {
					return false;
				}
				ll val = ins.front();
				ins.pop();
				w[pt[0]] = val;
				pc += 2;
			} else if(id == 4) {
				outs.push(nx[0]);
				pc += 2;
			} else if(id == 5) {
				if(nx[0] != 0) {
					pc = nx[1];
				} else {
					pc += 3;
				}
			} else if(id == 6) {
				if(nx[0] == 0) {
					pc = nx[1];
				} else {
					pc += 3;
				}
			} else if(id == 7) {
				nx[2] = pt[2];
				if(nx[0] < nx[1]) {
					w[nx[2]] = 1;
				} else {
					w[nx[2]] = 0;
				}
				pc += 4;
			} else if(id == 8) {
				nx[2] = pt[2];
				if(nx[0] == nx[1]) {
					w[nx[2]] = 1;
				} else {
					w[nx[2]] = 0;
				}
				pc += 4;
			} else if(id == 1) {
				nx[2] = pt[2];
				w[nx[2]] = nx[0]+nx[1];
				pc += 4;
			} else if(id == 2) {
				nx[2] = pt[2];
				//cout << nx[0] << " * " << nx[1] << '\n';
				w[nx[2]] = nx[0]*nx[1];
				pc += 4;
			} else if(id == 9) {
				reb += nx[0];
				pc += 2;
			} else {
				return false;
			}
		}
		return term;
	}
	void flush() {
		outs = queue<ll>();
	}
	bool done() {
		return term;
	}
};
vl x;
void input() {
	string s;
	cin >> s;
	ll t = 0;
	ll sgn = 1;
	for(int i=0;i<s.size();i++) {
		if(s[i] == ',') {
			x.push_back(t*sgn);
			t = 0;
			sgn = 1;
		} else if(s[i] == '-') {
			sgn *= -1;
		} else {
			t *= 10;
			t += (s[i]-'0');
		}
	}
	x.push_back(t);
}
const int dy[4] = {1,-1,0,0};
const int dx[4] = {0,0,-1,1};
set<ii> wall;
map<ii,int> dist,pt,dist2;
int rev(int dir) {
	return dir^1;
}
int main() {
	ii co = {0,0};
	ii st = {0,0};
	bool fd = false;
	ii wo = {-1,-1};
	input();
	Comp C(x);
	dist[co] = 0;
	queue<ii> q;
	q.push(co);
	while(!q.empty()) {
		ii po = q.front();
		q.pop();
		C.reset();
		vi nav;
		ii re = po;
		while(re != st) {
			nav.push_back(pt[re]);
			int a = dx[pt[re]];
			int b = dy[pt[re]];
			re.first -= a;
			re.second -= b;
		}
		for(int i=nav.size()-1;i>=0;i--) {
			C.feed(nav[i]+1);
		}
		C.run();
		while(!C.empty_outs()) {C.poll();}
		for(int i=0;i<4;i++) {
			ii u = {po.first+dx[i],po.second+dy[i]};
			if(dist.find(u) != dist.end()) {continue;}
			if(wall.find(u) != wall.end()) {continue;}
			C.feed(i+1);
			C.run();
			int res = C.poll();
			if(res == 0) {
				wall.insert(u);
			} else {
				dist[u] = dist[po]+1;
				pt[u] = i;
				q.push(u);
				if(res == 2) {
					fd = true;
					wo = u;
				}
				C.feed(rev(i)+1);
				C.run();
				while(!C.empty_outs()) {C.poll();}
			}
		}
	}
	q = queue<ii>();
	q.push(wo);
	dist2[wo] = 0;
	int ma = 0;
	while(!q.empty()) {
		ii po = q.front();
		q.pop();
		for(int i=0;i<4;i++) {
			ii u = {po.first+dx[i],po.second+dy[i]};
			if(dist2.find(u) != dist2.end()) {continue;}
			if(wall.find(u) != wall.end()) {continue;}
			dist2[u] = dist2[po]+1;
			ma = max(ma,dist2[u]);
			q.push(u);
		}
	}
	cout << "Part 1 solution: " << dist[wo] << '\n';
	cout << "Part 2 solution: " << ma << '\n';
}

I spent a bunch of time on setting up mapping display and interactivity which ended up being kind of waste, if rather entertaining.

Wandering around manually, I quickly noticed that the map was all single-tile corridors, so a naive "keep the wall on the left" approach would probably get me somewhere interesting eventually. It wasn't too difficult to write a function to have the robot check a direction and then return back to its original position if it actually succeeded in moving forward.

Sticking to the left wall, my robot quickly found the goal, but its path was apparently sub-optimal, so I needed to explore more. I set the robot to just keep exploring in the same manner, building up a map as it goes. In my case I just had it stop after 3k steps, but I'm sure a more elegant solution is possible.

Once you have the map, the actual solutions are quite straightforward graph problems: A* from the start to the station, then flood-fill from the station and count the steps.

#!/usr/bin/env crystal
require "../lib/utils.cr"
require "../lib/vm2.cr"

class Droid
  property cpu : VM2::VM

  property x : Int32
  property y : Int32
  property facing : Int64

  property move_count : Int32
  property start_pos : Tuple(Int32,Int32)
  property station : Tuple(Int32, Int32)

  property map : Hash(Tuple(Int32, Int32), Int32)

  DIRS = {
    0 => { 0, 0},
    1 => { 0,-1},
    2 => { 0, 1},
    3 => {-1, 0},
    4 => { 1, 0}
  }

  def initialize(cpu, curses = false)
    @cpu = cpu
    @x, @y = 0, 0
    @last_move = 0
    @move_count = 0
    @state = :ok
    @facing = 4
    @station = {-1,-1}
    @map = Hash(Tuple(Int32, Int32), Int32).new { |h,k| h[k] = 9 }
    @start_pos = {@x,@y}
  end

  def coords_facing(dir)
    d = DIRS[dir]
    {@x+d[0],@y+d[1]}
  end

  def right_from(facing)
    case facing
    when 1 then 4_i64
    when 2 then 3_i64
    when 3 then 1_i64
    when 4 then 2_i64
    else raise "bad dir"
    end
  end

  def left_from(facing)
    case facing
    when 1 then 3_i64
    when 2 then 4_i64
    when 3 then 2_i64
    when 4 then 1_i64
    else raise "bad dir"
    end
  end

  def check_dir(d)
    @cpu.send_input(d)
    @cpu.run
    res = @cpu.read_output
    case res
    when 1 # space ok, move back to where we started
      reverse = right_from(right_from(d))
      @cpu.send_input(reverse)
      @cpu.run
      raise "COULDN'T BACKTRACK !" if @cpu.read_output != 1
      :ok
    when 0 # wall
      :wall
    when 2 # station
      :station
    else raise "got bad output from cpu"
    end
  end

  def try_forward
    nx,ny = coords_facing(@facing)
    @cpu.send_input(@facing)
    @cpu.run
    res = @cpu.read_output
    case res
    when 1
      @map[{@x,@y}] = 1
      @x, @y = nx, ny
      @move_count += 1
      :ok
    when 0
      @map[{nx,ny}] = 9
      :wall
    when 2
      @map[{nx,ny}] = 0
      @station = {nx,ny}
      @x, @y = nx, ny
      :station
    else raise "got bad output form cpu"
    end
  end

  def turn_left
    @facing = left_from(@facing)
  end

  def turn_right
    @facing = right_from(@facing)
  end

  def run
    state = :look
    while true
      case state
      when :move
        state = :look
        nx,ny = coords_facing(@facing)
        case try_forward
        when :ok
        when :wall
          turn_right
        when :station
          #break
        end
      when :look
        state = :move
        lx,ly = coords_facing(left_from(@facing))
        d = left_from(@facing)
        case check_dir(d)
        when :ok
          @map[{lx,ly}] = 1
          turn_left
        when :wall # go forward
          @map[{lx,ly}] = 9
        when :station # end
          @map[{lx,ly}] = 0
        end
      end

      # 3k should be enough to map anything
      break if @move_count > 3000
    end
  end
end

# Extract map
prog = Utils.get_input_file(Utils.cli_param_or_default(0, "day15/input.txt"))
droid = Droid.new(VM2.from_string(prog))
droid.run

map = droid.map

# Use A* to map from droid.start_pos to droid.station

alias Pos = Tuple(Int32, Int32)

start = droid.start_pos
station = droid.station
solution = [] of Pos

visited = Set(Pos).new
open = [{start, [] of Pos, 1}]

def dist(a,b)
  Math.sqrt( (a[0]-b[0])*(a[0]-b[0]) + ((a[1]-b[1])*(a[1]-b[1])) )
end

def neighbors(loc) : Array(Pos)
  x,y = loc
  [{x-1,y}, {x+1,y}, {x,y+1}, {x, y-1}]
end

#puts "Start search..."

while !open.empty?
  loc, route, cost = open.pop
  next if visited.includes? loc

  new_route = [route, loc].flatten
  if loc == station
    solution = new_route.flatten
    break
  end

  visited.add(loc)

  neighbors(loc).each do |neighbor|
    next if map[neighbor]? == 9 || visited.includes? neighbor
    tile_cost = map[neighbor]? || 99
    new_cost = cost + tile_cost
    open << {neighbor, new_route, new_cost}
  end

  open = open.sort_by { |_,_,cost| cost }
end

puts "P1: %i" % (solution.size-1)

# Flood fill from station, count the steps

open = [station]
visited = Set(Pos).new
steps = 0

while !open.empty?
  frontier = [] of Pos
  open.each do |loc|
    next if visited.includes? loc
    visited.add(loc)
    neighbors(loc).each do |neighbor|
      frontier << neighbor if map[neighbor] == 1
    end
  end

  open = frontier
  steps += 1
end

puts "P2: %i" % (steps-2) # account for initial expand and final check

class Intputer(object):

    def __init__(self, instructions, pointer=0, relative_base=0, output_block=False):

        self.instructions = instructions
        self.pointer = pointer
        self.relative_base = relative_base
        self.curr_instruction = [int(num) for num in str(self.instructions[self.pointer])]
        self.output_block = output_block
        self.output_buffer = []
        self.input_buffer = []
        self.block = False
        self.isHalted = False

    def get_operands(self):
        for i in range(5 - len(self.curr_instruction)):
            self.curr_instruction.insert(0,0) # Pad to get the right number of 0s

        if self.curr_instruction[0] == 0:
            out_location = self.instructions[self.pointer + 3]
        elif self.curr_instruction[0] == 2:
            out_location = self.instructions[self.pointer + 3] + self.relative_base
        else:
            raise ValueError("Incorrect mode for output operand!")

        if self.curr_instruction[1] == 0:
            op_2_location = self.instructions[self.pointer+2]
        elif self.curr_instruction[1] == 1:
            op_2_location = self.pointer + 2
        elif self.curr_instruction[1] == 2:
            op_2_location = self.instructions[self.pointer+2] + self.relative_base
        else:
            raise ValueError("Incorrect mode for second operand!")

        if self.curr_instruction[2] == 0:
            op_1_location = self.instructions[self.pointer+1]
        elif self.curr_instruction[2] == 1:
            op_1_location = self.pointer + 1
        elif self.curr_instruction[2] == 2:
            op_1_location = self.instructions[self.pointer+1] + self.relative_base
        else:
            raise ValueError("Incorrect mode for first operand!")

        # We handle big memory on write, so this covers it on read
        try:
            op_1 = self.instructions[op_1_location]
        except IndexError:
            op_1 = 0

        try:
            op_2 = self.instructions[op_2_location]
        except IndexError:
            op_2 = 0

        return [op_1, op_2, out_location]

    def get_io_operand(self):

        for i in range(3 - len(self.curr_instruction)):
            self.curr_instruction.insert(0,0) # Pad to get the right number of 0s

        if self.curr_instruction[0] == 0:
            op = self.instructions[self.pointer + 1]
        elif self.curr_instruction[0] == 1:
            op = self.pointer + 1
        elif self.curr_instruction[0] == 2:
            op = self.instructions[self.pointer + 1] + self.relative_base
        else:
            raise ValueError("Incorrect mode for I/O operand!")

        return op

    def write_result(self, result, location):

        # Extend memory if needed
        try:
            self.instructions[location] = result
        except IndexError:
            self.instructions.extend([0] * ((location + 1) - len(self.instructions)))
            self.instructions[location] = result

    def add_instruction(self):
        operands = self.get_operands()

        result = operands[0] + operands[1]
        self.write_result(result, operands[2])
        self.pointer += 4

    def mult_instruction(self):
        operands = self.get_operands()

        result = operands[0] * operands[1]
        self.write_result(result, operands[2])
        self.pointer += 4

    def output_instruction(self):

        operand = self.get_io_operand()

        self.output_buffer.append(self.instructions[operand])

        if self.output_block:
            self.block = True

        self.pointer += 2

    def input_instruction(self):

        # Check for no input, and block if input is empty
        if len(self.input_buffer) < 1:
            self.block = True
            return

        operand = self.get_io_operand()

        self.write_result(self.input_buffer.pop(), operand)
        self.pointer += 2

    def jump_instruction(self, jump_type):

        operands = self.get_operands()

        if ((operands[0] and jump_type) or (not operands[0] and not jump_type)):
            self.pointer = operands[1]
        else:
            self.pointer += 3

    def less_than_instruction(self):

        operands = self.get_operands()

        if operands[0] < operands[1]:
            self.write_result(1, operands[2])
        else:
            self.write_result(0, operands[2])

        self.pointer += 4

    def equals_instruction(self):

        operands = self.get_operands()

        if operands[0] == operands[1]:
            self.write_result(1, operands[2])
        else:
            self.write_result(0, operands[2])

        self.pointer += 4

    def modify_base_instruction(self):

        operand = self.get_io_operand()

        self.relative_base += self.instructions[operand]

        self.pointer += 2

    def process_instructions(self, inputs=None):

        if inputs is not None:
            try:
                for item in inputs:
                    self.input_buffer.insert(0, item)
            except TypeError: # Catch singular inputs here
                self.input_buffer.insert(0,inputs)
        else:
            inputs = []

        while True:

            if self.pointer > (len(self.instructions) - 1):
                break
            elif self.instructions[self.pointer] == 99:
                self.isHalted = True
                break

            self.curr_instruction = [int(num) for num in str(self.instructions[self.pointer])]

            if self.curr_instruction[-1] == 1:
                self.add_instruction()
            elif self.curr_instruction[-1] == 2:
                self.mult_instruction()
            elif self.curr_instruction[-1] == 3:
                self.input_instruction()
            elif self.curr_instruction[-1] == 4:
                self.output_instruction()
            elif self.curr_instruction[-1] == 5:
                self.jump_instruction(True)
            elif self.curr_instruction[-1] == 6:
                self.jump_instruction(False)
            elif self.curr_instruction[-1] == 7:
                self.less_than_instruction()
            elif self.curr_instruction[-1] == 8:
                self.equals_instruction()
            elif self.curr_instruction[-1] == 9:
                self.modify_base_instruction()

            if self.block:
                self.block = False
                return

    def clear_output_buffer(self):
        self.output_buffer = []

def load_instructions(input_file):

    with open(input_file, 'r') as fid:
        data = fid.readline()

    instructions = data.strip().split(',')

    for idx in range(len(instructions)):
        instructions[idx] = int(instructions[idx])

    return instructions

import random
import copy
import Intputer

class RepairBot(object):

    def __init__(self, brain_instructions):

        self.brain = Intputer.Intputer(copy.copy(brain_instructions))
        self.initial_instructions = copy.copy(brain_instructions)
        self.location = [0, 0]
        self.map = {}
        self.map[tuple(self.location)] = 1
        self.move_history = []

    def reinitialize_brain(self):

        self.brain = Intputer.Intputer(copy.copy(self.initial_instructions))

    def move(self, direction):

        self.brain.process_instructions(direction)
        change_location = True
        if self.brain.output_buffer[-1] == 0:
            change_location = False

        new_location = copy.copy(self.location)

        if direction == 1:
             new_location[0] += 1
        elif direction == 2:
            new_location[0] -= 1
        elif direction == 3:
            new_location[1] -= 1
        elif direction == 4:
            new_location[1] += 1

        self.map[tuple(new_location)] = self.brain.output_buffer[-1]
        self.brain.clear_output_buffer()

        if change_location:
            self.location = new_location


    def find_valid_moves(self):
        valids = []
        locations = [(self.location[0]+1, self.location[1]),
                     (self.location[0]-1, self.location[1]),
                     (self.location[0], self.location[1]-1),
                     (self.location[0], self.location[1]+1)]

        for idx in range(4):

            try:
                if self.map[tuple(locations[idx])] == 1:
                    valids.append(idx + 1)
            except KeyError:
                # We don't need to do things just if there isn't anything in
                # there it's okay, but maybe we can move there?
                valids.append(idx + 1)

        return valids

    # This is admittedly the stupid way but I guess I'm stupid today
    def find_ox_sys(self):
        preferred_direction = 1

        while True:

            print(len(self.map))
            if 2 in self.map.values() and len(self.map) > 1656:
                return

            valid_moves = self.find_valid_moves()

            self.move(random.choice(valid_moves))

    def path_to_ox(self):

        wavefront_map = {}
        ox_location = list(self.map.keys())[list(self.map.values()).index(2)]
        wavefront_map[ox_location] = 0

        while (0,0) not in wavefront_map.keys():

            wavefront_keys = list(wavefront_map.keys())

            for curr_location in wavefront_keys:
                possible_locations = [(curr_location[0]+1, curr_location[1]),
                                      (curr_location[0]-1, curr_location[1]),
                                      (curr_location[0], curr_location[1]-1),
                                      (curr_location[0], curr_location[1]+1)]

                for possible_location in possible_locations:
                    if (possible_location in self.map.keys()
                        and self.map[possible_location] != 0
                        and possible_location not in wavefront_map.keys()):
                        wavefront_map[possible_location] = wavefront_map[curr_location] + 1

        return wavefront_map[(0,0)]

    def ox_time(self):

        wavefront_map = {}
        ox_location = list(self.map.keys())[list(self.map.values()).index(2)]
        wavefront_map[ox_location] = 0

        while True:
            old_len = len(wavefront_map)

            wavefront_keys = list(wavefront_map.keys())

            for curr_location in wavefront_keys:
                possible_locations = [(curr_location[0]+1, curr_location[1]),
                                      (curr_location[0]-1, curr_location[1]),
                                      (curr_location[0], curr_location[1]-1),
                                      (curr_location[0], curr_location[1]+1)]

                for possible_location in possible_locations:
                    if (possible_location in self.map.keys()
                        and self.map[possible_location] != 0
                        and possible_location not in wavefront_map.keys()):
                        wavefront_map[possible_location] = wavefront_map[curr_location] + 1

            new_len = len(wavefront_map)

            if new_len <= old_len:
                break

        return max(wavefront_map.values())

import Intputer
import RepairBot
import copy

input_file = "PuzzleInput.txt"
instructions = Intputer.load_instructions(input_file)
repair_bot = RepairBot.RepairBot(copy.copy(instructions))

repair_bot.find_ox_sys()
length = repair_bot.path_to_ox()
print(length)
time = repair_bot.ox_time()
print(time)