Hey, when the first task is “6 out of 49”, I challenge you to not hear Chicago in your head.

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.

Output

3
10
11
22
38
49

Approach

We need to generate 6 unique numbers, so we need to quickly check to see if a number we’ve generated is already part of the output set. Sounds like hashes to me.

Raku

Except when I went to refresh my memory about how Raku did random numbers, I remembered that there was a special routine on the List class: pick.

routine pick

multi sub    pick($count, *@list --> Seq:D)
multi method pick(List:D: $count --> Seq:D)
multi method pick(List:D: --> Mu)
multi method pick(List:D: Callable $calculate --> Seq:D)

If $count is supplied: Returns $count elements chosen at random and without repetition from the invocant. If * is passed as $count, or $count is greater than or equal to the size of the list, then all elements from the invocant list are returned in a random sequence; i.e. they are returned shuffled.

In method form, if $count is omitted: Returns a single random item from the list, or Nil if the list is empty

Since it returns a number of elements chosen at random without repetition, there’s all our work done for us. All we need to do is generate a list of integers from 1 to 49:

sub sixOutOfFourtyNine {
  return (1 .. 49).pick(6).sort;
}

I’m sorting the results as well, because that’s how the sample output was presented.

View the entire Raku script for this task on GitHub.

Approach Revision

But now that I’ve got the Raku version under my belt, I’m rethinking my approach. Why generate potentially duplicate random numbers, when I can generate the set of numbers from 1 – 49, and SHUFFLE those numbers, and then just pull the first 6 values off that list.

Perl

use List::Util qw( shuffle );

sub sixOutOfFourtyNine {
  return sort { $a <=> $b } ( shuffle(1 .. 49) )[0 .. 5];
}

View the entire Perl script for this task on GitHub.

Python

Except… when I went to look in the random module in Python to see if it had a shuffle method, I found out that not only did it have one…

random.shuffle(x)

Shuffle the sequence x in place.

To shuffle an immutable sequence and return a new shuffled list, use sample(x, k=len(x)) instead.

So there was a sample method that “Returns a k length list of unique elements chosen from the population sequence. Used for random sampling without replacement.” Bingo! Just what we need!

from random import sample

def sixOutOfFourtyNine():
    return sorted(sample(range(1, 49), 6))

View the entire Python script for this task on GitHub.

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

Input: @a = (1, 1, 2, 3, 5)
Output: true

@a is the initial part of the Fibonacci sequence a[n] = a[n-2] + a[n-1]
with a[0] = 1 and a[1] = 1.

Example 2

Input: @a = (4, 2, 4, 5, 7)
Output: false

a[1] and a[2] are even. Any linear combination of two even numbers with integer factors is even, too.
Because a[3] is odd, the given numbers cannot form a linear recurrence of second order with integer factors.

Example 3

Input: @a = (4, 1, 2, -3, 8)
Output: true

a[n] = a[n-2] - 2 * a[n-1]

Approach

Ok, so to determine if a sequence is a linear recurrence of second order we need to start examining the third element onwards and see if it’s the sum of integer multiples of the previous two values in the sequence (q times the previous value, p times the value before that).

I decided that there has to be an already-established way for solving these, and when I went looking, I found that there is: Cramer’s rule. If we have a linear system

then the values for x and y can be found with this formula:

To render this in our a[n] / p / q notation, then we get

p = (a[2] * a[2] - a[1] * a[3]) / (a[0] * a[2] - a[1] * a[1])
q = (a[0] * a[3] - a[2] * a[1]) / (a[0] * a[2] - a[1] * a[1])

If p and q have integer solutions (and the solutions for elements 0..3 are the same for 1..4), we’ve got a linear recurrence of second order.

Raku

sub findPandQ(@a) {
  my $p = (@a[2] * @a[2] - @a[1] * @a[3])
        / (@a[0] * @a[2] - @a[1] * @a[1]);
  my $q = (@a[0] * @a[3] - @a[2] * @a[1])
        / (@a[0] * @a[2] - @a[1] * @a[1]);
  return($p, $q);
}

sub isLinearRecurranceOfSecondOrder(@a) {
  my ($p1, $q1) = findPandQ(@a[0 .. 3]);
  my ($p2, $q2) = findPandQ(@a[1 .. 4]);
  if ($p1 != $p2 || $q1 != $q2) {
    say "Values for P ($p1, $p2) and Q ($q1, $q2) "
      ~ "are not consistent across all five elements";
    return False;
  }
  if ($p1 != $p1.Int || $q1 != $q1.Int) {
    say "Values for P ($p1) and Q ($q1) for first "
      ~ "four elements are not integers";
    return False;
  }
  say "Found integer values for P ($p1) and Q ($q1)";
  return True;
}

Here I’d like to show the output of my script:

$ raku/ch-2.raku
Example 1:
Input: @a = (1, 1, 2, 3, 5)
Found integer values for P (1) and Q (1)
Output: True

Example 2:
Input: @a = (4, 2, 4, 5, 7)
Values for P (0.5) and Q (1) for first four elements are not integers
Output: False

Example 3:
Input: @a = (4, 1, 2, -3, 8)
Found integer values for P (1) and Q (-2)
Output: True

It’s not that there aren’t factors p and q for the sequence in the second example; it’s that the factors aren’t both integers.

View the entire Raku script for this task on GitHub.

Perl

sub findPandQ {
  my @a = @_;
  my $p = ($a[2] * $a[2] - $a[1] * $a[3])
        / ($a[0] * $a[2] - $a[1] * $a[1]);
  my $q = ($a[0] * $a[3] - $a[2] * $a[1])
        / ($a[0] * $a[2] - $a[1] * $a[1]);
  return($p, $q);
}

sub isLinearRecurranceOfSecondOrder {
  my @a = @_;
  my ($p1, $q1) = findPandQ(@a[0 .. 3]);
  my ($p2, $q2) = findPandQ(@a[1 .. 4]);
  if ($p1 != $p2 || $q1 != $q2) {
    say "Values for P ($p1, $p2) and Q ($q1, $q2) "
      . "are not consistent across all five elements";
    return 0;
  }
  if ($p1 != int($p1) || $q1 != int($q1)) {
    say "Values for P ($p1) and Q ($q1) for first "
      . "four elements are not integers";
    return 0;
  }
  say "Found integer values for P ($p1) and Q ($q1)";
  return 1;
}

I don’t know why I’m not using Perl’s function signatures; they’ve been the default since Perl 5.36; but they still don’t feel very perl-ish to me. If I used them, though, the only changes from the Raku version would be

• $ sigil instead of @ for accessing individual array values
• . instead of ~ for string concatenation
• int($var) instead of $var.Int to get the integer portion of a variable
• Using 1 / 0 for booleans instead of the Raku Bools True / False.

View the entire Perl script for this task on GitHub.

Python

def findPandQ(a):
    p = (
      (a[2] * a[2] - a[1] * a[3])
      /
      (a[0] * a[2] - a[1] * a[1])
    )
    q = (
      (a[0] * a[3] - a[2] * a[1])
      / 
      (a[0] * a[2] - a[1] * a[1])
    )
    return(p, q)


def isLinearRecurranceOfSecondOrder(a):
    (p1, q1) = findPandQ(a[0:4])
    (p2, q2) = findPandQ(a[1:5])
    if p1 != p2 or q1 != q2:
        print(f'Values for P ({p1}, {p2}) ', end='')
        print(f'and Q ({q1}, {q2}) ', end='')
        print(f'are not consistent across all five elements')
        return False
    if p1 != int(p1) or q1 != int(q1):
        print(f'Values for P ({p1}) ', end='')
        print(f'and Q ({q1}) ', end='')
        print(f'for first four elements are not integers')
        return False

    print(f'Found integer values for P ({int(p1)}) ', end='')
    print(f'and Q ({int(q1)})')
    return True

The thing I have to remember about Python slices is that the ending element is not included in the slice. So a[0:3] will give me elements 0, 1, and 2, but not 3.

View the entire Python script for this task on GitHub.

Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-246/packy-anderson