Skip to content

Commit 62a4b70

Browse files
committed
day 15 massive performance improvements and start of day 16
1 parent 7b693f8 commit 62a4b70

File tree

3 files changed

+178
-30
lines changed

3 files changed

+178
-30
lines changed

input/day16.txt

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
Valve ZT has flow rate=0; tunnels lead to valves QQ, DS
2+
Valve JX has flow rate=22; tunnels lead to valves CI, ZH, UR
3+
Valve EM has flow rate=0; tunnels lead to valves WH, IT
4+
Valve AA has flow rate=0; tunnels lead to valves EQ, QD, NP, ZP, KX
5+
Valve HW has flow rate=0; tunnels lead to valves CI, BV
6+
Valve IK has flow rate=8; tunnels lead to valves ET, NU, ZO, XL, QD
7+
Valve HA has flow rate=0; tunnels lead to valves WQ, LB
8+
Valve WH has flow rate=12; tunnels lead to valves EM, LW
9+
Valve KU has flow rate=0; tunnels lead to valves BV, CF
10+
Valve QD has flow rate=0; tunnels lead to valves AA, IK
11+
Valve CF has flow rate=18; tunnels lead to valves KU, JT, CM
12+
Valve VC has flow rate=0; tunnels lead to valves AD, UY
13+
Valve JT has flow rate=0; tunnels lead to valves CF, ZH
14+
Valve QQ has flow rate=11; tunnel leads to valve ZT
15+
Valve ZP has flow rate=0; tunnels lead to valves EZ, AA
16+
Valve LI has flow rate=0; tunnels lead to valves LB, CM
17+
Valve CI has flow rate=0; tunnels lead to valves HW, JX
18+
Valve VK has flow rate=6; tunnels lead to valves YM, LC, HE, NU, TI
19+
Valve WL has flow rate=20; tunnels lead to valves LW, TO
20+
Valve TI has flow rate=0; tunnels lead to valves VK, YW
21+
Valve NU has flow rate=0; tunnels lead to valves VK, IK
22+
Valve DS has flow rate=9; tunnels lead to valves NP, MV, FR, ZT, YW
23+
Valve HE has flow rate=0; tunnels lead to valves VK, EQ
24+
Valve ZH has flow rate=0; tunnels lead to valves JT, JX
25+
Valve TO has flow rate=0; tunnels lead to valves MT, WL
26+
Valve CM has flow rate=0; tunnels lead to valves LI, CF
27+
Valve WM has flow rate=14; tunnels lead to valves MO, WQ, EC, RN
28+
Valve EZ has flow rate=16; tunnels lead to valves RT, RZ, ZP
29+
Valve PB has flow rate=0; tunnels lead to valves YM, UY
30+
Valve XL has flow rate=0; tunnels lead to valves IK, MS
31+
Valve LB has flow rate=17; tunnels lead to valves LI, HA, ON, UR, AD
32+
Valve WQ has flow rate=0; tunnels lead to valves WM, HA
33+
Valve BV has flow rate=13; tunnels lead to valves KU, RT, HW, MO, EH
34+
Valve RN has flow rate=0; tunnels lead to valves WM, RZ
35+
Valve LW has flow rate=0; tunnels lead to valves WH, WL
36+
Valve NP has flow rate=0; tunnels lead to valves AA, DS
37+
Valve MT has flow rate=0; tunnels lead to valves TO, HG
38+
Valve ET has flow rate=0; tunnels lead to valves IK, EC
39+
Valve HG has flow rate=19; tunnel leads to valve MT
40+
Valve MV has flow rate=0; tunnels lead to valves UY, DS
41+
Valve RT has flow rate=0; tunnels lead to valves BV, EZ
42+
Valve ON has flow rate=0; tunnels lead to valves LB, EH
43+
Valve MO has flow rate=0; tunnels lead to valves BV, WM
44+
Valve UY has flow rate=5; tunnels lead to valves PB, BR, MS, VC, MV
45+
Valve UR has flow rate=0; tunnels lead to valves JX, LB
46+
Valve YM has flow rate=0; tunnels lead to valves PB, VK
47+
Valve RZ has flow rate=0; tunnels lead to valves RN, EZ
48+
Valve AD has flow rate=0; tunnels lead to valves VC, LB
49+
Valve EH has flow rate=0; tunnels lead to valves ON, BV
50+
Valve EQ has flow rate=0; tunnels lead to valves AA, HE
51+
Valve KX has flow rate=0; tunnels lead to valves AA, BR
52+
Valve BR has flow rate=0; tunnels lead to valves UY, KX
53+
Valve LC has flow rate=0; tunnels lead to valves VK, IT
54+
Valve YW has flow rate=0; tunnels lead to valves TI, DS
55+
Valve EC has flow rate=0; tunnels lead to valves ET, WM
56+
Valve IT has flow rate=10; tunnels lead to valves LC, EM
57+
Valve MS has flow rate=0; tunnels lead to valves UY, XL
58+
Valve FR has flow rate=0; tunnels lead to valves DS, ZO
59+
Valve ZO has flow rate=0; tunnels lead to valves FR, IK

src/Days/Day15.php

Lines changed: 45 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -78,8 +78,13 @@ public function solvePart1(mixed $input): int|string|null
7878
return $count;
7979
}
8080

81+
8182
/**
8283
* Solve Part 2 of the day's problem.
84+
* 7.0s to 0.1s performance improvements:
85+
* - avoid using a 2d array and instead use a more efficient isValidPoint method to check if a point is valid
86+
* - check the four points just outside the diamond shape of the sensor's range
87+
* - avoid looping through the entire grid by checking only the perimeter of each sensor's range
8388
*/
8489
public function solvePart2(mixed $input): int|string|null
8590
{
@@ -88,48 +93,58 @@ public function solvePart2(mixed $input): int|string|null
8893
? 20 // for the example input
8994
: 4000000; // for the actual puzzle input
9095

96+
// create an array of sensors with their x, y, and distance to the closest beacon (manhattan distance)
9197
$sensors = $input->map(fn ($sensor) => [
9298
'x' => $sensor['sensor']['x'],
9399
'y' => $sensor['sensor']['y'],
94100
'distance' => abs($sensor['sensor']['x'] - $sensor['beacon']['x']) + abs($sensor['sensor']['y'] - $sensor['beacon']['y']),
95101
])->toArray();
96102

97-
// for each row, check if there is a gap in the coverage
98-
for ($y = 0; $y <= $max; $y++) {
99-
$ranges = [];
100-
foreach ($sensors as $sensor) {
101-
$dy = abs($sensor['y'] - $y);
102-
// if the row is within the sensor's range, add the range to the list
103-
if ($dy <= $sensor['distance']) {
104-
$dx = $sensor['distance'] - $dy;
105-
$ranges[] = [$sensor['x'] - $dx, $sensor['x'] + $dx];
103+
// horizontal, vertical, and diagonal points just outside the diamond shape of the sensor's range
104+
$points = [[-1, -1], [-1, 1], [1, -1], [1, 1]];
105+
106+
// check the perimeter of each sensor's range
107+
foreach ($sensors as $sensor) {
108+
// check points just outside the diamond shape of the sensor's range
109+
for ($dx = 0; $dx <= $sensor['distance'] + 1; $dx++) {
110+
$dy = $sensor['distance'] + 1 - $dx;
111+
112+
foreach ($points as [$signX, $signY]) {
113+
$x = $sensor['x'] + $dx * $signX;
114+
$y = $sensor['y'] + $dy * $signY;
115+
116+
// check if the point is within the bounds of the grid
117+
if ($x >= 0 && $x <= $max && $y >= 0 && $y <= $max) {
118+
if ($this->isValidPoint($x, $y, $sensors, $max)) {
119+
// return the tuning frequency
120+
return $x * 4000000 + $y;
121+
}
122+
}
106123
}
107124
}
125+
}
108126

109-
// sort ranges by start position
110-
usort($ranges, fn ($a, $b) => $a[0] <=> $b[0]);
111-
112-
// check for gaps in the coverage
113-
$x = 0;
114-
foreach ($ranges as $range) {
115-
if ($x < $range[0]) {
116-
// found the gap
117-
return $x * 4000000 + $y;
118-
}
119-
$x = max($x, $range[1] + 1);
120-
if ($x > $max) {
121-
// out of bounds
122-
break;
123-
}
124-
}
127+
return null;
128+
}
125129

126-
if ($x <= $max) {
127-
// found the gap
128-
return $x * 4000000 + $y;
130+
/**
131+
* check if a point is valid by ensuring it's outside the range of all sensors.
132+
*
133+
* @param int $x
134+
* @param int $y
135+
* @param array $sensors sensors with their x, y, and distance to the closest beacon
136+
* @param int $max
137+
* @return bool
138+
*/
139+
protected function isValidPoint(int $x, int $y, array $sensors, int $max): bool
140+
{
141+
foreach ($sensors as $sensor) {
142+
$distance = abs($x - $sensor['x']) + abs($y - $sensor['y']);
143+
if ($distance <= $sensor['distance']) {
144+
return false;
129145
}
130146
}
131-
132-
return null;
147+
return true;
133148
}
134149

135150
/**

src/Days/Day16.php

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
<?php
2+
3+
declare(strict_types=1);
4+
5+
namespace App\Days;
6+
7+
use App\Contracts\Day;
8+
use Illuminate\Support\Collection;
9+
10+
class Day16 extends Day
11+
{
12+
public const EXAMPLE1 = <<<eof
13+
Valve AA has flow rate=0; tunnels lead to valves DD, II, BB
14+
Valve BB has flow rate=13; tunnels lead to valves CC, AA
15+
Valve CC has flow rate=2; tunnels lead to valves DD, BB
16+
Valve DD has flow rate=20; tunnels lead to valves CC, AA, EE
17+
Valve EE has flow rate=3; tunnels lead to valves FF, DD
18+
Valve FF has flow rate=0; tunnels lead to valves EE, GG
19+
Valve GG has flow rate=0; tunnels lead to valves FF, HH
20+
Valve HH has flow rate=22; tunnel leads to valve GG
21+
Valve II has flow rate=0; tunnels lead to valves AA, JJ
22+
Valve JJ has flow rate=21; tunnel leads to valve II
23+
eof;
24+
25+
/**
26+
* Solve Part 1 of the day's problem.
27+
*/
28+
public function solvePart1(mixed $input): int|string|null
29+
{
30+
$input = $this->parseInput($input);
31+
dd($input);
32+
33+
return null;
34+
}
35+
36+
/**
37+
* Solve Part 2 of the day's problem.
38+
*/
39+
public function solvePart2(mixed $input): int|string|null
40+
{
41+
$input = $this->parseInput($input);
42+
43+
// todo: implement solution for Part 2
44+
45+
return null;
46+
}
47+
48+
/**
49+
* Parse the input data.
50+
* @return Collection<int, array<string, string|int|array<int, string>>>
51+
*/
52+
protected function parseInput(mixed $input): Collection
53+
{
54+
$input = is_array($input) ? $input : explode("\n", $input);
55+
56+
return collect($input)
57+
->map(function (string $line): array {
58+
$valve = null;
59+
$flowRate = null;
60+
$tunnels = null;
61+
if (preg_match('/Valve (\w+) has flow rate=(\d+); tunnels? leads? to valves? (.+)/', $line, $matches)) {
62+
$valve = $matches[1];
63+
$flowRate = (int)$matches[2];
64+
$tunnels = explode(', ', $matches[3]);
65+
}
66+
return [
67+
'valve' => $valve,
68+
'flow_rate' => $flowRate,
69+
'tunnels' => $tunnels,
70+
];
71+
})
72+
;
73+
}
74+
}

0 commit comments

Comments
 (0)