Merge remote-tracking branch 'upstream/master' into ch-077

52 files changed, 1992 insertions, 16 deletions

diff --git a/challenge-077/ash/blog.txt b/challenge-077/ash/blog.txt
new file mode 100644
index 0000000000..f95ba9e75f
--- /dev/null
+++ b/challenge-077/ash/blog.txt
@@ -0,0 +1 @@
+https://andrewshitov.com/2020/09/07/add-up-fibonacci-numbers-the-weekly-challenge-77-task-1/
diff --git a/challenge-077/ash/blog1.txt b/challenge-077/ash/blog1.txt
new file mode 100644
index 0000000000..a81f60f4d3
--- /dev/null
+++ b/challenge-077/ash/blog1.txt
@@ -0,0 +1 @@
+https://andrewshitov.com/2020/09/08/lonely-x-the-weekly-challenge-77-task-2/
diff --git a/challenge-077/ash/cpp/ch-2.cpp b/challenge-077/ash/cpp/ch-2.cpp
new file mode 100644
index 0000000000..2c7aa19721
--- /dev/null
+++ b/challenge-077/ash/cpp/ch-2.cpp
@@ -0,0 +1,60 @@
+/*
+    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;
+
+vector<int> test_move(vector<vector<char>> matrix, vector<int> current, vector<int> shift) {
+    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 = {
+        {'O', 'O', 'O', 'X'},
+        {'O', 'X', 'O', 'O'},
+        {'O', '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;
+        }
+    }
+}
diff --git a/challenge-077/ash/raku/ch-1.raku b/challenge-077/ash/raku/ch-1.raku
new file mode 100644
index 0000000000..cdab8466cc
--- /dev/null
+++ b/challenge-077/ash/raku/ch-1.raku
@@ -0,0 +1,11 @@
+#!/usr/bin/env raku
+
+# Task 1 from
+# https://perlweeklychallenge.org/blog/perl-weekly-challenge-077/
+
+# Comments: https://andrewshitov.com/2020/09/07/add-up-fibonacci-numbers-the-weekly-challenge-77-task-1/
+
+my $n = @*ARGS[0] // 42;
+my @fib = 1, 2, * + * ...^ * > $n;
+
+"$_.join(' + ') = $n".put for @fib.combinations.grep(*.sum == $n);
diff --git a/challenge-077/ash/raku/ch-2.raku b/challenge-077/ash/raku/ch-2.raku
new file mode 100644
index 0000000000..47d8524eaa
--- /dev/null
+++ b/challenge-077/ash/raku/ch-2.raku
@@ -0,0 +1,36 @@
+#!/usr/bin/env raku
+
+# 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/
+
+my @matrix =
+    < O O X >,
+    < X O O >,
+    < X O O >; # square matrix
+
+# my @matrix =
+#     < O O X O >,
+#     < X O O O >,
+#     < X O O X >,
+#     < O X O O >;
+
+my @neighbours = ([X] (-1, 0, 1) xx 2).grep(*.all != 0);
+
+for ^@matrix X ^@matrix -> @coord {
+    next if @matrix[@coord[0]][@coord[1]] eq 'O';
+
+    @coord.put if all((@neighbours.map(* <<+>> @coord)).grep(0 <= *.all <= @matrix.end).map({        
+        @matrix[$_[0]][$_[1]] eq 'O';
+    }));
+}
+
+# Output:
+# $ raku ch-2.raku 
+# 0 2
+
+# Or:
+# $ raku ch-2.raku 
+# 0 2
+# 2 3
diff --git a/challenge-077/ash/xslt/ch-2.xml b/challenge-077/ash/xslt/ch-2.xml
new file mode 100644
index 0000000000..ce27ac5cdb
--- /dev/null
+++ b/challenge-077/ash/xslt/ch-2.xml
@@ -0,0 +1,25 @@
+<?xml version="1.0"?>
+
+<!--
+    Task 2 from
+    https://perlweeklychallenge.org/blog/perl-weekly-challenge-077/
+
+    To get a solution, run:
+    $ xsltproc ch-2.xslt ch-2.xml 
+
+    For the given example matrix, you get the following output (items count from 1):
+    1, 2
+    3, 1
+-->
+
+<matrix>
+    <row>
+        <item>O</item> <item>X</item> <item>O</item>
+    </row>
+    <row>
+        <item>O</item> <item>O</item> <item>O</item>
+    </row>
+    <row>
+        <item>X</item> <item>O</item> <item>O</item>
+    </row>
+</matrix>
diff --git a/challenge-077/ash/xslt/ch-2.xslt b/challenge-077/ash/xslt/ch-2.xslt
new file mode 100644
index 0000000000..3a1fb688da
--- /dev/null
+++ b/challenge-077/ash/xslt/ch-2.xslt
@@ -0,0 +1,41 @@
+<?xml version="1.0"?>
+
+<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
+
+<xsl:output omit-xml-declaration="yes"/>
+
+<xsl:template match="/matrix">
+    <xsl:apply-templates select="row"/>
+</xsl:template>
+
+<xsl:template match="row">
+    <xsl:apply-templates select="item"/>
+</xsl:template>
+
+<!-- catch 'O's -->
+<xsl:template match="item"/>
+
+<xsl:template match="item[text() = 'X']">
+    <xsl:variable name="row" select="count(../preceding-sibling::*) + 1"/> <!-- position of parent -->
+    <xsl:variable name="col" select="position()"/>
+
+    <xsl:variable name="lonely" select="
+        (not(/matrix/row[$row    ]/item[$col - 1]) or /matrix/row[$row    ]/item[$col - 1] = 'O') and
+        (not(/matrix/row[$row    ]/item[$col + 1]) or /matrix/row[$row    ]/item[$col + 1] = 'O') and
+        (not(/matrix/row[$row + 1]/item[$col    ]) or /matrix/row[$row + 1]/item[$col    ] = 'O') and
+        (not(/matrix/row[$row - 1]/item[$col    ]) or /matrix/row[$row - 1]/item[$col    ] = 'O') and
+        (not(/matrix/row[$row + 1]/item[$col + 1]) or /matrix/row[$row + 1]/item[$col + 1] = 'O') and
+        (not(/matrix/row[$row - 1]/item[$col - 1]) or /matrix/row[$row - 1]/item[$col - 1] = 'O') and
+        (not(/matrix/row[$row + 1]/item[$col - 1]) or /matrix/row[$row + 1]/item[$col - 1] = 'O') and
+        (not(/matrix/row[$row - 1]/item[$col + 1]) or /matrix/row[$row - 1]/item[$col + 1] = 'O')
+    "/>
+
+    <xsl:if test="$lonely">
+        <xsl:value-of select="$row"/>
+        <xsl:text>, </xsl:text>
+        <xsl:value-of select="$col"/>
+        <xsl:text disable-output-escaping="yes">&#10;</xsl:text>
+    </xsl:if>
+</xsl:template>
+
+</xsl:stylesheet>
diff --git a/challenge-077/dave-jacoby/perl/ch-1.pl b/challenge-077/dave-jacoby/perl/ch-1.pl
new file mode 100755
index 0000000000..6dc2865d99
--- /dev/null
+++ b/challenge-077/dave-jacoby/perl/ch-1.pl
@@ -0,0 +1,63 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature qw{ say signatures state };
+no warnings qw{ experimental };
+
+use Carp;
+use Getopt::Long;
+use List::Util qw{ max sum0 uniq };
+
+my $n = 9;
+GetOptions( 'n=i' => \$n );
+croak "n < 1" if $n < 1;
+
+fib_sum($n);
+
+#
+sub fib_sum ( $n ) {
+    my @fib = reverse fib_list($n);
+    my @list = ( [] );
+    my @sums;
+    my %no;
+
+    while (@list) {
+        my $entry = shift @list;
+        for my $fib (@fib) {
+            next if grep { $_ == $fib } $entry->@*;
+            my $new->@* = sort { $b <=> $a } $fib, $entry->@*;
+            my $sum = sum0 $new->@*;
+            my $join = join ',', $new->@*;
+            next if $no{$join}++;
+            push @list, $new if $sum < $n;
+            push @sums, $new if $sum == $n;
+        }
+    }
+
+    if ( scalar @sums ) {
+        for my $sum (@sums) {
+            my $s = scalar $sum->@*;
+            my $p = join ' + ', $sum->@*;
+            say qq{$s as ($n = $p)};
+        }
+    }
+    else { print 0 }
+}
+
+# creates a list of fibonacci values where each value is
+# less than n and greater than zero, because zero is useless
+# in summation
+sub fib_list( $n ) {
+    my @output = ( 0, 1 );
+    my $i = 2;
+
+    while ( max(@output) < $n ) {
+        $output[$i] = $output[ $i - 1 ] + $output[ $i - 2 ];
+        my $max = max(@output);
+        $i++;
+    }
+
+    @output = uniq grep { $_ } grep { $_ <= $n } @output;
+    return @output;
+}
diff --git a/challenge-077/dave-jacoby/perl/ch-2.pl b/challenge-077/dave-jacoby/perl/ch-2.pl
new file mode 100755
index 0000000000..f35435cb75
--- /dev/null
+++ b/challenge-077/dave-jacoby/perl/ch-2.pl
@@ -0,0 +1,71 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature qw{ say signatures state };
+no warnings qw{ experimental };
+
+use List::Util qw{ first };
+
+my @input = (
+    [ [qw[ O O X ]], [qw[ X O O ]], [qw[ X O O ]], ],
+    [ [qw( O O X O)], [qw( X O O O)], [qw( X O O X)], [qw( O X O O)], ]
+);
+
+for my $input (@input) {
+    say join "\n    ", '', map { join ' ', $_->@* } $input->@*;
+    say '';
+
+    my $c = lonely_x($input);
+    if    ( $c == 0 ) { say "No lonely Xs were found" }
+    elsif ( $c == 1 ) { say "One lonely X was found" }
+    else              { say "$c lonely Xs were found" }
+}
+
+# lonely_x takes an arrayref containing a two-dimensional array
+# representing an m x n matrix containing only X and O, and
+# returns a count of "lonely Xs", which are Xs without an
+# X in a bordering position. If none are found, it returns
+# zero
+
+sub lonely_x ( $input ) {
+
+    my $c = 0;
+    my $x = scalar $input->@*;
+    my $y = scalar $input->[0]->@*;
+
+    # X and y are the outer bounds of the matrix. 
+    # i and j are the location within the matrix.
+    # p is the value in the current "center".
+    # ii and jj are the bordering locations to i and j
+    # pp is the value in the current border location
+
+    # if pp is X, we know that i,j is not lonely,
+    # and thus we used he named next to get to the 
+    # next. If, instead, we get to the end of the ii,jj
+    # loops, it must be lonely and we increment our 
+    # "lonely X" count.
+
+    for my $i ( 0 .. $x ) {
+    OUT: for my $j ( 0 .. $y ) {
+            my $p = $input->[$i][$j];
+            next unless defined $p;
+            my $ok = 'X' eq $p ? 1 : 0;
+            next unless $ok;
+
+            for my $ii ( $i - 1 .. $i + 1 ) {
+                next if $ii < 0;
+                for my $jj ( $j - 1 .. $j + 1 ) {
+                    next if $jj < 0;
+                    next if $i == $ii && $j == $jj;
+                    my $pp = $input->[$ii][$jj];
+                    next unless defined $pp;
+                    next OUT if $pp eq 'X';
+                }
+            }
+            $c++;
+        }
+    }
+
+    return $c;
+}
diff --git a/challenge-077/e-choroba/perl/ch-1.pl b/challenge-077/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..35a6107b69
--- /dev/null
+++ b/challenge-077/e-choroba/perl/ch-1.pl
@@ -0,0 +1,82 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+use feature qw{ say };
+
+use Memoize;
+
+memoize('fibonacci');
+sub fibonacci {
+    my ($n) = @_;
+    my ($f1, $f2) = (1, 1);
+    for (1 .. $n) {
+        ($f1, $f2) = ($f2, $f1 + $f2);
+    }
+    return $f1
+}
+
+memoize('fibonacci_sum');
+sub fibonacci_sum {
+    my ($n) = @_;
+    return [[1]] if 1 == $n;
+
+    my @sum;
+    my $start_index = 1;
+    while ((my $start_f = fibonacci($start_index)) <= $n) {
+
+        push @sum, [$n]
+            and last
+            if $n == $start_f;
+
+        my $index = $start_index;
+        while ((my $f = fibonacci($index)) <= $n / 2) {
+            no warnings 'recursion';
+            my $s = fibonacci_sum($n - $f);
+
+            my @s = map [$f, @$_],
+                    grep $f < $_->[0],
+                    @$s
+                or last;
+
+            push @sum, @s;
+            ++$index;
+        }
+        ++$start_index;
+    }
+
+    return \@sum
+}
+
+sub pretty_print {
+    my ($n) = @_;
+    for my $s (@{ fibonacci_sum($n) }) {
+        say join(' + ', @$s), " = $n";
+    }
+}
+
+use Test::More;
+
+is fibonacci(0), 1;
+is fibonacci(1), 1;
+is fibonacci(2), 2;
+is fibonacci(3), 3;
+is fibonacci(4), 5;
+
+is_deeply fibonacci_sum(1),  [[1]],                              'one';
+is_deeply fibonacci_sum(2),  [[2]],                              'two';
+is_deeply fibonacci_sum(3),  [[1, 2], [3]],                      'three';
+is_deeply fibonacci_sum(4),  [[1, 3]],                           'four';
+is_deeply fibonacci_sum(5),  [[2, 3], [5]],                      'five';
+is_deeply fibonacci_sum(6),  [[1, 2, 3], [1, 5]],                'six';
+is_deeply fibonacci_sum(7),  [[2, 5]],                           'seven';
+is_deeply fibonacci_sum(8),  [[1, 2, 5], [3, 5], [8]],           'eight';
+is_deeply fibonacci_sum(9),  [[1, 3, 5], [1, 8]],                'nine';
+is_deeply fibonacci_sum(10), [[2, 3, 5], [2, 8]],                'ten';
+is_deeply fibonacci_sum(11), [[1, 2, 3, 5], [1, 2, 8], [3, 8]],  'eleven';
+is_deeply fibonacci_sum(12), [[1, 3, 8]],                        'twelve';
+is_deeply fibonacci_sum(13), [[2, 3, 8], [5, 8], [13]],          'thirteen';
+is_deeply fibonacci_sum(14), [[1, 2, 3, 8], [1, 5, 8], [1, 13]], 'fourteen';
+
+done_testing();
+
+pretty_print(18200); # Takes about 5s.
diff --git a/challenge-077/e-choroba/perl/ch-2.pl b/challenge-077/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..ebf221f3bc
--- /dev/null
+++ b/challenge-077/e-choroba/perl/ch-2.pl
@@ -0,0 +1,111 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+my $NO_X = qr/[^X] [^X] [^X]/;
+
+sub lonely_x {
+    my ($input) = @_;
+
+    my ($previous, @check);
+    my $count = 0;
+    my $verify = sub {
+        for my $ch (@check) {
+            $count += substr($_[0], $ch - 2, 5) =~ $NO_X;
+        }
+    };
+
+    open my $in, '<', \$input;
+    while (<$in>) {
+        $previous //= ' ' x length;
+        $verify->($_);
+        @check = ();
+
+        while (/(?=[^X] X [^X])/g) {
+            my $pos = pos;
+            push @check, $pos + 2 if substr($previous, $pos, 5) =~ $NO_X;
+        }
+        $previous = $_;
+    }
+    $verify->(' ' x length $previous);
+
+    return $count
+}
+
+use Test::More tests => 5;
+
+is lonely_x(<< '__'),
+[ O O X ]
+[ X O X ]
+[ X O O ]
+__
+0, 'None found';
+
+is lonely_x(<< '__'),
+[ O O X ]
+[ X O O ]
+[ X O O ]
+__
+1, 'Example 1';
+
+is lonely_x(<< '__'),
+[ O O X O ]
+[ X O O O ]
+[ X O O X ]
+[ O X O O ]
+__
+2, 'Example 2';
+
+is lonely_x(<< '__'),
+[ O O O X O X X ]
+[ X O O O O O O ]
+[ O O O O X O X ]
+[ O O X O O O O ]
+[ O X O O X O O ]
+[ X O O O X O X ]
+__
+5, 'Five';
+
+is lonely_x(<< '__'),
+[ X X X X O X O O O O O X X X X X O O O O O O X X X X O O X X X O O O O X O O ]
+[ O O O O O O X O X O X O O O O X O X X X X O O X X X X O X O X O O X O O X X ]
+[ O X O X X O O O O O O X X X O O O X O X O X X X O O X O O O O X O X X X O X ]
+[ O X O X X O O O O X O X O O X X X O X O O X O X O X O O O X X O X O X X X X ]
+[ O O X X X O O O X O X O O X O X O O X X O X O X X O X X O X X O O O O O O X ]
+[ O O O X X X O O O O O O O X O X X O X O O O O O X X X O X X O O O O X O O O ]
+[ O X X X X X O O X O X X O O X O X X X O X O O X O X O X X O X O O X X X X X ]
+[ O O O X O X X X O O X X O X X O X O O O O X O X X X O X X O O X O O O X O O ]
+[ X O X X X O O O O O X O X O O O O O O X X O X O O O O O X O O O X O X O O X ]
+[ X X X O O O X O O O O X O X O X O X O O X X X O X X O O X X X O O O O O O O ]
+[ X O X O X O X O X X O O X X X X X X X X X X X O X X O X O O O X O O O X O O ]
+[ X O X O O X O X X O X O X O X X O X X O O X O O O X X X O O O X X X O X O X ]
+[ O X O O X X X O X X O O O O O X O O O X O O O X X X X O X X O O X X O O X O ]
+[ X O O O X O X X O O X O O O X X O X O O O X X X O X O X O O O X O X O X X O ]
+[ X X X X X X X O X O X O O O X O O X O X X X X O O O O X X X O O O X X O X X ]
+[ O X X O O X X X O O X X O X O O O X O X O X X O O X O O X O O O O O O O O X ]
+[ O X O X O O O X O X O X O O O O X X X O X X O O X X O X X X O O X O X X O O ]
+[ O O X O X O O X X X X O O X O X O O X O X O X X X O X X O X X O O X X X O X ]
+[ O X X O O O O X O O O O O X X O O X X O X O X O X O O X O O X O X O X O X O ]
+[ O X X O X X X X O O X X X X O X O O X O X O X O O O X O X X X X O O X X X X ]
+[ O O O O O O O X X X X O O X O O X X O O O X O O X O X O X O O X X O O O O X ]
+[ O O X O X O O X X X O O X X X X O O X X X X X X X O O X O O O X O O O X O X ]
+[ X O X O X O O X O X O X X O X O X O X X X O O O O X X X X X X X O X O O X O ]
+[ O O X O O X O X O X O O O O O O O O X O X O O O O X X O X X X X O X X X O X ]
+[ X X X X X O O X O X X X O X X X O O X O X O X O O O O O O O O O O O O X O X ]
+[ X O O O O X X O O O O O O X X X O O O O X X O O O X X O O X O O X X O X X O ]
+[ O X O X X O O O X X X X X O X O X X X X O X O X O O O O X O O O O O O X O X ]
+[ X X O O O X O X X X O X X X O X O X O O O X X O O X X X O X O O O O O X O X ]
+[ O X X X X X X X O O O X O O X O O X O O X O X X O X X X X X X O O X O X O X ]
+[ O X X X X O O X O X O X X O X O X X O O O O O O X X O X X O O O O O X O O X ]
+[ X O O X O O X O X O X O O X X O X O X O X O X O O X O X X O X O O X O X O O ]
+[ O X O O X X X O X O X O O O O X O O X O X X X X O O X O O X X O O O O O X X ]
+[ X X O X X O O O X X X O X O O O X X O X X O X X O X O O X X X O O O O O X O ]
+[ O O X X X X X X X O X X X X O O X O X O X X X O O X X X X O O O X O O O O X ]
+[ O X O O X X X O X O X O O O O X X X O O O O O O X O X X X O X O X X X X O O ]
+[ X X X O O O O O X O O X X X O O O O X O O X X O O X O O X O X O X X X O X X ]
+[ X X O X O X X O O O X X X O X O X X X X X X X O X X X X X O O X O X O X X X ]
+[ X X O O O O X X X X O O X X X O O O O X O O X O X O O O X O O O O X O X X X ]
+[ X O O X O O O X X X X X X O O O X O O X X X O X O X X X X X O X O O X X X O ]
+[ O X O O O X O O O X O X O O X O O X O O O O X X X O X X X O X O O O O O X O ]
+__
+6, 'Six';
diff --git a/challenge-077/feng-chang/raku/ch-1.raku b/challenge-077/feng-chang/raku/ch-1.raku
new file mode 100755
index 0000000000..18676223f9
--- /dev/null
+++ b/challenge-077/feng-chang/raku/ch-1.raku
@@ -0,0 +1,29 @@
+#!/bin/env raku
+
+my Bool $found = False;
+my $Num;
+
+sub fib-sum(Int:D $N, @fibs, @num) {
+    if $N == 0 {
+        say "{ @num.join(' + ') } = $Num";
+        $found = True;
+        return;
+    }
+    return unless @fibs;
+    return if $N < @fibs[0];
+
+    my @F = @fibs;
+    my @N = @num;
+    @N.push(@F.shift);
+    fib-sum($N - @fibs[0], @F, @N);
+
+    fib-sum($N, @F, @num);
+}
+
+sub MAIN(Int:D $N) {
+    my Int @fibs = 1, 2, * + * ...^ * > $N;
+    $Num = $N;
+
+    fib-sum($N, @fibs, Array.new);
+    0.say unless $found;
+}
diff --git a/challenge-077/feng-chang/raku/ch-2.raku b/challenge-077/feng-chang/raku/ch-2.raku
new file mode 100755
index 0000000000..b9fdf10332
--- /dev/null
+++ b/challenge-0