Project Euler #17, Take Two

So, here's the completed version of the changes I made using the script from my last post.

	use v6;
	my %number_lengths = (
	1 => 3,
	2 => 3,
	3 => 5,
	4 => 4,
	5 => 4,
	6 => 3,
	7 => 5,
	8 => 5,
	9 => 4,
	10 => 3,
	11 => 6,
	12 => 6,
	13 => 8,
	14 => 8,
	15 => 7,
	16 => 7,
	17 => 9,
	18 => 8,
	19 => 8,
	20 => 6,
	30 => 6,
	40 => 5,
	50 => 5,
	60 => 5,
	70 => 7,
	80 => 6,
	90 => 6
	);
	for 1..9 -> $n
	{
	%number_lengths{$n * 100} = %number_lengths{$n} + 7;
	}
	sub NumberLength(@numbers, %number_lengths, $number)
	{
	given $number
	{
	when 0 { return 4; }
	when 1000 { return 11; }
	}
	my $n = $number;
	my $length = 0;
	for @numbers -> $number
	{
	if ($number <= $n)
	{
	$length += %number_lengths{$number};
	$n -= $number;
	}
	}
	return $length;
	}
	my @numbers = %number_lengths.keys.map({+$_}).sort.reverse;
	my $letter = 0;
	for 1..1000 -> $number
	{
	$letter += NumberLength(@numbers, %number_lengths, $number);
	}
	say $letter;

view raw euler_017_02.pl hosted with ❤ by GitHub

It works directly with the number string length rather than the strings themselves, and optimizes the inner loop to only scan the list of numbers with known names once for each call to NumberLength.

The resulting script executes in ten seconds on my MBP, making it about 18 times faster than my first attempt.

I think that's about as far as it is reasonable to take this approach to solving the problem. But that's because this approach, when you get right down to it, is a brute force approach. I suspect there is another huge performance increase to be had by being smarter about the problem. But that is for another day...