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

— Day 2: 1202 Program Alarm (Part 1) —

So I’ve realised that it’s taking me far longer to write these blog posts than to actually solve the puzzles so far – and I’m never going to catch up with the most recent puzzles if I spend too long making these blog posts as well! So I’m going to try and be a bit briefer on stuff already covered in Day 1 Part 1 and Day 1 Part 2 – like setting up the test files.

So the first thing I did was take the provided inputs and place them into input files as before and create a new test file. In this part it looks like we are creating a sort of computer so I’ve called my class ElfComputer. I’ve also adopted the Day#Part# terminology for folders rather than puzzle#.

/src/day2/ElfComputer.php

<?php

namespace PuzzleSolvers\Day2;

use PuzzleSolvers\PuzzleSolver;

class ElfComputer extends PuzzleSolver
{
    public function run()
    {
    }
}

/tests/Day2Part1Test.php

<?php

use PHPUnit\Framework\TestCase;
use PuzzleSolvers\Day2\ElfComputer;

final class Puzzle1Part2Test extends TestCase
{
    public function testInputs(): 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 ElfComputer('day2/part1/' . $inputFileNumber);
            $puzzleSolver->run();
            $this->assertSame($output, $puzzleSolver->getOutput());
        }
    }
}

I’ve also updated the make tests command to use --testdox and --debug as I think this will be more useful going forward

Makefile

.PHONY: tests
tests:
	composer dump-autoload
	./vendor/phpunit/phpunit/phpunit --testdox --debug tests

So now we have some failing tests lets look at the requirements and see if we can break the problem down.

It looks like there are a few main concepts

  • program – which is an array of integers
  • position – which points at a specific part of a program
  • opcodes – which defines a type of action to perform

Step 1 – initialise the program and position

So lets start by loading the input we receive into the initial program and set the initial position to 0. I wrote a test first:

public function testInitialiseLoadsInputToProgramAndSetsPositionTo0(): void
{
    $elfComputer = new ElfComputer('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());
}

Now make to make the test pass I tried:

private $program;
private $position;

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

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

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

This was almost correct – except we’re doing strict type checking on the elements of the program array as integers in the test and we are getting strings instead.

   │ Failed asserting that two arrays are identical.
   │ --- Expected
   │ +++ Actual
   │ @@ @@
   │  Array &0 (
   │ -    0 => 1
   │ -    1 => 9
   │ -    2 => 10
   │ -    3 => 3
   │ -    4 => 2
   │ -    5 => 3
   │ -    6 => 11
   │ -    7 => 0
   │ -    8 => 99
   │ -    9 => 30
   │ -    10 => 40
   │ -    11 => 50
   │ +    0 => '1'
   │ +    1 => '9'
   │ +    2 => '10'
   │ +    3 => '3'
   │ +    4 => '2'
   │ +    5 => '3'
   │ +    6 => '11'
   │ +    7 => '0'
   │ +    8 => '99'
   │ +    9 => '30'
   │ +    10 => '40'
   │ +    11 => '50'
   │  )

So we need to map all the elements to integers which I did using array_map()

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

We now have a passing test 🙂

✔ Initialise loads input to program and sets position to 0

Step 2 – loop through the program and read opcodes

First I wanted to add two basic functions to read values at a given position or at current position with an optional offset. So I wrote the tests first using file 0 as input:

public function testReadMemory(): void
{
    $elfComputer = new ElfComputer('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 ElfComputer('day2/part1/0');
    $elfComputer->initialise();
    $elfComputer->setPosition(1);

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

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

Then make them pass

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 setPosition(int $position): void
{
    $this->position = $position;
}

So next we want to implement the loop to read from memory through the program

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

        $this->position++;
    }
}

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

Running make tests showed that we broke our initial test testInputs and introduced an error

Puzzle1 Part2
 ✘ Inputs
   │
   │ count(): Parameter must be an array or an object that implements Countable
   │
   │ /home/hamish/sites/adventofcode2019/src/day2/ElfComputer.php:30
   │ /home/hamish/sites/adventofcode2019/src/day2/ElfComputer.php:20
   │ /home/hamish/sites/adventofcode2019/tests/Day2Part1Test.php:19

This is because we are not calling initialise() on the elfComputer

foreach ($outputs as $inputFileNumber => $output) {
    $puzzleSolver = new ElfComputer('day2/part1/' . $inputFileNumber);
    $puzzleSolver->initialise();
    $puzzleSolver->run();
    $this->assertSame($output, $puzzleSolver->getOutput());
}

Step 3 – execute operations

So the next step is to start reading opcodes and executing them – this should start to make some of our basic test inputs pass to validate addition and multiplication

At this point I realised it would be useful to have some write operations to match our read operations so I created 2 more tests:

public function testWriteMemory(): void
{
    $elfComputer = new ElfComputer('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 ElfComputer('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]);
}

And make them pass

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

We are given 3 opcodes

  • 1 – add
  • 2 – multiply
  • 99 – exit

The input example in file 1

1,0,0,0,99&nbsp;becomes&nbsp;<em>2</em>,0,0,0,99&nbsp;(1 + 1 = 2)

provides a functional test for the add operation.

So let’s just try and implement the operation

Opcode 1 adds together numbers read from two positions and stores the result in a third position. The three integers immediately after the opcode tell you these three positions – the first two indicate the positions from which you should read the input values, and the third indicates the position at which the output should be stored.

public function execute(int $opcode)
{
    if ($opcode === 1) {
        $value = $this->readMemoryOffset(1) + $this->readMemoryOffset(2);
        $this->writeMemory($value, 3);
    }
}

At this point I realised that we aren’t setting the output correctly at the conclusion of the program. So I updated the run() function as follows:

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

        $this->position++;
    }

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

Running tests again I can see that we’re getting close now. Although I’ve decided that the testInputs function is not actually clear enough as to which inputs are passing and which are failing – I’ll probably look at that in the next part…

Puzzle1 Part2
 ✘ Inputs
   │
   │ Failed asserting that two strings are identical.
   │ --- Expected
   │ +++ Actual
   │ @@ @@
   │ -'3500,9,10,70,2,3,11,0,99,30,40,50'
   │ +'1,9,10,19,2,3,11,0,99,30,40,50'

Next I implemented the multiply operation which is basically the same as 1 but with multiplication:

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

At this point after still having failing tests I realised I’ve made a mistake – my code is writing to position 3 every time – rather than reading the value at position offset 3 and then using that as the new position to write to. Here’s the fix:

public function execute(int $opcode)
{
    if ($opcode === 1) {
        $value = $this->readMemoryOffset(1) + $this->readMemoryOffset(2);
        $this->writeMemory($value, $this->readMemoryOffset(3));
    }

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

Running tests again I can see that I still haven’t got it right. I need to read the description more closely!

Opcode 1 adds together numbers read from two positions and stores the result in a third position. The three integers immediately after the opcode tell you these three positions – the first two indicate the positions from which you should read the input values, and the third indicates the position at which the output should be stored.

Again the key bit there is “the first two indicate the positions from which you should read the input values”. Currently we’re just reading them as actual values to be added. Ok so let’s try again:

public function execute(int $opcode)
{
    if ($opcode === 1) {
        $operand1Position = $this->readMemoryOffset(1);
        $operand2Position = $this->readMemoryOffset(2);
        $value = $this->readMemory($operand1Position) + $this->readMemory($operand2Position);
        $this->writeMemory($value, $this->readMemoryOffset(3));
    }

    if ($opcode === 2) {
        $operand1Position = $this->readMemoryOffset(1);
        $operand2Position = $this->readMemoryOffset(2);
        $value = $this->readMemory($operand1Position) * $this->readMemory($operand2Position);
        $this->writeMemory($value, $this->readMemoryOffset(3));
    }
}

OK finally we’re getting close. The above code could be condensed down to something like

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

But I prefer to keep it a bit more human-readable!

Finally lets add opcode 99 which just causes an early exit

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

make tests is now succeeding for everything except the last example

   │ Failed asserting that two strings are identical.
   │ --- Expected
   │ +++ Actual
   │ @@ @@
   │ -'30,1,1,4,2,5,6,0,99'
   │ +'30,1,3,4,2,5,6,0,99'

There’s still one major function of the program which we haven’t implemented yet – and it’s kind of amazing that the programs have been successful so far…

Once you’re done processing an opcode, move to the next one by stepping forward 4 positions.

So we’re currently iterating over every element in the program and executing it as if it were a valid opcode position! So let’s move up by 4 positions instead of 1 after execution:

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

        $this->position += 4;
    }

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

And voila! make tests are green.

But while tests are green there is catch in the final part of the puzzle

before running the program, replace position 1 with the value 12 and replace position 2 with the value 2What value is left at position 0 after the program halts?

So let’s get our real test input file, save it to /day2/part1/input.txt

1,0,0,3,1,1,2,3,1,3,4,3,1,5,0,3,2,6,1,19,1,19,10,23,2,13,23,27,1,5,27,31,2,6,31,35,1,6,35,39,2,39,9,43,1,5,43,47,1,13,47,51,1,10,51,55,2,55,10,59,2,10,59,63,1,9,63,67,2,67,13,71,1,71,6,75,2,6,75,79,1,5,79,83,2,83,9,87,1,6,87,91,2,91,6,95,1,95,6,99,2,99,13,103,1,6,103,107,1,2,107,111,1,111,9,0,99,2,14,0,0

Let’s create a basic solve.php script and modify it slightly to get the answer exactly as requested. Using our solve.php script from Day 1 Part 1 gives:

/src/day2/solve.php

<?php

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

use PuzzleSolvers\Day2\ElfComputer;

$elfComputer = new ElfComputer('day2/part1/input.txt');
$elfComputer->run();
echo "Day 2 Part 1 answer: " . $elfComputer->getOutput() . "\n";

So how do we modify the above to get the precise answer:

<?php

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

use PuzzleSolvers\Day2\ElfComputer;

$elfComputer = new ElfComputer('day2/part1/input.txt');
$elfComputer->initialise();
$elfComputer->writeMemory(12, 1);
$elfComputer->writeMemory(2, 2);
$elfComputer->run();
$output = $elfComputer->getProgram();

echo "Day 2 Part 1 answer: " . $output[0] . "\n";

Note that I’m using getProgram() – which returns an array – rather than getOutput() – which returns a string.

Let’s get that gold star!

$ php src/day2/solve.php 
Day 2 Part 1 answer: 4138687

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

Next up: Day 2 Part 2

Leave a comment

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