From 753d64f20e66f7dcba008dac11b2d6f05d4bfb38 Mon Sep 17 00:00:00 2001 From: Abigail Date: Wed, 14 Oct 2020 00:15:12 +0200 Subject: Perl solution for week 82/part 2 --- challenge-082/abigail/input-2-1 | 3 ++ challenge-082/abigail/input-2-2 | 3 ++ challenge-082/abigail/input-2-3 | 3 ++ challenge-082/abigail/input-2-4 | 3 ++ challenge-082/abigail/output-2-1.exp | 2 ++ challenge-082/abigail/output-2-2.exp | 2 ++ challenge-082/abigail/output-2-3.exp | 2 ++ challenge-082/abigail/output-2-4.exp | 2 ++ challenge-082/abigail/perl/ch-2.pl | 63 ++++++++++++++++++++++++++++++++++++ 9 files changed, 83 insertions(+) create mode 100644 challenge-082/abigail/input-2-1 create mode 100644 challenge-082/abigail/input-2-2 create mode 100644 challenge-082/abigail/input-2-3 create mode 100644 challenge-082/abigail/input-2-4 create mode 100644 challenge-082/abigail/output-2-1.exp create mode 100644 challenge-082/abigail/output-2-2.exp create mode 100644 challenge-082/abigail/output-2-3.exp create mode 100644 challenge-082/abigail/output-2-4.exp create mode 100644 challenge-082/abigail/perl/ch-2.pl diff --git a/challenge-082/abigail/input-2-1 b/challenge-082/abigail/input-2-1 new file mode 100644 index 0000000000..f2469bebef --- /dev/null +++ b/challenge-082/abigail/input-2-1 @@ -0,0 +1,3 @@ +XY +X +XXY diff --git a/challenge-082/abigail/input-2-2 b/challenge-082/abigail/input-2-2 new file mode 100644 index 0000000000..d294e4dd65 --- /dev/null +++ b/challenge-082/abigail/input-2-2 @@ -0,0 +1,3 @@ +XXY +XXZ +XXXXZY diff --git a/challenge-082/abigail/input-2-3 b/challenge-082/abigail/input-2-3 new file mode 100644 index 0000000000..6e8b1c35e5 --- /dev/null +++ b/challenge-082/abigail/input-2-3 @@ -0,0 +1,3 @@ +YX +X +XXY diff --git a/challenge-082/abigail/input-2-4 b/challenge-082/abigail/input-2-4 new file mode 100644 index 0000000000..19c0d3d76c --- /dev/null +++ b/challenge-082/abigail/input-2-4 @@ -0,0 +1,3 @@ +FOO BAR 1 HELLO +FOO BAR 2 WORLD +FOO BAR 2 FOO BAR 1 WORLDHELLO diff --git a/challenge-082/abigail/output-2-1.exp b/challenge-082/abigail/output-2-1.exp new file mode 100644 index 0000000000..3b20e34eeb --- /dev/null +++ b/challenge-082/abigail/output-2-1.exp @@ -0,0 +1,2 @@ +# Very simple match +1 diff --git a/challenge-082/abigail/output-2-2.exp b/challenge-082/abigail/output-2-2.exp new file mode 100644 index 0000000000..d58ab7476b --- /dev/null +++ b/challenge-082/abigail/output-2-2.exp @@ -0,0 +1,2 @@ +# Another simple match +1 diff --git a/challenge-082/abigail/output-2-3.exp b/challenge-082/abigail/output-2-3.exp new file mode 100644 index 0000000000..64d32460c4 --- /dev/null +++ b/challenge-082/abigail/output-2-3.exp @@ -0,0 +1,2 @@ +# No match +0 diff --git a/challenge-082/abigail/output-2-4.exp b/challenge-082/abigail/output-2-4.exp new file mode 100644 index 0000000000..96e3e6efa7 --- /dev/null +++ b/challenge-082/abigail/output-2-4.exp @@ -0,0 +1,2 @@ +# Backtracking required +1 diff --git a/challenge-082/abigail/perl/ch-2.pl b/challenge-082/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..8a176e1e79 --- /dev/null +++ b/challenge-082/abigail/perl/ch-2.pl @@ -0,0 +1,63 @@ +#!/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 3 strings; $A, $B and $C. +# +# Write a script to check if $C is created by interleave $A and $B. +# +# Print 1 if check is success otherwise 0. +# + +chomp (my $A = <>); +chomp (my $B = <>); +chomp (my $C = <>); + +sub is_interleaved; +sub is_interleaved ($A, $B, $C) { + # + # If $A or $B is empty, the other should equal $C. + # This also takes care of the situation where all strings + # are empty (which means, they are interleaved). + # + return $A eq $C if !length $B; + return $B eq $C if !length $A; + + # + # The length of $C must equal the length of $A plus the + # length of $B, else $C cannot be an interleaving of $A and $B. + # + return unless length ($A) + length ($B) == length ($C); + + # + # Now, let $A = a . A', $B = b . B', $C = c . C', where + # a, b, and c are the first characters of the strings + # $A, $B, $C, and A', B', C' the rest of the strings. + # $C is an interleaving of $A and $B if one of the following + # statements is true: + # * a eq c, and C' is an interleaving of A' and $B. + # * b eq c, and C' is an interleaving of $A and B'. + # + # Note that at this point, none of the strings $A, $B or $C are empty. + # + my ($a, $A_prime) = $A =~ /^(.)(.*)$/; + my ($b, $B_prime) = $B =~ /^(.)(.*)$/; + my ($c, $C_prime) = $C =~ /^(.)(.*)$/; + return $a eq $c && is_interleaved ($A_prime, $B, $C_prime) || + $b eq $c && is_interleaved ($A, $B_prime, $C_prime); +} + +say is_interleaved ($A, $B, $C) ? 1 : 0; + + +__END__ -- cgit