-
Notifications
You must be signed in to change notification settings - Fork 0
/
24.php
103 lines (81 loc) · 1.97 KB
/
24.php
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
<?php
function calc($bridge)
{
$sum = 0;
foreach ($bridge as $pipe) {
$sum += $pipe[0] + $pipe[1];
}
return $sum;
}
function hasher($pipes)
{
$parts = [];
foreach ($pipes as $pipe) {
$parts[] = implode('/', $pipe);
}
return implode(';', $parts);
}
function recurse(&$cache, $bridge, $pipes, $last)
{
if (count($pipes) == 0) {
return 0;
}
$max = 0;
foreach ($pipes as $p) {
if ($p[0] == $last || $p[1] == $last) {
$last2 = $p[0] == $last ? $p[1] : $p[0];
$p2 = $pipes;
$key = null;
foreach ($p2 as $i => $pipe) {
if ($pipe == $p) {
$key = $i;
break;
}
}
if ($key !== null) {
unset($p2[$key]);
}
$bridge[] = $p;
$sum = calc([$p]) + recurse($cache, $bridge, $p2, $last2);
if ($sum > $max) {
$max = $sum;
}
$h = hasher($bridge);
$cache[$h] = true;
array_pop($bridge);
}
}
return $max;
}
$contents = trim(file_get_contents('24-input.txt'));
$rows = explode("\n", $contents);
$pipes = [];
foreach ($rows as $row) {
$row = explode('/', $row);
$pipes[] = [ (int)min($row), (int)max($row) ];
}
$cache = [];
$bridge = [];
$max = recurse($cache, $bridge, $pipes, 0);
echo 'Part A: ' . $max . PHP_EOL;
// =========== //
$glen = 0;
$gmax = 0;
foreach ($cache as $key => $val) {
$bridge = [];
$parts = explode(';', $key);
foreach ($parts as $part) {
$parts = explode('/', $part);
$bridge[] = [ (int)$parts[0], (int)$parts[1] ];
}
if (count($bridge) > $glen) {
$glen = count($bridge);
$gmax = calc($bridge);
} elseif (count($bridge) == $glen) {
$max = calc($bridge);
if ($max > $gmax) {
$gmax = $max;
}
}
}
echo 'Part B: ' . $gmax . PHP_EOL;