diff options
| -rw-r--r-- | challenge-123/abigail/perl/ch-1.pl | 20 |
1 files changed, 13 insertions, 7 deletions
diff --git a/challenge-123/abigail/perl/ch-1.pl b/challenge-123/abigail/perl/ch-1.pl index 83fb0e30ec..37077af736 100644 --- a/challenge-123/abigail/perl/ch-1.pl +++ b/challenge-123/abigail/perl/ch-1.pl @@ -19,19 +19,21 @@ use experimental 'lexical_subs'; use List::Util qw [min]; my @ugly = (1); -my @primes = (2, 3, 5); -my %next = map {$_ => 0} @primes; +my $next_2 = 0; +my $next_3 = 0; +my $next_5 = 0; # # We will maintain the following invariants: # -# Foreach $p in @primes: -# $p * $ugly [$next {$p} - 1] <= $ugly [-1] < $p * $ugly [$next {$p}] +# 2 * $ugly [$next_2 - 1] <= $ugly [-1] < 2 * $ugly [$next_2] +# 3 * $ugly [$next_3 - 1] <= $ugly [-1] < 3 * $ugly [$next_2] +# 5 * $ugly [$next_5 - 1] <= $ugly [-1] < 5 * $ugly [$next_2] # # And since every ugly number (except the first) is either twice an # ugly number, three times an ugly number, or five times an ugly # number, the next ugly number will be the minimum of -# (2 * $ugly [$next {2}], 3 * $ugly [$next {3}], 5 * $ugly [$next {5}]). +# (2 * $ugly [$next_2], 3 * $ugly [$next_3], 5 * $ugly [$next_5]). # # We will spend O(1) time per generated ugly number, so our # program will run in O(N) time, using O(N) memory. @@ -42,14 +44,18 @@ while (my $n = <>) { # # Calculate the next ugly number. # - push @ugly => min map {$_ * $ugly [$next {$_}]} @primes; + push @ugly => min 2 * $ugly [$next_2], + 3 * $ugly [$next_3], + 5 * $ugly [$next_5]; # # Update pointers. It could be that more than one pointer needs # updating. (This happens if the ugly number generated is # divisible by 6, 10, 15, or 30). No pointer ever needs updating twice. # - $_ * $ugly [$next {$_}] <= $ugly [-1] and $next {$_} ++ for @primes; + $next_2 ++ if 2 * $ugly [$next_2] <= $ugly [-1]; + $next_3 ++ if 3 * $ugly [$next_3] <= $ugly [-1]; + $next_5 ++ if 5 * $ugly [$next_5] <= $ugly [-1]; } say $ugly [-1]; } |