Merge branch 'master' of https://github.com/manwar/perlweeklychallenge-club

89 files changed, 5336 insertions, 1912 deletions

diff --git a/challenge-086/abigail/blog.txt b/challenge-086/abigail/blog.txt
new file mode 100644
index 0000000000..9cab9b37f2
--- /dev/null
+++ b/challenge-086/abigail/blog.txt
@@ -0,0 +1 @@
+https://wp.me/pcxd30-3w
diff --git a/challenge-086/abigail/c/ch-1.c b/challenge-086/abigail/c/ch-1.c
new file mode 100644
index 0000000000..f081b5e098
--- /dev/null
+++ b/challenge-086/abigail/c/ch-1.c
@@ -0,0 +1,126 @@
+/*
+ * Challenge
+ *
+ * You are given an array of integers @N and an integer $A.
+ *
+ * Write a script to find find if there exists a pair of elements in
+ * the array whose difference is $A.
+ *
+ * Print 1 if exists otherwise 0.
+ */
+
+# include <stdlib.h>
+# include <stdio.h>
+# include <stdbool.h>
+# include <math.h>
+
+# define DEFAULT_BUF_SIZE  128
+# define BUF_INCREMENT       1.25   /* Increment the buffer size by   *
+                                     * a quarter each time we run out *
+                                     * of memory space.               */
+/*
+ * Compare two integer values, returning -1, 0, 1 if the first
+ * is smaller, equal, or larger than the second.
+ */
+int cmp (const void * a, const void * b) {
+    long diff = * (long *) a - * (long *) b;
+    return  diff < 0 ? -1
+         :  diff > 0 ?  1
+         :              0;
+}
+
+/*
+ * Binary search: return true if target is in array,
+ * with index i, min <= i < max.
+ */
+bool bin_search (long * array, long target, size_t min, size_t max) {
+    size_t mid = (min + max) / 2;   /* In C, dividing integers yields an *
+                                     * integer, so there is no need for  *
+                                     * flooring.                         */
+
+    return min >= max            ? false
+         : array [mid] == target ? true
+         : array [mid] >  target ?
+                     bin_search (array, target, min,     mid)
+         :           bin_search (array, target, mid + 1, max);
+}
+
+
+int main (void) {
+    /* Arguments for getline () */
+    char *  line    = NULL;
+    size_t  len     = 0;
+
+    /* We'll store the numbers in array, which we will reuse for each *
+     * line we're processing. We also need to keep track of how much  *
+     * memory we have allocated for the array.                        */
+    long * array    = NULL;
+    size_t buf_size = DEFAULT_BUF_SIZE;
+
+    /* The target difference */
+    long target;
+
+    /* Give the array some starting memory to work with.              */
+    if ((array = (long *) malloc (buf_size * sizeof (long))) == NULL) {
+        fprintf (stderr, "Out of memory\n");
+        return (1);
+    }
+
+    /*
+     * Iterate over the input, reading one line at a time
+     * Every odd line will be a sequence of integers, every
+     * even line will be a single integer. We'll do processing
+     * after each even line.
+     */
+    bool   is_even = true;
+    size_t size    = 0;       /* Number of integers in array.     */
+    while (getline (&line, &len, stdin) != -1) {
+        int    offset;
+        char * line_ptr = line;
+
+        is_even = !is_even;
+
+        if (!is_even) {
+            size = 0;   /* Reset size of array */
+            long input; /* Each long read from the line */
+
+            /* Scan the line just read, one long at a time */
+            while (sscanf (line_ptr, "%ld%n", &input, &offset) == 1) {
+                line_ptr += offset;
+
+                if (++ size >= buf_size) {
+                    /* Get some more memory. */
+                    buf_size = (size_t) floorf (buf_size * BUF_INCREMENT);
+                    if ((array = (long *) realloc (array,
+                                 buf_size * sizeof (long))) == NULL) {
+                        fprintf (stderr, "Out of memory\n");
+                        return (1);
+                    }
+                }
+
+                /* Store it */
+                array [size - 1] = input;
+            }
+
+            /* Quick sort to sort the array */
+            qsort (array, size, sizeof (long), cmp);
+        }
+        else {
+            char * endptr;
+            target = labs (strtol (line, &endptr, 10));
+
+            /*
+             * Iterate over the array, and check whether further down
+             * the array we find a number equal to target + array [i] --
+             * if so, there is a pair whose difference is target.
+             */
+            bool winner = false;
+            for (size_t i = 0; i < size && !winner; i ++) {
+                winner = bin_search (array, target + array [i], i + 1, size);
+            }
+            printf ("%d\n", winner ? 1 : 0);
+        }
+    }
+    free (line);
+    free (array);
+}
diff --git a/challenge-086/abigail/node/ch-1.js b/challenge-086/abigail/node/ch-1.js
new file mode 100644
index 0000000000..2a376d9a67
--- /dev/null
+++ b/challenge-086/abigail/node/ch-1.js
@@ -0,0 +1,47 @@
+//
+// Read STDIN. Split on newlines, then on whitespace, and turn the results
+// into numbers. Since the input will be newline terminated, we have an
+// empty line to filter out.
+//
+let lines = require      ("fs")
+          . readFileSync (0)               // Read all.
+          . toString     ()                // Turn it into a string.
+          . split        ("\n");           // Split on newlines.
+
+
+//
+// Iterate pair wise over the lines
+//
+for (let i = 0; i < lines . length - 1; i += 2) {
+    //
+    // First line is a set of integers, split on
+    // white space, and store the numbers in a hash.
+    //
+    let data = lines [i] . split  (" ")
+                         . reduce ((acc, val) => {
+        acc [val] = acc [val] ? acc [val] + 1 : 1;
+        return acc;
+    }, {});
+
+    //
+    // Second line is the target difference
+    //
+    let diff = +lines [i + 1];
+
+    //
+    // For each number in the array, check whether there is
+    // another number so their difference is that target
+    // difference. Special care has to be taken if the target
+    // difference is 0.
+    //
+    let winner = 0;
+    Object . keys (data) . forEach ((number) => {
+        if (!winner) {
+            let target = number - diff;
+            if (data [target] && (diff || data [target] > 1)) {
+                winner = 1;
+            }
+        }
+    });
+    console . log (winner);
+}
diff --git a/challenge-086/abigail/perl/ch-1.pl b/challenge-086/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..2b06f9ef59
--- /dev/null
+++ b/challenge-086/abigail/perl/ch-1.pl
@@ -0,0 +1,61 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# Challenge
+#
+# You are given an array of integers @N and an integer $A.
+#
+# Write a script to find find if there exists a pair of elements in
+# the array whose difference is $A.
+#
+# Print 1 if exists otherwise 0.
+#
+
+#
+# This can be solved trivally by taking the difference of all
+# pairs of numbers from @N, and see whether their difference
+# equals $A. But that leads to a quadractic algorithm.
+#
+# But we can do this in linear time. For each element $x in @N,
+# check with $A - $x exists in @N. Special care has to be taken
+# in case $A - $x == $x: we have to make sure $x then appears 
+# at least twice in @N.
+#
+# If we store the elements of @N in a hash, checking whether
+# number exists in @N can be done in O (1) expected time.
+#
+
+
+LINE: while (!eof ()) {
+    #
+    # Read data:
+    #   odd  lines are the numbers in @N
+    #   even lines are the differences ($A).
+    #
+    my %data;
+    $data {$_} ++ for <> =~ /[0-9]+/g;
+    last if eof ();
+    chomp (my $diff = <>);
+
+    foreach my $number (keys %data) {
+        my $target = $number - $diff;
+        if ($data {$target} && ($diff || $data {$number} > 1)) {
+            say 1;
+            next LINE;
+        }
+    }
+
+    say 0;
+}
+
+
+__END__
diff --git a/challenge-086/abigail/perl/ch-2.pl b/challenge-086/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..44646e9087
--- /dev/null
+++ b/challenge-086/abigail/perl/ch-2.pl
@@ -0,0 +1,427 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+################################################################################
+#
+# Challenge:
+#
+# You are given Sudoku puzzle (9x9).
+# 
+# Write a script to complete the puzzle and must respect the following rules:
+#  a) Each row must have the numbers 1-9 occuring just once.
+#  b) Each column must have the numbers 1-9 occuring just once.
+#  c) The numbers 1-9 must occur just once in each of the
+#     9 sub-boxes (3x3) of the grid.
+#
+################################################################################
+
+################################################################################
+#
+# Note:
+#
+# - We could of course make use of a module which solves Sudoku's,
+#   but what's the point of that?
+# - We are not restricting ourselves to 9x9 sudokus. It's rather
+#   trivial to extend it to any NxN sized sudoku. We only restrict
+#   the size to the number of bits in an integer (32, 64, 128, depending
+#   on the platform and compilation options).
+# - For even more fun, we solve "X" sudoku's as well. (An X sudoku has
+#   an additional constraint that the numbers on the diagonal are unique
+#   as well).
+#
+################################################################################
+
+################################################################################
+#
+# While there are more efficient algorithms (for instance, Donald Knuths
+# "Algorithm X" using a dancing links technique), we're using a 
+# brute force solution. But we're trying to do this in a smart way.
+#
+# We will split the sudoku into two sets. A set of solved cells,
+# and a set of unsolved set. For each solved cell, we store its
+# value; for each unsolved cell, we keep track of what possible
+# solutions it can have.
+#
+# The set of solved cells is initialized with the clues of the puzzle.
+# Each unsolved cell is represented as a bitfield, where each different
+# bit represents a different possible solution (so, for a NxN sudoku,
+# the bit fields have N bits). If the bit is 1, the corresponding value
+# may be a solution, if it's 0, it can no lo