blob: 0fbc29baa1147e5454ad28ea3717bc53c4b4d714 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
my Int $hits = 0;
my Int $miss = 0;
multi sub MAIN( Int $N, :$s )
{
my ($n, @c) = collatz( $N );
say "n: $n, length: { @c.elems }";
say @c.join( ',' );
}
multi sub MAIN( Int $N, :$l )
{
my $start = now;
my %result;
for 1..$N -> $n
{
my Int $count = 0;
my Int $cache = 0;
my @new = gather for collatz( $n ) -> $collatz
{
# Dynamic programming:
# see what you have computed so far, so you
# don't have to compute it again
if %result{ $collatz }:exists
{
$hits += $cache = %result{ $collatz };
last;
}
$miss++;
take $collatz, $count++;
}
%result{ .[0] } = @new.elems - .[1] + $cache
for @new;
}
# say "halftime: { now - $start } seconds";
say "n: { .key }, length: { .value - 1 }" for
%result
.grep( *.key < $N )
.sort( *.value * -1 )
.head(20);
say "runtime: { now - $start }";
say "cache misses: $miss, cache hits: $hits";
}
sub collatz( Int $n ) is pure
{
$n, { $^n %% 2 ?? $^n div 2 !! $^n * 3 + 1 } ... { $^n == 1 }
}
|
