PWC 246 Random use of algebra

It's December, and that means neglecting our responsibilities with Advent of Code. But there's still time to squeeze in the Perl Weekly Challenge, too.

Task 1: 6 out of 49

6 out of 49 is a German lottery.
Write a script that outputs six unique
random integers from the range 1 to 49.

Let's be random. 6 out of 49. 25 or 6 to 4. Weasels ripped my flesh. My hovercraft is full of eels.

'Tis easy, if we remember that Perl has a rand() function, and if we remember how it works. int(rand(49)) returns a number between 0 and 48, so we need to bump it to move it between 1 and 49. Then, we need to do it six times, and to make it look more like lottery results, let's sort, too. It's a one-liner from the shell prompt.

perl -wE 'say for sort { $a <=> $b} map { int(rand(49)) + 1 } 1..6;'

-wE -- what's that? -w enables warnings, always a good idea. -E (as opposed to -e) executes the following string but also enables optional features, which is convenient for allowing say.

So that was really easy. Too bad it's wrong. The problem is that these numbers are supposed to act like lottery picks. That means they should be six unique numbers, and there's no guarantee that our simple answer won't contain duplicates. So, let's use a hash and pick numbers until we get six unique ones:

my %seen;
while ( scalar(keys %seen) < 6 )
{
    $seen{ int(rand(49)) + 1 } = 1;
}
say for sort { $a <=> $b } keys %seen;

Task 2: Linear Recurrence of Second Order

You are given an array @a of five integers.
Write a script to decide whether the given
integers form a linear recurrence of second
order with integer factors.

A linear recurrence of second order has the form
a[n] = p * a[n-2] + q * a[n-1] with n > 1
where p and q must be integers.

• Example 1: 1,1,2,3,5 is a second-order linear recurrence because a[n] = a[n-2] + a[n-1] (it's the beginning of the Fibonacci sequence of course).
• Example 2: 2,4,2,5,7 can't be a linear recurrence because it starts with multiples of even numbers, and therefore no combination of them will yield an odd number.
• Example 3: 4,1,2,-3,8 is a sequence that can be created with the recurrence a[n] = a[n-2] - 2 * a[n-1]

It's time to smugly take revenge on the bozos in algebra class who used to whine, "But when will we ever use this in real life?" Ha! The time has come, and as far as I can tell, this is real life. Or a damn good simulation.

To be a second-order recurrence relation, we have to find p and q that solve the set of equations

• a[0]*p + a[1]*q = a[2]
• a[1]*p + a[2]*q = a[3]
• a[2]*p + a[3]*q = a[4]

We can the first pair of these to solve for p and q in terms of the elements of a, and using those values of p and q, we also have to verify that a[4] can be generated from a[2]*p + a[3]*q = a[4]

From the first equation, we will get
p = (a[2] - a[1]*q)/a[0]
Substituting that into the second equation, we will get
q = (a[1]*a[2] - a[0]*a[3]) / (a[1]*a[1] - a[0]*a[2] )

So, given a sequence of at least 4 values, we can determine q, and from that we can determine p. Both have to be integers, per the problem statement. It's also possible that one of those denominators is zero, meaning that the recurrence can't be satisfied.

There are some odd cases. For instance, if a[0] is zero, then we will not be able to determine p. Or if the sequence starts out, for example, with 4,6,9, then our equation for q will have 0 as its denominator (6*6 - 4*9). For this reason, we should check for these possibilities, and if these equations don't work, we can alternatively use the second and third equations as a way to find p and q. For the moment, let's ignore that and write the code that implements what we have so far.

We could golf this down to some pretty cryptic code, but let's throw a bone to readability this week. First step, let's define the function that produces q:

sub fq($a0, $a1, $a2, $a3)
{
    my $denom = $a1*$a1 - $a0*$a2;
    return undef if $denom == 0;
    my $q = ($a1*$a2 - $a0*$a3)/$denom;
    return $q;
}

Amusing aside: I originally wanted to call this function q, but it gave me weird results. Do you see it? Of course: q is the built-in single-quote operator. A function q can be defined, but it can't be called because it won't override the operator.

Second step, let's define the function that produces p.

sub fp($q, $a0, $a1, $a2)
{
    return undef if $a0 == 0;
    my $p = ($a2 - $a1 * $q) / $a0;
    return $p;
}

And if we can find p and q, then we can write the code to check for a linear recurrence:

sub isl2(@a)
{
    my $q = fq( @a[0..3] );
    return false unless defined $q && int($q) == $q;

    my $p = fp($q, @a[0..2]);
    return false unless defined $p && int($p) == $p;

    # Must also be true for remaing values of @a
    for my $i ( 4 .. $#a )
    {
        my $nexta = $p * $a[$i-2] + $q * $a[$i-1];
        if ( $a[$i] != $nexta )
        {
            return false;
        }
    }
    return true;
}

Where did true and false come from? Since version 5.36, these booleans are available as built-ins, and this was a natural place to use them. They're still experimental, so using them requires

use builtin qw/true false/; no warnings "experimental::builtin"