Amplification Circuit


Fork me on GitHub
2019-12-07

Day 07: Amplification Circuit

Description:
--- Day 7: Amplification Circuit ---

Based on the navigational maps, you're going to need to send more power to your ship's thrusters to reach Santa in time. To do this, you'll need to configure a series of amplifiers already installed on the ship.

There are five amplifiers connected in series; each one receives an input signal and produces an output signal. They are connected such that the first amplifier's output leads to the second amplifier's input, the second amplifier's output leads to the third amplifier's input, and so on. The first amplifier's input value is 0, and the last amplifier's output leads to your ship's thrusters.

O-------O O-------O O-------O O-------O O-------O
0 ->| Amp A |->| Amp B |->| Amp C |->| Amp D |->| Amp E |-> (to thrusters)
O-------O O-------O O-------O O-------O O-------O

The Elves have sent you some Amplifier Controller Software (your puzzle input), a program that should run on your existing Intcode computer. Each amplifier will need to run a copy of the program.

When a copy of the program starts running on an amplifier, it will first use an input instruction to ask the amplifier for its current phase setting (an integer from 0 to 4). Each phase setting is used exactly once, but the Elves can't remember which amplifier needs which phase setting.

The program will then call another input instruction to get the amplifier's input signal, compute the correct output signal, and supply it back to the amplifier with an output instruction. (If the amplifier has not yet received an input signal, it waits until one arrives.)

Your job is to find the largest output signal that can be sent to the thrusters by trying every possible combination of phase settings on the amplifiers. Make sure that memory is not shared or reused between copies of the program.

For example, suppose you want to try the phase setting sequence 3,1,2,4,0, which would mean setting amplifier A to phase setting 3, amplifier B to setting 1, C to 2, D to 4, and E to 0. Then, you could determine the output signal that gets sent from amplifier E to the thrusters with the following steps:

Start the copy of the amplifier controller software that will run on amplifier A. At its first input instruction, provide it the amplifier's phase setting, 3. At its second input instruction, provide it the input signal, 0. After some calculations, it will use an output instruction to indicate the amplifier's output signal.
Start the software for amplifier B. Provide it the phase setting (1) and then whatever output signal was produced from amplifier A. It will then produce a new output signal destined for amplifier C.
Start the software for amplifier C, provide the phase setting (2) and the value from amplifier B, then collect its output signal.
Run amplifier D's software, provide the phase setting (4) and input value, and collect its output signal.
Run amplifier E's software, provide the phase setting (0) and input value, and collect its output signal.

The final output signal from amplifier E would be sent to the thrusters. However, this phase setting sequence may not have been the best one; another sequence might have sent a higher signal to the thrusters.

Here are some example programs:

Max thruster signal 43210 (from phase setting sequence 4,3,2,1,0):

3,15,3,16,1002,16,10,16,1,16,15,15,4,15,99,0,0

Max thruster signal 54321 (from phase setting sequence 0,1,2,3,4):

3,23,3,24,1002,24,10,24,1002,23,-1,23,
101,5,23,23,1,24,23,23,4,23,99,0,0

Max thruster signal 65210 (from phase setting sequence 1,0,4,3,2):

3,31,3,32,1002,32,10,32,1001,31,-2,31,1007,31,0,33,
1002,33,7,33,1,33,31,31,1,32,31,31,4,31,99,0,0,0

Try every combination of phase settings on the amplifiers. What is the highest signal that can be sent to the thrusters?

--- Part Two ---

It's no good - in this configuration, the amplifiers can't generate a large enough output signal to produce the thrust you'll need. The Elves quickly talk you through rewiring the amplifiers into a feedback loop:

O-------O O-------O O-------O O-------O O-------O
0 -+->| Amp A |->| Amp B |->| Amp C |->| Amp D |->| Amp E |-.
| O-------O O-------O O-------O O-------O O-------O |
| |
'--------------------------------------------------------+
|
v
(to thrusters)

Most of the amplifiers are connected as they were before; amplifier A's output is connected to amplifier B's input, and so on. However, the output from amplifier E is now connected into amplifier A's input. This creates the feedback loop: the signal will be sent through the amplifiers many times.

In feedback loop mode, the amplifiers need totally different phase settings: integers from 5 to 9, again each used exactly once. These settings will cause the Amplifier Controller Software to repeatedly take input and produce output many times before halting. Provide each amplifier its phase setting at its first input instruction; all further input/output instructions are for signals.

Don't restart the Amplifier Controller Software on any amplifier during this process. Each one should continue receiving and sending signals until it halts.

All signals sent or received in this process will be between pairs of amplifiers except the very first signal and the very last signal. To start the process, a 0 signal is sent to amplifier A's input exactly once.

Eventually, the software on the amplifiers will halt after they have processed the final loop. When this happens, the last output signal from amplifier E is sent to the thrusters. Your job is to find the largest output signal that can be sent to the thrusters using the new phase settings and feedback loop arrangement.

Here are some example programs:

Max thruster signal 139629729 (from phase setting sequence 9,8,7,6,5):

3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,
27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5

Max thruster signal 18216 (from phase setting sequence 9,7,8,5,6):

3,52,1001,52,-5,52,3,53,1,52,56,54,1007,54,5,55,1005,55,26,1001,54,
-5,54,1105,1,12,1,53,54,53,1008,54,0,55,1001,55,1,55,2,53,55,53,4,
53,1001,56,-1,56,1005,56,6,99,0,0,0,0,10

Try every combination of the new phase settings on the amplifier feedback loop. What is the highest signal that can be sent to the thrusters?

Input:
3,8,1001,8,10,8,105,1,0,0,21,46,67,88,101,126,207,288,369,450,99999,3,9,1001,9,5,9,1002,9,5,9,1001,9,5,9,102,3,9,9,101,2,9,9,4,9,99,3,9,102,4,9,9,101,5,9,9,102,5,9,9,101,3,9,9,4,9,99,3,9,1001,9,3,9,102,2,9,9,1001,9,5,9,102,4,9,9,4,9,99,3,9,102,3,9,9,1001,9,4,9,4,9,99,3,9,102,3,9,9,1001,9,3,9,1002,9,2,9,101,4,9,9,102,3,9,9,4,9,99,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,99,3,9,101,1,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,99,3,9,101,1,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,1,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,99,3,9,101,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,101,1,9,9,4,9,3,9,101,1,9,9,4,9,99,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,99

Part 1:
namespace AdventOfCode2019_07_1
{
	const DAY     = 7;
	const PROBLEM = 1;

	export async function run()
	{
		let input = await AdventOfCode.getInput(DAY);
		if (input == null) return;

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

		let outputs = [];

		for(let i=0; i < 5*5*5*5*5; i++)
		{
			let v = i;
			let a1 = v%5; v = Math.floor(v/5);
			let a2 = v%5; v = Math.floor(v/5);
			let a3 = v%5; v = Math.floor(v/5);
			let a4 = v%5; v = Math.floor(v/5);
			let a5 = v%5; v = Math.floor(v/5);

			if ([a1,a2,a3,a4,a5].sort((a, b) => a - b).filter((v,i,s) => s.indexOf(v)===i).length !== 5) continue;

			const runner1 = new Interpreter(code, [a1, 0]);
			runner1.run();

			const runner2 = new Interpreter(code, [a2, runner1.output[0]]);
			runner2.run();

			const runner3 = new Interpreter(code, [a3, runner2.output[0]]);
			runner3.run();

			const runner4 = new Interpreter(code, [a4, runner3.output[0]]);
			runner4.run();

			const runner5 = new Interpreter(code, [a5, runner4.output[0]]);
			runner5.run();
			
			outputs.push(runner5.output[0]);
			AdventOfCode.outputConsole([a1,a2,a3,a4,a5].toString() + "  -->  " + runner1.output[0] + " |> " + runner2.output[0] + " |> " + runner3.output[0] + " |> " + runner4.output[0] + " |> " + runner5.output[0]);
		}

		const max = outputs.sort((a, b) => a - b).reverse()[0];

		AdventOfCode.output(DAY, PROBLEM, max.toString());
	}

	class Interpreter
	{
		program: number[];
		input: number[];
		instructionpointer: number;
		inputpointer: number;
		output: number[];

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

		run()
		{
			while(true)
			{
				const cmd = new Op(this.program[this.instructionpointer]);
				let ipinc = true;

				if (cmd.opcode == OpCode.ADD)
				{
					const p0 = cmd.getParameter(this, 0);
					const p1 = cmd.getParameter(this, 1);
					const pv = p0 + p1;
					cmd.setParameter(this, 2, pv);
				}
				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);
				}
				else if (cmd.opcode == OpCode.HALT)
				{
					return;
				}
				else if (cmd.opcode == OpCode.IN)
				{
					const pv = this.input[this.inputpointer];
					cmd.setParameter(this, 0, pv);
					this.inputpointer++;
				}
				else if (cmd.opcode == OpCode.OUT)
				{
					const p0 = cmd.getParameter(this, 0);
					this.output.push(p0);
					//AdventOfCode.outputConsole("# " + p0);
				}
				else if (cmd.opcode == OpCode.TJMP)
				{
					const p0 = cmd.getParameter(this, 0);
					if (p0 != 0) { this.instructionpointer = cmd.getParameter(this, 1); ipinc=false; }
				}
				else if (cmd.opcode == OpCode.FJMP)
				{
					const p0 = cmd.getParameter(this, 0);
					if (p0 == 0) { this.instructionpointer = cmd.getParameter(this, 1); ipinc=false; }
				}
				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);
				}
				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);
				}
				else throw "Unknown Op: " + cmd.opcode + " @ " + this.instructionpointer;

				if (ipinc) this.instructionpointer += 1 + cmd.parametercount;
			}
		}
	}

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

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

	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);
			}

			     if (this.opcode == OpCode.ADD)  { this.name="ADD";   this.parametercount=3; }
			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 throw "Unknown opcode: "+this.opcode;
		}

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

			let p = prog[ip+1+index];

				 if (this.modes[index] == ParamMode.POSITION_MODE)  p = prog[p];
			else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) p = 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[ip+1+index];

				 if (this.modes[index] == ParamMode.POSITION_MODE)  prog[p] = value;
			else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) throw "Immediate mode not allowed in write";
			else throw "Unknown ParamMpde: "+this.modes[index];
		}
	}
}
Result: 844468

Part 2:
namespace AdventOfCode2019_07_2
{
	const DAY     = 7;
	const PROBLEM = 2;

	export async function run()
	{
		let input = await AdventOfCode.getInput(DAY);
		if (input == null) return;

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

		let outputs: number[] = [];

		for(let i=0; i < 5*5*5*5*5; i++)
		{
			let v = i;
			let a1 = v%5 + 5; v = Math.floor(v/5);
			let a2 = v%5 + 5; v = Math.floor(v/5);
			let a3 = v%5 + 5; v = Math.floor(v/5);
			let a4 = v%5 + 5; v = Math.floor(v/5);
			let a5 = v%5 + 5; v = Math.floor(v/5);

			if ([a1,a2,a3,a4,a5].sort((a, b) => a - b).filter((v,i,s) => s.indexOf(v)===i).length !== 5) continue;

			const r = evalConfiguration(code, a1,a2,a3,a4,a5)
			
			outputs.push(r);
			AdventOfCode.outputConsole([a1,a2,a3,a4,a5].toString() + "  -->  " + r);
		}

		const max = outputs.sort((a, b) => a - b).reverse()[0];

		AdventOfCode.output(DAY, PROBLEM, max.toString());
	}

	function evalConfiguration(code: number[], a1 : number, a2 : number, a3 : number, a4 : number, a5 : number) : number
	{
		const runner1 = new Interpreter(code, [a1, 0]);
		const runner2 = new Interpreter(code, [a2]);
		const runner3 = new Interpreter(code, [a3]);
		const runner4 = new Interpreter(code, [a4]);
		const runner5 = new Interpreter(code, [a5]);

		let optr1 = 0;
		let optr2 = 0;
		let optr3 = 0;
		let optr4 = 0;
		let optr5 = 0;

		while (!runner5.is_halted)
		{
			runner1.singleStep();
			if (runner1.output.length > optr1)
			{
				runner2.inputqueue.push(runner1.output[optr1]); 
				optr1++; 
			}

			runner2.singleStep();
			if (runner2.output.length > optr2)
			{ 
				runner3.inputqueue.push(runner2.output[optr2]); 
				optr2++; 
			}

			runner3.singleStep();
			if (runner3.output.length > optr3)
			{ 
				runner4.inputqueue.push(runner3.output[optr3]); 
				optr3++; 
			}

			runner4.singleStep();
			if (runner4.output.length > optr4)
			{ 
				runner5.inputqueue.push(runner4.output[optr4]); 
				optr4++; 
			}

			runner5.singleStep();
			if (runner5.output.length > optr5)
			{
				runner1.inputqueue.push(runner5.output[optr5]);
				optr5++;
			}
		}

		return runner5.output.reverse()[0];
	}

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

		is_halted: boolean = false;

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

		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;
		}

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

			if (cmd.opcode == OpCode.ADD)
			{
				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 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 
	{
		ADD  = 1,
		MUL  = 2,
		IN   = 3,
		OUT  = 4,
		TJMP = 5,
		FJMP = 6,
		LT   = 7,
		EQ   = 8,
		HALT = 99,
	}

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

	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);
			}

			     if (this.opcode == OpCode.ADD)  { this.name="ADD";   this.parametercount=3; }
			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 throw "Unknown opcode: "+this.opcode;
		}

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

			let p = prog[ip+1+index];

				 if (this.modes[index] == ParamMode.POSITION_MODE)  p = prog[p];
			else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) p = 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[ip+1+index];

				 if (this.modes[index] == ParamMode.POSITION_MODE)  prog[p] = value;
			else if (this.modes[index] == ParamMode.IMMEDIATE_MODE) throw "Immediate mode not allowed in write";
			else throw "Unknown ParamMpde: "+this.modes[index];
		}
	}
}
Result: 4215746


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