Discussion on: Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires

[Stephanie Hope]

PHP, because I'm having to learn it at my internship at the moment. Something isn't right here, because it takes several minutes to run, but at least the solution appears eventually.

<?php

$input = file("input3.txt");

$wire1 = explode(",", substr($input[0], 0, strlen($input[0]) - 1));
$wire2 = explode(",", $input[1]);

$wire1_posn = trace_wire($wire1);
$wire2_posn = trace_wire($wire2);

[$distance, $time] = find_intersections($wire1_posn, $wire2_posn);
echo "\n min distance = $distance, min time = $time";

function find_intersections($wire1, $wire2)
{
    $distances = array();
    $times = array();
    foreach ($wire1 as $posn) {
        if (in_array($posn, $wire2)) {
            [$x, $y] = explode(",", $posn);
            $distances[] = abs($x) + abs($y);

            $time1 = array_search($posn, $wire1);
            $time2 = array_search($posn, $wire2);

            $times[] = $time1 + $time2 +2;
        }
        echo ".\n";
    }
    return array(min($distances), min($times));
}

function trace_wire($wire)
{
    $x = 0;
    $y = 0;

    foreach ($wire as $path) {
        $direction = $path[0];
        $distance = substr($path, 1);
        if ($direction == "U") {
            for ($i = 0; $i < $distance; $i++) {
                $y--;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "D") {
            for ($i = 0; $i < $distance; $i++) {
                $y++;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "L") {
            for ($i = 0; $i < $distance; $i++) {
                $x--;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "R") {
            for ($i = 0; $i < $distance; $i++) {
                $x++;
                $wire_posn[] = "$x, $y";
            }
        }
    }
    return $wire_posn;
}

[Stephanie Hope]

I was able to improve the speed hugely with just a little tweaking, from over 7 minutes to around 0.1 seconds!

[Jon Bristow]

If you’re enumerating every point you’re operating with two lists of hundreds of thousands of items. Worse, I don’t think there’s a way around a cartesian join of the two sets (potentially squaring your already hideous number of data).

Running into performance problems is expected, driving the solution into minutes if you’re not careful (I crashed my jvm and lost a few minutes manually killing it and my ide as they consumed as much processor and memory power as they could)