Merge pull request #4807 from Abigail/abigail/week-127

Abigail/week 127

20 files changed, 468 insertions, 46 deletions

diff --git a/challenge-127/abigail/README.md b/challenge-127/abigail/README.md
index 07235caf33..0c99f58d44 100644
--- a/challenge-127/abigail/README.md
+++ b/challenge-127/abigail/README.md
@@ -1,28 +1,28 @@
 # Solutions by Abigail
-## [Count Numbers][task1]
+## [Disjoint Sets][task1]
 
-> You are given a positive integer `$N`.
+> You are given two sets with unique integers.
 > 
-> Write a script to print count of numbers from `1` to `$N` that don't
-> contain digit `1`.
+> Write a script to figure out if they are disjoint.
+> 
+> > The two sets are disjoint if they don't have any common members.
+
 
-### Example
+### Examples
 
 ~~~~
-Input: $N = 15
-Output: 8
+Input: @S1 = (1, 2, 5, 3, 4)
+       @S2 = (4, 6, 7, 8, 9)
 ~~~~
 
-There are 8 numbers between `1` and `15` that don't contain digit `1`:
-`2, 3, 4, 5, 6, 7, 8, 9`.
+Output: `0` as the given two sets have common member `4`.
 
 ~~~~
-Input: $N = 25
-Output: 13
+Input: @S1 = (1, 3, 5, 7, 9)
+       @S2 = (0, 2, 4, 6, 8)
 ~~~~
 
-There are 13 numbers between `1` and `25` that don't contain digit `1`:
-`2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24, 25`.
+Output: `1` as the given two sets do not have common member.
 
 
 ### Solutions
@@ -36,51 +36,57 @@ There are 13 numbers between `1` and `25` that don't contain digit `1`:
 * [Ruby](ruby/ch-1.rb)
 
 ### Blog
-[Perl Weekly Challenge 126: Count Numbers][blog1]
+[Perl Weekly Challenge 127: Disjoint Sets][blog1]
 
-## [Minesweeper Game][task2]
+## [Conflict Intervals][task2]
 
-> You are given a rectangle with points marked with either `x` or `*`.
-> Please consider the `x` as a land mine.
-> 
-> Write a script to print a rectangle with numbers and `x` as in the
-> Minesweeper game.
+> You are given a list of intervals.
 > 
-> > A number in a square of the minesweeper game indicates the
-> > number of mines within the neighbouring squares (usually `8`),
-> > also implies that there are no bombs on that square.
+> Write a script to find out if the current interval conflicts with
+> any of the previous intervals.
 
-### Example
+### Examples
 
 ~~~~
-Input:
-    x * * * x * x x x x
-    * * * * * * * * * x
-    * * * * x * x * x *
-    * * * x x * * * * *
-    x * * * x * * * * x
-
-Output:
-    x 1 0 1 x 2 x x x x
-    1 1 0 2 2 4 3 5 5 x
-    0 0 1 3 x 3 x 2 x 2
-    1 1 1 x x 4 1 2 2 2
-    x 1 1 3 x 2 0 0 1 x
-~~~
+Input: @Intervals = [(1,4), (3,5), (6,8), (12, 13), (3,20)]
+Output: [(3,5), (3,20)]
+~~~~
+
+* The 1st interval `(1,4)` do not have any previous intervals to compare with,
+  so skip it.
+* The 2nd interval `(3,5)` does conflict with previous interval (1,4).
+* The 3rd interval `(6,8)` do not conflicts with any of the previous intervals
+  `(1,4)` and `(3,5)`, so skip it.
+* The 4th interval `(12,13)` again do not conflicts with any of the previous
+  intervals `(1,4)`, `(3,5)` and `(6,8)`, so skip it.
+* The 5th interval `(3,20)` conflicts with the first interval `(1,4)`.
+
+~~~~
+Input: @Intervals = [(3,4), (5,7), (6,9), (10, 12), (13,15)]
+Output: [(6,9)]
+~~~~
+
+* The 1st interval `(3,4)` do not have any previous intervals to compare with,
+  so skip it.
+* The 2nd interval `(5,7)` do not conflicts with the previous interval `(3,4)`,
+  so skip it.
+* The 3rd interval `(6,9)` does conflict with one of the previous
+  intervals `(5,7)`.
+* The 4th interval `(10,12)` do not conflicts with any of the previous
+  intervals `(3,4)`, `(5,7)` and `(6,9)`, so skip it.
+* The 5th interval `(13,15)` do not conflicts with any of the previous
+  intervals `(3,4)`, `(5,7)`, `(6,9)` and `(10,12)`, so skip it.
 
 ### Solutions
 * [AWK](awk/ch-2.awk)
-* [C](c/ch-2.c)
-* [Lua](lua/ch-2.lua)
-* [Node.js](node/ch-2.js)
 * [Perl](perl/ch-2.pl)
 
 ### Blog
-[Perl Weekly Challenge 126: Minesweeper Game][blog2]
+[Perl Weekly Challenge 127: Conflict Intervals][blog2]
 
 
 
-[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-126/#TASK1
-[task2]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-126/#TASK2
-[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-126-1.html
-[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-126-2.html
+[task1]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-127/#TASK1
+[task2]: https://perlweeklychallenge.org/blog/perl-weekly-challenge-127/#TASK2
+[blog1]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-127-1.html
+[blog2]: https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-127-2.html
diff --git a/challenge-127/abigail/awk/ch-1.awk b/challenge-127/abigail/awk/ch-1.awk
new file mode 100644
index 0000000000..6f16c38d63
--- /dev/null
+++ b/challenge-127/abigail/awk/ch-1.awk
@@ -0,0 +1,23 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
+{
+    delete seen
+    for (i = 1; i <= NF; i ++) {
+        seen [0 + $i] ++
+    }
+    for (i in seen) {
+        if (seen [i] > 1) {
+            print 0
+            next
+        }
+    }
+    print 1
+}
diff --git a/challenge-127/abigail/awk/ch-2.awk b/challenge-127/abigail/awk/ch-2.awk
new file mode 100644
index 0000000000..53d66a3689
--- /dev/null
+++ b/challenge-127/abigail/awk/ch-2.awk
@@ -0,0 +1,49 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-2.awk < input-file
+#
+
+function intersects (x_low, x_high, y_low, y_high) {
+    return (x_high >= y_low && x_low <= y_high)
+}
+
+{
+    delete vertices
+    #
+    # Read input
+    #
+    for (i = 1; i <= NF; i ++) {
+        gsub (/[^0-9]/, "", $i)
+        vertices [i] = 0 + $i
+    }
+
+    #
+    # Make sure vertices are low-high for each interval; swap if not
+    #
+    for (i = 1; i <= NF; i += 2) {
+        if (vertices [i] > vertices [i + 1]) {
+            t = vertices [i]
+            vertices [i] = vertices [i + 1]
+            vertices [i + 1] = t
+        }
+    }
+
+    #
+    # Check for intersections
+    #
+    for (i = 3; i <= NF; i += 2) {
+        for (j = 1; j < i; j += 2) {
+            if (intersects(vertices [i], vertices [i + 1],
+                           vertices [j], vertices [j + 1])) {
+                print (1)
+                next
+            }
+        }
+    }
+    print (0)
+}
diff --git a/challenge-127/abigail/bash/ch-1.sh b/challenge-127/abigail/bash/ch-1.sh
new file mode 100644
index 0000000000..1fc137e81f
--- /dev/null
+++ b/challenge-127/abigail/bash/ch-1.sh
@@ -0,0 +1,35 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-1.sh < input-file
+#
+
+set -f
+
+declare -A seen
+
+while read -a numbers
+do    seen=()
+
+      #
+      # Histogram of numbers. Get rid of separator
+      #
+      for  number in ${numbers[@]}
+      do   ((seen[${number/;/}] ++))
+      done
+
+      #
+      # Print 1/0 depending on whether they are disjunct or not
+      #
+      ((out = 1))
+      for val in ${seen[@]}
+      do  if   ((val > 1))
+          then ((out = 0))
+          fi
+      done
+      echo $out
+done
diff --git a/challenge-127/abigail/blog.txt b/challenge-127/abigail/blog.txt
new file mode 100644
index 0000000000..1b23db806e
--- /dev/null
+++ b/challenge-127/abigail/blog.txt
@@ -0,0 +1 @@
+https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-127-1.html
diff --git a/challenge-127/abigail/blog1.txt b/challenge-127/abigail/blog1.txt
new file mode 100644
index 0000000000..0683411d3c
--- /dev/null
+++ b/challenge-127/abigail/blog1.txt
@@ -0,0 +1 @@
+https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-127-2.html
diff --git a/challenge-127/abigail/c/ch-1.c b/challenge-127/abigail/c/ch-1.c
new file mode 100644
index 0000000000..8354b9ce1f
--- /dev/null
+++ b/challenge-127/abigail/c/ch-1.c
@@ -0,0 +1,75 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <ctype.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file
+ */
+
+int cmp (const void * a, const void * b) {
+    return (* (int *) a - * (int *) b);
+}
+
+int main (void) {
+    char *  line    = NULL;
+    size_t  len     = 0;
+    size_t  str_len;
+
+    while ((str_len = getline (&line, &len, stdin)) != -1) {
+        /*
+         * First, get rid of ';', and count the number of integers.
+         */
+        char * line_ptr = line;
+        size_t count = 1;
+        while (* line_ptr) {
+            if (* line_ptr == ';') {
+                * line_ptr =  ' ';
+            }
+            if (line_ptr != line &&
+                !isspace (* line_ptr) && isspace (* (line_ptr - 1))) {
+                count ++;
+            }
+            line_ptr ++;
+        }
+
+        /*
+         * Create an array of the input numbers 
+         */
+        int * numbers;
+        if ((numbers = (int *) malloc (count * sizeof (int))) == NULL) {
+            perror ("Malloc failed");
+            exit (1);
+        }
+        line_ptr = line;
+        int i = 0;
+        int skip;
+        int number;
+        while (sscanf (line_ptr, "%d%n", &number, &skip) == 1) {
+            numbers [i ++] = number;
+            line_ptr += skip;
+        }
+
+        qsort (numbers, i, sizeof (int), cmp);
+
+        /*
+         * Iterate through the array to see if a number duplicates
+         */
+        int out = 1;
+        for (int j = 1; j < i; j ++) {
+            if (numbers [j] == numbers [j - 1]) {
+                out = 0;
+                break;
+            }
+        }
+
+        printf ("%d\n", out);
+    }
+    free (line);
+
+    return (0);
+}
diff --git a/challenge-127/abigail/lua/ch-1.lua b/challenge-127/abigail/lua/ch-1.lua
new file mode 100644
index 0000000000..517e884e6c
--- /dev/null
+++ b/challenge-127/abigail/lua/ch-1.lua
@@ -0,0 +1,22 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-1.lua < input-file
+--
+
+for line in io . lines () do
+    local seen = {}
+    local out  = 1
+    for number in line : gmatch ("([-+]?[0-9]+)") do
+        if seen [number] then
+            out = 0  -- We have a duplicate
+        else
+            seen [number] = 1
+        end
+    end
+    print (out)
+end
diff --git a/challenge-127/abigail/node/ch-1.js b/challenge-127/abigail/node/ch-1.js
new file mode 100644
index 0000000000..931330be8b
--- /dev/null
+++ b/challenge-127/abigail/node/ch-1.js
@@ -0,0 +1,24 @@
+#!/usr/local/bin/node
+
+//
+// See ../README.md
+//
+
+//
+// Run as: node ch-1.js < input-file
+//
+
+  require ('readline')
+. createInterface ({input: process . stdin})   
+. on              ('line', line => {
+    let seen = {}
+    let out  = 1
+    line . split (/[ ;]+/) . forEach (n => {
+        if (n in seen) {
+            out = 0
+        }
+        seen [n] = 1
+    })
+    console . log (out)
+})
+
diff --git a/challenge-127/abigail/perl/ch-1.pl b/challenge-127/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..f5010edb02
--- /dev/null
+++ b/challenge-127/abigail/perl/ch-1.pl
@@ -0,0 +1,38 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# Run as: perl ch-1.pl < input-file
+#
+
+#
+# The two sets given each contain unique integers. So, the sets
+# are disjoint if and only if their union doesn't contain duplicates.
+# An array of integers doesn't contain duplicates if we create a hash
+# out of the array (values don't matter), then check whether the number
+# of keys of the hash is the same as the number of elements in the array.
+# We'll use the hash %_ and the array @_. A hash in scalar context
+# gives the number of keys in the hash.
+#
+# We assume each line of input contains two sets of integers, the
+# integers separated by white space, and the sets with semi-colons.
+# For each line of input, we print either a 1 or a 0 to the output.
+#
+
+while (<>) {
+    %_ = map {$_ => $_} @_ = /[-+]?[0-9]+/g; say %_ == @_ ? 1 : 0;
+}
+
+__END__
diff --git a/challenge-127/abigail/perl/ch-2.pl b/challenge-127/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..2bb751c058
--- /dev/null
+++ b/challenge-127/abigail/perl/ch-2.pl
@@ -0,0 +1,84 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# See ../README.md
+#
+
+#
+# "You are given a list of intervals".
+#
+# Uhm, what's the domain? Which dimension, and from which set are the
+# the coordinates? N? Z? Q? R? C? Something else?
+#
+# The examples given have 1-d intervals, with positive integer coordinates,
+# so we'll assume we only have positive integer coordinates, and our
+# intervals are 1-d.
+#
+# "Write a script to find out if the current interval conflicts with
+#  any of the previous intervals."
+#
+# This suggest we should output a true/false value. Or perhaps multiple.
+# What is "the current interval"? The first one? The last one? 
+# The examples aren't very useful, as it prints out some of the 
+# intersection intervals, leaving out others.
+#
+# Did noone proofread the challenge?
+#
+# We'll just going to assume 1 should be printed if there is a pair of
+# intervals which intersect, and 0 otherwise.
+#
+
+#
+# The best solution would be to build an interval tree, which can be
+# done in O (n log n) time, and for each of the intervals, check if
+# it intersects with any of the others. The latter can be done in 
+# O (log n) time for each interval, which would give an O (n log n)
+# solution. However, we'll do the easy thing: just compare each pair
+# of intervals, stopping as soon as we have an intersecting pair.
+# Worst case there are no intersections, and we're doing O (n^2)
+# comparisons (each of them can be done in O (1) time).
+#
+
+#
+# Run as: perl ch-1.pl < input-file
+#
+
+#
+# Return true if two intervals intersect, false otherwise.
+#
+my sub intersects ($x, $y) {($$x [1] >= $$y [0]) && ($$x [0] <= $$y [1])}
+
+MAIN: while (<>) {
+    my @intervals = map {[split /[^0-9]+/]} /[1-9][0-9]*[^0-9]+[1-9][0-9]*/g;
+
+    #
+    # Make sure the intervals are all in order, that is, have their
+    # first vertex < second vertex.
+    #
+    foreach my $interval (@intervals) {
+        @$interval = reverse @$interval if $$interval [1] < $$interval [0];
+    }
+
+    # 
+    # Compare each pair of intervals
+    #
+
+    for (my $i = 1; $i < @intervals; $i ++) {
+        for (my $j = 0; $j < $i; $j ++) {
+            if (intersects $intervals [$i], $intervals [$j]) {
+                say 1;
+                next MAIN;
+            }
+        }
+    }
+    say 0;
+}
diff --git a/challenge-127/abigail/python/ch-1.py b/challenge-127/abigail/python/ch-1.py
new file mode 100644
index 0000000000..8e4bb3c380
--- /dev/null
+++ b/challenge-127/abigail/python/ch-1.py
@@ -0,0 +1,21 @@
+#!/opt/local/bin/python
+
+#
+# See ../README.md
+#
+
+#
+# Run as: python ch-1.py < input-file
+#
+
+import fileinput
+import re
+
+for line in fileinput . input ():
+    seen = {}
+    out  = 1
+    for number in re . findall (r"[-+]?[0-9]+", line):
+        if number in seen:
+            out = 0
+        seen [number] = 1
+    print (out)
diff --git a/challenge-127/abigail/ruby/ch-1.rb b/challenge-127/abigail/ruby/ch-1.rb
new file mode 100644
index 0000000000..e9b02c3ca9
--- /dev/null
+++ b/challenge-127/abigail/ruby/ch-1.rb
@@ -0,0 +1,24 @@
+#!/usr/bin/ruby
+
+#
+# See ../README.md
+#
+ 
+#
+# Run as: ruby ch-1.rb < input-file
+#
+
+ARGF . each_line do
+    | line |
+    out = 1
+    seen = {}
+    line . scan(/[-+]?[0-9]+/) do
+        | number |
+        if seen [number] then
+            out = 0
+        else
+            seen [number] = 1
+        end
+    end
+    puts (out)
+end
diff --git a/challenge-127/abigail/t/ctest.ini b/challenge-127/abigail/t/ctest.ini
new file mode 100644
index 0000000000..52ac608c40
--- /dev/null
+++ b/challenge-127/abigail/t/ctest.ini
@@ -0,0 +1,9 @@
+# 

+# Configuration file for running tests, using ctest.

+# See https://github.com/Abigail/Misc/blob/master/ctest

+# 

+

+[names]

+1-1 = Given examples

+2-1 = Given examples

+2-2 = No intersection

diff --git a/challenge-127/abigail/t/input-1-1 b/challenge-127/abigail/t/input-1-1
new file mode 100644
index 0000000000..98343f4871
--- /dev/null
+++ b/challenge-127/abigail/t/input-1-1
@@ -0,0 +1,2 @@
+1 2 5 3 4; 4 6 7 8 9
+1 3 5 7 9; 0 2 4 6 8
diff --git a/challenge-127/abigail/t/input-2-1 b/challenge-127/abigail/t/input-2-1
new file mode 100644
index 0000000000..692e1b6566
--- /dev/null
+++ b/challenge-127/abigail/t/input-2-1
@@ -0,0 +1,2 @@
+(1, 4), (3, 5), (6, 8), (12, 13), (3, 20)
+(3, 4), (5, 7), (6, 9), (10, 12), (13, 15)
diff --git a/challenge-127/abigail/t/input-2-2 b/challenge-127/abigail/t/input-2-2
new file mode 100644
index 0000000000..c19bd6fefb
--- /dev/null
+++ b/challenge-127/abigail/t/input-2-2
@@ -0,0 +1 @@
+(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), (11, 12)
diff --git a/challenge-127/abigail/t/output-1-1.exp b/challenge-127/abigail/t/output-1-1.exp
new file mode 100644
index 0000000000..0d66ea1aee
--- /dev/null
+++ b/challenge-127/abigail/t/output-1-1.exp
@@ -0,0 +1,2 @@
+0
+1
diff --git a/challenge-127/abigail/t/output-2-1.exp b/challenge-127/abigail/t/output-2-1.exp
new file mode 100644
index 0000000000..6ed281c757
--- /dev/null
+++ b/challenge-127/abigail/t/output-2-1.exp
@@ -0,0 +1,2 @@
+1
+1
diff --git a/challenge-127/abigail/t/output-2-2.exp b/challenge-127/abigail/t/output-2-2.exp
new file mode 100644
index 0000000000..573541ac97
--- /dev/null
+++ b/challenge-127/abigail/t/output-2-2.exp
@@ -0,0 +1 @@
+0