Perl solutions for week 92

9 files changed, 162 insertions, 48 deletions

diff --git a/challenge-092/abigail/README.md b/challenge-092/abigail/README.md
index 525fe7067b..eb2482a03f 100644
--- a/challenge-092/abigail/README.md
+++ b/challenge-092/abigail/README.md
@@ -1,65 +1,44 @@
-Solution by Abigail
+# Solution by Abigail
 
-# Task 1: Count Number
+## Task 1: Isomorphic Strings
 
-You are given a positive number `$N`.
+You are given two strings `$A` and `$B`.
 
-Write a script to count number and display as you read it.
+Write a script to check if the given strings are Isomorphic. Print
+`1` if they are otherwise `0`.
 
-### Example 1:
+### Examples
+~~~~
+Input: $A = "abc"; $B = "xyz"
+Output: 1
 
-    Input: $N = 1122234
-    Output: 21321314
+Input: $A = "abb"; $B = "xyy"
+Output: 1
 
-as we read "two 1 three 2 one 3 one 4"
+Input: $A = "sum"; $B = "add"
+Output: 0
+~~~~
 
-### Example 2:
-
-    Input: $N = 2333445
-    Output: 12332415
-
-as we read "one 2 three 3 two 4 one 5"
-
-### Example 3:
-
-    Input: $N = 12345
-    Output: 1112131415
-
-as we read "one 1 one 2 one 3 one 4 one 5"
-
-## Solutions
+### Solutions
 * [Perl](perl/ch-1.pl).
 
-[Blog post](https://wp.me/pcxd30-j2).
 
-# Task 2: Jump Game
+## Task 2: Insert Interval
 
-You are given an array of positive numbers @N, where value at each
-index determines how far you are allowed to jump further.
+You are given a set of sorted non-overlapping intervals and a new interval.
 
-Write a script to decide if you can jump to the last index. Print
-1 if you are able to reach the last index otherwise 0.
+Write a script to merge the new interval to the given set of intervals.
 
-### Example 1:
+### Examples
+~~~~
+Input $S = (1,4), (8,10); $N = (2,6)
+Output: (1,6), (8,10)
 
-    Input: @N = (1, 2, 1, 2)
-    Output: 1
+Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+Output: (1,2), (3,10)
 
-as we jump one place from index 0 and then twoe places from index
-1 to reach the last index.
+Input $S = (1,5), (7,9); $N = (10,11)
+Output: (1,5), (7,9), (10,11)
 
-### Example 2:
-
-    Input: @N = (2,1,1,0,2)
-    Output: 0
-
-it is impossible to reach the last index. as we jump two places
-from index 0 to reach index 2, followed by one place jump from index
-2 to reach the index 3. once you reached the index 3, you can't go
-any further because you can only jump 0 position further.
-
-
-## Solutions
+### Solutions
 * [Perl](perl/ch-2.pl).
-
-[Blog post](https://wp.me/pcxd30-jq).
diff --git a/challenge-092/abigail/perl/ch-1.pl b/challenge-092/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..9d6c224e92
--- /dev/null
+++ b/challenge-092/abigail/perl/ch-1.pl
@@ -0,0 +1,50 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+sub solve;
+
+my @lines = <>;
+say $_ ? 1 : 0 for map {solve @lines [$_ - 1, $_]} grep {$_ % 2} keys @lines;
+exit;
+
+#
+# Return true of $A and $B are isomorphic.
+#
+# What we want is to show there is a bijection f between the letters
+# of $A and the letters of $B.
+#
+# For a bijection, we need to show that:
+#     f and f^-1 (the inverse of f) are total
+#     f (x) == f (y)  <=> x == y
+#
+# 1) we check that $A and $B have the same length, otherwise either
+#    f or f^-1 isn't total.
+# 2) x == y => f (x) == f (y)
+# 3) |dom (f)| = |img (f)|  (Size of the domain of f is the
+#                            size of the image of f)
+# 
+sub solve ($A, $B) {
+    return 0 unless length ($A) == length ($B);      # 1)
+    my @A = split // => $A;
+    my @B = split // => $B;
+    my %mapping;
+    foreach my $i (keys @A) {
+        my $A = $A [$i];
+        my $B = $B [$i];
+        return 0 if $B ne ($mapping {$A} //= $B);    # 2)
+    }
+    my %reverse = reverse %mapping;
+    keys %reverse == keys %mapping;                  # 3)
+}
+
+
+
+__END__
diff --git a/challenge-092/abigail/perl/ch-2.pl b/challenge-092/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..2c1b8f6dc4
--- /dev/null
+++ b/challenge-092/abigail/perl/ch-2.pl
@@ -0,0 +1,58 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+while (<>) {
+    #
+    # Read in the input:
+    #   - Extract a bunch of numbers from the input
+    #   - Pair them up to form intervals
+    #   - Pop the last one for $N
+    #
+    chomp;
+    my @numbers = /[0-9]+/g;
+    my @intervals;
+    push @intervals => [splice @numbers => 0, 2] while @numbers;
+    my $N = pop @intervals;
+
+    #
+    # Partition the intervals into three sets:
+    #    - Intervals completely to the left of $N
+    #    - Intervals intersecting $N
+    #    - Intervals completely to the right of $N
+    #
+    # Each set my be empty. The first and last set will be unmodified.
+    #
+    my @pre  = grep {$$_ [1] <  $$N [0]} @intervals;
+    my @mid  = grep {$$_ [0] <= $$N [1] &&
+                     $$_ [1] >= $$N [0]} @intervals;
+    my @post = grep {$$_ [0] >  $$N [1]} @intervals;
+
+    #
+    # Merge the middle set will be with $N, the result is a single interval:
+    #    - If the middle set is not empty, and the start of the
+    #      first interval in the set is to the left of the start
+    #      of $N, the start point of the merged interval is the start
+    #      point of the merged interval, else it's the start point of $N.
+    #    - For the endpoint, we compare the end points of last interval
+    #      in the middle set with the end point of $N.
+    #  
+    my $mid  = [@mid && $mid  [0] [0] < $$N [0] ? $mid  [0] [0] : $$N [0],
+                @mid && $mid [-1] [1] > $$N [1] ? $mid [-1] [1] : $$N [1]];
+
+    #
+    # Print the result.
+    #
+    say join ", " => map {"(" . $$_ [0] . ", " . $$_ [1] . ")"}
+                    @pre, $mid, @post;
+}
+
+
+__END__
diff --git a/challenge-092/abigail/t/input-1-1 b/challenge-092/abigail/t/input-1-1
new file mode 100644
index 0000000000..34b4f01444
--- /dev/null
+++ b/challenge-092/abigail/t/input-1-1
@@ -0,0 +1,6 @@
+abc
+xyz
+abb
+xyy
+sum
+add
diff --git a/challenge-092/abigail/t/input-1-2 b/challenge-092/abigail/t/input-1-2
new file mode 100644
index 0000000000..2ae872f5c7
--- /dev/null
+++ b/challenge-092/abigail/t/input-1-2
@@ -0,0 +1,6 @@
+short
+longer
+longer
+short
+abbb
+xyy
diff --git a/challenge-092/abigail/t/input-2-1 b/challenge-092/abigail/t/input-2-1
new file mode 100644
index 0000000000..d4c309b445
--- /dev/null
+++ b/challenge-092/abigail/t/input-2-1
@@ -0,0 +1,3 @@
+1 4 8 10 2 6
+1 2 3 7 8 10 5 8
+1 5 7 9 10 11
diff --git a/challenge-092/abigail/t/output-1-1.exp b/challenge-092/abigail/t/output-1-1.exp
new file mode 100644
index 0000000000..cb9ab047bc
--- /dev/null
+++ b/challenge-092/abigail/t/output-1-1.exp
@@ -0,0 +1,4 @@
+# Given examples
+1
+1
+0
diff --git a/challenge-092/abigail/t/output-1-2 b/challenge-092/abigail/t/output-1-2
new file mode 100644
index 0000000000..0f22ad9b8d
--- /dev/null
+++ b/challenge-092/abigail/t/output-1-2
@@ -0,0 +1,4 @@
+# Unequal lengths
+0
+0
+0
diff --git a/challenge-092/abigail/t/output-2-1.exp b/challenge-092/abigail/t/output-2-1.exp
new file mode 100644
index 0000000000..1a60432fc5
--- /dev/null
+++ b/challenge-092/abigail/t/output-2-1.exp
@@ -0,0 +1,4 @@
+# Given examples
+(1, 6), (8, 10)
+(1, 2), (3, 10)
+(1, 5), (7, 9), (10, 11)