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

— Day 3: Crossed Wires (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 Day2Part2 (as in the end of Day2Part2). You also might like to check out Getting Started – or my solution for Day2Part1 to get up to speed. I hope somebody finds this useful!

I also created a javascript Visualization for this puzzle here if you’re interested.

Ok, so after reading through this puzzle description I think this looks like quite a fun one. My initial thoughts are to maintain a couple of arrays of coordinates for the wires paths and then use some kind of array intersection to get the path intersections.

So as in previous posts – the first thing I did was to create some end-to-end tests.

/tests/Day3Part1Test.php

<?php

use PHPUnit\Framework\TestCase;
use PuzzleSolvers\Day3\CrossedWiresMeasurer;

final class Day3Part1Test extends TestCase
{
    public function testEndToEnd(): void
    {
        $outputs = [6, 159, 135];
        foreach ($outputs as $inputFileNumber => $output) {
            $puzzleSolver = new CrossedWiresMeasurer('day3/part1/' . $inputFileNumber);
            $puzzleSolver->run();
            $this->assertSame($output, $puzzleSolver->getOutput());
        }
    }
}

And added the relevent input files using the 3 examples to /inputs/day3/part1/

R8,U5,L5,D3
U7,R6,D4,L4
R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83
R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7

Finally I initialised my CrossedWiresMeasurer Class

/src/day3/CrossedWiresMeasurer.php

<?php

namespace PuzzleSolvers\Day3;

use PuzzleSolvers\PuzzleSolver;

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

Now we have some failing tests after running make tests. Hooray!

In this puzzle I decided to add a basic debug class that will send stuff to STDERR which will print on the PHPUnit output. I called it PuzzleDebugger.

/src/PuzzleDebugger.php

<?php

class PuzzleDebugger
{
    public static function print($message)
    {
        if (is_array($message)) {
            $message = print_r($message, true);
        }

        fwrite(STDERR, $message . "\n");
    }
}

So we can add an info message to our testEndToEnd() as to which file is currently running:

/tests/Day3Part1Test.php

<?php

use PHPUnit\Framework\TestCase;
use PuzzleSolvers\Day3\CrossedWiresMeasurer;

final class Day3Part1Test extends TestCase
{
    public function testEndToEnd(): void
    {
        $outputs = [6, 159, 135];
        foreach ($outputs as $inputFileNumber => $output) {
            $inputFile = 'day3/part1/' . $inputFileNumber;
            \PuzzleDebugger::print('TESTING INPUT FILE ' . $inputFile);
            $puzzleSolver = new CrossedWiresMeasurer($inputFile);
            $puzzleSolver->run();
            $this->assertSame($output, $puzzleSolver->getOutput());
        }
    }
}

Ok so now lets start by adding some properties to our main class to track the positions of laid wire.

Each position is going to consist of an x and a y coordinate. Also in the interest of using the array key as a sort of hash of the position I’ll store the key as a string in the format "$x,$y". I don’t think the value of the array actually matters too much for this puzzle? But I’ll just store a 2 element array with an x an y value.

This time I’m just going to make everything public and not worry about setters and getters etc.

<?php

namespace PuzzleSolvers\Day3;

use PuzzleSolvers\PuzzleSolver;

class CrossedWiresMeasurer extends PuzzleSolver
{
    public $wires = [
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ]
        ],
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ]
        ],
    ];

    public function run()
    { }
}

Next I want to write a function which allows us to lay the wire according to the moves U, D, L, R. So first I write a test for the Up move.

/tests/Day3Part1Test.php

public function testLayWireUp()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');

    $crossedWiresMeasurer->layWire(0, 'U');

    $this->assertSame([
        '0,0' => [
            'x' => 0,
            'y' => 0,
        ],
        '0,1' => [
            'x' => 0,
            'y' => 1,
        ],
    ], $crossedWiresMeasurer->wires[0]);
}

Now in my coordinate system y + 1 is up, y - 1 is down, x + 1 is to the right, x -1 is to the left. Now make the test pass.

public function layWire($wireId, $direction)
{
    $wireEndPosition = end($this->wires[$wireId]);

    if ($direction === 'U') {
        $newY = $wireEndPosition['y'] + 1;
        $newX = $wireEndPosition['x'];
    }

    $newPositionKey = $newX . ',' . $newY;

    $this->wires[$wireId][$newPositionKey] = [
        'x' => $newX,
        'y' => $newY,
    ];
}

OK so make tests is now passing for our testLayWireUp

I can see how this could (should?) probably be decomposed into some separate objects. But I’m just going to plow ahead 🙂

Let’s add 3 more tests for laying Down, Right and Left:

public function testLayWireDown()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');

    $crossedWiresMeasurer->layWire(0, 'D');

    $this->assertSame([
        '0,0' => [
            'x' => 0,
            'y' => 0,
        ],
        '0,-1' => [
            'x' => 0,
            'y' => -1,
        ],
    ], $crossedWiresMeasurer->wires[0]);
}

public function testLayWireRight()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');

    $crossedWiresMeasurer->layWire(0, 'R');

    $this->assertSame([
        '0,0' => [
            'x' => 0,
            'y' => 0,
        ],
        '1,0' => [
            'x' => 1,
            'y' => 0,
        ],
    ], $crossedWiresMeasurer->wires[0]);
}

public function testLayWireLeft()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');

    $crossedWiresMeasurer->layWire(0, 'L');

    $this->assertSame([
        '0,0' => [
            'x' => 0,
            'y' => 0,
        ],
        '-1,0' => [
            'x' => -1,
            'y' => 0,
        ],
    ], $crossedWiresMeasurer->wires[0]);
}

And make them pass – this should be fairly straightforward extention of what we had for U:

public function layWire($wireId, $direction)
{
    $wireEndPosition = end($this->wires[$wireId]);

    if ($direction === 'U') {
        $newY = $wireEndPosition['y'] + 1;
        $newX = $wireEndPosition['x'];
    }

    if ($direction === 'D') {
        $newY = $wireEndPosition['y'] - 1;
        $newX = $wireEndPosition['x'];
    }

    if ($direction === 'R') {
        $newY = $wireEndPosition['y'];
        $newX = $wireEndPosition['x'] + 1;
    }

    if ($direction === 'L') {
        $newY = $wireEndPosition['y'];
        $newX = $wireEndPosition['x'] - 1;
    }

    $newPositionKey = $newX . ',' . $newY;

    $this->wires[$wireId][$newPositionKey] = [
        'x' => $newX,
        'y' => $newY,
    ];
}

Cool make tests pass. We’re getting close to laying some cable… The next thing we probably want to do is to specify how far to lay as part of the function. So let’s write a test for laying 2 segments:

public function testLayWireLeft2()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');

    $crossedWiresMeasurer->layWire(0, 'L', 2);

    $this->assertSame([
        '0,0' => [
            'x' => 0,
            'y' => 0,
        ],
        '-1,0' => [
            'x' => -1,
            'y' => 0,
        ],
        '-2,0' => [
            'x' => -2,
            'y' => 0,
        ],
    ], $crossedWiresMeasurer->wires[0]);
}

and then make it pass. Essentially we just want to add for ($i = 0; $i &lt; $length; $i++) { around the whole function and accept an optional new argument. Here is the final function:

public function layWire(int $wireId, string $direction, int $length = 1)
{
    for ($i = 0; $i < $length; $i++) {
        $wireEndPosition = end($this->wires[$wireId]);

        if ($direction === 'U') {
            $newY = $wireEndPosition['y'] + 1;
            $newX = $wireEndPosition['x'];
        }

        if ($direction === 'D') {
            $newY = $wireEndPosition['y'] - 1;
            $newX = $wireEndPosition['x'];
        }

        if ($direction === 'R') {
            $newY = $wireEndPosition['y'];
            $newX = $wireEndPosition['x'] + 1;
        }

        if ($direction === 'L') {
            $newY = $wireEndPosition['y'];
            $newX = $wireEndPosition['x'] - 1;
        }

        $newPositionKey = $newX . ',' . $newY;

        $this->wires[$wireId][$newPositionKey] = [
            'x' => $newX,
            'y' => $newY,
        ];
    }
}

Eventually I realised that there is a bug in this approach were we cannot reliably use end() to get the last point in the wire when it crosses back on itself. So I refactored this by adding a new property:

public $wireEndPoints = [
    [
        'x' => 0,
        'y' => 0,
    ],
    [
        'x' => 0,
        'y' => 0,
    ],
];

And layWire() to:

public function layWire(int $wireId, string $direction, int $length = 1)
{
for ($i = 0; $i < $length; $i++) {
    $wireEndPoint = $this->wireEndPoints[$wireId];

    if ($direction === 'U') {
        $newY = $wireEndPoint['y'] + 1;
        $newX = $wireEndPoint['x'];
    }

    if ($direction === 'D') {
        $newY = $wireEndPoint['y'] - 1;
        $newX = $wireEndPoint['x'];
    }

    if ($direction === 'R') {
        $newY = $wireEndPoint['y'];
        $newX = $wireEndPoint['x'] + 1;
    }

    if ($direction === 'L') {
        $newY = $wireEndPoint['y'];
        $newX = $wireEndPoint['x'] - 1;
    }

    $newPositionKey = $newX . ',' . $newY;

    $this->wires[$wireId][$newPositionKey] = [
        'x' => $newX,
        'y' => $newY,
    ];

    $this->wireEndPoints[$wireId] = [
        'x' => $newX,
        'y' => $newY,
    ];
}

OK cool – now we can lay some wires. Let’s create a function to use the inputs to initialise the sequence. First let’s write a test with a shortish wire path:

public function testInitialiseWires()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/test_intitialise_wires');

    $crossedWiresMeasurer->initialise();

    $this->assertSame([
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ],
            '1,0' => [
                'x' => 1,
                'y' => 0,
            ],
            '2,0' => [
                'x' => 2,
                'y' => 0,
            ],
            '2,-1' => [
                'x' => 2,
                'y' => -1,
            ],
        ],
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ],
            '-1,0' => [
                'x' => -1,
                'y' => 0,
            ],
            '-1,1' => [
                'x' => -1,
                'y' => 1,
            ],
            '-1,2' => [
                'x' => -1,
                'y' => 2,
            ],
        ]
    ], $crossedWiresMeasurer->wires);
}

Next create the test input file

/inputs/day3/test_intitialise_wires

R2,D1
L1,U2

Now let’s make it pass. My first attempt looked like this:

    public function initialise()
    {
        foreach ($this->inputs as $wireId => $wireSequence) {
            foreach ($wireSequence as $moveInstruction) {
                $direction = $moveInstruction[0];
                $length = $moveInstruction[1];
                $this->layWire($wireId, $direction, $length);
            }
        }
    }

make tests

 ✘ Initialise wires
   │
   │ Invalid argument supplied for foreach()
   │
   │ /home/hamish/sites/adventofcode2019/src/day3/CrossedWiresMeasurer.php:30
   │ /home/hamish/sites/adventofcode2019/tests/Day3Part1Test.php:118

OK – so I forgot to convert the input move sequence into an array. Here’s my second attempt:

    public function initialise()
    {
        foreach ($this->inputs as $wireId => $wireSequenceString) {
            $wireSequence = explode(',', $wireSequenceString);
            foreach ($wireSequence as $moveInstruction) {
                $direction = $moveInstruction[0];
                $length = $moveInstruction[1];
                $this->layWire($wireId, $direction, $length);
            }
        }
    }

And that passes 🙂 So we can now initialise our wires. The next step is to get the points where they are intersecting. Because our two wire arrays use the coordinates as the key we can simply use PHPs handy array_intersect_key() function. So first make a test:

public function testGetIntersections()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');
    $crossedWiresMeasurer->wires = [
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ],
            '5,5' => [
                'x' => 5,
                'y' => 5,
            ],
            '3,2' => [
                'x' => 3,
                'y' => 2,
            ]
        ],
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ],
            '1,6' => [
                'x' => 1,
                'y' => 6,
            ],
            '5,5' => [
                'x' => 5,
                'y' => 5,
            ]
        ],
    ];

    $intersections = $crossedWiresMeasurer->getIntersections();

    $this->assertSame([
        '5,5' => [
            'x' => 5,
            'y' => 5,
        ],
    ], $intersections);
}

In my test the wires are not contiguous – but I don’t think that matters. I’ve also excluded the 0,0 intersection from the result as per the instructions:

While the wires do technically cross right at the central port where they both start, this point does not count

OK – so let’s make it pass:

    public function getIntersections()
    {
        $intersections = [];

        $intersections = array_intersect_key($this->wires[0], $this->wires[1]);
        unset($intersections['0,0']);

        return $intersections;
    }

OK – so we have our intersections array of points. Let’s look at the question again to see what we need to do to get the actual answer!

What is the Manhattan distance from the central port to the closest intersection?

OK so this is basically just adding the absolute value of the x and y coordinates. Lets write a test first:

public function testGetPointManhattenDistance()
{
    $crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/0');
    $point = [
        'x' => 3,
        'y' => 3,
    ];

    $pointManhattenDistance = $crossedWiresMeasurer->getPointManhattenDistance($point);

    $this->assertSame(6, $pointManhattenDistance);
}

And make it pass:

public function getPointManhattenDistance($point)
{
    return abs($point['x']) + abs($point['y']);
}

OK – now everything is in place to implement the run() function and see if we can make our original end-to-end tests pass!

public function run()
{
    $this->initialise();
    $intersections = $this->getIntersections();
    foreach ($intersections as $intersectionPoint) {
        $distance = $this->getPointManhattenDistance($intersectionPoint);
        if (empty($this->output) || $distance < $this->output) {
            $this->output = $distance;
        }
    }
}

Running make tests we can see that our first end-to-end test passes but the second one fails 🙁

 ✘ End to end
   │
   │ Failed asserting that 15 is identical to 159.
   │
   │ /home/hamish/sites/adventofcode2019/tests/Day3Part1Test.php:16
   │

The distance is way to small… So what’s gone wrong? Well at this point some debugging is required which is where the PuzzleDebugger class came in handy. To cut a long story short a casual assumption I made earlier was incorrect. Placing debug statements throughout the code and examining the output revealed the issue:

public function layWire(int $wireId, string $direction, int $length = 1)
{
    \PuzzleDebugger::print($direction);
    \PuzzleDebugger::print($length);
    ...

The output from test file 1 which has the instructions R75,D30,R83,U83... was the following:

TESTING INPUT FILE day3/part1/1
R
7
D
3
R
8
U
8

So basically this is telling us that only the first digit of the length is being passed through to the layWire() function. This is not something I covered in my tests so far as my tests only use lengths < 10! The issue here is initialise:

public function initialise()
{
    foreach ($this->inputs as $wireId => $wireSequenceString) {
        $wireSequence = explode(',', $wireSequenceString);
        foreach ($wireSequence as $moveInstruction) {
            $direction = $moveInstruction[0];
            $length = $moveInstruction[1];
            $this->layWire($wireId, $direction, $length);
        }
    }
}

Specifically:

$direction = $moveInstruction[0];
$length = $moveInstruction[1];

Is only taking the first digit for length! So I updated this to capture the rest of the string:

$direction = $moveInstruction[0];
$length = substr($moveInstruction, 1);

Now let’s run make tests again – and all our tests pass! So let’s create a solve.php script similar to the other puzzles:

/src/day3/solve.php

<?php

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

use PuzzleSolvers\Day3\CrossedWiresMeasurer;

$crossedWiresMeasurer = new CrossedWiresMeasurer('day3/part1/input');
$crossedWiresMeasurer->run();
$output = $crossedWiresMeasurer->getOutput();

echo "Day 3 Part 1 answer: " . $output . "\n";

Final /src/day3/CrossedWiresMeasurer.php

<?php

namespace PuzzleSolvers\Day3;

use PuzzleSolvers\PuzzleSolver;

class CrossedWiresMeasurer extends PuzzleSolver
{
    public $wires = [
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ]
        ],
        [
            '0,0' => [
                'x' => 0,
                'y' => 0,
            ]
        ],
    ];

    public $wireEndPoints = [
        [
            'x' => 0,
            'y' => 0,
        ],
        [
            'x' => 0,
            'y' => 0,
        ],
    ];

    public function run()
    {
        $this->initialise();
        $intersections = $this->getIntersections();
        foreach ($intersections as $intersectionPoint) {
            $distance = $this->getPointManhattenDistance($intersectionPoint);
            if (empty($this->output) || $distance < $this->output) {
                $this->output = $distance;
            }
        }
    }

    public function getIntersections()
    {
        $intersections = [];

        $intersections = array_intersect_key($this->wires[0], $this->wires[1]);
        unset($intersections['0,0']);

        return $intersections;
    }

    public function getPointManhattenDistance($point)
    {
        return abs($point['x']) + abs($point['y']);
    }

    public function initialise()
    {
        foreach ($this->inputs as $wireId => $wireSequenceString) {
            $wireSequence = explode(',', $wireSequenceString);
            foreach ($wireSequence as $moveInstruction) {
                $direction = $moveInstruction[0];
                $length = intval(substr($moveInstruction, 1));
                $this->layWire($wireId, $direction, $length);
            }
        }
    }

    public function layWire(int $wireId, string $direction, int $length = 1)
    {
        for ($i = 0; $i < $length; $i++) {
            $wireEndPoint = $this->wireEndPoints[$wireId];

            if ($direction === 'U') {
                $newY = $wireEndPoint['y'] + 1;
                $newX = $wireEndPoint['x'];
            }

            if ($direction === 'D') {
                $newY = $wireEndPoint['y'] - 1;
                $newX = $wireEndPoint['x'];
            }

            if ($direction === 'R') {
                $newY = $wireEndPoint['y'];
                $newX = $wireEndPoint['x'] + 1;
            }

            if ($direction === 'L') {
                $newY = $wireEndPoint['y'];
                $newX = $wireEndPoint['x'] - 1;
            }

            $newPositionKey = $newX . ',' . $newY;

            $this->wires[$wireId][$newPositionKey] = [
                'x' => $newX,
                'y' => $newY,
            ];

            $this->wireEndPoints[$wireId] = [
                'x' => $newX,
                'y' => $newY,
            ];
        }
    }
}

My input file is shown below

/inputs/day3/part1/input

R1009,U993,L383,D725,R163,D312,R339,U650,R558,U384,R329,D61,L172,D555,R160,D972,L550,D801,L965,U818,L123,D530,R176,D353,L25,U694,L339,U600,L681,D37,R149,D742,R762,U869,R826,U300,L949,U978,L303,U361,R136,D343,L909,U551,R745,U913,L566,D292,R820,U886,R205,D431,L93,D71,R577,U872,L705,U510,L698,U963,R607,U527,L669,D543,R690,U954,L929,D218,R490,U500,L589,D332,R949,D538,R696,U659,L188,U468,L939,U833,L445,D430,R78,D303,R130,D649,R849,D712,L511,U745,R51,U973,R799,U829,R605,D771,L837,U204,L414,D427,R538,U116,R540,D168,R493,U900,L679,U431,L521,D500,L428,U332,L954,U717,L853,D339,L88,U807,L607,D496,L163,U468,L25,U267,L759,D898,L591,U445,L469,U531,R596,D486,L728,D677,R350,D429,R39,U568,R92,D875,L835,D841,R877,U178,L221,U88,R592,U692,R455,U693,L419,U90,R609,U672,L293,U168,R175,D456,R319,D570,R504,D165,L232,D624,L604,D68,R807,D59,R320,D281,L371,U956,L788,D897,L231,D829,R287,D798,L443,U194,R513,D925,L232,U225,L919,U563,R448,D889,R661,U852,L950,D558,L269,U186,L625,U673,L995,U732,R435,U849,L413,D690,L158,D234,R361,D458,L271,U90,L781,U754,R256,U162,L842,U927,L144,D62,R928,D238,R473,U97,L745,U303,L487,D349,L520,D31,L825,U385,L133,D948,L39,U62,R801,D664,L333,U134,R692,U385,L658,U202,L279,D374,R489,D686,L182,U222,R733,U177,R94,D603,L376,U901,R216,D851,L155,D214,L460,U758,R121,D746,L180,U175,L943,U146,L166,D251,L238,U168,L642,D341,R281,U182,R539,D416,R553,D67,L748,U272,R257,D869,L340,U180,R791,U138,L755,D976,R731,U713,R602,D284,L258,U176,R509,U46,R935,U576,R96,U89,L913,U703,R833
L1006,D998,R94,D841,R911,D381,R532,U836,L299,U237,R781,D597,L399,D800,L775,D405,L485,U636,R589,D942,L878,D779,L751,U711,L973,U410,L151,U15,L685,U417,L106,D648,L105,D461,R448,D743,L589,D430,R883,U37,R155,U350,L421,U23,R337,U816,R384,D671,R615,D410,L910,U914,L579,U385,R916,U13,R268,D519,R289,U410,L389,D885,L894,U734,L474,U707,L72,U155,L237,U760,L127,U806,L15,U381,L557,D727,L569,U320,L985,D452,L8,D884,R356,U732,L672,D458,L485,U402,L238,D30,R644,U125,R753,U183,L773,U487,R849,U210,L164,D808,L595,D668,L340,U785,R313,D72,L76,D263,R689,U604,R471,U688,R462,D915,R106,D335,R869,U499,R190,D916,R468,D882,R56,D858,L143,D741,L386,U856,R50,U853,R151,D114,L773,U854,L290,D344,L23,U796,L531,D932,R314,U960,R643,D303,L661,D493,L82,D491,L722,U848,L686,U4,L985,D509,L135,D452,R500,U105,L326,D101,R222,D944,L645,D362,L628,U305,L965,U356,L358,D137,R787,U728,R967,U404,R18,D928,L695,D965,R281,D597,L791,U731,R746,U163,L780,U41,L255,U81,L530,D964,R921,D297,R475,U663,L226,U623,L984,U943,L143,U201,R926,U572,R343,U839,R764,U751,R128,U939,R987,D108,R474,U599,R412,D248,R125,U797,L91,D761,L840,U290,L281,U779,R650,D797,R185,D320,L25,U378,L696,U332,R75,D620,L213,D667,R558,U267,L846,U306,R939,D220,R311,U827,R345,U534,R56,D679,R48,D845,R898,U8,R862,D960,R753,U319,L886,D795,R805,D265,R876,U729,R894,D368,R858,U744,R506,D327,L903,U919,L721,U507,L463,U753,R775,D719,R315,U128,R17,D376,R999,D386,L259,U181,L162,U605,L265,D430,R35,D968,R207,U466,R796,D667,R93,U749,L315,D410,R312,U929,L923,U260,R638

Let’s get that gold star!

$ php src/day3/solve.php 
Day 3 Part 1 answer: 273

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/day3/part1/input with your own file. Did it work? Let me know!

Next up: Day 3 Part 2

Leave a comment

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