Merge pull request #10767 from pme/challenge-285

challenge-285

4 files changed, 274 insertions, 0 deletions

diff --git a/challenge-285/peter-meszaros/perl/ch-1.pl b/challenge-285/peter-meszaros/perl/ch-1.pl
new file mode 100755
index 0000000000..3c5a00ebf2
--- /dev/null
+++ b/challenge-285/peter-meszaros/perl/ch-1.pl
@@ -0,0 +1,56 @@
+#!/usr/bin/env perl
+#
+=head1 Task 1: No Connection
+
+Submitted by: Mohammad Sajid Anwar
+
+You are given a list of routes, @routes.
+
+Write a script to find the destination with no further outgoing connection.
+
+=head2 Example 1
+
+    Input: @routes = (["B","C"], ["D","B"], ["C","A"])
+    Output: "A"
+
+    "D" -> "B" -> "C" -> "A".
+    "B" -> "C" -> "A".
+    "C" -> "A".
+    "A".
+
+=head2 Example 2
+
+    Input: @routes = (["A","Z"])
+    Output: "Z"
+
+=cut
+
+use strict;
+use warnings;
+use Test2::V0 -no_srand => 1;
+use Data::Dumper;
+
+my $cases = [
+    [[["B", "C"], ["D","B"], ["C","A"]], "A", 'Example 1'],
+    [[["A", "Z"]                      ], "Z", 'Example 2'],
+];
+
+sub no_connection
+{
+    my $branches = shift;
+
+    my (%s, @e);
+    for my $br (@$branches) {
+        push @e, $br->[0];
+        $s{$br->[1]} = 1;
+    }
+    delete @s{@e};
+    return (keys %s)[0];
+}
+
+for (@$cases) {
+    is(no_connection($_->[0]), $_->[1], $_->[2]);
+}
+done_testing();
+
+exit 0;
diff --git a/challenge-285/peter-meszaros/perl/ch-2.pl b/challenge-285/peter-meszaros/perl/ch-2.pl
new file mode 100755
index 0000000000..e88658dc4e
--- /dev/null
+++ b/challenge-285/peter-meszaros/perl/ch-2.pl
@@ -0,0 +1,85 @@
+#!/usr/bin/env perl
+#
+=head1 Task 2: Making Change
+
+Submitted by: David Ferrone
+
+Compute the number of ways to make change for given amount in cents. By using
+the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many
+distinct ways can the total value equal to the given amount? Order of coin
+selection does not matter.
+
+    A penny (P) is equal to 1 cent.
+    A nickel (N) is equal to 5 cents.
+    A dime (D) is equal to 10 cents.
+    A quarter (Q) is equal to 25 cents.
+    A half-dollar (HD) is equal to 50 cents.
+
+=head2 Example 1
+
+    Input: $amount = 9
+    Ouput: 2
+
+    1: 9P
+    2: N + 4P
+
+=head2 Example 2
+
+    Input: $amount = 15
+    Ouput: 6
+
+    1: D + 5P
+    2: D + N
+    3: 3N
+    4: 2N + 5P
+    5: N + 10P
+    6: 15P
+
+=head2 Example 3
+
+    Input: $amount = 100
+    Ouput: 292
+
+=cut
+
+use strict;
+use warnings;
+use Test2::V0 -no_srand => 1;
+use Data::Dumper;
+
+my $cases = [
+    [  9,   2, 'Example 1'],
+    [ 15,   6, 'Example 2'],
+    [100, 292, 'Example 3'],
+];
+
+# https://tech.tonyballantyne.com/2019/03/04/coin-change-problem/
+#             HD   Q   D  N  P
+my $values = [50, 25, 10, 5, 1];
+
+sub coin
+{
+    my ($n, $val) = @_;
+
+    return 1 if $values->[$val] == 1;
+
+    my $total = 0;
+    while ($n >= $values->[$val]) {
+        $total += coin($n, $val+1);
+        $n -= $values->[$val];
+    }
+    return $total + coin($n, $val+1);
+}
+
+sub making_change
+{
+    my $sum = shift;
+    return coin($sum, 0);
+}
+
+for (@$cases) {
+    is(making_change($_->[0]), $_->[1], $_->[2]);
+}
+done_testing();
+
+exit 0;
diff --git a/challenge-285/peter-meszaros/tcl/ch-1.tcl b/challenge-285/peter-meszaros/tcl/ch-1.tcl
new file mode 100755
index 0000000000..0ed48b993a
--- /dev/null
+++ b/challenge-285/peter-meszaros/tcl/ch-1.tcl
@@ -0,0 +1,50 @@
+#!/usr/bin/env tclsh
+#
+# Task 1: No Connection
+#
+# Submitted by: Mohammad Sajid Anwar
+# 
+# You are given a list of routes, @routes.
+# 
+# Write a script to find the destination with no further outgoing connection.
+# 
+# Example 1
+# 
+#     Input: @routes = (["B","C"], ["D","B"], ["C","A"])
+#     Output: "A"
+# 
+#     "D" -> "B" -> "C" -> "A".
+#     "B" -> "C" -> "A".
+#     "C" -> "A".
+#     "A".
+# 
+# Example 2
+# 
+#     Input: @routes = (["A","Z"])
+#     Output: "Z"
+# 
+
+package require tcltest
+
+set cases {
+    {{{"B" "C"} {"D" "B"} {"C" "A"}} "A" "Example 1"}
+    {{{"A" "Z"}                    } "Z" "Example 2"}
+}
+
+proc no_connection {branches} {
+    foreach br $branches {
+        lappend e [lindex $br 0]
+        dict append s [lindex $br 1] 1
+    }
+    set s [dict remove $s {*}$e]
+    return [dict keys $s]
+}
+
+tcltest::configure -verbose {pass}
+foreach case $cases {
+    tcltest::test [lindex $case 2] {} {
+        no_connection [lindex $case 0]
+    } [lindex $case 1]
+}
+
+exit 0
diff --git a/challenge-285/peter-meszaros/tcl/ch-2.tcl b/challenge-285/peter-meszaros/tcl/ch-2.tcl
new file mode 100755
index 0000000000..16e8fd101b
--- /dev/null
+++ b/challenge-285/peter-meszaros/tcl/ch-2.tcl
@@ -0,0 +1,83 @@
+#!/usr/bin/env tclsh
+#
+# Task 2: Making Change
+# 
+# Submitted by: David Ferrone
+# 
+# Compute the number of ways to make change for given amount in cents. By using
+# the coins e.g. Penny, Nickel, Dime, Quarter and Half-dollar, in how many
+# distinct ways can the total value equal to the given amount? Order of coin
+# selection does not matter.
+# 
+#     A penny (P) is equal to 1 cent.
+#     A nickel (N) is equal to 5 cents.
+#     A dime (D) is equal to 10 cents.
+#     A quarter (Q) is equal to 25 cents.
+#     A half-dollar (HD) is equal to 50 cents.
+# 
+# Example 1
+# 
+#     Input: $amount = 9
+#     Ouput: 2
+# 
+#     1: 9P
+#     2: N + 4P
+# 
+# Example 2
+# 
+#     Input: $amount = 15
+#     Ouput: 6
+# 
+#     1: D + 5P
+#     2: D + N
+#     3: 3N
+#     4: 2N + 5P
+#     5: N + 10P
+#     6: 15P
+# 
+# Example 3
+# 
+#     Input: $amount = 100
+#     Ouput: 292
+# 
+
+package require tcltest
+
+set cases {
+    {  9   2 "Example 1"}
+    { 15   6 "Example 2"}
+    {100 292 "Example 3"}
+}
+
+# https://tech.tonyballantyne.com/2019/03/04/coin-change-problem/
+#             HD   Q   D  N  P
+set values [list 50 25 10 5 1]
+
+proc coin {n val} {
+    global values
+
+    if {[lindex $values $val] == 1} {
+        return 1
+    }
+
+    set total 0
+    while {$n >= [lindex $values $val]} {
+        incr total [coin $n [expr $val + 1]]
+        incr n [expr - [lindex $values $val]]
+    }
+    incr total [coin $n [expr $val + 1]]
+    return $total
+}
+
+proc making_change {sum} {
+    return [coin $sum 0]
+}
+
+tcltest::configure -verbose {pass}
+foreach case $cases {
+    tcltest::test [lindex $case 2] {} {
+        making_change [lindex $case 0]
+    } [lindex $case 1]
+}
+
+exit 0