diff options
Diffstat (limited to 'challenge-077')
37 files changed, 1310 insertions, 72 deletions
diff --git a/challenge-077/andinus/README b/challenge-077/andinus/README index 1653e8e915..9437e98f28 100644 --- a/challenge-077/andinus/README +++ b/challenge-077/andinus/README @@ -1,102 +1,52 @@ ━━━━━━━━━━━━━━━ - CHALLENGE 076 + CHALLENGE 077 ━━━━━━━━━━━━━━━ Table of Contents ───────────────── -1 Task 1 - Prime Sum +1 Task 1 - Fibonacci Sum .. 1.1 Perl -1 Task 1 - Prime Sum -════════════════════ +1 Task 1 - Fibonacci Sum +════════════════════════ - You are given a number `$N'. Write a script to find the minimum number - of prime numbers required, whose summation gives you `$N'. + You are given a positive integer `$N'. - • For the sake of this task, please assume 1 is not a prime number. + Write a script to find the total number of Fibonacci Numbers required + to get `$N' on addition. You are NOT allowed to repeat a number. Print + 0 if none found. + + *Note*: This solution is incomplete. Others have pushed complete + solutions, look at those. 1.1 Perl ──────── • Program: [file:perl/ch-1.pl] - • Help taken from: [https://stackoverflow.com/a/35756072]. - - User input is stored in `$input'. - ┌──── - │ my $input = shift @ARGV; - │ chomp $input; - └──── - - 1 is assumed not to be a prime number so we reject numbers less than - or equal to 1. - ┌──── - │ die "Invalid input, enter numbers greater than 1.\n" if $input <= 1; - └──── - - If it's a prime number then the minimum sum is the number itself so we - just return it & exit. - ┌──── - │ say $input and exit 0 if is_prime($input) == 1; - └──── - - If `$input' is even then we loop from 2 to `$input / 2' & check if - both `$i' & `$diff' are primes. If both are primes then we have our - numbers. - Eventually we'll find 2 primes to be a sum of even numbers. From - WikiPedia, [Goldbach's conjecture] has been shown to hold for all - integers less than `4 × 10^18'. + Make a list of all possible sums of `$input'. ┌──── - │ if ($input % 2 == 0) { - │ foreach my $i (2 ... $input / 2) { - │ my $diff = $input - $i; - │ say "$i + $diff" - │ if is_prime($i) and is_prime($diff); - │ } + │ my @sums; + │ foreach my $num (0 ... $input / 2) { + │ my $diff = $input - $num; + │ push @sums, [$diff, $num]; │ } └──── - If the input is odd then we first check if `$input - 2' is a prime, if - it is then input is the sum of two primes, 2 & `$input - 2'. + Loop over `@sums' & then print those sets which have both `$sums->[0]' + & `$sums->[1]' in fibonacci series. ┌──── - │ elsif (is_prime($input - 2)) { - │ say "2 + $input"; - │ } - └──── - - If even that doesn't match then the minimum sum will have three - numbers. 3 & then we use the same function as for even numbers to find - the other two primes. - ┌──── - │ else { - │ foreach my $i (2 ... ($input - 3) / 2) { - │ my $diff = $input - 3 - $i; - │ say "3 + $i + $diff" - │ if is_prime($i) and is_prime($diff); - │ } - │ } - └──── - - If $num is divisible by any number between 2 & `sqrt($num)' then it's - not prime. - ┌──── - │ sub is_prime { - │ my $num = shift @_; + │ sub is_fib { return Math::Fibonacci::isfibonacci(@_) } │ - │ foreach my $i (2 ... sqrt($num)) { - │ return 0 if $num % $i == 0; - │ } - │ return 1; + │ foreach (@sums) { + │ next unless is_fib($_->[0]) and is_fib($_->[1]); + │ say "$_->[0] + $_->[1]"; │ } └──── - - -[Goldbach's conjecture] -https://en.wikipedia.org/wiki/Goldbach%2527s_conjecture diff --git a/challenge-077/andinus/blog-1.txt b/challenge-077/andinus/blog-1.txt new file mode 100644 index 0000000000..3758cbc1da --- /dev/null +++ b/challenge-077/andinus/blog-1.txt @@ -0,0 +1 @@ +https://andinus.tilde.institute/pwc/challenge-077/ diff --git a/challenge-077/andinus/perl/ch-1.pl b/challenge-077/andinus/perl/ch-1.pl new file mode 100755 index 0000000000..83a03c6069 --- /dev/null +++ b/challenge-077/andinus/perl/ch-1.pl @@ -0,0 +1,25 @@ +#!/usr/bin/perl + +use strict; +use warnings; +use feature 'say'; + +use Math::Fibonacci; + +my $input = shift @ARGV; +chomp $input; + +die "Invalid input, enter numbers greater than 0.\n" if $input < 0; + +my @sums; +foreach my $num (0 ... $input / 2) { + my $diff = $input - $num; + push @sums, [$diff, $num]; +} + +sub is_fib { return Math::Fibonacci::isfibonacci(@_) } + +foreach (@sums) { + next unless is_fib($_->[0]) and is_fib($_->[1]); + say "$_->[0] + $_->[1]"; +} diff --git a/challenge-077/arne-sommer/blog.txt b/challenge-077/arne-sommer/blog.txt new file mode 100644 index 0000000000..80ea989b42 --- /dev/null +++ b/challenge-077/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/lonely-sum.html diff --git a/challenge-077/arne-sommer/raku/ch-1.p6 b/challenge-077/arne-sommer/raku/ch-1.p6 new file mode 100755 index 0000000000..719e169ecf --- /dev/null +++ b/challenge-077/arne-sommer/raku/ch-1.p6 @@ -0,0 +1,60 @@ +#! /usr/bin/env raku + +subset PositiveInt of Int where * >= 1; + +unit sub MAIN (PositiveInt $N, :v(:$verbose), :u(:$upto)); + +my $label; +my $found; + + +$upto + ?? (1..$N).map({ fibonal-decomposition($_) }) + !! fibonal-decomposition($N); + +sub fibonal-decomposition($target) +{ + $found = False; + $label = 'a'; + + my @fibs; + my $fibonacci := (1, 1, * + * ... Inf); + + for $fibonacci -> $fib { last if $fib > $target; @fibs.unshift: $fib; } + @fibs.pop; + + if $verbose + { + say ": Target: $target" if $upto; + say ": Fibonacci (reverse): { @fibs.join(", ") }"; + } + + recurse(0, (), @fibs, $target); + + say "0" unless $found; + say "" if $upto; +} + +sub recurse ($value is copy, @values is copy, @fibonacci is copy, $input) +{ + if $value < $input + { + while @fibonacci + { + my $add = @fibonacci.shift; + + if $value + $add <= $input + { + my $value2 = $value + $add; + my @values2 = @values.clone.push: $add; + recurse($value2, @values2, @fibonacci, $input); + } + } + } + + elsif $value == $input + { + say "{ $label++ }) { @values.join(' + ') } = $input"; + $found = True; + } +} diff --git a/challenge-077/arne-sommer/raku/ch-2.p6 b/challenge-077/arne-sommer/raku/ch-2.p6 new file mode 100755 index 0000000000..035cf2d973 --- /dev/null +++ b/challenge-077/arne-sommer/raku/ch-2.p6 @@ -0,0 +1,43 @@ +#! /usr/bin/env raku + +unit sub MAIN ($matrix where $matrix.IO.f && $matrix.IO.r = 'matrix1.txt', + :v(:$verbose)); + +my @matrix = $matrix.IO.lines.map( *.words.list ); + +die "Uneven grid row length" unless [==] @(@matrix)>>.elems; + +die "Single characters only in the grid" if @(@matrix)>>.chars>>.max.max > 1; + +my $rows = @matrix.elems; +my $cols = @matrix[0].elems; + +my $is_lonely = 0; + +for ^$rows -> $row +{ + for ^$cols -> $col + { + say ": [$row,$col] -> @matrix[$row][$col] { is_lonely(@matrix, $row, $col) ?? 'is lonely' !! '' }" if $verbose; + $is_lonely++ if is_lonely(@matrix, $row, $col); + } +} + +say $is_lonely; + +sub is_lonely (@matrix, $row, $col) +{ + return False if @matrix[$row][$col] eq 'O'; + + for (-1, 0, 1) -> $r + { + for (-1, 0, 1) -> $c + { + next if $r == $c == 0; + next unless @matrix[$row + $r][$col + $c].defined; + + return False if @matrix[$row + $r][$col + $c] eq 'X'; + } + } + return True; +} diff --git a/challenge-077/arne-sommer/raku/fibonacci-sum b/challenge-077/arne-sommer/raku/fibonacci-sum new file mode 100755 index 0000000000..719e169ecf --- /dev/null +++ b/challenge-077/arne-sommer/raku/fibonacci-sum @@ -0,0 +1,60 @@ +#! /usr/bin/env raku + +subset PositiveInt of Int where * >= 1; + +unit sub MAIN (PositiveInt $N, :v(:$verbose), :u(:$upto)); + +my $label; +my $found; + + +$upto + ?? (1..$N).map({ fibonal-decomposition($_) }) + !! fibonal-decomposition($N); + +sub fibonal-decomposition($target) +{ + $found = False; + $label = 'a'; + + my @fibs; + my $fibonacci := (1, 1, * + * ... Inf); + + for $fibonacci -> $fib { last if $fib > $target; @fibs.unshift: $fib; } + @fibs.pop; + + if $verbose + { + say ": Target: $target" if $upto; + say ": Fibonacci (reverse): { @fibs.join(", ") }"; + } + + recurse(0, (), @fibs, $target); + + say "0" unless $found; + say "" if $upto; +} + +sub recurse ($value is copy, @values is copy, @fibonacci is copy, $input) +{ + if $value < $input + { + while @fibonacci + { + my $add = @fibonacci.shift; + + if $value + $add <= $input + { + my $value2 = $value + $add; + my @values2 = @values.clone.push: $add; + recurse($value2, @values2, @fibonacci, $input); + } + } + } + + elsif $value == $input + { + say "{ $label++ }) { @values.join(' + ') } = $input"; + $found = True; + } +} diff --git a/challenge-077/arne-sommer/raku/fibonacci-sum-first b/challenge-077/arne-sommer/raku/fibonacci-sum-first new file mode 100755 index 0000000000..47bdb4503c --- /dev/null +++ b/challenge-077/arne-sommer/raku/fibonacci-sum-first @@ -0,0 +1,82 @@ +#! /usr/bin/env raku + +subset PositiveInt of Int where * >= 1; + +unit sub MAIN (PositiveInt $N, :v(:$verbose), :u(:$upto), :f(:$first)); + +my $label; +my $found; +my $found2 = True; + +if $first +{ + my $current = 1; + + while ( $found2 ) + { + fibonal-decomposition($current); + say ": Checking $current" if $verbose; + $current++; + } +} +else +{ + $upto + ?? (1..$N).map({ fibonal-decomposition($_) }) + !! fibonal-decomposition($N); +} + +sub fibonal-decomposition($target) +{ + $found = False; + $label = 'a'; + + my @fibs; + my $fibonacci := (1, 1, * + * ... Inf); + + for $fibonacci -> $fib { last if $fib > $target; @fibs.unshift: $fib; } + @fibs.pop; + + if $verbose && ! $first + { + say ": Target: $target" if $upto; + say ": Fibonacci (reverse): { @fibs.join(", ") }"; + } + + recurse(0, (), @fibs, $target); + + unless $first + { + say "0" unless $found; + say "" if $upto; + } +} + + +sub recurse ($value is copy, @values is copy, @fibonacci is copy, $input) +{ + if $value < $input + { + while @fibonacci + { + my $add = @fibonacci.shift; + + if $value + $add <= $input + { + my $value2 = $value + $add; + my @values2 = @values.clone.push: $add; + recurse($value2, @values2, @fibonacci, $input); + } + } + } + + elsif $value == $input + { + say "{ $label++ }) { @values.join(' + ') } = $input" unless $first; + $found = True; + } + elsif $first + { + $found2 = False; + } +} diff --git a/challenge-077/arne-sommer/raku/fibonacci-sum-first-verbose b/challenge-077/arne-sommer/raku/fibonacci-sum-first-verbose new file mode 100755 index 0000000000..33e8296265 --- /dev/null +++ b/challenge-077/arne-sommer/raku/fibonacci-sum-first-verbose @@ -0,0 +1,84 @@ +#! /usr/bin/env raku + +subset PositiveInt of Int where * >= 1; + +unit sub MAIN (PositiveInt $N, :v(:$verbose), :u(:$upto), :f(:$first)); + +my $label; +my $found; +my $found2 = True; +my $recursion; + +if $first +{ + my $current = 1; + + while ( $found2 ) + { + $recursion = 0; + fibonal-decomposition($current); + say ": Checking $current [Recursive calls: $recursion]" if $verbose; + $current++; + } +} +else +{ + $upto + ?? (1..$N).map({ fibonal-decomposition($_) }) + !! fibonal-decomposition($N); +} + +sub fibonal-decomposition($target) +{ + $found = False; + $label = 'a'; + + my @fibs; + my $fibonacci := (1, 1, * + * ... Inf); + + for $fibonacci -> $fib { last if $fib > $target; @fibs.unshift: $fib; } + @fibs.pop; + + if $verbose && ! $first + { + say ": Target: $target" if $upto; + say ": Fibonacci (reverse): { @fibs.join(", ") }"; + } + + recurse(0, (), @fibs, $target); + + unless $first + { + say "0" unless $found; + say "" if $upto; + } +} + +sub recurse ($value is copy, @values is copy, @fibonacci is copy, $input) +{ + $recursion++; + if $value < $input + { + while @fibonacci + { + my $add = @fibonacci.shift; + + if $value + $add <= $input + { + my $value2 = $value + $add; + my @values2 = @values.clone.push: $add; + recurse($value2, @values2, @fibonacci, $input); + } + } + } + + elsif $value == $input + { + say "{ $label++ }) { @values.join(' + ') } = $input" unless $first; + $found = True; + } + elsif $first + { + $found2 = False; + } +} diff --git a/challenge-077/arne-sommer/raku/lonely-x b/challenge-077/arne-sommer/raku/lonely-x new file mode 100755 index 0000000000..035cf2d973 --- /dev/null +++ b/challenge-077/arne-sommer/raku/lonely-x @@ -0,0 +1,43 @@ +#! /usr/bin/env raku + +unit sub MAIN ($matrix where $matrix.IO.f && $matrix.IO.r = 'matrix1.txt', + :v(:$verbose)); + +my @matrix = $matrix.IO.lines.map( *.words.list ); + +die "Uneven grid row length" unless [==] @(@matrix)>>.elems; + +die "Single characters only in the grid" if @(@matrix)>>.chars>>.max.max > 1; + +my $rows = @matrix.elems; +my $cols = @matrix[0].elems; + +my $is_lonely = 0; + +for ^$rows -> $row +{ + for ^$cols -> $col + { + say ": [$row,$col] -> @matrix[$row][$col] { is_lonely(@matrix, $row, $col) ?? 'is lonely' !! '' }" if $verbose; + $is_lonely++ if is_lonely(@matrix, $row, $col); + } +} + +say $is_lonely; + +sub is_lonely (@matrix, $row, $col) +{ + return False if @matrix[$row][$col] eq 'O'; + + for (-1, 0, 1) -> $r + { + for (-1, 0, 1) -> $c + { + next if $r == $c == 0; + next unless @matrix[$row + $r][$col + $c].defined; + + return False if @matrix[$row + $r][$col + $c] eq 'X'; + } + } + return True; +} diff --git a/challenge-077/arne-sommer/raku/matrix1.txt b/challenge-077/arne-sommer/raku/matrix1.txt new file mode 100644 index 0000000000..f8beeb613f --- /dev/null +++ b/challenge-077/arne-sommer/raku/matrix1.txt @@ -0,0 +1,3 @@ +O O X +X O O +X O O diff --git a/challenge-077/arne-sommer/raku/matrix2.txt b/challenge-077/arne-sommer/raku/matrix2.txt new file mode 100644 index 0000000000..d81104f1b2 --- /dev/null +++ b/challenge-077/arne-sommer/raku/matrix2.txt @@ -0,0 +1,4 @@ +O O X O +X O O O +X O O X +O X O O diff --git a/challenge-077/ash/cpp/ch-2a.cpp b/challenge-077/ash/cpp/ch-2a.cpp new file mode 100644 index 0000000000..b0c250a7f6 --- /dev/null +++ b/challenge-077/ash/cpp/ch-2a.cpp @@ -0,0 +1,65 @@ +/* + Task 2 from + https://perlweeklychallenge.org/blog/perl-weekly-challenge-077/ + + Comments: https://andrewshitov.com/2020/09/08/lonely-x-the-weekly-challenge-77-task-2/ + + Compile as: + $ g++ -std=c++17 ch-2.cpp + + Output for the given example of matrix: + $ ./a.out + 0, 3 + 1, 1 + 2, 3 +*/ + +#include <iostream> +#include <vector> + +using namespace std; + +int test_move_calls = 0; +vector<int> test_move(vector<vector<char>> matrix, vector<int> current, vector<int> shift) { + test_move_calls++; + + current[0] += shift[0]; + current[1] += shift[1]; + + if (current[0] < 0 || current[0] >= matrix.size() || + current[1] < 0 || current[1] >= matrix[0].size()) { + return vector<int>(); + } + else { + return current; + } +} + +int main() { + vector<vector<char>> matrix = { + {'X', 'O', 'O', 'X'}, + {'O', 'O', 'X', 'O'}, + {'X', 'O', 'O', 'X'} + }; + + vector<vector<int>> neighbours = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; + + for (auto row = 0; row != matrix.size(); row++) { + for (auto col = 0; col != matrix[0].size(); col++) { + if (matrix[row][col] == 'O') continue; + + bool ok = true; + for (auto neighbour : neighbours) { + auto move = test_move(matrix, vector<int>{row, col}, neighbour); + if (move.empty()) continue; + if (matrix[move[0]][move[1]] == 'X') { + ok = false; + break; + } + } + if (ok) cout << row << ", " << col << endl; + } + } + + cout << test_move_calls << " checks made" << endl; +} diff --git a/challenge-077/ash/cpp/ch-2b.cpp b/challenge-077/ash/cpp/ch-2b.cpp new file mode 100644 index 0000000000..85e142c642 --- /dev/null +++ b/challenge-077/ash/cpp/ch-2b.cpp @@ -0,0 +1,82 @@ +/* + Task 2 from + https://perlweeklychallenge.org/blog/perl-weekly-challenge-077/ + + Comments: https://andrewshitov.com/2020/09/08/lonely-x-the-weekly-challenge-77-task-2/ + + Compile as: + $ g++ -std=c++17 ch-2.cpp + + Output for the given example of matrix: + $ ./a.out + 0, 3 + 1, 1 + 2, 3 + + + If there Xs that have other Xs as their neighbours, then + this program makes less cell checks than ch-2.cpp: + + $ g++ -std=c++17 ch-2.cpp + bash-3.2$ ./a.out + 0, 0 + 2, 0 + 35 checks made + + $ g++ -std=c++17 ch-2a.cpp + $ ./a.out + 0, 0 + 2, 0 + 30 checks made +*/ + +#include <iostream> +#include <vector> + +using namespace std; + +int test_move_calls = 0; +vector<int> test_move(vector<vector<char>> matrix, vector<int> current, vector<int> shift) { + test_move_calls++; + + current[0] += shift[0]; + current[1] += shift[1]; + + if (current[0] < 0 || current[0] >= matrix.size() || + current[1] < 0 || current[1] >= matrix[0].size()) { + return vector<int>(); + } + else { + return current; + } +} + +int main() { + vector<vector<char>> matrix = { + {'X', 'O', 'O', 'X'}, + {'O', 'O', 'X', 'O'}, + {'X', 'O', 'O', 'X'} + }; + + vector<vector<int>> neighbours = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; + + for (auto row = 0; row != matrix.size(); row++) { + for (auto col = 0; col != matrix[0].size(); col++) { + if (matrix[row][col] != 'X') continue; + + bool ok = true; + for (auto neighbour : neighbours) { + auto move = test_move(matrix, vector<int>{row, col}, neighbour); + if (move.empty()) continue; + if (matrix[move[0]][move[1]] != 'O') { + matrix[move[0]][move[1]] = 'Y'; + ok = false; + break; + } + } + if (ok) cout << row << ", " << col << endl; + } + } + + cout << test_move_calls << " checks made" << endl; +} diff --git a/challenge-077/ash/html/ch-2.html b/challenge-077/ash/html/ch-2.html new file mode 100644 index 0000000000..3b1cd76bb6 --- /dev/null +++ b/challenge-077/ash/html/ch-2.html @@ -0,0 +1,106 @@ +<html> + +<!-- + Task 2 from + https://perlweeklychallenge.org/blog/perl-weekly-challenge-077/ + + Comments: https://andrewshitov.com/2020/09/08/lonely-x-the-weekly-challenge-77-task-2/ +--> + +<head> + <meta charset="UTF-8"/> + <title>Lonely X</title> + <style> + * { + text-align: center; + font-family: Arial, sans-serif; + } + #Shape table { + margin: auto; + /* border-collapse: collapse; */ + } + /* #Shape table tr td input { + width: 50px; + height: 50px; + } */ + #Shape table tr td { + border: 5px solid white; + } + #Shape table tr td.lonely { + border: 5px solid green; + } + </style> +</head> +<body> + <p> + <input type="text" name="width" id="MatrixWidth" size="3" value="3" /> + × + <input type="text" name="height" id="MatrixHeight" size="3" value="3" /> + + <input type="submit" value="Set the shape" onclick="set_shape()" /> + </p> + + <div id="Shape"></div> + + <p>Note: Lonely X is marked green.</p> + + <script> + let w = 0; + let h = 0; + + function set_shape() { + w = parseInt(document.getElementById('MatrixWidth').value); + h = parseInt(document.getElementById('MatrixHeight').value); + + let table = '<table>'; + for (let y = 0; y != h; y++) { + table += '<tr>'; + for (let x = 0; x != w; x++) { + table += '<td><input type="checkbox" data-x="' + x + '" data-y="' + y + '" onclick="update_lonely()" /></td>'; + } + table += '</tr>'; + } + table += '</table>'; + document.getElementById('Shape').innerHTML = table; + } + + function update_lonely() { + let cells = document.getElementById('Shape').getElementsByTagName('input'); + + let neigbours = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]]; + + for (let i = 0; i != cells.length; i++) { + cells[i].parentNode.className = ''; + + if (!cells[i].checked) continue; + let x = parseInt(cells[i].getAttribute('data-x')); + let y = parseInt(cells[i].getAttribute('data-y')); + + let is_ok = true; + for (let c = 0; c != neigbours.length; c++) { + if (!test_cell(x + neigbours[c][0], y + neigbours[c][1])) { + is_ok = false; + break; + } + } + + if (is_ok) { + cells[i].parentNode.className = 'lonely'; + } + } + } + + function test_cell(x, y) { + if (x < 0 || y < 0 || x >= w || y >= h) { + return true; + } + else { + let cell = document.querySelector('#Shape tr td input[data-x="'+ x + '"][data-y="' + y + '"]'); + return !cell.checked; + } + } + + set_shape(); + </script> +</body> |