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…
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 concatenationint($var)
instead of$var.Int
to get the integer portion of a variable- Using
1
/0
for booleans instead of the Raku BoolsTrue
/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