Rafraîchissoir

By Shahed Nooshmand

Perl Weekly Challenge: week 54

Here are my solutions for this week’s tasks:

Task #1

Write a script to accept two integers n (>=1) and k (>=1). It should print the kth permutation of n integers.

Here’s a one-liner for that:

raku -e 'say [~] (1..get).permutations[get−1]'

The only thing to note is that the first get is our ‘n’ and the second one is our ‘k’, which we get in that order.

Task #2

Ah, the Collatz conjecture. Here you go:

raku -e 'put “\e[F\e[K” ~ join “ → ”, (prompt(“\n”).trim-trailing, -> \n { n %% 2 ?? n ÷ 2 !! 3 × n + 1 } … 1)'

Here’s how it works: we get a number, start a sequence with it, put it into ‘n’, and calculate the next term based on whether ‘n’ is even or not. We keep doing this until we reach 1.

To make the result look nicer, we put an arrow between the terms. The “\e[F\e[K” is just two ANSI escape codes; \e[F takes the cursor to the beginning of the previous line, and \e[K clears to the end of the line. This way, when we enter 23 as input, instead of having to look at this:

23
23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

We simply see this:

23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Now we get to the Extra credit:

Have your script calculate the sequence length for all starting numbers up to 1000000 (1e6), and output the starting number and sequence length for the longest 20 sequences.

Lazy people like me might be tempted to solve this problem with the following one-liner:

raku -e '.put for (gather {take $_ => +($_, { $_ %% 2 ?? $_ ÷ 2 !! 3 × $_ + 1 } … 1) for 1..^1e6}).sort(−*.value)[^20]'

What this script does is that it basically maps every number from one up to a million to the size of its corresponding hailstone sequence, and then sorts the map by those sizes, takes out the top 20, and shows them.

However, this script is slow. Like, really slow. It’s so slow, it hurts my impatience.

The issue, I think, is that for every number we are generating a whole sequence all the way down to 1. That takes time. Instead, we could generate as much of it as we need, and use a previously generated sequence to complete it. For example, given 10, since we know the “8 → 4 → 2 → 1” already, we just calculate the “10 → 5 → 16 → 8”.

So, here’s a script that keeps track of previous sequences and reuses them when needed:

#!/usr/bin/env raku

my %hail = 1 => 1;

for 1..^1e6 {
	my $n = $_;
	my $i = 0;
	until %hail{$n}:exists {
		$n = $n %% 2 ?? $n ÷ 2 !! $n × 3 + 1;
		$i++
	}
	%hail{$_} = $i + %hail{$n}
}

.put for %hail.sort(−*.value)[^20]

This one took about two minutes, which is still a lot. But this time, it’s not the algorithm’s fault. With a few changes, the Raku script above becomes the following Perl script:

#!/usr/bin/env perl

my %hail = (1 => 1);

for (1..1e6-1) {
	my $n = $_;
	my $i = 0;
	until (exists $hail{$n}) {
		$n = $n % 2 ? $n * 3 + 1 : $n / 2;
		$i++
	}
	$hail{$_} = $i + $hail{$n}
}

print "$_	$hail{$_}\n" for (sort { $hail{$b} <=> $hail{$a} } keys %hail)[0..19]

Which took about 9 seconds to finish.