Perl Weekly Challenge: Week 23

Challenge 1:

Create a script that prints nth order forward difference series. You should be a able to pass the list of numbers and order number as command line parameters. Let me show you with an example.

Suppose we have list (X) of numbers: 5, 9, 2, 8, 1, 6 and we would like to create 1st order forward difference series (Y). So using the formula Y(i) = X(i+1) - X(i), we get the following numbers: (9-5), (2-9), (8-2), (1-8), (6-1). In short, the final series would be: 4, -7, 6, -7, 5. If you noticed, it has one less number than the original series. Similary you can carry on 2nd order forward difference series like: (-7-4), (6+7), (-7-6), (5+7) => -11, 13, -13, 12.

This is trivial to translate into code. This is Perl5:

for (0 .. $opts{'n'} - 1) {
    @series = map { $series[$_] - $series[$_ - 1] } (1 .. $#series);
}

(Full code on Github.)

and this is Perl6:

for 0 ..^ $n {
    @series = (1 ..^ @series.elems).map({ @series[$_] - @series[$_ - 1] });
}

(Full code on Github.)

Challenge 2:

Create a script that prints Prime Decomposition of a given number. The prime decomposition of a number is defined as a list of prime numbers which when all multiplied together, are equal to that number. For example, the Prime decomposition of 228 is 2,2,3,19 as 228 = 2 * 2 * 3 * 19.

This page was a useful extra resource for understanding how to solve this challenge though in the end I didn't use a tree data structure as it recommends.

For Perl5, I once again pulled out my trusty isPrime() and nextPrime() functions which I used in previous weeks challenges in order to create a recursive function for finding prime factors.

sub factorize {
    my ($n, $primeFactors) = @_;
    if ($n < 2) {
        return;
    }

    my $p = nextPrime(1);
    while ($p <= $n) {

        if ($n % $p == 0) {
            push @{$primeFactors}, $p;
            factorize($n / $p, $primeFactors);
        }
        $p = nextPrime();
    }
}

I had to make a small modification to nextPrime() though. It uses a state variable, $i, to keep track of where it is in the sequence of integers so it can find the next prime number. The next time it is called, it will pick up where it left off. This has been good enough for previous challenges but this time we need to restart the sequence in every call to factorize(). So I've added an optional parameter which will reset the value of $i if present.

sub nextPrime {
    state $i = 1;
    if (scalar @_) {
        $i = shift;
    }

    while ($i++) {
        if (isPrime($i)) {
            return $i;
        }
    }
}

(Full code on Github.)

For Perl6 we don't need any extra functions because testing for primes is built-in. The Perl6 version of factorize() looks like this:

sub factorize(Int $n, @primeFactors) {
    if $n < 2 {
        return;
    }

    my $i = 0;
    my @primes = (1 .. ∞).grep({ .is-prime });
    my $p = @primes[$i];

    while $p <= $n {

        if $n %% $p {
            @primeFactors.push($p);
            factorize($n div $p, @primeFactors);
            return;
        }
        $p = @primes[$i++];
    }
}

(Full code on Github.)