Advent of Code 2019 Day 5 (Part 1) PHP Hints

— Day 5: Sunny with a Chance of Asteroids (Part 1) —

Hello – if you’re just visiting this blog for the first time all code can be found on GitHub here. The state of the code at the beginning of this post is release Day4Part2 (as in the end of Day4Part2). You also might like to check out Getting Started – or my solution for Day2Part2 to get up to speed. I hope somebody finds this useful!

So in this puzzle it looks like we’re revisiting the intcode computer from Day 2 – or as I’ve called it the ElfComputer. Judging by the comments on Reddit we’ll be returning to the intcode computer several times… It looks like we’ll be adding operations for inputs and outputs as well as introducing an immediate parameter mode.

Now, your ship computer will also need to handle parameters in mode 1immediate mode. In immediate mode, a parameter is interpreted as a value – if the parameter is 50, its value is simply 50.

So let’s start by creating a new ElfComputer2 which is just a copy from Day 2 Part 2 – as I don’t want to affect my solution from that part. But I will carry forward the end-to-end tests from Part2 to make sure we don’t break them.

/tests/Day5Part1Test.php

<?php

use PHPUnit\Framework\TestCase;
use PuzzleSolvers\Day5\ElfComputer2;

final class Day5Part1Test extends TestCase
{
    public function testDay2EndToEnd(): void
    {
        $outputs = [
            '3500,9,10,70,2,3,11,0,99,30,40,50',
            '2,0,0,0,99',
            '2,3,0,6,99',
            '2,4,4,5,99,9801',
            '30,1,1,4,2,5,6,0,99',
        ];
        foreach ($outputs as $inputFileNumber => $output) {
            $puzzleSolver = new ElfComputer2('day2/part1/' . $inputFileNumber);
            $puzzleSolver->initialise();
            $puzzleSolver->run();
            $this->assertSame($output, $puzzleSolver->getOutput());
        }
    }

    public function testInitialiseLoadsInputToProgramAndSetsPositionTo0(): void
    {
        $elfComputer = new ElfComputer2('day2/part1/0');

        $elfComputer->initialise();

        $this->assertSame([1, 9, 10, 3, 2, 3, 11, 0, 99, 30, 40, 50], $elfComputer->getProgram());
        $this->assertSame(0, $elfComputer->getPosition());
    }

    public function testReadMemory(): void
    {
        $elfComputer = new ElfComputer2('day2/part1/0');
        $elfComputer->initialise();
        $elfComputer->setPosition(1);

        $value0 = $elfComputer->readMemory(0);
        $this->assertSame(1, $value0);

        $value1 = $elfComputer->readMemory();
        $this->assertSame(9, $value1);

        $value2 = $elfComputer->readMemory(2);
        $this->assertSame(10, $value2);
    }

    public function testReadMemoryOffset(): void
    {
        $elfComputer = new ElfComputer2('day2/part1/0');
        $elfComputer->initialise();
        $elfComputer->setPosition(1);

        $value1 = $elfComputer->readMemoryOffset(0);
        $this->assertSame(9, $value1);

        $value3 = $elfComputer->readMemoryOffset(2);
        $this->assertSame(3, $value3);
    }

    public function testWriteMemory(): void
    {
        $elfComputer = new ElfComputer2('day2/part1/0');
        $elfComputer->initialise();
        $elfComputer->setPosition(1);

        $elfComputer->writeMemory(5, 0);
        $elfComputer->writeMemory(42);

        $program = $elfComputer->getProgram();
        $this->assertSame(5, $program[0]);
        $this->assertSame(42, $program[1]);
    }

    public function testWriteMemoryOffset(): void
    {
        $elfComputer = new ElfComputer2('day2/part1/0');
        $elfComputer->initialise();
        $elfComputer->setPosition(1);

        $elfComputer->writeMemoryOffset(5, 2);
        $elfComputer->writeMemoryOffset(42);

        $program = $elfComputer->getProgram();
        $this->assertSame(5, $program[3]);
        $this->assertSame(42, $program[1]);
    }
}

Now let’s create some end-to-end tests for the 3 examples provided in the explanation:

/inputs/day5/0

3,0,4,0,99

/inputs/day5/1

1002,4,3,4,33

/inputs/day5/2

1101,100,-1,4,0
public function testEndToEnd()
{
    $outputs = [
        [42, 0, 4, 0, 99],
        [1002, 4, 3, 4, 99],
        [1101, 100, -1, 4, 99],
    ];
    $programOutput = [
        [42],
        [],
        [],
    ];
    foreach ($outputs as $inputFileNumber => $output) {
        $elfComputer = new ElfComputer2('day5/part1/' . $inputFileNumber);
        $elfComputer->initialise();
        $elfComputer->input = 42;
        $elfComputer->run();

        $this->assertSame($programOutput[$inputFileNumber], $elfComputer->outputs);
        $this->assertSame($outputs[$inputFileNumber], $elfComputer->program);
    }
}

Now in this test I’ve assumed two new properties in the ElfComputer input and outputs. It appears that we can accept 1 input but produce multiple outputs.

Running make tests shows us that this is failing. So let’s try and make the first input sequence 3,0,4,0,99 pass which should take an input 42 and write it to position 0 then output what is at position 0 and halt. So basically take an input and add it to the outputs.

First let’s add the new properties in ElfComputer2. We also need to add an instruction length as these instructions are only 2 integers long. I also decided to just make everything public for convenience…

public $program;
public $position;
public $input;
public $outputs;
public $instructionLength = 4;

Let’s try and add the opcodes for them

if ($opcode == 3) {
    $this->writeMemory($this->input, $this->readMemoryOffset(1));
    $this->instructionLength = 2;
}

if ($opcode == 4) {
    $operand1Position = $this->readMemoryOffset(1);
    $this->outputs[] = $this->readMemory($operand1Position);
    $this->instructionLength = 2;
}

Next we need to increment the position pointer by the instruction length rather than 4:

public function run()
{
    while ($this->position < $this->getProgramSize()) {
        $opcode = $this->readMemory();
        $this->execute($opcode);

        $this->position += $this->instructionLength;
    }

    $this->output = implode(',', $this->program);
}

Now running make tests is passing for our first input file! Looking at the second file 1002,4,3,4,33 we are going to have to implement parameter modes by parsing the instruction. So let’s write a test for this first:

public function testParseInstruction()
{
    $elfComputer = new ElfComputer2('day5/part1/0');
    $parsedInstruction = $elfComputer->parseInstruction('1002');

    $this->assertSame(2, $parsedInstruction['opcode']);
    $this->assertSame(0, $parsedInstruction['mode1']);
    $this->assertSame(1, $parsedInstruction['mode2']);
    $this->assertSame(0, $parsedInstruction['mode3']);
}

the rightmost two digits of the first value, 02, indicate opcode 2, multiplication. Then, going right to left, the parameter modes are 0 (hundreds digit), 1 (thousands digit), and 0 (ten-thousands digit, not present and therefore zero)

Now let’s make that test pass…

public function parseInstruction($instruction)
{
    $parsedInstuction = [];
    $parsedInstuction['opcode'] = (int) substr($instruction, -2, 2);
    $parsedInstuction['mode1'] = (strlen($instruction) > 2) ? (int) substr($instruction, -3, 1) : 0;
    $parsedInstuction['mode2'] = (strlen($instruction) > 3) ? (int) substr($instruction, -4, 1) : 0;
    $parsedInstuction['mode3'] = (strlen($instruction) > 4) ? (int) substr($instruction, -5, 1) : 0;

    return $parsedInstuction;
}
Day5 Part1
 ✘ End to end
   │
   │ Failed asserting that null is identical to Array &0 ().
   │
   │ /home/hamish/sites/adventofcode2019/tests/Day5Part1Test.php:43

Looks like we need to initialise outputs to an empty array:

public function initialise()
{
    $this->position = 0;
    $this->program = array_map('intval', explode(',', $this->inputs[0]));
    $this->outputs = [];
}

Next we need to modify our execute and run function so that we’re dealing with string “instructions” instead of simple opcodes:

public function run()
{
    while ($this->position < $this->getProgramSize()) {
        $instruction = $this->parseInstruction($this->readMemory());
        $this->execute($instruction);

        $this->position += $this->instructionLength;
    }

    $this->output = implode(',', $this->program);
}

...

public function execute($instruction)
{
    $opcode = $instruction['opcode'];

...

Now our test is showing that we’re getting close:

Day5 Part1
 ✘ End to end
   │
   │ Failed asserting that two arrays are identical.
   │ --- Expected
   │ +++ Actual
   │ @@ @@
   │      1 => 4
   │      2 => 3
   │      3 => 4
   │ -    4 => 99
   │ +    4 => 132
   │  )
   

Now we need to modify our opcode execution blocks to respect the parameter modes being passed in the instruction. First I added this function:

public function getParameter(int $offset, int $mode)
{
    $parameter = $this->readMemoryOffset($offset);
    if ($mode == 0) {
        $parameter = $this->readMemory($parameter);
    }

    return $parameter;
}

And then execute becomes:

public function execute($instruction)
{
    $opcode = $instruction['opcode'];

    if ($opcode === 1) {
        $parameter1 = $this->getParameter(1, $instruction['mode1']);
        $parameter2 = $this->getParameter(2, $instruction['mode2']);
        $parameter3 = $this->readMemoryOffset(3);
        $value = $parameter1 + $parameter2;
        $this->writeMemory($value, $parameter3);
        $this->instructionLength = 4;
    }

    if ($opcode === 2) {
        $parameter1 = $this->getParameter(1, $instruction['mode1']);
        $parameter2 = $this->getParameter(2, $instruction['mode2']);
        $parameter3 = $this->readMemoryOffset(3);
        $value = $parameter1 * $parameter2;
        $this->writeMemory($value, $parameter3);
        $this->instructionLength = 4;
    }

    if ($opcode == 3) {
        $this->writeMemory($this->input, $this->readMemoryOffset(1));
        $this->instructionLength = 2;
    }

    if ($opcode == 4) {
        $parameter1 = $this->getParameter(1, $instruction['mode1']);
        $this->outputs[] = $parameter1;
        $this->instructionLength = 2;
    }

    if ($opcode === 99) {
        $this->position = $this->getProgramSize();
    }
}

Note that I added instruction lengths to each opcode and that writeMemory instructions are always in parameter mode. Now let’s run make tests again and hooray – now our end-to-end tests pass as well! Let’s get our puzzle input and write our solve.php script

/src/day5/solve.php

<?php

require_once __DIR__ . '/../../vendor/autoload.php';

use PuzzleSolvers\Day5\ElfComputer2;

$elfComputer = new ElfComputer2('day5/part1/input');
$elfComputer->initialise();
$elfComputer->input = 1;
$elfComputer->run();
$outputs = $elfComputer->outputs;

echo "Day 5 Part 1 answer: " . end($outputs) . "\n";

/inputs/day5/part1/input

3,225,1,225,6,6,1100,1,238,225,104,0,1002,114,46,224,1001,224,-736,224,4,224,1002,223,8,223,1001,224,3,224,1,223,224,223,1,166,195,224,1001,224,-137,224,4,224,102,8,223,223,101,5,224,224,1,223,224,223,1001,169,83,224,1001,224,-90,224,4,224,102,8,223,223,1001,224,2,224,1,224,223,223,101,44,117,224,101,-131,224,224,4,224,1002,223,8,223,101,5,224,224,1,224,223,223,1101,80,17,225,1101,56,51,225,1101,78,89,225,1102,48,16,225,1101,87,78,225,1102,34,33,224,101,-1122,224,224,4,224,1002,223,8,223,101,7,224,224,1,223,224,223,1101,66,53,224,101,-119,224,224,4,224,102,8,223,223,1001,224,5,224,1,223,224,223,1102,51,49,225,1101,7,15,225,2,110,106,224,1001,224,-4539,224,4,224,102,8,223,223,101,3,224,224,1,223,224,223,1102,88,78,225,102,78,101,224,101,-6240,224,224,4,224,1002,223,8,223,101,5,224,224,1,224,223,223,4,223,99,0,0,0,677,0,0,0,0,0,0,0,0,0,0,0,1105,0,99999,1105,227,247,1105,1,99999,1005,227,99999,1005,0,256,1105,1,99999,1106,227,99999,1106,0,265,1105,1,99999,1006,0,99999,1006,227,274,1105,1,99999,1105,1,280,1105,1,99999,1,225,225,225,1101,294,0,0,105,1,0,1105,1,99999,1106,0,300,1105,1,99999,1,225,225,225,1101,314,0,0,106,0,0,1105,1,99999,1107,226,677,224,102,2,223,223,1006,224,329,101,1,223,223,1108,226,677,224,1002,223,2,223,1005,224,344,101,1,223,223,8,226,677,224,102,2,223,223,1006,224,359,1001,223,1,223,1007,226,677,224,1002,223,2,223,1005,224,374,101,1,223,223,1008,677,677,224,1002,223,2,223,1005,224,389,1001,223,1,223,1108,677,226,224,1002,223,2,223,1006,224,404,1001,223,1,223,1007,226,226,224,1002,223,2,223,1005,224,419,1001,223,1,223,1107,677,226,224,1002,223,2,223,1006,224,434,101,1,223,223,108,677,677,224,1002,223,2,223,1005,224,449,1001,223,1,223,1107,677,677,224,102,2,223,223,1005,224,464,1001,223,1,223,108,226,226,224,1002,223,2,223,1006,224,479,1001,223,1,223,1008,226,226,224,102,2,223,223,1005,224,494,101,1,223,223,108,677,226,224,102,2,223,223,1005,224,509,1001,223,1,223,8,677,226,224,1002,223,2,223,1006,224,524,101,1,223,223,7,226,677,224,1002,223,2,223,1006,224,539,101,1,223,223,7,677,226,224,102,2,223,223,1006,224,554,1001,223,1,223,7,226,226,224,1002,223,2,223,1006,224,569,101,1,223,223,107,677,677,224,102,2,223,223,1006,224,584,101,1,223,223,1108,677,677,224,102,2,223,223,1006,224,599,1001,223,1,223,1008,677,226,224,1002,223,2,223,1005,224,614,1001,223,1,223,8,677,677,224,1002,223,2,223,1006,224,629,1001,223,1,223,107,226,677,224,1002,223,2,223,1006,224,644,101,1,223,223,1007,677,677,224,102,2,223,223,1006,224,659,101,1,223,223,107,226,226,224,1002,223,2,223,1006,224,674,1001,223,1,223,4,223,99,226

And here is the final ElfComputer2 Class

<?php

namespace PuzzleSolvers\Day5;

use PuzzleSolvers\PuzzleSolver;

class ElfComputer2 extends PuzzleSolver
{
    public $program;
    public $position;
    public $input;
    public $outputs;
    public $instructionLength = 4;

    public function initialise()
    {
        $this->position = 0;
        $this->program = array_map('intval', explode(',', $this->inputs[0]));
        $this->outputs = [];
    }

    public function run()
    {
        while ($this->position < $this->getProgramSize()) {
            $instruction = $this->parseInstruction($this->readMemory());
            $this->execute($instruction);

            $this->position += $this->instructionLength;
        }

        $this->output = implode(',', $this->program);
    }

    public function parseInstruction($instruction)
    {
        $parsedInstuction = [];
        $parsedInstuction['opcode'] = (int) substr($instruction, -2, 2);
        $parsedInstuction['mode1'] = (strlen($instruction) > 2) ? (int) substr($instruction, -3, 1) : 0;
        $parsedInstuction['mode2'] = (strlen($instruction) > 3) ? (int) substr($instruction, -4, 1) : 0;
        $parsedInstuction['mode3'] = (strlen($instruction) > 4) ? (int) substr($instruction, -5, 1) : 0;

        return $parsedInstuction;
    }

    public function getParameter(int $offset, int $mode)
    {
        $parameter = $this->readMemoryOffset($offset);
        if ($mode == 0) {
            $parameter = $this->readMemory($parameter);
        }

        return $parameter;
    }

    public function execute($instruction)
    {
        $opcode = $instruction['opcode'];

        if ($opcode === 1) {
            $parameter1 = $this->getParameter(1, $instruction['mode1']);
            $parameter2 = $this->getParameter(2, $instruction['mode2']);
            $parameter3 = $this->readMemoryOffset(3);
            $value = $parameter1 + $parameter2;
            $this->writeMemory($value, $parameter3);
            $this->instructionLength = 4;
        }

        if ($opcode === 2) {
            $parameter1 = $this->getParameter(1, $instruction['mode1']);
            $parameter2 = $this->getParameter(2, $instruction['mode2']);
            $parameter3 = $this->readMemoryOffset(3);
            $value = $parameter1 * $parameter2;
            $this->writeMemory($value, $parameter3);
            $this->instructionLength = 4;
        }

        if ($opcode == 3) {
            $this->writeMemory($this->input, $this->readMemoryOffset(1));
            $this->instructionLength = 2;
        }

        if ($opcode == 4) {
            $parameter1 = $this->getParameter(1, $instruction['mode1']);
            $this->outputs[] = $parameter1;
            $this->instructionLength = 2;
        }

        if ($opcode === 99) {
            $this->position = $this->getProgramSize();
        }
    }

    public function getProgramSize(): int
    {
        return count($this->program);
    }

    public function readMemory($position = null)
    {
        if (is_null($position)) {
            $position = $this->position;
        }

        return $this->program[$position];
    }

    public function readMemoryOffset($offset = 0)
    {
        return $this->program[$this->position + $offset];
    }

    public function writeMemoryOffset(int $value, $offset = 0)
    {
        $this->program[$this->position + $offset] = $value;
    }

    public function writeMemory(int $value, $position = null)
    {
        if (is_null($position)) {
            $position = $this->position;
        }
        $this->program[$position] = $value;
    }

    public function getProgram(): array
    {
        return $this->program ?: [];
    }

    public function getPosition(): int
    {
        return $this->position ?: 0;
    }

    public function setPosition(int $position): void
    {
        $this->position = $position;
    }
}

Now let’s get that gold star!

$ php src/day5/solve.php 
Day 5 Part 1 answer: 7692125

The final code for this part can be found on GitHub here. Remember my answer may not be the same as yours for your real input. Make sure to replace your /inputs/day5/part1/input with your own file. Did it work? Let me know!

Next up: Day 5 Part 2

Leave a comment

Your email address will not be published. Required fields are marked *