This is my response to The Weekly Challenge #246.
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
@a of five integers.
a[n] = p * a[n-2] + q * a[n-1] with n > 1
where p and q must be integers.
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.
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.
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:
p and q values are low.
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.