diff options
| -rw-r--r-- | challenge-044/daniel-mantovani/perl/ch-1.pl | 142 | ||||
| -rw-r--r-- | challenge-044/daniel-mantovani/perl/ch-2.pl | 63 |
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) +# $> |