diff options
| -rw-r--r-- | challenge-092/abigail/README.md | 75 | ||||
| -rw-r--r-- | challenge-092/abigail/perl/ch-1.pl | 50 | ||||
| -rw-r--r-- | challenge-092/abigail/perl/ch-2.pl | 58 | ||||
| -rw-r--r-- | challenge-092/abigail/t/input-1-1 | 6 | ||||
| -rw-r--r-- | challenge-092/abigail/t/input-1-2 | 6 | ||||
| -rw-r--r-- | challenge-092/abigail/t/input-2-1 | 3 | ||||
| -rw-r--r-- | challenge-092/abigail/t/output-1-1.exp | 4 | ||||
| -rw-r--r-- | challenge-092/abigail/t/output-1-2 | 4 | ||||
| -rw-r--r-- | challenge-092/abigail/t/output-2-1.exp | 4 |
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) |