2019-12-19

# Day 19: Tractor Beam

Description:
--- Day 19: Tractor Beam ---

Unsure of the state of Santa's ship, you borrowed the tractor beam technology from Triton. Time to test it out.

When you're safely away from anything else, you activate the tractor beam, but nothing happens. It's hard to tell whether it's working if there's nothing to use it on. Fortunately, your ship's drone system can be configured to deploy a drone to specific coordinates and then check whether it's being pulled. There's even an Intcode program (your puzzle input) that gives you access to the drone system.

The program uses two input instructions to request the X and Y position to which the drone should be deployed. Negative numbers are invalid and will confuse the drone; all numbers should be zero or positive.

Then, the program will output whether the drone is stationary (0) or being pulled by something (1). For example, the coordinate X=0, Y=0 is directly in front of the tractor beam emitter, so the drone control program will always report 1 at that location.

To better understand the tractor beam, it is important to get a good picture of the beam itself. For example, suppose you scan the 10x10 grid of points closest to the emitter:

X
0-> 9
0#.........
|.#........
v..##......
...###....
....###...
Y .....####.
......####
......####
.......###
9........##

In this example, the number of points affected by the tractor beam in the 10x10 area closest to the emitter is 27.

However, you'll need to scan a larger area to understand the shape of the beam. How many points are affected by the tractor beam in the 50x50 area closest to the emitter? (For each of X and Y, this will be 0 through 49.)

--- Part Two ---

You aren't sure how large Santa's ship is. You aren't even sure if you'll need to use this thing on Santa's ship, but it doesn't hurt to be prepared. You figure Santa's ship might fit in a 100x100 square.

The beam gets wider as it travels away from the emitter; you'll need to be a minimum distance away to fit a square of that size into the beam fully. (Don't rotate the square; it should be aligned to the same axes as the drone grid.)

For example, suppose you have the following tractor beam readings:

#.......................................
.#......................................
..##....................................
...###..................................
....###.................................
.....####...............................
......#####.............................
......######............................
.......#######..........................
........########........................
.........#########......................
..........#########.....................
...........##########...................
...........############.................
............############................
.............#############..............
..............##############............
...............###############..........
................###############.........
................#################.......
.................########OOOOOOOOOO.....
..................#######OOOOOOOOOO#....
...................######OOOOOOOOOO###..
....................#####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
.....................####OOOOOOOOOO#####
......................###OOOOOOOOOO#####
.......................##OOOOOOOOOO#####
........................#OOOOOOOOOO#####
.........................OOOOOOOOOO#####
..........................##############
..........................##############
...........................#############
............................############
.............................###########

In this example, the 10x10 square closest to the emitter that fits entirely within the tractor beam has been marked O. Within it, the point closest to the emitter (the only highlighted O) is at X=25, Y=20.

Find the 100x100 square closest to the emitter that fits entirely within the tractor beam; within that square, find the point closest to the emitter. What value do you get if you take that point's X coordinate, multiply it by 10000, then add the point's Y coordinate? (In the example above, this would be 250020.)

Input:
109,424,203,1,21102,1,11,0,1105,1,282,21102,1,18,0,1105,1,259,2102,1,1,221,203,1,21101,31,0,0,1105,1,282,21101,38,0,0,1105,1,259,20102,1,23,2,21201,1,0,3,21102,1,1,1,21101,57,0,0,1106,0,303,2101,0,1,222,20101,0,221,3,21001,221,0,2,21101,259,0,1,21101,80,0,0,1106,0,225,21102,1,97,2,21102,1,91,0,1105,1,303,1201,1,0,223,20102,1,222,4,21101,259,0,3,21101,225,0,2,21102,1,225,1,21102,1,118,0,1106,0,225,21001,222,0,3,21102,1,21,2,21102,133,1,0,1106,0,303,21202,1,-1,1,22001,223,1,1,21101,0,148,0,1105,1,259,1201,1,0,223,20101,0,221,4,21001,222,0,3,21101,14,0,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,195,0,0,106,0,109,20207,1,223,2,20102,1,23,1,21102,-1,1,3,21101,0,214,0,1106,0,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,2101,0,-4,249,21201,-3,0,1,21202,-2,1,2,21201,-1,0,3,21101,0,250,0,1106,0,225,22101,0,1,-4,109,-5,2105,1,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2105,1,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,21202,-2,1,-2,109,-3,2105,1,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,22102,1,-2,3,21101,0,343,0,1105,1,303,1105,1,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,22101,0,-4,1,21102,1,384,0,1106,0,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21202,1,1,-4,109,-5,2106,0,0

Part 1:
``````namespace AdventOfCode2019_19_1
{
const DAY     = 19;
const PROBLEM = 1;

export async function run()
{
if (input == null) return;

const code = input.trim().split(",").map(p => parseInt(p.trim()));

let sum = 0;
let out = "";
for(let y=0; y<50; y++)
{
for(let x=0; x<50; x++)
{
let rnr = new Interpreter(code, [x, y]);
rnr.fullRun();
if (rnr.output[0] === 0)
{
out += ".";
}
else if (rnr.output[0] === 1)
{
out += "#";
sum += 1;
}
}
out += "\n";
}

}

class Interpreter
{
program: InfMem;
inputqueue: number[];
instructionpointer: number;
output: number[];
relative_base: number;

is_halted: boolean = false;

constructor(prog: number[], input: number[])
{
this.program = new InfMem(prog);
this.inputqueue = input;
this.instructionpointer = 0;
this.output = [];
this.relative_base = 0;
}

fullRun() : number[]
{
while(!this.is_halted)
{
const r = this.singleStep();

if (r === StepResult.EXECUTED) continue;
if (r === StepResult.HALTED) return this.output;
if (r === StepResult.WAITING_FOR_IN) throw "not enough input";

throw "unknown output of singleStep";
}

return this.output;
}

autoRun() : StepResult
{
while(!this.is_halted)
{
const r = this.singleStep();

if (r === StepResult.EXECUTED) continue;
if (r === StepResult.HALTED) return StepResult.HALTED;
if (r === StepResult.WAITING_FOR_IN) return StepResult.WAITING_FOR_IN;

throw "unknown output of singleStep";
}

return StepResult.HALTED;
}

singleStep() : StepResult
{
const cmd = new Op(this.program.r(this.instructionpointer));

{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 + p1;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.MUL)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 * p1;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.HALT)
{
this.is_halted = true;
return StepResult.HALTED;
}
else if (cmd.opcode == OpCode.IN)
{
if (this.inputqueue.length == 0) return StepResult.WAITING_FOR_IN;

const pv = this.inputqueue[0];
cmd.setParameter(this, 0, pv);
this.inputqueue = this.inputqueue.slice(1);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.OUT)
{
const p0 = cmd.getParameter(this, 0);
this.output.push(p0);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.TJMP)
{
const p0 = cmd.getParameter(this, 0);
if (p0 != 0) this.instructionpointer = cmd.getParameter(this, 1);
else this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.FJMP)
{
const p0 = cmd.getParameter(this, 0);
if (p0 == 0) this.instructionpointer = cmd.getParameter(this, 1);
else this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.LT)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 < p1 ? 1 : 0;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.EQ)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 == p1 ? 1 : 0;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.ARB)
{
const p0 = cmd.getParameter(this, 0);
this.relative_base = this.relative_base+p0;

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else throw "Unknown Op: " + cmd.opcode + " @ " + this.instructionpointer;
}

private incInstrPtr(cmd: Op)
{
this.instructionpointer += 1 + cmd.parametercount;
}
}

enum StepResult { EXECUTED, HALTED, WAITING_FOR_IN }

enum OpCode
{
MUL  = 2,
IN   = 3,
OUT  = 4,
TJMP = 5,
FJMP = 6,
LT   = 7,
EQ   = 8,
ARB  = 9,
HALT = 99,
}

enum ParamMode
{
POSITION_MODE  = 0,
IMMEDIATE_MODE = 1,
RELATIVE_MODE  = 2,
}

class Op
{
opcode: OpCode;
modes: ParamMode[];

name: string;
parametercount: number;

constructor(v: number)
{
this.opcode = v%100;
v = Math.floor(v/100);
this.modes = [];
for(let i=0; i<4; i++)
{
this.modes.push(v%10);
v = Math.floor(v/10);
}

else if (this.opcode == OpCode.MUL)  { this.name="MUL";   this.parametercount=3; }
else if (this.opcode == OpCode.HALT) { this.name="HALT";  this.parametercount=0; }
else if (this.opcode == OpCode.IN)   { this.name="IN";    this.parametercount=1; }
else if (this.opcode == OpCode.OUT)  { this.name="OUT";   this.parametercount=1; }
else if (this.opcode == OpCode.TJMP) { this.name="TJMP";  this.parametercount=2; }
else if (this.opcode == OpCode.FJMP) { this.name="FJMP";  this.parametercount=2; }
else if (this.opcode == OpCode.LT)   { this.name="LT";    this.parametercount=3; }
else if (this.opcode == OpCode.EQ)   { this.name="EQ";    this.parametercount=3; }
else if (this.opcode == OpCode.ARB)  { this.name="ARB";   this.parametercount=1; }
else throw "Unknown opcode: "+this.opcode;
}

getParameter(proc: Interpreter, index: number): number
{
const prog = proc.program;
const ip   = proc.instructionpointer;

let p = prog.r(ip+1+index);

if (this.modes[index] == ParamMode.POSITION_MODE)  p = prog.r(p);
else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) p = p;
else if (this.modes[index] == ParamMode.RELATIVE_MODE)  p = prog.r(proc.relative_base+p);
else throw "Unknown ParamMode: "+this.modes[index];

return p;
}

setParameter(proc: Interpreter, index: number, value: number): void
{
const prog = proc.program;
const ip   = proc.instructionpointer;

let p = prog.r(ip+1+index);

if (this.modes[index] == ParamMode.POSITION_MODE)  prog.w(p, value);
else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) throw "Immediate mode not allowed in write";
else if (this.modes[index] == ParamMode.RELATIVE_MODE)  prog.w(proc.relative_base+p, value);
else throw "Unknown ParamMode: "+this.modes[index];
}
}

class InfMem
{
private data: { [_:number]:number } = {};

constructor(v: number[])
{
for(let i=0; i<v.length;i++) this.data[i]=v[i];
}

r(pos: number): number
{
if (!(pos in this.data)) this.data[pos] = 0;
return this.data[pos];
}

w(pos: number, val: number): number
{
return this.data[pos] = val;
}
}
}
``````
Result: 181

Part 2:
``````namespace AdventOfCode2019_19_2
{
const DAY     = 19;
const PROBLEM = 2;

export async function run()
{
if (input == null) return;

const code = input.trim().split(",").map(p => parseInt(p.trim()));

const RECT_LEN = 100;

let grid: {[_:number]: boolean} = {};

let lout = [];

for(let y=0; y<10; y++)
{
let out = "";
for(let x=0; x<50; x++)
{
let rnr = new Interpreter(code, [x, y]); rnr.fullRun();
if (rnr.output[0] === 0) out += " ";
else if (rnr.output[0] === 1) out += "#";
}
out = out.trimEnd();
out = out.replace(/ /g, ".");
lout.push(out);
}

let xstart = 0;
for(let y=10;; y++)
{
let out = "";
let xsum = 0;
for(let x=xstart;; x++)
{
let rnr = new Interpreter(code, [x, y]);
rnr.fullRun();

if (rnr.output[0] === 0)
{
if (xsum===0)xstart=x;
out += ".";
grid[y*100000+x]=false;
}
else if (rnr.output[0] === 1)
{
out += "#";
xsum += 1;
grid[y*100000+x]=true;

if (xsum>=RECT_LEN)
{
const ibr = (y)*100000+(x);
const ibl = (y)*100000+(x-RECT_LEN+1);
const itr = (y-RECT_LEN+1)*100000+(x);
const itl = (y-RECT_LEN+1)*100000+(x-RECT_LEN+1);

const br = ibr in grid && grid[ibr];
const bl = ibl in grid && grid[ibl];
const tr = itr in grid && grid[itr];
const tl = itl in grid && grid[itl];

if (br && bl && tr && tl)
{
lout.push(out);
if (lout.length>128) lout.shift();

//let fstr = "";
//for (let yy=0; yy<=y+1; yy++)
//{
//	for (let xx=0; xx<=x+1; xx++)
//	{
//		let iidd = yy*100000+xx;
//		let trac = iidd in grid && grid[iidd];
//		let ship = (xx >= (x-RECT_LEN+1)) &&
//				   (xx <= (x)) &&
//				   (yy >= (y-RECT_LEN+1)) &&
//				   (yy <= (y));
//		if (!trac) fstr += ".";
//		else if (ship) fstr += "O";
//		else fstr += "#";
//	}
//	fstr += "\n";
//}

return;
}
}
}

if (xsum>0 && rnr.output[0] === 0) break;
}
lout.push(out);
if (lout.length>100) lout.shift();
}
}

class Interpreter
{
program: InfMem;
inputqueue: number[];
instructionpointer: number;
output: number[];
relative_base: number;

is_halted: boolean = false;

constructor(prog: number[], input: number[])
{
this.program = new InfMem(prog);
this.inputqueue = input;
this.instructionpointer = 0;
this.output = [];
this.relative_base = 0;
}

fullRun() : number[]
{
while(!this.is_halted)
{
const r = this.singleStep();

if (r === StepResult.EXECUTED) continue;
if (r === StepResult.HALTED) return this.output;
if (r === StepResult.WAITING_FOR_IN) throw "not enough input";

throw "unknown output of singleStep";
}

return this.output;
}

autoRun() : StepResult
{
while(!this.is_halted)
{
const r = this.singleStep();

if (r === StepResult.EXECUTED) continue;
if (r === StepResult.HALTED) return StepResult.HALTED;
if (r === StepResult.WAITING_FOR_IN) return StepResult.WAITING_FOR_IN;

throw "unknown output of singleStep";
}

return StepResult.HALTED;
}

singleStep() : StepResult
{
const cmd = new Op(this.program.r(this.instructionpointer));

{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 + p1;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.MUL)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 * p1;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.HALT)
{
this.is_halted = true;
return StepResult.HALTED;
}
else if (cmd.opcode == OpCode.IN)
{
if (this.inputqueue.length == 0) return StepResult.WAITING_FOR_IN;

const pv = this.inputqueue[0];
cmd.setParameter(this, 0, pv);
this.inputqueue = this.inputqueue.slice(1);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.OUT)
{
const p0 = cmd.getParameter(this, 0);
this.output.push(p0);

this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.TJMP)
{
const p0 = cmd.getParameter(this, 0);
if (p0 != 0) this.instructionpointer = cmd.getParameter(this, 1);
else this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.FJMP)
{
const p0 = cmd.getParameter(this, 0);
if (p0 == 0) this.instructionpointer = cmd.getParameter(this, 1);
else this.incInstrPtr(cmd);

return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.LT)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 < p1 ? 1 : 0;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.EQ)
{
const p0 = cmd.getParameter(this, 0);
const p1 = cmd.getParameter(this, 1);
const pv = p0 == p1 ? 1 : 0;
cmd.setParameter(this, 2, pv);

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else if (cmd.opcode == OpCode.ARB)
{
const p0 = cmd.getParameter(this, 0);
this.relative_base = this.relative_base+p0;

this.incInstrPtr(cmd);
return StepResult.EXECUTED;
}
else throw "Unknown Op: " + cmd.opcode + " @ " + this.instructionpointer;
}

private incInstrPtr(cmd: Op)
{
this.instructionpointer += 1 + cmd.parametercount;
}
}

enum StepResult { EXECUTED, HALTED, WAITING_FOR_IN }

enum OpCode
{
MUL  = 2,
IN   = 3,
OUT  = 4,
TJMP = 5,
FJMP = 6,
LT   = 7,
EQ   = 8,
ARB  = 9,
HALT = 99,
}

enum ParamMode
{
POSITION_MODE  = 0,
IMMEDIATE_MODE = 1,
RELATIVE_MODE  = 2,
}

class Op
{
opcode: OpCode;
modes: ParamMode[];

name: string;
parametercount: number;

constructor(v: number)
{
this.opcode = v%100;
v = Math.floor(v/100);
this.modes = [];
for(let i=0; i<4; i++)
{
this.modes.push(v%10);
v = Math.floor(v/10);
}

else if (this.opcode == OpCode.MUL)  { this.name="MUL";   this.parametercount=3; }
else if (this.opcode == OpCode.HALT) { this.name="HALT";  this.parametercount=0; }
else if (this.opcode == OpCode.IN)   { this.name="IN";    this.parametercount=1; }
else if (this.opcode == OpCode.OUT)  { this.name="OUT";   this.parametercount=1; }
else if (this.opcode == OpCode.TJMP) { this.name="TJMP";  this.parametercount=2; }
else if (this.opcode == OpCode.FJMP) { this.name="FJMP";  this.parametercount=2; }
else if (this.opcode == OpCode.LT)   { this.name="LT";    this.parametercount=3; }
else if (this.opcode == OpCode.EQ)   { this.name="EQ";    this.parametercount=3; }
else if (this.opcode == OpCode.ARB)  { this.name="ARB";   this.parametercount=1; }
else throw "Unknown opcode: "+this.opcode;
}

getParameter(proc: Interpreter, index: number): number
{
const prog = proc.program;
const ip   = proc.instructionpointer;

let p = prog.r(ip+1+index);

if (this.modes[index] == ParamMode.POSITION_MODE)  p = prog.r(p);
else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) p = p;
else if (this.modes[index] == ParamMode.RELATIVE_MODE)  p = prog.r(proc.relative_base+p);
else throw "Unknown ParamMode: "+this.modes[index];

return p;
}

setParameter(proc: Interpreter, index: number, value: number): void
{
const prog = proc.program;
const ip   = proc.instructionpointer;

let p = prog.r(ip+1+index);

if (this.modes[index] == ParamMode.POSITION_MODE)  prog.w(p, value);
else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) throw "Immediate mode not allowed in write";
else if (this.modes[index] == ParamMode.RELATIVE_MODE)  prog.w(proc.relative_base+p, value);
else throw "Unknown ParamMode: "+this.modes[index];
}
}

class InfMem
{
private data: { [_:number]:number } = {};

constructor(v: number[])
{
for(let i=0; i<v.length;i++) this.data[i]=v[i];
}

r(pos: number): number
{
if (!(pos in this.data)) this.data[pos] = 0;
return this.data[pos];
}

w(pos: number, val: number): number
{
return this.data[pos] = val;
}
}
}
``````
Result: 4240964

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript