with Raku and Friends

This is my response to The Weekly Challenge #246.

6 out of 49 is a German lottery.

Write a script that outputs six unique random integers from the range 1 to 49.

Output:

Write a script that outputs six unique random integers from the range 1 to 49.

Output:

3
10
11
22
38
49

This is extremely easy:

File: 6-out-of-49#! /usr/bin/env raku
(1..49).pick(6).sort>>.say;

We start with the sequence `1..49`

, then `pick`

6 random values (without repetition) from that sequence. Then we `sort`

the selection (numerically, as the values are integers) as the challenge seems to
imply that we should, and finally apply `say`

on each value (with the
`>>.`

invocation) so that each one is printed on a seperate line.

See docs.raku.org/routine/pick for more information about `pick`

.

See docs.raku.org/routine/sort for more information about `sort`

.

Running it:

$ ./6-out-of-49
12
13
28
41
43
45
$ ./6-out-of-49
1
3
13
16
17
33

The numbers may look random. But you should not bet your life (or money, or somebody else's life or money) on a computer being able to generate truly random numbers.

#! /usr/bin/env perl
my %six; # [1]
while (keys %six < 6) # [2]
{
$six{ int(1+ rand(48)) } = 1; # [2a]
}
foreach my $key (sort { $a <=> $b } keys %six) # [3]
{
print "$key\n"; # [3a]
}

[1] We are going to store the random numbers in this hash, thus eliminating duplicates automatically.

[2] As long as have not gotten the six numbers, add a new one to the hash.

[3] Sort the keys (the numbers) numerically, and print them on separate lines.

Running ut gives the (un)expected result:

$ ./6-out-of-49.perl
12
19
34
38
42
45
$ ./6-out-of-49.perl
5
7
12
21
23
40

#! /usr/bin/env ruby
six = {}
while six.length < 6 do
six[ rand(1...49) ] = 1
end
seven = [];
six.each do |key, value| # [1]
seven.push key
end
seven.sort { |a,b| a <=> b }.each do |key| # [2]
puts key
end

Running it:

$ ./6-out-of-49.ruby
7
11
12
24
33
47
$ ./6-out-of-49.ruby
30
36
38
43
44
48

#! /bin/bash
declare -A SIX
for (( ; ; ))
do
key=$(($RANDOM % 49 + 1))
SIX[$key]=1
if [ ${#SIX[*]} -gt 5 ]; then
break
fi
done
IFS=$'\n' sorted=($(sort -n <<<"${!SIX[*]}"))
unset IFS
for value in ${sorted[@]}; do
echo "$value"
done

Running it:

$ ./6-out-of-49.sh
5
6
17
29
44
48
$ ./6-out-of-49.sh
4
6
27
29
35
46

CREATE TABLE lotto (Value INT NOT NULL);
INSERT INTO lotto VALUES
(1), (2), (3), (4), (5), (6), (7), (8), (9), (10),
(11),(12),(13),(14),(15),(16),(17),(18),(19),(20),
(21),(22),(23),(24),(25),(26),(27),(28),(29),(30),
(31),(32),(33),(34),(35),(36),(37),(38),(39),(40),
(41),(42),(43),(43),(45),(46),(47),(48),(49);
-- SELECT * FROM lotto ORDER BY RANDOM() LIMIT 6;
SELECT * FROM (SELECT * FROM lotto ORDER BY RANDOM() LIMIT 6) ORDER BY Value;

The **first** block (`CREATE`

) is the creation of a database
table.

The **second** block (`INSERT`

) adds 49 rows to this table,
each with a single value (from 1 to 49).

The **third** block (`-- SELECT`

) selects 6 values randomly,
without repetition. But the order is random as well, so it is commented
out (with the sql `--`

start of comment marker.

The **fourth** and final block (`SELECT`

) wraps the expression
from the third block into a select that orders the values.

Run it by feeding the file to the «sqlite3» command:

$ sqlite3 < ./6-out-of-49.sql
2
10
33
36
39
49
$ sqlite3 < ./6-out-of-49.sql
2
5
7
10
46
49

You are given an array

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

Example 1:

`@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]

Let us take a look at the first example, the Fibonacci sequence (the
1 based version of it). Here both `p`

and `q`

are
`1`

.

We can specify it with this Raku code:

(1, 1, * + * ... Inf)

This is Sequence #041 in my Centenary Sequences with Raku - Part 4: Primes and Fibonacci article.

Ok. But that does not really help us.

Let us go back to the examples. Som observations:

- All the values are single digits. This (hopefully) implies that the
`p`

and`q`

values are low. - The 4th value in the third example is negative. This implies that
either
`p`

or`q`

is negative.

We are going to solve this with loops for the `p`

and `q`

values. I have chosen to use -10 and 10 as lower and upper limits. But is this
reasonable? Let use try to reverse engineer the task, and find out.

The following program gives us the sequence, given the two first values and
`p`

and `q`

:

#! /usr/bin/env raku
unit sub MAIN (Int $first, # [1]
Int $second, # [1a]
Int :$p = 1, # [2]
Int :$q = 1, # [2a]
UInt :$limit = 10); # [3]
my $seq := ($first, $second, $p * * + $q * * ... Inf); # [4]
say $seq[^$limit].join(", "); # [5]

[1] The first and second values.

[2] The `p`

and `q`

values, as named parameters with
default value 1.

[3] The number of values to print from the sequence.

[4] The first and third stars are mutiplication operators, and the second and fourth ones are placeholder variables that refer back to the previous values in the sequence.

[5] Pretty print the requested number of vales. Note that the sequnce is lazy, so it will only generate the values that is requested (printed, in this case).

Running it:

$ ./reverse-lroso 1 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55

That is the Fibonacci sequence.

Let us try with different `p`

and `q`

values:

$ ./reverse-lroso -p=10 -q=10 1 1
1, 1, 20, 210, 2300, 25100, 274000, 2991000, 32650000, 356410000
$ ./reverse-lroso -p=10 -q=-10 1 1
1, 1, 0, 10, -100, 1100, -12000, 131000, -1430000, 15610000
$ ./reverse-lroso -p=12 -q=-12 1 1
1, 1, 0, 12, -144, 1872, -24192, 312768, -4043520, 52275456
$ ./reverse-lroso -p=12 -q=-2 1 1
1, 1, 10, -8, 136, -368, 2368, -9152, 46720, -203264
$ ./reverse-lroso -p=12 -q=1 1 1
1, 1, 13, 25, 181, 481, 2653, 8425, 40261, 141361
$ ./reverse-lroso -p=-1 -q=-1 1 1
1, 1, -2, 1, 1, -2, 1, 1, -2, 1
$ ./reverse-lroso -p=-1 -q=-2 1 1
1, 1, -3, 5, -7, 9, -11, 13, -15, 17
$ ./reverse-lroso -p=-2 -q=-1 1 1
1, 1, -3, 1, 5, -7, -3, 17, -11, -23
$ ./reverse-lroso -p=-2 -q=-2 1 1
1, 1, -4, 6, -4, -4, 16, -24, 16, 16
$ ./reverse-lroso -p=10 -q=9 1 1
1, 1, 19, 181, 1819, 18181, 181819, 1818181, 18181819, 181818181

The -10 and 10 limits seems reasonable, for the examples given in the challenge.

But the program will not be able to detect the examples above
where either `p`

, `q`

or both are outside of those
limits. That may be a problem...

#! /usr/bin/env raku
unit sub MAIN (*@a where @a.elems == 5 && all(@a) ~~ Int, # [1]
:v(:$verbose));
for -10 .. 10 -> $p # [2]
{
for -10 .. 10 -> $q # [3]
{
is-lroso(@a, $p, $q) if $p * @a[0] + $q * @a[1] == @a[2]; # [4]
}
}
say 'false'; # [5]
sub is-lroso (@a is copy, $p, $q) # [6]
{
my $first = @a.shift; # [7]
my $second = @a.shift; # [8]
my $target; # [9]
while (@a.elems) # [10]
{
$target = @a.shift; # [11]
return unless $p * $first + $q * $second == $target; # [12]
$first = $second; # [13]
$second = $target; # [14]
}
say ": p:$p, q:$q" if $verbose;
say 'true'; # [15]
exit; # [15a]
}

[1] The 5 integers.

[2] Iterate over the possible values for `p`

.

[3] Ditto for `q`

.

[4] Check the rest of the values, but only if the third one is as expected. The condition is here to speed up the program. Feel free to remove it.

[5] We have not found a match at all, then we have failed. Say so.

[6] Procedure cheking if the sequence can be generated
with the `p`

and `q`

values. Note the
`is copy`

so that we can change this variable.

See docs.raku.org/type/Signature#index-entry-trait_is_copy for more information about `is copy`

.

[7] Get the first value.

[8] And the second.

[9] The target, or the third value, will be placed here.

[10] As long as we have more values to check.

[11] Set the target, what we expect to get as the next value in the sequence.

[12] Return if we do not get the target by applying the rule.

[13,14] Set the first and second values ready for the next iteration.

[15] We have verified the rule if we get here. Say so, and terminate the porgram.

Running it:

$ ./lroso 1 1 2 3 5
true
$ ./lroso 4 2 4 5 7
false
$ ./lroso 4 1 2 -3 8
true

Looking good.

Verbose mode will give you the values of `p`

and
`q`

:

$ ./lroso -v 1 1 2 3 5
: p:1, q:1
true
$ ./lroso -v 4 2 4 5 7
false
$ ./lroso -v 4 1 2 -3 8
: p:1, q:-2
true

Do remember that `p`

and/or `q`

outside the limits
(-10 .. 10) will not be detected:

$ ./reverse-lroso -p=12 -q=12 1 1
1, 1, 24, 300, 3888, 50256, 649728, 8399808, 108594432, 1403930880
$ ./lroso 1 1 24 300 3888
false

And that's it.