Learning things about PHP during Advent of Code (Days 1-3)

Last year, I found out about Advent of Code a few days after it began, and never managed to get caught up. I had to drop it in the first week due to being busy with university work, but came back a few times over the past year and eventually ended up stuck on Day 11.

I'm hoping that a year later I'm able to get a bit further. This time I'll be doing the puzzles in PHP, since that's what I'm using in my internship at the moment. My very first observation, after using Java last year, was that getting the input file in is so much easier now!

I found Day 1 fairly straightforward, and made a few initial mistakes on Day 2 but was able to fix them. Day 3 seemed like a big jump in difficulty. It took me a while to get my head around what needed to be done, and then when I (thought I) had it, I wasn't sure if my code was even working it took so long to finish. That's the solution I posted in the thread here. It took over 7 minutes to run.

I knew that there had to be something I could do, so I looked up other ways to check if something was in an array. I found out about the key_exists() method, and after changing my code so the array used keys (like the maps I'm familiar with from Java) I managed to decrease the run time from over 7 minutes to around 0.1 seconds!

I was amazed that this small change produced such a huge improvement. Looking at this Stackoverflow question and its answers I learned that arrays in PHP are actually hashmaps, and that searching for a key is O(1) while searching for a value is O(n) - I've never really learned about Big O notation, but I do know that O(1) is better (best?).

My final code is like so:

$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\n";

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

            $times[] = $wire1[$posn] + $wire2[$posn];
        }
    }
    return array(min($distances), min($times));
}

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

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

I hope I keep learning useful things this month!

(My other solutions can be found on my GitHub, here.)

Comments

[Jon Bristow]

Ooh, I live for these moments when the “magic behind the curtain” in a language clicks into place.

It’s tough for me to mentally switch between “array backed” lists in languages like Java and the “everything is a dictionary” approaches of php, python, and javascript. (And others on both sides!) I’m thankful every day that google exists to help remind me.

Bonus “fun(?)” fact: the creator of the Advent of Code has a whole collection of PHP’s more dangerous and strange quirks and foibles: PHP Sadness

[David Schoemehl]

This was a big help for me. I had implemented part 1 in python storing every point and running a similar loop looking for each point in wire_1 in wire 2. Something like:

(I don't know how to use the markup to show this as Python code with indents.)
for segment in wire_1:
if segment in wire_2:
intersections.append(segment)

It worked great with the sample data, but took 16 minutes to find the answer with my actual problem data. This sent me down a path of trying to store line endpoints and calculate intersections, which would still be a more efficient solution from a memory perspective, but the math gets more complicated. After reading your post I started looking for alternatives and found that by using sets instead of lists in Python I had similar performance results.

intersections = set(wire_1) & set(wire_2)

Running time now is .2 sec! Thanks!