Skip to content

Commit 99705c9

Browse files
jthatchjthatch
committed
complete day 16 part 2
1 parent 1889540 commit 99705c9

File tree

2 files changed

+110
-198
lines changed

2 files changed

+110
-198
lines changed

‎Dockerfile

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,10 @@ RUN apt update -y \
3232
USER root
3333
COPY xdebug.ini /usr/local/etc/php/conf.d/xdebug.ini
3434

35+
# set php memory limit to 1G for use when running php via the shell as makefile does this automatically
36+
RUN echo "memory_limit = 1G" > /usr/local/etc/php/conf.d/memory-limit.ini
37+
38+
3539
# composer
3640
# disabled to keep sizes down, we'll need git and zip added to the image in order to use composer
3741
COPY --from=composer:2.2.6 /usr/bin/composer /usr/local/bin/composer

‎src/Days/Day16.php

Lines changed: 106 additions & 198 deletions
Original file line numberDiff line numberDiff line change
@@ -6,6 +6,7 @@
66

77
use App\Contracts\Day;
88
use Illuminate\Support\Collection;
9+
use SplQueue;
910

1011
class Day16 extends Day
1112
{
@@ -22,14 +23,12 @@ class Day16 extends Day
2223
Valve JJ has flow rate=21; tunnel leads to valve II
2324
EOF;
2425

25-
protected array $flowRates = [];
26-
protected array $valves = [];
27-
protected array $valvesToIds = [];
28-
protected static array $cache = [];
29-
protected array $cache2 = [];
30-
31-
private const CACHE_FILE = __DIR__.'/../../day16_cache.php';
32-
protected bool $saveToCache = false;
26+
protected array $flowRates = [];
27+
protected array $valves = [];
28+
protected array $valvesToIds = [];
29+
protected static array $cache = [];
30+
protected array $distances = [];
31+
protected array $nonZeroValves = [];
3332

3433
public function solvePart1(mixed $input): int|string|null
3534
{
@@ -44,221 +43,146 @@ public function solvePart1(mixed $input): int|string|null
4443

4544
public function solvePart2(mixed $input): int|string|null
4645
{
47-
$valves = $this->parseInput($input);
48-
//dump($valves['AA']);
49-
$this->saveToCache = 0 !== $valves['AA']['id'];
50-
self::$cache = [];
51-
$this->cache2 = $this->saveToCache ? $this->loadCache() : [];
52-
printf("save to cache: %s, Cache size: %d memory: %d\n", $this->saveToCache ? 'true' : 'false', count($this->cache2), memory_get_usage(true));
53-
//dd('got here');
54-
$this->valves = $valves->toArray();
55-
$this->valvesToIds = $valves->pluck('id', 'valve')->toArray();
56-
$this->flowRates = $valves->pluck('flow_rate', 'valve')->toArray();
57-
58-
$result = $this->findMaxPressureWithElephant('AA', 'AA', [], 26);
59-
60-
if ($this->saveToCache) {
61-
$this->saveCache();
62-
}
63-
64-
return $result;
46+
self::$cache = [];
47+
$valves = $this->parseInput($input);
48+
$this->valves = $valves->toArray();
49+
$this->flowRates = $valves->pluck('flow_rate', 'valve')->toArray();
50+
$this->distances = $this->calculateDistances();
51+
$this->nonZeroValves = array_values(array_keys(array_filter($this->flowRates, fn ($rate) => $rate > 0)));
52+
53+
$allValves = (1 << count($this->nonZeroValves)) - 1;
54+
return $this->dfs('AA', 'AA', $allValves, 26, 26);
6555
}
6656

67-
protected function findMaxPressure(string $currentValve, array $openValves, int $remainingTime): int
57+
protected function dfs(string $myPos, string $elephantPos, int $remainingValves, int $myTime, int $elephantTime): int
6858
{
69-
sort($openValves);
70-
$key = "{$currentValve}".implode(',', $openValves)."{$remainingTime}";
71-
//$key = $this->createBitmaskKey([$currentValve], $openValves, $remainingTime);
59+
if ($myTime <= 0 && $elephantTime <= 0) {
60+
return 0;
61+
}
7262

63+
$key = $this->getStateKey($myPos, $elephantPos, $remainingValves, $myTime, $elephantTime);
7364
if (isset(self::$cache[$key])) {
7465
return self::$cache[$key];
7566
}
7667

77-
if (0 === $remainingTime) {
78-
return 0;
79-
}
80-
8168
$maxPressure = 0;
8269

83-
// Try opening the current valve
84-
if (!in_array($currentValve, $openValves) && $this->flowRates[$currentValve] > 0) {
85-
$newOpenValves = [...$openValves, $currentValve];
86-
$pressureReleased = $this->flowRates[$currentValve] * ($remainingTime - 1);
87-
$recursivePressure = $this->findMaxPressure($currentValve, $newOpenValves, $remainingTime - 1);
88-
$maxPressure = $pressureReleased + $recursivePressure;
89-
}
90-
91-
// Try moving to each connected valve
92-
foreach ($this->valves[$currentValve]['tunnels'] as $nextValve) {
93-
$pressure = $this->findMaxPressure($nextValve, $openValves, $remainingTime - 1);
94-
$maxPressure = max($maxPressure, $pressure);
70+
// Optimize: Only consider moves for the actor with more time
71+
if ($myTime >= $elephantTime) {
72+
$maxPressure = $this->tryMoves($myPos, $elephantPos, $remainingValves, $myTime, $elephantTime, true);
73+
} else {
74+
$maxPressure = $this->tryMoves($elephantPos, $myPos, $remainingValves, $elephantTime, $myTime, false);
9575
}
9676

9777
self::$cache[$key] = $maxPressure;
9878
return $maxPressure;
9979
}
10080

101-
protected function findMaxPressureWithElephant(
102-
string $humanValve,
103-
string $elephantValve,
104-
array $openValves,
105-
int $remainingTime
106-
): int {
107-
sort($openValves);
108-
$sortedValves = [$humanValve, $elephantValve];
109-
sort($sortedValves);
110-
111-
$key = $this->createBitmaskKey($sortedValves, $openValves, $remainingTime);
112-
113-
static $cacheCount = 0;
114-
115-
static $maxDepthReached = 0;
116-
static $maxValvesOpened = 0;
81+
protected function tryMoves(string $pos, string $otherPos, int $remainingValves, int $time, int $otherTime, bool $isMe): int
82+
{
83+
$maxPressure = 0;
84+
for ($i = 0; $i < count($this->nonZeroValves); $i++) {
85+
if (($remainingValves & (1 << $i)) === 0) {
86+
continue;
87+
}
88+
$valve = $this->nonZeroValves[$i];
89+
$timeToOpen = $this->distances[$pos][$valve] + 1;
11790

118-
$currentDepth = 26 - $remainingTime;
119-
$valvesOpenedCount = count($openValves);
91+
if ($timeToOpen < $time) {
92+
$newTime = $time - $timeToOpen;
93+
$pressure = $this->flowRates[$valve] * $newTime;
94+
$newRemainingValves = $remainingValves & ~(1 << $i);
12095

121-
$maxDepthReached = max($maxDepthReached, $currentDepth);
122-
$maxValvesOpened = max($maxValvesOpened, $valvesOpenedCount);
96+
$subPressure = $isMe
97+
? $this->dfs($valve, $otherPos, $newRemainingValves, $newTime, $otherTime)
98+
: $this->dfs($otherPos, $valve, $newRemainingValves, $otherTime, $newTime);
12399

124-
if (isset($this->cache2[$key])) {
125-
return $this->cache2[$key];
100+
$maxPressure = max($maxPressure, $pressure + $subPressure);
101+
}
126102
}
103+
return $maxPressure;
104+
}
127105

128-
if (0 === $remainingTime) {
129-
return 0;
130-
}
106+
protected function getStateKey(string $pos1, string $pos2, int $remainingValves, int $time1, int $time2): string
107+
{
108+
$pos1Id = array_search($pos1, $this->nonZeroValves);
109+
$pos2Id = array_search($pos2, $this->nonZeroValves);
131110

132-
// Early termination check
133-
$unopenedValves = array_diff(array_keys($this->flowRates), $openValves);
134-
$potentialPressure = array_sum(array_intersect_key($this->flowRates, array_flip($unopenedValves))) * $remainingTime;
135-
if (0 === $potentialPressure) {
136-
$this->cache2[$key] = 0;
137-
return 0;
138-
}
111+
// if the position is not in nonZeroValves (e.g., 'AA'), use a special value
112+
$pos1Id = false === $pos1Id ? 31 : $pos1Id;
113+
$pos2Id = false === $pos2Id ? 31 : $pos2Id;
139114

140-
// todo output the total count of $this->cache2 and the number of unique keys
141-
/* $totalStates = count($this->cache2);
142-
$uniqueKeys = count(array_unique(array_keys($this->cache2)));
143-
printf("Total states: %d, Unique keys: %d\n", $totalStates, $uniqueKeys); */
144-
145-
//$cacheCount++;
146-
static $lastReportedCount = 0;
147-
$cacheCount = count($this->cache2);
148-
if ($this->saveToCache && $cacheCount >= $lastReportedCount + 100000) {
149-
$depthProgress = ($maxDepthReached / 26) * 100;
150-
$valveProgress = ($maxValvesOpened / count(array_filter($this->flowRates))) * 100;
151-
printf(
152-
" Cache count: %d (Depth: %.2f%%, Valves: %.2f%%)\n",
153-
$cacheCount,
154-
$depthProgress,
155-
$valveProgress
156-
);
157-
$this->reportLongRunning();
158-
$lastReportedCount = $cacheCount - ($cacheCount % 100000);
115+
if ($pos1Id > $pos2Id || ($pos1Id === $pos2Id && $time1 > $time2)) {
116+
[$pos1Id, $pos2Id, $time1, $time2] = [$pos2Id, $pos1Id, $time2, $time1];
159117
}
160118

161-
$maxPressure = 0;
119+
// use a 64-bit integer (as a string) to store the state
120+
return sprintf(
121+
'%d',
122+
($pos1Id & 0x1F) | (($pos2Id & 0x1F) << 5) | (($remainingValves & 0xFFFF) << 10) | (($time1 & 0x1F) << 26) | (($time2 & 0x1F) << 31)
123+
);
124+
}
162125

163-
// Both open valves
164-
if ($humanValve !== $elephantValve && !in_array($humanValve, $openValves) && $this->flowRates[$humanValve] > 0 && !in_array($elephantValve, $openValves) && $this->flowRates[$elephantValve] > 0) {
165-
$newOpenValves = [...$openValves, $humanValve, $elephantValve];
166-
$pressureReleased = ($this->flowRates[$humanValve] + $this->flowRates[$elephantValve]) * ($remainingTime - 1);
167-
$recursivePressure = $this->findMaxPressureWithElephant(
168-
$humanValve,
169-
$elephantValve,
170-
$newOpenValves,
171-
$remainingTime - 1
172-
);
173-
$maxPressure = max($maxPressure, $pressureReleased + $recursivePressure);
126+
protected function calculateDistances(): array
127+
{
128+
$distances = [];
129+
foreach ($this->valves as $start => $data) {
130+
$distances[$start] = $this->bfs($start);
174131
}
132+
return $distances;
133+
}
175134

176-
// Human opens valve, elephant moves
177-
if (!in_array($humanValve, $openValves) && $this->flowRates[$humanValve] > 0) {
178-
$newOpenValves = [...$openValves, $humanValve];
179-
$pressureReleased = $this->flowRates[$humanValve] * ($remainingTime - 1);
180-
foreach ($this->valves[$elephantValve]['tunnels'] as $nextElephantValve) {
181-
$recursivePressure = $this->findMaxPressureWithElephant(
182-
$humanValve,
183-
$nextElephantValve,
184-
$newOpenValves,
185-
$remainingTime - 1
186-
);
187-
$maxPressure = max($maxPressure, $pressureReleased + $recursivePressure);
188-
}
189-
}
135+
protected function bfs(string $start): array
136+
{
137+
$queue = new SplQueue();
138+
$queue->enqueue([$start, 0]);
139+
$visited = [$start => 0];
190140

191-
// Elephant opens valve, human moves
192-
if (!in_array($elephantValve, $openValves) && $this->flowRates[$elephantValve] > 0) {
193-
$newOpenValves = [...$openValves, $elephantValve];
194-
$pressureReleased = $this->flowRates[$elephantValve] * ($remainingTime - 1);
195-
foreach ($this->valves[$humanValve]['tunnels'] as $nextHumanValve) {
196-
$recursivePressure = $this->findMaxPressureWithElephant(
197-
$nextHumanValve,
198-
$elephantValve,
199-
$newOpenValves,
200-
$remainingTime - 1
201-
);
202-
$maxPressure = max($maxPressure, $pressureReleased + $recursivePressure);
203-
}
204-
}
141+
while (!$queue->isEmpty()) {
142+
[$valve, $distance] = $queue->dequeue();
205143

206-
// Both move
207-
foreach ($this->valves[$humanValve]['tunnels'] as $nextHumanValve) {
208-
foreach ($this->valves[$elephantValve]['tunnels'] as $nextElephantValve) {
209-
$pressure = $this->findMaxPressureWithElephant(
210-
$nextHumanValve,
211-
$nextElephantValve,
212-
$openValves,
213-
$remainingTime - 1
214-
);
215-
$maxPressure = max($maxPressure, $pressure);
144+
foreach ($this->valves[$valve]['tunnels'] as $neighbor) {
145+
if (!isset($visited[$neighbor])) {
146+
$visited[$neighbor] = $distance + 1;
147+
$queue->enqueue([$neighbor, $distance + 1]);
148+
}
216149
}
217150
}
218151

219-
// Cache the result with more aggressive eviction strategy
220-
$this->cache2[$key] = $maxPressure;
221-
222-
static $lastSaveTime = 0;
223-
$currentTime = microtime(true);
224-
if ($currentTime - $lastSaveTime > 30 && $this->saveToCache) { // Save every 30 seconds
225-
printf("Saving %d keys to cache\n", count($this->cache2));
226-
$this->saveCache();
227-
$lastSaveTime = $currentTime;
228-
}
229-
230-
return $maxPressure;
152+
return $visited;
231153
}
232154

233-
/**
234-
* todo fix this
235-
* create a unique bitmask key for the given valve names, open valves and remaining time
236-
*
237-
* @param array $valveNames e.g. ["AA", "BB"]
238-
* @param array $openValves e.g. ["CC", "DD"]
239-
* @param integer $remainingTime e.g. 26
240-
* @return integer
241-
*/
242-
243-
protected function createBitmaskKey(array $valveNames, array $openValves, int $remainingTime): int
155+
protected function findMaxPressure(string $currentValve, array $openValves, int $remainingTime): int
244156
{
245-
$bitmask = 0;
157+
sort($openValves);
158+
$key = "{$currentValve}".implode(',', $openValves)."{$remainingTime}";
246159

247-
// Encode valve names (2 valves, 7 bits each)
248-
$bitmask |= ($this->valvesToIds[$valveNames[0]] & 0x7F) << 57;
249-
$bitmask |= ($this->valvesToIds[$valveNames[1]] & 0x7F) << 50;
160+
if (isset(self::$cache[$key])) {
161+
return self::$cache[$key];
162+
}
250163

251-
// Encode open valves (up to 50 valves, 1 bit each)
252-
foreach ($openValves as $openValve) {
253-
if (isset($this->valvesToIds[$openValve])) {
254-
$bitmask |= 1 << ($this->valvesToIds[$openValve] & 0x3F);
255-
}
164+
if (0 === $remainingTime) {
165+
return 0;
256166
}
257167

258-
// Encode remaining time (5 bits, max 31 minutes)
259-
$bitmask |= ($remainingTime & 0x1F) << 45;
168+
$maxPressure = 0;
169+
170+
// try opening the current valve
171+
if (!in_array($currentValve, $openValves) && $this->flowRates[$currentValve] > 0) {
172+
$newOpenValves = [...$openValves, $currentValve];
173+
$pressureReleased = $this->flowRates[$currentValve] * ($remainingTime - 1);
174+
$recursivePressure = $this->findMaxPressure($currentValve, $newOpenValves, $remainingTime - 1);
175+
$maxPressure = $pressureReleased + $recursivePressure;
176+
}
177+
178+
// try moving to each connected valve
179+
foreach ($this->valves[$currentValve]['tunnels'] as $nextValve) {
180+
$pressure = $this->findMaxPressure($nextValve, $openValves, $remainingTime - 1);
181+
$maxPressure = max($maxPressure, $pressure);
182+
}
260183

261-
return $bitmask;
184+
self::$cache[$key] = $maxPressure;
185+
return $maxPressure;
262186
}
263187

264188
protected function parseInput(mixed $input): Collection
@@ -280,20 +204,4 @@ protected function parseInput(mixed $input): Collection
280204
return [];
281205
});
282206
}
283-
284-
private function loadCache(): array
285-
{
286-
if (file_exists(self::CACHE_FILE) && $this->saveToCache) {
287-
$cache = include self::CACHE_FILE;
288-
return is_array($cache) ? $cache : [];
289-
}
290-
return [];
291-
}
292-
293-
private function saveCache(): void
294-
{
295-
$cacheContent = "<?php\nreturn ".var_export($this->cache2, true).";\n";
296-
file_put_contents(self::CACHE_FILE, $cacheContent);
297-
//$this->cacheModified = false;
298-
}
299207
}

0 commit comments

Comments
 (0)