diff options
67 files changed, 4004 insertions, 2253 deletions
diff --git a/challenge-246/cheok-yin-fung/blog.txt b/challenge-246/cheok-yin-fung/blog.txt new file mode 100644 index 0000000000..c44901c6bc --- /dev/null +++ b/challenge-246/cheok-yin-fung/blog.txt @@ -0,0 +1 @@ +https://e7-87-83.github.io/coding/challenge_246.html diff --git a/challenge-246/cheok-yin-fung/perl/ch-2.pl b/challenge-246/cheok-yin-fung/perl/ch-2.pl index 6bb71825bc..06db7aa977 100644 --- a/challenge-246/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-246/cheok-yin-fung/perl/ch-2.pl @@ -76,7 +76,7 @@ sub check { return 0 if $a[3] % $d1 != 0; $u0 = $u0 *($a[3]/$d1); $v0 = $v0 *($a[3]/$d1); - say "$a[3] = $a0*$u0+$b0*$v0"; + say "$a[3] = $a1*$u0+$b1*$v0"; # for my $j (-10..10) { # my $x1 = $u0 + $b1/$d1*$j ; # my $y1 = $v0 - $a1/$d1*$j; @@ -112,7 +112,7 @@ sub check { } } -use Test::More tests=>10; +use Test::More tests=>11; ok check(1, 1, 2, 3, 5); ok !check(4, 2, 4, 5, 7); ok check(4, 1, 2, -3, 8); @@ -126,3 +126,4 @@ ok check(1, 0, 0, 0, 0); ok check(0, 3, 0, 0, 0); ok !check(0, 0, 3, 0, 0); +ok check(2, 4, 8, 16, 32); diff --git a/challenge-246/dave-jacoby/blog.txt b/challenge-246/dave-jacoby/blog.txt new file mode 100644 index 0000000000..dad54dfbf8 --- /dev/null +++ b/challenge-246/dave-jacoby/blog.txt @@ -0,0 +1 @@ +https://jacoby.github.io/2023/12/05/make-it-unique-weekly-challenge-246.html diff --git a/challenge-246/dave-jacoby/perl/ch-1.pl b/challenge-246/dave-jacoby/perl/ch-1.pl index 6b58ba3912..6b670775a8 100644 --- a/challenge-246/dave-jacoby/perl/ch-1.pl +++ b/challenge-246/dave-jacoby/perl/ch-1.pl @@ -4,11 +4,31 @@ use strict; use warnings; use experimental qw{ say postderef signatures state }; -say join "\n", - sort { $a <=> $b } # and the example is sorted numerically, so we will - map { 1 + int rand 49 } # which are random and between 1 and 49 - # but int rand ( n ) will give a number between 0 and n-1 - # so adding 1 will put it at the right range - 1 .. 6; # we want six numbers +my %hash; +# Write a script that outputs six unique random integers +# from the range 1 to 49. + +# I had missed 'unique', which means we have to be sure we +# deal with duplicates. Use the random number as keys to a hash +# and you won't get duplicates. + +# Adding the numeric sort just makes it pretty. + +while ( scalar keys %hash < 6 ) { + my $n = 1 + int rand 49; + $hash{$n} = 1; +} + +say join "\n", sort { $a <=> $b } keys %hash; + +# And here is my first pass, which ignored "unique". +# Because of that, it was very simple. + +# say join "\n", +# sort { $a <=> $b } # and the example is sorted numerically, so we will +# map { 1 + int rand 49 } # which are random and between 1 and 49 +# # but int rand ( n ) will give a number between 0 and n-1 +# # so adding 1 will put it at the right range +# 1 .. 6; # we want six numbers diff --git a/challenge-246/dave-jacoby/perl/ch-2.pl b/challenge-246/dave-jacoby/perl/ch-2.pl index 2cf6806510..9ff50ee947 100644 --- a/challenge-246/dave-jacoby/perl/ch-2.pl +++ b/challenge-246/dave-jacoby/perl/ch-2.pl @@ -4,8 +4,6 @@ use strict; use warnings; use experimental qw{ say postderef signatures state }; -use Algorithm::Combinatorics qw{ variations }; - my @examples = ( [ 1, 1, 2, 3, 5 ], @@ -25,16 +23,12 @@ for my $e (@examples) { sub lrso (@input) { OUTER: for my $n ( 2 .. -1 + scalar @input ) { - for my $p ( 1 .. 100 ) { - for my $pp ( 1, -1 ) { - my $ppp = ( $p * $pp ) * $input[ $n - 2 ]; - for my $q ( 1 .. 100 ) { - for my $qq ( 1, -1 ) { - my $qqq = ( $q * $qq ) * $input[ $n - 1 ]; - my $rrr = $ppp + $qqq; - next OUTER if $rrr == $input[$n]; - } - } + for my $p ( -100 .. 100 ) { + my $pp = $p * $input[ $n - 2 ]; + for my $q ( -100 .. 100 ) { + my $qq = $q * $input[ $n - 1 ]; + my $rr = $pp + $qq; + next OUTER if $rr == $input[$n]; } } return 'false'; diff --git a/challenge-246/jeanluc2020/blog-1.txt b/challenge-246/jeanluc2020/blog-1.txt new file mode 100644 index 0000000000..861845124f --- /dev/null +++ b/challenge-246/jeanluc2020/blog-1.txt @@ -0,0 +1 @@ +http://gott-gehabt.de/800_wer_wir_sind/thomas/Homepage/Computer/perl/theweeklychallenge-246-1.html diff --git a/challenge-246/jeanluc2020/blog-2.txt b/challenge-246/jeanluc2020/blog-2.txt new file mode 100644 index 0000000000..84aa5fe2ec --- /dev/null +++ b/challenge-246/jeanluc2020/blog-2.txt @@ -0,0 +1 @@ +http://gott-gehabt.de/800_wer_wir_sind/thomas/Homepage/Computer/perl/theweeklychallenge-246-2.html diff --git a/challenge-246/jeanluc2020/perl/ch-1.pl b/challenge-246/jeanluc2020/perl/ch-1.pl new file mode 100755 index 0000000000..224607b208 --- /dev/null +++ b/challenge-246/jeanluc2020/perl/ch-1.pl @@ -0,0 +1,49 @@ +#!/usr/bin/perl +# https://theweeklychallenge.org/blog/perl-weekly-challenge-246/#TASK1 +# +# 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 +# +############################################################ +## +## discussion +## +############################################################ +# +# Collect random numbers until we have 6 of them. In case we randomly select a +# number that we saw already, discard the number and select another random +# number instead. +# +use strict; +use warnings; + +my $result = {}; + +sub next_rand { + my $n = int(rand(49)) + 1; + return $n unless $result->{$n}; + # print "Collision, need another random number!\n"; + return next_rand(); +} + +foreach(1..6) { + my $n = next_rand(); + $result->{$n} = 1; +} + +print join("\n", sort {$a<=>$b} keys %$result), "\n"; + diff --git a/challenge-246/jeanluc2020/perl/ch-2.pl b/challenge-246/jeanluc2020/perl/ch-2.pl new file mode 100755 index 0000000000..1522081a63 --- /dev/null +++ b/challenge-246/jeanluc2020/perl/ch-2.pl @@ -0,0 +1,147 @@ +#!/usr/bin/perl +# https://theweeklychallenge.org/blog/perl-weekly-challenge-246/#TASK2 +# +# 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] +# +############################################################ +## +## discussion +## +############################################################ +# +# We need a solution that allows for +# p * a[0] + q * a[1] = a[2] +# p * a[1] + q * a[2] = a[3] +# p * a[2] + q * a[3] = a[4] +# +# A linear combination of a number a in term of two other numbers b and c +# is possible if gcd(b,c) divides a; however there might be multiple +# such combinations possible so it is not possible from one triplet of +# numbers to determine which (if any) linear recurrence works for all +# 5 numbers. For example (4,2,4): 1*4+0*2=4, 0*4+2*2=4, 2*4-2*2=4, +# 3*4-4*2=4, -1*4+8*2=4, ... +# The gcd method however allows to check whether there is any potential +# solution at all, so let's start with that. Since the gcd of two numbers +# can slso be combined linearly out of the two numbers I can only assume +# the task was meant to use that, however in the general case we might have +# to check any of the (potentially infinitely many) linear combinations for +# whether or not their factors are suitable for the whole chain of numbers, +# and it doesn't even hold true for the first example. +# So we can try to find a few linear combinations from the first triplet, +# and if any of those works for all numbers we're good. +# As a heuristic for the range of p and q we use +/- |a|+|b| and try more or +# less all combinations of these; since we have multiple numbers we just +# take the maximum of those numbers * 2 instead. +# +use strict; +use warnings; + +linear_recurrence_of_second_order(1, 1, 2, 3, 5); +linear_recurrence_of_second_order(4, 2, 4, 5, 7); +linear_recurrence_of_second_order(4, 1, 2, -3, 8); + +sub linear_recurrence_of_second_order { + my @a = @_; + my ($i, $j, $k,$l, $m) = @a; + + if($k % gcd($i, $j)) { + return false(); + } + if($l % gcd($j, $k)) { + return false(); + } + if($m % gcd($k, $l)) { + return false(); + } + + my $limit = 2 * absmax(@a); + foreach my $p ( -$limit..$limit ) { + foreach my $q ( -$limit..$limit ) { + if($p * $i + $q * $j == $k) { + if($p * $j + $q * $k == $l) { + if($p * $k + $q * $l == $m) { + return true(); + } + } + } + } + } + return false(); + +} + +sub absmax { + my @list = @_; + my $max = abs($list[0]); + foreach my $elem (@list) { + $max = abs($elem) if abs($elem) > $max; + } + return $max; +} + +sub true { + print "Output: true\n"; + return 1; +} + +sub false { + print "Output: false\n"; + return 0; +} + +sub gcd { + my ($x, $y) = @_; + if($x < 0) { + return gcd(-$x, $y); + } + if($y < 0) { + return gcd($x, -$y); + } + if($x < $y) { + return gcd($y, $x); + } + my $z = $x % $y; + if($z) { + return gcd($y, $z); + } else { + return $y; + } +} diff --git a/challenge-246/jeanluc2020/python/ch-1.py b/challenge-246/jeanluc2020/python/ch-1.py new file mode 100755 index 0000000000..7a96c4e070 --- /dev/null +++ b/challenge-246/jeanluc2020/python/ch-1.py @@ -0,0 +1,47 @@ +#!/usr/bin/python3 +# https://theweeklychallenge.org/blog/perl-weekly-challenge-246/#TASK1 +# +# 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 +# +############################################################ +## +## discussion +## +############################################################ +# +# Collect random numbers until we have 6 of them. In case we randomly select a +# number that we saw already, discard the number and select another random +# number instead. +# +import random + +result = {} + +def next_rand() -> int: + res = random.randint(1,49) + if res in result: + # collision, calculate a new random number + return next_rand() + return res + +for i in range(6): + num = next_rand() + result[num] = 1 + +print("\n".join(str(x) for x in sorted(result.keys()))) + diff --git a/challenge-246/jeanluc2020/python/ch-2.py b/challenge-246/jeanluc2020/python/ch-2.py new file mode 100755 index 0000000000..d17d941039 --- /dev/null +++ b/challenge-246/jeanluc2020/python/ch-2.py @@ -0,0 +1,125 @@ +#!/usr/bin/python3 +# https://theweeklychallenge.org/blog/perl-weekly-challenge-246/#TASK2 +# +# 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] +# +############################################################ +## +## discussion +## +############################################################ +# +# We need a solution that allows for +# p * a[0] + q * a[1] = a[2] +# p * a[1] + q * a[2] = a[3] +# p * a[2] + q * a[3] = a[4] +# +# A linear combination of a number a in term of two other numbers b and c +# is possible if gcd(b,c) divides a; however there might be multiple +# such combinations possible so it is not possible from one triplet of +# numbers to determine which (if any) linear recurrence works for all +# 5 numbers. For example (4,2,4): 1*4+0*2=4, 0*4+2*2=4, 2*4-2*2=4, +# 3*4-4*2=4, -1*4+8*2=4, ... +# The gcd method however allows to check whether there is any potential +# solution at all, so let's start with that. Since the gcd of two numbers +# can slso be combined linearly out of the two numbers I can only assume +# the task was meant to use that, however in the general case we might have +# to check any of the (potentially infinitely many) linear combinations for +# whether or not their factors are suitable for the whole chain of numbers, +# and it doesn't even hold true for the first example. +# So we can try to find a few linear combinations from the first triplet, +# and if any of those works for all numbers we're good. +# As a heuristic for the range of p and q we use +/- |a|+|b| and try more or +# less all combinations of these; since we have multiple numbers we just +# take the maximum of those numbers * 2 instead. +# + +def true(): + print("Output: true") + return True + +def false(): + print("Output: false") + return False + +def absmax(elems: list): + max = abs(elems[0]) + for elem in elems: + if abs(elem) > max: + max = abs(elem) + return max + +def gcd(x: int, y: int) -> int: + if x < 0: + return gcd(-x, y) + if y < 0: + return gcd(x, -y) + if x < y: + return gcd(y, x) + z = x % y + if z > 0: + return gcd(y, z) + return y + +def linear_recurrence_of_second_order(a: list) -> bool: + (i, j, k, l, m) = a + + if k % gcd(i, j) > 0: + return false() + if l % gcd(j, k) > 0: + return false() + if m % gcd(k, l) > 0: + return false() + + limit = 2 * absmax(a) + + for p in range(-limit, 2*limit): + for q in range(-limit, 2*limit): + if p*i + q*j == k: + if p*j + q*k == l: + if p*k + q*l == m: + return true() + return false() + + +linear_recurrence_of_second_order([1, 1, 2, 3, 5]) +linear_recurrence_of_second_order([4, 2, 4, 5, 7]) +linear_recurrence_of_second_order([4, 1, 2, -3, 8]) diff --git a/challenge-246/laurent-rosenfeld/blog1.txt b/challenge-246/laurent-rosenfeld/blog1.txt new file mode 100644 index 0000000000..0e28fd88c0 --- /dev/null +++ b/challenge-246/laurent-rosenfeld/blog1.txt @@ -0,0 +1 @@ +https://blogs.perl.org/users/laurent_r/2023/12/perl-weekly-challenge-246-linear-recurrence-of-second-order.html diff --git a/challenge-246/laurent-rosenfeld/perl/ch-2.pl b/challenge-246/laurent-rosenfeld/perl/ch-2.pl new file mode 100644 index 0000000000..fa464dfdcf --- /dev/null +++ b/challenge-246/laurent-rosenfeld/perl/ch-2.pl @@ -0,0 +1,26 @@ +use strict; +use warnings; +use feature 'say'; + +sub linear_rec { + my @in = @_; + my ($min, $max) = (sort {$a <=> $b} @in)[0, -1]; + for my $p ($min .. $max) { + for my $q ($min .. $max) { + for my $i (2..$#in) { + last if $in[$i] !=< |