🎄 Advent of Code Day 10

Today you are looking at a strange metal country with lots of pipes. How did I get there? Oh, with the glider - I had to read it again while writing this post. After quickly sketching the positions of all the pipes, you get this

1
2
3
4
5
..F7.
.FJ|.
SJ.L7
|F--J
LJ...

And also have a legend of what each of the symbols mean. For easier understanding, I made a much simpler map that contains only empty ground and starting position.

1
2
3
. . .
. S .
. . .

Lets say starting position is at [0, 0] so the other positions will looks like this

1
2
3
[-1,-1] [-1,0] [-1,1]
[0,-1]  [0,0]  [0,1]
[1,-1]  [1,0]  [1,1]

This tells me how the pipes are connected to the each other

1
2
3
4
5
6
7
8
'|' => [[0, -1], [0, 1]], // up and down (N/S)
'-' => [[-1, 0], [1, 0]], // left and right (W/E)
'L' => [[-1, 0], [0, 1]], // 90 degree left (N/E)
'J' => [[-1, 0], [0, -1]], // 90 degree right (N/W)
'7' => [[1, 0], [0, -1]], // 90 degree left (S/W)
'F' => [[1, 0], [0, 1]], // 90 degree right (S/E)
'.' => [[0, 0]], // ground (no direction from here)
'S' => [[0, 0]], // starting positifion

And to find the coordinates of my starting position, I used

1
2
3
4
5
foreach ($map as $index => $row) {
    if (in_array('S', $row)) {
        $start = [$index, array_search('S', $row)]; // [2, 0] for test input
    }
}

It is at [2,0] so only possible directions are N, S, and E

At this point I still didn’t know what to do with it :D I just knew that I had to find a loop and find how many steps it takes to get to the farthest point from the starting position.

1
2
3
4
5
..45.
.236.
01.78
14567
23...

For test input it is 8.

I was able to find the start point and now I had to find the next one. My first attempt was to check all the destinations around my current position. Yes, this worked for the S pipe, but not for the special pipes.

I created another function to get the destination for a pipe type based on its location on the map.

1
2
3
4
5
6
7
8
$getPipe = function($x, $y) use ($map, $pipes): array {
	$pipe = $map[$x][$y];
	if (!isset($pipes[$pipe]) || $pipe == 'S') {
		return $pipes;
	}

	return [$pipes[$pipe]];
};

But not all the pipes around my current position are connected to it. When I find a possible next position, I check if it is connected back by looking at the shape of the pipe at that position and where it can connect.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
$areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
	[$x,$y] = $start;
	[$dx, $dy] = $destination;
	$pipe = $map[$dx][$dy];

	// connected to each pipe when tere is connection from it
	if ($pipe == 'S') {
		return true;
	}

	foreach($pipes[$pipe] as $direction) {
		[$px, $py] = $direction;
		[$px, $py] = [$dx + $px, $dy + $py];

		if ($px == $x && $py == $y) {
			return true;
		}
	}
	return false;
};

I have tested this function manually and I get the following responses. They looked fine to me.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
2 Possible connections for [2,0] S
Possible connection 0: 3 0 |
Possible connection 1: 2 1 J

. . .

2 Possible connections for [1,3] |
Possible connection 0: 0 3 7
Possible connection 1: 2 3 L

2 Possible connections for [2,3] L
Possible connection 0: 1 3 |
Possible connection 1: 2 4 7

2 Possible connections for [2,4] 7
Possible connection 0: 3 4 J
Possible connection 1: 2 3 L

2 Possible connections for [3,4] J
Possible connection 0: 2 4 7
Possible connection 1: 3 3 -

2 Possible connections for [3,3] -
Possible connection 0: 3 2 -
Possible connection 1: 3 4 J

2 Possible connections for [3,1] F
Possible connection 0: 4 1 J
Possible connection 1: 3 2 -

2 Possible connections for [4,1] J
Possible connection 0: 3 1 F
Possible connection 1: 4 0 L

2 Possible connections for [4,0] L
Possible connection 0: 3 0 |
Possible connection 1: 4 1 J

2 Possible connections for [3,0] |
Possible connection 0: 2 0 S
Possible connection 1: 4 0 L

So it was time to put it all together.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
function findNext($x, $y, $map, $pipes, $next): array
{

    $areConnected = function (array $start, array $destination) use ($map, $pipes): bool {
        [$x,$y] = $start;
        [$dx, $dy] = $destination;
        $pipe = $map[$dx][$dy];

        // / connected to each pipe when tere is connection from it
        if ($pipe == 'S') {
            return true;
        }

        foreach($pipes[$pipe] as $direction) {
            [$px, $py] = $direction;
            [$px, $py] = [$dx + $px, $dy + $py];

            if ($px == $x && $py == $y) {
                return true;
            }
        }

        return false;

    };

    $getPipe = function($x, $y) use ($map, $pipes): array {
        $pipe = $map[$x][$y];

        if (!isset($pipes[$pipe]) || $pipe == 'S') {
            return $pipes;
        }

        return [$pipes[$pipe]];
    };

    foreach ($getPipe($x,$y) as $index => $pipe)
    {
        foreach ($pipe as $dIndex => $direction) {
            [$dx, $dy] = $direction;
            [$dx, $dy] = [$x + $dx, $y + $dy];

            // this is the same location
            if ($x == $dx && $y == $dy) {
                continue;
            }

            // skip if location not exists
            if (!isset($map[$dx][$dy])) {
                continue;
            }

            // skip if ground
            if ($map[$dx][$dy] == '.') {
                continue;
            }

            // check if both points are connected
            if (!$areConnected([$x, $y], [$dx, $dy])) {
                continue;
            }

            $possibleNext = [
                $dx,
                $dy,
            ];

            if (array_search($possibleNext, $next) !== false) {
                continue;
            } else {
                $next[] = $possibleNext;
                $possibleNext = [];
            }
        }
    }

    return $next;
}

Now I finally had a working function which returns me each location to which pipe is connected. Every time there are 2, only exception is start pipe as I mentioned above.

I still had one piece missing. How to count the farthest path. For this I created another array where I put every possible next location that my function returns. (possibleNext locations are pipes that are connected to my current location)

In the next step I compared these (from findNext function) against this connections array and removed location if it was checked before (is already in connections).

When hasNext was zero, I knew that I had checked every connected location in the loop.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
while($hasNext) {
    foreach($next as  $index => $possibleNext) {
        [$x, $y] = [$possibleNext[0], $possibleNext[1]];
        echo 'Checking [' . $x . ',' . $y . ']' . PHP_EOL;
        $next = findNext($x, $y, $map, $pipes, $next);

        foreach($next as $nIndex => $nValue) {
            if (array_search([$nValue[0], $nValue[1]], $connections) !== false) {
                unset($next[$nIndex]);
            } else {
                $connections[] = [$nValue[0], $nValue[1]];
            }
        }

        $hasNext = count($next) > 0;
    }
}

Next I just counted how many entires I had in the connections array and divided by 2 to get the furthest point.

🥳 Tada! Wow, that was hard. Only part 1 for me today, but I’m really glad I did it.