Merge pull request #3046 from pauloscustodio/092-perl

Add Perl solution to challenge 092

3 files changed, 171 insertions, 0 deletions

diff --git a/challenge-092/paulo-custodio/perl/ch-1.pl b/challenge-092/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..163e7d530b
--- /dev/null
+++ b/challenge-092/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,58 @@
+#!/usr/bin/perl
+
+# Challenge 092
+# 
+# TASK #1 › Isomorphic Strings
+# Submitted by: Mohammad S Anwar
+# You are given two strings $A and $B.
+# 
+# Write a script to check if the given strings are Isomorphic. Print 1 if they are otherwise 0.
+# 
+# Example 1:
+# Input: $A = "abc"; $B = "xyz"
+# Output: 1
+# Example 2:
+# Input: $A = "abb"; $B = "xyy"
+# Output: 1
+# Example 3:
+# Input: $A = "sum"; $B = "add"
+# Output: 0
+
+use strict;
+use warnings;
+use 5.030;
+
+say isomorphic(@ARGV);
+
+sub isomorphic {
+	my($a, $b) = @_;
+	
+	# both strings must be the same size
+	if (!defined($a) || !defined($b) || length($a) != length($b)) {
+		return 0;
+	}
+	
+	# convert each string to a list and check the mapping
+	my(%mapping, %mapped);
+	my @a = split(//, $a);
+	my @b = split(//, $b);
+	while (@a) {
+		my $a = shift @a;
+		my $b = shift @b;
+		if (!$mapping{$a}) {			# a is new
+			if ($mapped{$b}) {			# b already mapped to some other a
+				return 0;
+			}
+			else {						# store mapping
+				$mapping{$a} = $b;
+				$mapped{$b} = 1;
+			}
+		}								# a already occurred
+		else {
+			if ($mapping{$a} ne $b) {	# previous mapping is different
+				return 0;
+			}
+		}
+	}
+	return 1;
+}
diff --git a/challenge-092/paulo-custodio/perl/ch-2.pl b/challenge-092/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..bfbdd28249
--- /dev/null
+++ b/challenge-092/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,90 @@
+#!/usr/bin/perl
+
+# Challenge 092
+# 
+# TASK #2 › Insert Interval
+# Submitted by: Mohammad S Anwar
+# You are given a set of sorted non-overlapping intervals and a new interval.
+# 
+# Write a script to merge the new interval to the given set of intervals.
+# 
+# Example 1:
+# Input $S = (1,4), (8,10); $N = (2,6)
+# Output: (1,6), (8,10)
+# Example 2:
+# Input $S = (1,2), (3,7), (8,10); $N = (5,8)
+# Output: (1,2), (3,10)
+# Example 3:
+# Input $S = (1,5), (7,9); $N = (10,11)
+# Output: (1,5), (7,9), (10,11)
+
+use strict;
+use warnings;
+use 5.030;
+
+my @intervals;			# set of all intervals
+add_interval(parse($_)) for @ARGV;
+print_intervals();
+
+# convert a string "(a,b)" into [a,b]
+sub parse {
+	my($text) = @_;
+	my($a, $b) = ($text =~ /(\d+)\D+(\d+)/) or die "invalid interval: $text\n";
+	return ($a, $b);
+}
+
+# add a new interval in order, merge if overlapping
+sub add_interval {
+	my($s, $e) = @_;
+	add_interval_1(sort {$a <=> $b} ($s, $e));
+	merge_intervals();
+}
+
+sub add_interval_1 {
+	my($a, $b) = @_;
+	if (!@intervals) {						# first interval
+		push @intervals, [$a, $b];
+	}
+	else {
+		for (my $i = 0; $i < @intervals; $i++) {
+			my $this = $intervals[$i];
+			if ($b < $this->[0]) {							# before, not overlapping
+				splice(@intervals, $i, 0, [$a, $b]);
+				return;
+			}
+			elsif ($b >= $this->[0] && $b < $this->[1]) {	# end within this interval
+				if ($a < $this->[0]) {						# merge start
+					$this->[0] = $a;
+				}
+				return;
+			}
+			elsif ($b >= $this->[1] && $a < $this->[1]) {	# end after inteval, start within
+				$this->[1] = $b;
+				if ($a < $this->[0]) {						# merge start
+					$this->[0] = $a;
+				}
+				return;
+			}
+		}
+		push @intervals, [$a, $b];							# append to end
+	}
+}
+
+sub merge_intervals {
+	for (my $i = 0; $i+1 < @intervals; $i++) {
+		while ($i+1 < @intervals) {
+			my $this = $intervals[$i];
+			my $next = $intervals[$i+1];
+			if ($this->[1] < $next->[0]) {					# not overlapping
+				last;										# next interval
+			}
+			else {
+				splice(@intervals, $i, 2, [$this->[0], $next->[1]]);	# merge and test again
+			}
+		}
+	}
+}
+
+sub print_intervals {
+	say join(", ", map {"(".$_->[0].",".$_->[1].")"} @intervals);
+}
diff --git a/challenge-092/paulo-custodio/test.pl b/challenge-092/paulo-custodio/test.pl
new file mode 100644
index 0000000000..51e9f3e6e9
--- /dev/null
+++ b/challenge-092/paulo-custodio/test.pl
@@ -0,0 +1,23 @@
+#!/usr/bin/perl
+
+use strict;
+use warnings;
+use Test::More;
+use 5.030;
+
+is capture("perl perl/ch-1.pl abc xyz"), "1\n";
+is capture("perl perl/ch-1.pl abb xyy"), "1\n";
+is capture("perl perl/ch-1.pl sum add"), "0\n";
+
+is capture("perl perl/ch-2.pl 1,4 8,10 2,6"), 		"(1,6), (8,10)\n";
+is capture("perl perl/ch-2.pl 1,2 3,7 8,10 5,8"), 	"(1,2), (3,10)\n";
+is capture("perl perl/ch-2.pl 1,5 7,9 10,11"), 		"(1,5), (7,9), (10,11)\n";
+
+done_testing;
+
+sub capture {
+	my($cmd) = @_;
+	my $out = `$cmd`;
+	$out =~ s/[ \t\v\f\r]*\n/\n/g;
+	return $out;
+}