Challenge
Jack Applegame
japplegame at gmail.com
Sat May 9 22:42:54 UTC 2020
I recently came across an interesting exercise.
Given a series of positive numbers, each of which belongs to the
set
{ 2^^i * 3^^j * 5^^k | i, j, k ≥ 0 }.
The series is ordered in ascending order. The beginning looks
like this:
{ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, ... }
The goal is to get the Nth element of the series. For example,
for N = 10, the answer is 12.
On the Internet, I found an elegant and incredibly fast solution
in Haskell:
```
mergeUniq :: Ord a => [a] -> [a] -> [a]
mergeUniq (x:xs) (y:ys) = case x `compare` y of
EQ -> x : mergeUniq xs ys
LT -> x : mergeUniq xs (y:ys)
GT -> y : mergeUniq (x:xs) ys
powers :: [Integer]
powers = 1 : expand 2 `mergeUniq` expand 3 `mergeUniq` expand 5
where
expand factor = (factor *) <$> powers
main = print $ powers!!999999
```
On my machine, the 1000000th element is found in 0.215s. OMG!
After that, I spent almost the entire day searching for at least
the same fast solution in D.
My first attempt was simple and quite pretty, but awfully slow:
```
import std.stdio;
import std.array;
import std.bigint;
import std.algorithm;
auto generate(int n) {
BigInt[] nums = [BigInt("1")];
foreach(i; 0..n) {
nums = merge(nums, [nums[i] * 2, nums[i] * 3, nums[i] *
5]).uniq().array();
}
return nums[n - 1];
}
void main() {
writeln(generate(5000));
}
```
0.275s for 5000th element.
At the end of the day, I managed to catch up and even overtake
Haskell by emulating its lazyness with ranges and a funny trick.
Victory! :)
If you find this interesting, I will publish my latest version.
And feel free to find your own solution. ;)
More information about the Digitalmars-d-learn
mailing list