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

— Day 3: Crossed Wires (Part 2) —

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 Day3Part1 (as in the end of Day3Part1). 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.

So it looks like part 2 to this puzzle is only a minor adjustment in the way we calculate the distance. Rather than using the Manhatten Distance we need to:

calculate the number of steps each wire takes to reach each intersection; choose the intersection where the sum of both wires’ steps is lowest.

So the first thing I did was set up my end-to-end tests using the provided examples:

/tests/Day3Part2Test.php

<?php

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

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

I’m thinking that the easiest way to do this is to just keep track of the length of the wire as we are laying it. When we identify the intersections we can just lookup the length at that point.

So I copied the CrossedWiresMeasurer class from the Day3Part1 and created CrossedWiresMeasurer2

/src/day3/CrossedWiresMeasurer2.php

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

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

Now I want to modify our wires and wiretEndPoints to also store length:

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

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

And create a function to get the sum of wire lengths at a specific point

public function getWireLengths($point)
{
    return $this->wires[0][$point['x'] . ',' . $point['y']]['length'] + $this->wires[1][$point['x'] . ',' . $point['y']]['length'];
}

Now modify the layWires() function to update the wires lengths as we lay them

public function layWire(int $wireId, string $direction, int $length = 1)
{
    ...

    $newPositionKey = $newX . ',' . $newY;
    $newLength = $wireEndPoint['length'] + 1;

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

Now modify the run function to use the new getWireLengths():

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

Now this works for our input but I think there is a bug that we are overwriting the length each time a line intersects on itself. We actually want to keep the shortest length. So lets write a quick test for that. First I created a short wire path where the wires intersect at x=0, y=1 and saved it as a test input file:
/inputs/day3/part2/crossing_wires_length

U2,R1,D1,L1
U2,R1,D1,L1

Now I want to test that the intersection point has length 1 and not length 5

public function testWirePointStoresShortestLength()
{
    $inputFile = 'day3/part2/crossing_wires_length';
    $crossedWiresMeasurer2 = new CrossedWiresMeasurer2($inputFile);
    $crossedWiresMeasurer2->initialise();

    \PuzzleDebugger::print($crossedWiresMeasurer2->wires[0]);

    $this->assertSame(1, $crossedWiresMeasurer2->wires[0]['0,1']['length']);
}

This test indeed fails so we can make it pass by checking for a length value and not overwriting – however the wireEndPoint length still has to always increase:

if (isset($this->wires[$wireId][$newPositionKey])) {
    $newLength = $this->wires[$wireId][$newPositionKey]['length'];
} else {
    $newLength = $wireEndPoint['length'] + 1;
}

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

$this->wireEndPoints[$wireId] = [
    'x' => $newX,
    'y' => $newY,
    'length' => $wireEndPoint['length'] + 1,
];

Now that test passes as well, it’s time to update our solve.php script.

/src/day3/solve.php

<?php

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

use PuzzleSolvers\Day3\CrossedWiresMeasurer;
use PuzzleSolvers\Day3\CrossedWiresMeasurer2;

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

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

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

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

Here is the final class:

<?php

namespace PuzzleSolvers\Day3;

use PuzzleSolvers\PuzzleSolver;

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

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

    public function run()
    {
        $this->initialise();
        $intersections = $this->getIntersections();
        foreach ($intersections as $intersectionPoint) {
            $distance = $this->getWireLengths($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 getWireLengths($point)
    {
        return $this->wires[0][$point['x'] . ',' . $point['y']]['length'] + $this->wires[1][$point['x'] . ',' . $point['y']]['length'];
    }

    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;

            if (isset($this->wires[$wireId][$newPositionKey])) {
                $newLength = $this->wires[$wireId][$newPositionKey]['length'];
            } else {
                $newLength = $wireEndPoint['length'] + 1;
            }

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

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

let’s get that gold star!

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

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 4 Part 1

Leave a comment

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