Last active
January 12, 2024 21:13
-
-
Save uestla/9a69321ef803db39cab67048b08e1880 to your computer and use it in GitHub Desktop.
Project Euler - solutions written in PHP
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<?php | |
declare(strict_types = 1); | |
final readonly class solution { | |
public function __construct( | |
public int $n, | |
public string $info, | |
) {} | |
}; | |
$solvers = [ | |
1 => static function (): solution { | |
$sum = 0; | |
$ns = []; | |
$l = 1000; | |
for ($i = 1; $i < $l; $i++) { | |
if ($i % 3 === 0 || $i % 5 === 0) { | |
$sum += $i; | |
$ns[] = $i; | |
} | |
} | |
return new solution($sum, implode(' + ', array_slice($ns, -10)) . ' = ' . $sum); | |
}, | |
2 => static function (): solution { | |
$a = 1; | |
$b = 2; | |
$sum = 2; | |
$ns = []; | |
$l = 4_000_000; | |
while ($b <= $l) { | |
$_ = $b; | |
$b = $a + $b; | |
$a = $_; | |
if ($b % 2 === 0) { | |
$sum += $b; | |
$ns[] = $b; | |
} | |
} | |
return new solution($sum, implode(' + ', $ns) . ' = ' . $sum); | |
}, | |
3 => static function (): solution { | |
$n = 600_851_475_143; | |
$ns = []; | |
for ($d = 2; $d <= sqrt($n); $d++) { | |
while ($n % $d === 0) { | |
$n = (int) ($n / $d); | |
$ns[] = $d; | |
} | |
} | |
$ns[] = $n; | |
return new solution($n, implode(' -> ', $ns)); | |
}, | |
4 => static function (): solution { | |
$n = 0; | |
$ns = []; | |
for ($a = 999; $a >= 100; $a--) { | |
for ($b = 999; $b >= 100; $b--) { | |
$p = (string) ($a * $b); | |
$len = strlen($p); | |
for ($i = 0; $i < $len / 2; $i++) { | |
if ($p[$i] !== $p[$len - $i - 1]) { | |
continue 2; | |
} | |
} | |
if ((int) $p > $n) { | |
$n = (int) $p; | |
$ns[] = $p; | |
} | |
} | |
} | |
return new solution($n, implode(' -> ', $ns)); | |
}, | |
5 => static function (): solution { | |
$a = 1; | |
$ns = [$a]; | |
for ($b = 2; $b <= 20; $b++) { | |
$hcf = 0; | |
$m = $a; | |
$n = $b; | |
while (true) { | |
$rem = $n % $m; | |
if ($rem === 0) { | |
$hcf = $m; | |
break; | |
} | |
$n = $m; | |
$m = $rem; | |
} | |
$a = ($a * $b) / $hcf; | |
$ns[] = $a; | |
} | |
return new solution($a, implode(' -> ', $ns)); | |
}, | |
6 => static function (): solution { | |
$a = $b = 0; | |
for ($i = 1; $i <= 100; $i++) { | |
$a += $i ** 2; | |
$b += $i; | |
} | |
$b2 = $b ** 2; | |
$n = $b2 - $a; | |
return new solution($n, sprintf('%d^2 - %d = %d - %d = %d', $b, $a, $b2, $a, $n)); | |
}, | |
7 => static function (): solution { | |
$l = 10_001; | |
$primes = [2]; | |
for ($n = 3; ; $n += 2) { | |
$isPrime = true; | |
foreach ($primes as $p) { | |
if ($n % $p === 0) { | |
$isPrime = false; | |
break; | |
} | |
} | |
if ($isPrime) { | |
$primes[] = $n; | |
} | |
if (count($primes) === $l) { | |
break; | |
} | |
} | |
return new solution($n, '... ' . implode(', ', array_slice($primes, -10))); | |
}, | |
8 => static function (): solution { | |
$a = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'; | |
$n = 0; | |
$l = 13; | |
$ns = []; | |
for ($i = 0; $i < strlen($a) - $l; $i++) { | |
$p = $a[$i]; | |
$cns = [$p]; | |
for ($j = 1; $j < $l; $j++) { | |
$p *= $a[$i + $j]; | |
$cns[] = $a[$i + $j]; | |
} | |
if ($p > $n) { | |
$n = $p; | |
$ns = $cns; | |
} | |
} | |
return new solution($n, implode(' * ', $ns) . ' = ' . $n); | |
}, | |
9 => static function (): solution { | |
$n = 0; | |
for ($a = 3; $a <= 998; $a++) { | |
for ($b = 4; $b <= 998; $b++) { | |
$c = 1000 - $a - $b; | |
if (($a ** 2 + $b ** 2) === $c ** 2) { | |
$n = $a * $b * $c; | |
break 2; | |
} | |
} | |
} | |
return new solution($n, sprintf('%d^2 + %d^2 = %d^2', $a, $b, $c)); | |
}, | |
10 => static function (): solution { | |
$sum = 0; | |
$primes = []; | |
$l = 2_000_000; | |
$processed = []; | |
for ($n = 2; $n < $l; $n++) { | |
if (isset($processed[$n])) { | |
continue ; | |
} | |
$processed[$n] = true; | |
$primes[] = $n; | |
$sum += $n; | |
for ($q = 2; ; $q++) { | |
$m = $q * $n; | |
if ($m >= $l) { | |
break; | |
} | |
$processed[$m] = true; | |
} | |
} | |
return new solution($sum, '... ' . implode(' + ', array_slice($primes, -10)) . ' = ' . $sum); | |
}, | |
11 => static function (): solution { | |
$g = ' | |
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 | |
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 | |
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 | |
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 | |
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 | |
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 | |
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 | |
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 | |
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 | |
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 | |
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 | |
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 | |
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 | |
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 | |
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 | |
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 | |
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 | |
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 | |
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 | |
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 | |
'; | |
$g = array_map( | |
fn($s): array => array_map('intval', explode(' ', trim($s))), | |
explode("\n", trim($g)), | |
); | |
$n = 0; | |
$ns = []; | |
$nsc = 4; | |
$gs = count($g); | |
$dirs = [[0, 1], [1, 0], [1, 1], [1, -1]]; | |
for ($i = 0; $i < $gs; $i++) { | |
for ($j = 0; $j < $gs; $j++) { | |
foreach ($dirs as $vc) { | |
$m = $g[$i][$j]; | |
$cns = [$m]; | |
for ($k = 1; $k <= $nsc - 1; $k++) { | |
$r = $i + $vc[0] * $k; | |
$c = $j + $vc[1] * $k; | |
if ($r <= 0 || $r >= $gs || $c <= 0 || $c >= $gs) { | |
continue 2; | |
} | |
$nb = $g[$r][$c]; | |
$m *= $nb; | |
$cns[] = $nb; | |
} | |
if ($m > $n) { | |
$n = $m; | |
$ns = $cns; | |
} | |
} | |
} | |
} | |
return new solution($n, implode(' * ', $ns) . ' = ' . $n); | |
}, | |
]; | |
$solutions = [ | |
1 => 233_168, | |
2 => 4_613_732, | |
3 => 6_857, | |
4 => 906_609, | |
5 => 232_792_560, | |
6 => 25_164_150, | |
7 => 104_743, | |
8 => 23_514_624_000, | |
9 => 31_875_000, | |
10 => 142_913_828_922, | |
11 => 70_600_674, | |
]; | |
(static function () use ($solvers, $solutions): void { | |
foreach ($solvers as $no => $solver) { | |
$start = hrtime(true); | |
$solution = $solver(); | |
$time = round((hrtime(true) - $start) / 1e6, 2); | |
assert($solution->n === $solutions[$no]); | |
echo '#', $no, ' ', $solution->n, | |
' (', $time, 'ms)', "\n", | |
$solution->info, "\n\n"; | |
} | |
})(); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment