74 lines
1.8 KiB
D
74 lines
1.8 KiB
D
import core.stdc.stdio, std.algorithm, std.range;
|
|
|
|
enum factorial = (in uint n) pure nothrow @safe @nogc
|
|
=> reduce!q{a * b}(1u, iota(1u, n + 1));
|
|
|
|
uint iLog10(in uint x) pure nothrow @safe @nogc
|
|
in {
|
|
assert(x > 0);
|
|
} body {
|
|
return (x >= 1_000_000_000) ? 9 :
|
|
(x >= 100_000_000) ? 8 :
|
|
(x >= 10_000_000) ? 7 :
|
|
(x >= 1_000_000) ? 6 :
|
|
(x >= 100_000) ? 5 :
|
|
(x >= 10_000) ? 4 :
|
|
(x >= 1_000) ? 3 :
|
|
(x >= 100) ? 2 :
|
|
(x >= 10) ? 1 : 0;
|
|
}
|
|
|
|
uint nextStep(uint x) pure nothrow @safe @nogc {
|
|
typeof(return) result = 0;
|
|
|
|
while (x > 0) {
|
|
result += (x % 10) ^^ 2;
|
|
x /= 10;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
uint check(in uint[] number) pure nothrow @safe @nogc {
|
|
uint candidate = reduce!((tot, n) => tot * 10 + n)(0, number);
|
|
|
|
while (candidate != 89 && candidate != 1)
|
|
candidate = candidate.nextStep;
|
|
|
|
if (candidate == 89) {
|
|
uint[10] digitsCount;
|
|
foreach (immutable d; number)
|
|
digitsCount[d]++;
|
|
|
|
return reduce!((r, c) => r / c.factorial)
|
|
(number.length.factorial, digitsCount);
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
void main() nothrow @nogc {
|
|
enum uint limit = 100_000_000;
|
|
immutable uint cacheSize = limit.iLog10;
|
|
|
|
uint[cacheSize] number;
|
|
uint result = 0;
|
|
uint i = cacheSize - 1;
|
|
|
|
while (true) {
|
|
if (i == 0 && number[i] == 9)
|
|
break;
|
|
if (i == cacheSize - 1 && number[i] < 9) {
|
|
number[i]++;
|
|
result += number.check;
|
|
} else if (number[i] == 9) {
|
|
i--;
|
|
} else {
|
|
number[i]++;
|
|
number[i + 1 .. $] = number[i];
|
|
i = cacheSize - 1;
|
|
result += number.check;
|
|
}
|
|
}
|
|
|
|
printf("%u\n", result);
|
|
}
|