Merge pull request #4521 from pauloscustodio/paulo-custodio

Add Perl solution to challenge 121

5 files changed, 122 insertions, 0 deletions

diff --git a/challenge-121/paulo-custodio/perl/ch-1.pl b/challenge-121/paulo-custodio/perl/ch-1.pl
new file mode 100644
index 0000000000..c4e113d08d
--- /dev/null
+++ b/challenge-121/paulo-custodio/perl/ch-1.pl
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl
+
+# Challenge 121
+#
+# TASK #1 › Invert Bit
+# Submitted by: Mohammad S Anwar
+# You are given integers 0 <= $m <= 255 and 1 <= $n <= 8.
+#
+# Write a script to invert $n bit from the end of the binary representation of
+# $m and print the decimal representation of the new binary number.
+#
+# Example
+# Input: $m = 12, $n = 3
+# Output: 8
+#
+# Binary representation of $m = 00001100
+# Invert 3rd bit from the end = 00001000
+# Decimal equivalent of 00001000 = 8
+#
+# Input $m = 18, $n = 4
+# Output: 26
+#
+# Binary representation of $m = 00010010
+# Invert 4th bit from the end = 00011010
+# Decimal equivalent of 00011010 = 26
+
+use Modern::Perl;
+my($m,$n) = @ARGV;
+say $m ^ (1 << ($n-1));
diff --git a/challenge-121/paulo-custodio/perl/ch-2.pl b/challenge-121/paulo-custodio/perl/ch-2.pl
new file mode 100644
index 0000000000..4a45cb60ee
--- /dev/null
+++ b/challenge-121/paulo-custodio/perl/ch-2.pl
@@ -0,0 +1,68 @@
+#!/usr/bin/env perl
+
+# Challenge 121
+#
+# TASK #2 › The Travelling Salesman
+# Submitted by: Jorg Sommrey
+# You are given a NxN matrix containing the distances between N cities.
+#
+# Write a script to find a round trip of minimum length visiting all N cities
+# exactly once and returning to the start.
+#
+# Example
+# Matrix: [0, 5, 2, 7]
+#         [5, 0, 5, 3]
+#         [3, 1, 0, 6]
+#         [4, 5, 4, 0]
+#
+# Output:
+#         length = 10
+#         tour = (0 2 1 3 0)
+
+use Modern::Perl;
+my @dist = read_dist();
+my($length, @path) = shortest_tour(\@dist);
+say "length = $length";
+say "tour = (@path)";
+
+sub read_dist {
+    my @dist;
+    while (<>) {
+        my @row = split(' ', $_);
+        push @dist, \@row;
+    }
+    return @dist;
+}
+
+sub shortest_tour {
+    my($dist) = @_;
+    my @shortest = (100000);    # first solution
+    tour($dist, \@shortest, 0, 0);
+    return @shortest;
+}
+
+sub tour {
+    my($dist, $shortest, $length, @path) = @_;
+    my %cities;
+    for (0..$#$dist) { $cities{$_}=1; }
+    for (@path) { delete $cities{$_}; }
+    my @pending_cities = sort {$a<=>$b} keys %cities;
+
+    # no more cities to visit?
+    if (@pending_cities == 0) {     # found solution
+        $length += $dist->[$path[-1]][$path[0]];
+        push @path, $path[0];
+        if ($length < $shortest->[0]) {
+            @$shortest = ($length, @path);
+        }
+    }
+    else { # try each city
+        for my $city (@pending_cities) {
+            tour($dist, $shortest,
+                 $length+$dist->[$path[-1]][$city],
+                 @path, $city);
+        }
+    }
+}
+
+
diff --git a/challenge-121/paulo-custodio/t/test-1.yaml b/challenge-121/paulo-custodio/t/test-1.yaml
new file mode 100644
index 0000000000..94728d5b05
--- /dev/null
+++ b/challenge-121/paulo-custodio/t/test-1.yaml
@@ -0,0 +1,10 @@
+- setup:
+  cleanup:
+  args:     12 3
+  input:
+  output:   8
+- setup:
+  cleanup:
+  args:     18 4
+  input:
+  output:   26
diff --git a/challenge-121/paulo-custodio/t/test-2.yaml b/challenge-121/paulo-custodio/t/test-2.yaml
new file mode 100644
index 0000000000..e2475fd224
--- /dev/null
+++ b/challenge-121/paulo-custodio/t/test-2.yaml
@@ -0,0 +1,11 @@
+- setup:
+  cleanup:
+  args:
+  input:    |
+            |0 5 2 7
+            |5 0 5 3
+            |3 1 0 6
+            |4 5 4 0
+  output:   |
+            |length = 10
+            |tour = (0 2 1 3 0)
diff --git a/challenge-121/paulo-custodio/test.pl b/challenge-121/paulo-custodio/test.pl
new file mode 100644
index 0000000000..ba6c37260b
--- /dev/null
+++ b/challenge-121/paulo-custodio/test.pl
@@ -0,0 +1,4 @@
+#!/usr/bin/env perl
+use Modern::Perl;
+use Test::More;
+require '../../challenge-001/paulo-custodio/test.pl';