aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-127/abigail/README.md98
-rw-r--r--challenge-127/abigail/awk/ch-1.awk23
-rw-r--r--challenge-127/abigail/awk/ch-2.awk49
-rw-r--r--challenge-127/abigail/bash/ch-1.sh35
-rw-r--r--challenge-127/abigail/blog.txt1
-rw-r--r--challenge-127/abigail/blog1.txt1
-rw-r--r--challenge-127/abigail/c/ch-1.c75
-rw-r--r--challenge-127/abigail/lua/ch-1.lua22
-rw-r--r--challenge-127/abigail/node/ch-1.js24
-rw-r--r--challenge-127/abigail/perl/ch-1.pl38
-rw-r--r--challenge-127/abigail/perl/ch-2.pl84
-rw-r--r--challenge-127/abigail/python/ch-1.py21
-rw-r--r--challenge-127/abigail/ruby/ch-1.rb24
-rw-r--r--challenge-127/abigail/t/ctest.ini9
-rw-r--r--challenge-127/abigail/t/input-1-12
-rw-r--r--challenge-127/abigail/t/input-2-12
-rw-r--r--challenge-127/abigail/t/input-2-21
-rw-r--r--challenge-127/abigail/t/output-1-1.exp2
-rw-r--r--challenge-127/abigail/t/output-2-1.exp2
-rw-r--r--challenge-127/abigail/t/output-2-2.exp1
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
generated by cgit (git 2.34.1) at 2026-05-25 15:25:54 +0000