Last active
March 11, 2018 18:17
-
-
Save stevenpray/3d15e91b572c086ac487864463e68d33 to your computer and use it in GitHub Desktop.
Project Euler 92: Investigating a square digits number chain with a surprising property. How many starting numbers below ten million will arrive at 89?
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); | |
ini_set('memory_limit', '1G'); | |
ini_set('max_execution_time', '0'); | |
/** | |
* Maps the given number to array of its digits. | |
* | |
* @param int $number | |
* @return int[]|false | |
*/ | |
function num_split(int $number): array | |
{ | |
$chars = str_split((string)$number); | |
if (!is_array($chars)) { | |
return false; | |
} | |
$digits = []; | |
foreach ($chars as $char) { | |
$digits[] = (int)$char; | |
} | |
return $digits; | |
} | |
// assert(count(array_diff([4, 4], num_split(44))) === 0); | |
// assert(count(array_diff([8, 9], num_split(89))) === 0); | |
// assert(count(array_diff([1, 0, 0, 0, 0, 0, 0, 0], num_split(10000000))) === 0); | |
/** | |
* Reduces the given number to the square of its digits. | |
* | |
* @param int $number | |
* @return int | |
*/ | |
function square_digits(int $number): int | |
{ | |
$digits = num_split($number); | |
$total = 0; | |
foreach ($digits as $digit) { | |
$total += $digit ** 2; | |
} | |
return $total; | |
} | |
// assert(square_digits(44) === 32); | |
// assert(square_digits(85) === 89); | |
// assert(square_digits(10000000) === 1); | |
/** | |
* Return the termination value of 1 or 89 for the given number. | |
* | |
* @param int $number | |
* @return int | |
*/ | |
function terminate(int $number): int | |
{ | |
/** @var int[] $TERMINATIONS */ | |
global $TERMINATIONS; | |
if (in_array($number, [1, 89], true)) { | |
return $number; | |
} | |
if (is_array($TERMINATIONS) && array_key_exists($number, $TERMINATIONS)) { | |
return $TERMINATIONS[$number]; | |
} | |
$TERMINATIONS[$number] = terminate(square_digits($number)); | |
return $TERMINATIONS[$number]; | |
} | |
// assert(terminate(44) === 1); | |
// assert(terminate(85) === 89); | |
// assert(terminate(10000000) === 1); | |
$start = microtime(true); | |
$count = 0; | |
for ($i = 1; $i <= 10000; $i++) { | |
if (terminate($i) === 89) { | |
$count++; | |
} | |
} | |
echo $count, PHP_EOL; | |
echo microtime(true) - $start, PHP_EOL; | |
echo memory_get_peak_usage(true), PHP_EOL; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment