Last active
April 27, 2022 17:42
-
-
Save ultimania92/c087680fa297a6e34429b2d796c29dfc to your computer and use it in GitHub Desktop.
A readable form of a problem presented (given a start and end range as integers, return all numbers that are 'naturally' sorted and have at least one repeating number)
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 | |
/* | |
Some notes; | |
solution takes 2 integers in a range; returns all numbers that are sorted naturally already (number never 'descends' mid-string); | |
Took about 35-40 minutes (5-10 on devising a solution, 20-25ish on writing code) | |
Also there are certainly more loop-based performance optimizations, but PHP is already pretty performant; I like preg_match. | |
*/ | |
function sortNumberStringChars(string $string, bool $reverse=False): string { | |
$stringArray = str_split($string); | |
sort($stringArray); | |
return implode('', $reverse ? array_reverse($stringArray) : $stringArray); | |
} | |
function generateRangePasswordCombinations(int $rangeStart, int $rangeEnd): array { | |
$combinations = []; | |
$repeatingCharRegex = '/(.)\1/'; | |
for($currentNumber = $rangeStart; $currentNumber <= $rangeEnd; $currentNumber++) { | |
/* | |
In short, only two checks here needed: | |
- One additional one I thought of while walking away; any number containing a zero can never be valid under these rules. | |
- A simple repeating char regex works well for a small case like this for detecting repeats. Readability wins in this case. | |
- We can trivially split/sort/implode a string and see if the start/end values are equal (no change). | |
*/ | |
$numStr = strval($currentNumber); | |
if(strpos($numStr, '0')) { continue; } | |
if(preg_match($repeatingCharRegex, $numStr) && sortNumberStringChars($numStr) == $numStr) { | |
$combinations[] = $numStr; | |
} | |
return $combinations; | |
} | |
function solution(int $rangeStart, int $rangeEnd): int { | |
return sizeof(generateRangePasswordCombinations($rangeStart, $rangeEnd)); | |
} | |
// Super-rudimentary testing framework | |
// Add your own cases to verify; No easy trivial way to verify some of these. | |
// First element is your range, second is the expected value. | |
$test_cases = [ | |
[[234660, 234669], 4], // 234666, 234667, 234668, 234669 | |
[[234660, 234678], 5], // Above, but also *77 | |
[[264360, 746325], 945], // The aforementioned test case; | |
]; | |
foreach($test_cases as $case) { | |
$test_range = $case[0]; | |
$result_count = solution($test_range[0], $test_range[1]); | |
print(sprintf("PasswordCombinations: Range %d - %d, ". | |
"expected %d combinations; %d found\n", | |
$test_range[0], $test_range[1], $case[1], $result_count)); | |
} | |
/* | |
And for the PHPUnit fans: | |
We can trivially assert that at higher numbers, we would see less combinations. | |
This is due to the 'decreasing' nature of the number pool, and that | |
the number is already 'naturally' sorted. | |
PHPUnit code: | |
$test->assertGreaterThan(solution(100000,199999), | |
solution(200000,299999), | |
'There should be more values at a lower char range than the higher-bounded range!'); | |
*/ | |
if(solution(100000,199999) > solution(200000,299999)) { | |
print("SUCCESS: Lower numbers have higher range!"); | |
} else { | |
print("ERROR: Lower numbers have lower range!"); | |
} | |
?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment