Merge pull request #1165 from dmanto/branch-for-challenge-044

my proposed solutions for challenge-044, p5 1 & 2

2 files changed, 205 insertions, 0 deletions

diff --git a/challenge-044/daniel-mantovani/perl/ch-1.pl b/challenge-044/daniel-mantovani/perl/ch-1.pl
new file mode 100644
index 0000000000..e38eaac055
--- /dev/null
+++ b/challenge-044/daniel-mantovani/perl/ch-1.pl
@@ -0,0 +1,142 @@
+# Only 100, please.
+# You are given a string “123456789”.
+# Write a script that would insert ”+” or ”-” in between digits
+# so that when you evaluate, the result should be 100.
+
+use strict;
+use warnings;
+use v5.20;
+
+# I would like to try a brute force approach, in the sense
+# that all valid combinations of "+" and "-" or nothing
+# are inserted between digits.
+#
+# so between two consecutive digits, we
+# have just 3 alternatives:
+#
+# - No insertion
+# - a "+" sign
+# - a "-" sign
+#
+# that means 3 alternatives between any consecutive digits.
+# we will define an array of 8 (or l-1 in general, where l is
+# the length of the input string in digits) elements,
+# corresponding to the modification we will introduce between
+# digits 1 and 2, then between digits 2 and 3, ... and finally
+# between digits 8 and 9.
+#
+# the element will be:
+# 0 or non existant (undef), meaning no insertion
+# 1 meaning to insert a "+" sign
+# 2 meaning to insert a "-" sign
+#
+# So if we want to check all combinations, that will be
+# an array of at most 8 elements, with values 0, 1 or 2
+#
+# That array can be represented by a ternary number of up
+# to 9 digits. So to try every combination, we can convert
+# an integer variable to its base 3 representation, so
+# incrementing that integer will generate another case
+#
+
+sub ter {
+  my @m;
+  my $n = shift;
+  while ($n) {
+    push @m, $n % 3;
+    $n = int($n/3);
+  }
+  return @m;
+}
+
+#
+# this function ter() will return an array of digits from 0 to 2
+# from an integer
+#
+# lets analize an example. For the integer 567, we obtain the following
+# array as a result: (0, 0, 0, 0, 1, 2)
+#
+# so the final result, after applying those modifications to the
+# original string would be:
+#
+# 123456789
+# 1
+#        => 0 means join 1 & 2 (12)
+# 2
+#        => 0 means keep joining (123)
+# 3
+#        => 0 means keep joining (1234)
+# 4
+#        => 0 means keep joining (12345)
+# 5
+#        => 1 means insert a "+" sign (12345 + 6)
+# 6
+#        => 2 means insert a "-" sign (12345 + 6 - 7)
+# 7
+#        => undef means keep joining (12345 + 6 - 78)
+# 8
+#        => undef means keep joining (12345 + 6 - 789)
+# 9
+#
+# so the final result is 12345 + 6 - 789 = 11562
+#
+# as it is different to our target result (200), we will need
+# to continue trying
+#
+# we need a function to modify an imput string as a result
+# of applying the integer according to the defined rules
+
+sub modify_string {
+    my ($in, $mod) = @_;
+    my @mods = ter($mod);
+    # if @m vector has more than needed elements, return undef
+    return undef if length($in) < @mods + 1;
+    my $result = '';
+    for my $d (split '', $in) {
+        my $m = (shift @mods) // 0;             # undefs at the end mean empty inter-digit appends
+        $result .= $d . ('', ' + ', ' - ')[$m]; # just peek what to insert according to $m
+    }
+    return $result;
+}
+
+#
+# modify_string returns a string with a mathematical formula that needs to be
+# evaluated.
+#
+# For instance, modify_string(123456789, 567) will return
+# "12345 + 6 - 789"
+#
+#
+# we will get from command line the original string and the target number like this:
+#
+
+my ($input, $target) = @ARGV;
+die "Usage; $0 <input number> <target sum>" unless $input =~ /^\d+$/ && $target =~ /^-?\d+$/;
+say "Found answer(s):";
+my $n = 0;
+while (defined (my $x = modify_string ($input, $n))) {
+  say "$target = $x" if eval $x == $target;
+  $n++;    
+}
+
+#
+# as we are just incrementing a number ($n) that will produce all
+# available combinations, we are confident that we will be able to
+# spot all valid solutions
+#
+# Example usage:
+# $>perl ch-1.pl 123456789 100
+# Found answer(s):
+# 100 = 123 - 45 - 67 + 89
+# 100 = 12 - 3 - 4 + 5 - 6 + 7 + 89
+# 100 = 12 + 3 + 4 + 5 - 6 - 7 + 89
+# 100 = 123 + 4 - 5 + 67 - 89
+# 100 = 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9
+# 100 = 12 + 3 - 4 + 5 + 67 + 8 + 9
+# 100 = 1 + 23 - 4 + 56 + 7 + 8 + 9
+# 100 = 1 + 2 + 34 - 5 + 67 - 8 + 9
+# 100 = 1 + 23 - 4 + 5 + 6 + 78 - 9
+# 100 = 123 + 45 - 67 + 8 - 9
+# 100 = 123 - 4 - 5 - 6 - 7 + 8 - 9
+# $>
+#
diff --git a/challenge-044/daniel-mantovani/perl/ch-2.pl b/challenge-044/daniel-mantovani/perl/ch-2.pl
new file mode 100644
index 0000000000..8d9d2d8249
--- /dev/null
+++ b/challenge-044/daniel-mantovani/perl/ch-2.pl
@@ -0,0 +1,63 @@
+# Make it $200
+# You have only $1 left at the start of the week.
+# You have been given an opportunity to make it $200.
+# The rule is simple with every move you can either
+# double what you have or add another $1.
+# Write a script to help you get $200 with the smallest number of moves.
+
+use strict;
+use warnings;
+use v5.10;
+
+# from the problem, you can conclude that at every intermediate step,
+# you should multiply by 2 when possible, because it will sum up at
+# least same amount that adding $1.
+#
+# what I mean is that, if for example your current total is $25, there
+# is not better steps that multiply by 2 three consecutive times,
+# to get the final $200
+#
+# So if we analize the problem backwards, we can start from the target
+# ($200), then divide by 2 whenever we can, or substract 1 if you cannot.
+# At the end, we shold do the inverse operation on each step, in
+# a reversed order.
+#
+# There should not be shorter sequences that this one
+#
+
+#
+# will be something like this:
+#
+
+my $target = shift @ARGV;
+die "Usage: perl $0 <target>" unless $target =~ /^\d+$/ && $target > 0;
+
+my @steps;
+while ($target > 1) {
+    if ($target % 2) {
+        push @steps, sprintf('Add $1 to $%i (new total $%i)', $target-1, $target);
+        $target--;
+    } else {
+        push @steps, sprintf('Multiply $%i by 2 (new total $%i)', $target / 2, $target);
+        $target /= 2;
+    }
+}
+
+for my $i (1..@steps) {
+    say "Step #$i: ", pop @steps;
+}
+
+#
+# example usage:
+#
+# $> perl ch-2.pl 200
+# Step #1: Multiply $1 by 2 (new total $2)
+# Step #2: Add $1 to $2 (new total $3)
+# Step #3: Multiply $3 by 2 (new total $6)
+# Step #4: Multiply $6 by 2 (new total $12)
+# Step #5: Multiply $12 by 2 (new total $24)
+# Step #6: Add $1 to $24 (new total $25)
+# Step #7: Multiply $25 by 2 (new total $50)
+# Step #8: Multiply $50 by 2 (new total $100)
+# Step #9: Multiply $100 by 2 (new total $200)
+# $>