From f7c2a86860fd2837b37965e3560f90c520975a1d Mon Sep 17 00:00:00 2001 From: David Schwartz Date: Sun, 23 May 2021 01:25:33 -0400 Subject: Added solutions for challenge 113, they can be improved though --- challenge-113/dms061/perl/ch-1.pl | 95 +++++++++++++++++++++++++++++++++++++++ challenge-113/dms061/perl/ch-2.pl | 94 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 189 insertions(+) create mode 100644 challenge-113/dms061/perl/ch-1.pl create mode 100644 challenge-113/dms061/perl/ch-2.pl diff --git a/challenge-113/dms061/perl/ch-1.pl b/challenge-113/dms061/perl/ch-1.pl new file mode 100644 index 0000000000..bbd861a700 --- /dev/null +++ b/challenge-113/dms061/perl/ch-1.pl @@ -0,0 +1,95 @@ +use strict; +use warnings; + +=pod + +=head1 Question 1 + +You are given a positive integer $N and a digit $D. + +Write a script to check if $N can be represented as a sum of positive integers +having $D at least once. If check passes print 1 otherwise 0. + +=head1 Question about question +Can the numbers repeat? E.g., if $D is 1, is 1 + 1 + ... + 1 = $N a valid answer? +It will make the problem more difficult, but I think yes... + +=head1 Method + +1) Create a list of (positive) integers with $D digit present that are < $N +2) Generate the power set of those digits +3) Sum the sets +4) Print all sets when the sum = $N + +=head1 Optimizations + +TODO + +=head1 links + +https://origin.geeksforgeeks.org/check-if-n-can-be-represented-as-sum-of-positive-integers-containing-digit-d-at-least-once/ + +=cut + +sub push2each{ + my ($val, @arr) = @_; + # Creates a copy by turning the refernce into a value array + # Pushes the new value and then returns a reference to it + return map {my @cp = @{$_}; push @cp, $val; \@cp;} @arr; +} + +sub print_nested{ + print "("; + print "[@{$_}] " foreach @_; + print ")\n"; +} + +sub power_set{ + return ([]) if @_ == 0; # base case, no elements, set with empty set + my ($head, @rest) = @_; + # for some reason the following line needed parens around it. Errors otherwise. + my @pset = power_set (@rest); #add remaining sets without $head + push @pset, push2each ($head, @pset); #add remaining sets with head + return @pset; +} + +#my @a = ([1, 2], [3, 4]); +#my @b = push2each 9, @a; +#print_nested @a; +#print "B->@b\n"; +#print_nested @b; +#my @a = (7, 8, 9); +#my @pa = power_set (@a); +#print_nested @pa; + +=pod + +brute function is ugly but effective. It generates summations using the values provided +until $sum = $n or $sum > $n + + +=cut + +sub brute { + my ($sum, $n, @vals) = @_; + print "In func, sum: $sum\n"; + # Base cases: + return 1 if $sum == $n; + return 0 if $sum > $n; + for (@vals){ + return 1 if brute ($sum + $_, $n, @vals); + } + return 0; +} + +# Get $n and $d. TODO add param checks on ARGV +my ($n, $d) = @ARGV; +print "$d\n"; +# collect all numbers with $d in them +my @nums = grep /\d*$d\d*/, 1..($n-1); +# print "All numbers with digit $d that are < $n:\n@nums\n"; +my $repr = brute 0, $n, @nums; +print "Output: $repr\n"; +#my @pset = power_set (@nums); +#print_nested @pset; + diff --git a/challenge-113/dms061/perl/ch-2.pl b/challenge-113/dms061/perl/ch-2.pl new file mode 100644 index 0000000000..fd80a64992 --- /dev/null +++ b/challenge-113/dms061/perl/ch-2.pl @@ -0,0 +1,94 @@ +=pod + +=head1 Question 2 + +You are given a Binary Tree. + +Write a script to replace each node of the tree with the sum of all the remaining nodes. + +Example +Input Binary Tree + + 1 + / \ + 2 3 + / / \ + 4 5 6 + \ + 7 + +Output Binary Tree + + 27 + / \ + 26 25 + / / \ + 24 23 22 + \ + 21 + +NOTE: the example output has the new values as the total_sum - node_value, so remaining nodes in the +question does not mean nodes in the subtrees, it means all the other nodes in the tree + +=head1 Approach + +Do a preorder iteration, summing values to get the sum +Then do another preorder iteration, and update values (sum - node val) -> done! + +Issue: how should we encode the tree? +(val, ref_branch1, ref_branch2)? +or should we try working with objects in perl? +Going to use references to hashes to build a quick tree out of references (and make it look like an object XD) + +=cut + +use strict; +use warnings; + +#sub preorder (&@); + +sub new { + my ($val, $lref, $rref) = @_; + my $node = {val => $val, left => $lref, right => $rref}; + return $node; +} + +sub preorder (&@) { + my ($expr, $node) = @_; + $_ = $node->{"val"}; + $node->{"val"} = &$expr; + # the & forces it to run without the prototype + # important because we switch from asking for an anon-block + # to a code ref (which encapsulates that block) + &preorder ($expr, $node->{"left"}) if $node->{"left"}; + &preorder ($expr, $node->{"right"}) if $node->{"right"}; +} + +sub print_tree { + my $node = shift; + preorder {print "Val: $_\n"; $_;} $node; +} + +my $test = new 10; +$test->{"left"} = new 20; +$test->{"right"} = new 30; + +print "Original:\n"; +print_tree $test; +my $sum = 0; +preorder {$sum += $_; $_;} $test; +preorder {$sum - $_} $test; +print "Modified:\n"; +print_tree $test; + +#preorder &print, $test; +# experiment with function prototypes to make something similar to map for trees :) +#sub call_ref (&@) { +# my ($f, $x) = @_; +# $_ = $x; +# print "test?\n"; +# return $f->($x); +#} + +#print (call_ref {print "$_\n"; $_;} 10); + -- cgit From b9522164f3a9255ee230ebe52a99c019826320b0 Mon Sep 17 00:00:00 2001 From: David Schwartz Date: Sun, 23 May 2021 17:17:21 -0400 Subject: Changed output formatting and added example output files --- challenge-113/dms061/perl/ch-1-example.txt | 153 +++++++++++++++++++++++++++++ challenge-113/dms061/perl/ch-1.pl | 80 +++++++++------ challenge-113/dms061/perl/ch-2-example.txt | 17 ++++ challenge-113/dms061/perl/ch-2.pl | 10 +- 4 files changed, 227 insertions(+), 33 deletions(-) create mode 100644 challenge-113/dms061/perl/ch-1-example.txt create mode 100644 challenge-113/dms061/perl/ch-2-example.txt diff --git a/challenge-113/dms061/perl/ch-1-example.txt b/challenge-113/dms061/perl/ch-1-example.txt new file mode 100644 index 0000000000..4eb6ad52f9 --- /dev/null +++ b/challenge-113/dms061/perl/ch-1-example.txt @@ -0,0 +1,153 @@ +dms@Zixzax:~/perlweeklychallenge-club/challenge-113/dms061/perl$ perl ch-1.pl 25 7 +Numbers: 7 17 +Output: 0 + +dms@Zixzax:~/perlweeklychallenge-club/challenge-113/dms061/perl$ perl ch-1.pl 24 7 +Numbers: 7 17 +Output: 1 + +dms@Zixzax:~/perlweeklychallenge-club/challenge-113/dms061/perl$ perl ch-1.pl +Input: n = 10, d = 1 --> Output: 1 +Input: n = 10, d = 2 --> Output: 1 +Input: n = 10, d = 3 --> Output: 0 +Input: n = 10, d = 4 --> Output: 0 +Input: n = 10, d = 5 --> Output: 1 +Input: n = 10, d = 6 --> Output: 0 +Input: n = 10, d = 7 --> Output: 0 +Input: n = 10, d = 8 --> Output: 0 +Input: n = 10, d = 9 --> Output: 0 +Input: n = 11, d = 1 --> Output: 1 +Input: n = 11, d = 2 --> Output: 0 +Input: n = 11, d = 3 --> Output: 0 +Input: n = 11, d = 4 --> Output: 0 +Input: n = 11, d = 5 --> Output: 0 +Input: n = 11, d = 6 --> Output: 0 +Input: n = 11, d = 7 --> Output: 0 +Input: n = 11, d = 8 --> Output: 0 +Input: n = 11, d = 9 --> Output: 0 +Input: n = 12, d = 1 --> Output: 1 +Input: n = 12, d = 2 --> Output: 1 +Input: n = 12, d = 3 --> Output: 1 +Input: n = 12, d = 4 --> Output: 1 +Input: n = 12, d = 5 --> Output: 0 +Input: n = 12, d = 6 --> Output: 1 +Input: n = 12, d = 7 --> Output: 0 +Input: n = 12, d = 8 --> Output: 0 +Input: n = 12, d = 9 --> Output: 0 +Input: n = 13, d = 1 --> Output: 1 +Input: n = 13, d = 2 --> Output: 0 +Input: n = 13, d = 3 --> Output: 0 +Input: n = 13, d = 4 --> Output: 0 +Input: n = 13, d = 5 --> Output: 0 +Input: n = 13, d = 6 --> Output: 0 +Input: n = 13, d = 7 --> Output: 0 +Input: n = 13, d = 8 --> Output: 0 +Input: n = 13, d = 9 --> Output: 0 +Input: n = 14, d = 1 --> Output: 1 +Input: n = 14, d = 2 --> Output: 1 +Input: n = 14, d = 3 --> Output: 0 +Input: n = 14, d = 4 --> Output: 0 +Input: n = 14, d = 5 --> Output: 0 +Input: n = 14, d = 6 --> Output: 0 +Input: n = 14, d = 7 --> Output: 1 +Input: n = 14, d = 8 --> Output: 0 +Input: n = 14, d = 9 --> Output: 0 +Input: n = 15, d = 1 --> Output: 1 +Input: n = 15, d = 2 --> Output: 0 +Input: n = 15, d = 3 --> Output: 1 +Input: n = 15, d = 4 --> Output: 0 +Input: n = 15, d = 5 --> Output: 1 +Input: n = 15, d = 6 --> Output: 0 +Input: n = 15, d = 7 --> Output: 0 +Input: n = 15, d = 8 --> Output: 0 +Input: n = 15, d = 9 --> Output: 0 +Input: n = 16, d = 1 --> Output: 1 +Input: n = 16, d = 2 --> Output: 1 +Input: n = 16, d = 3 --> Output: 1 +Input: n = 16, d = 4 --> Output: 1 +Input: n = 16, d = 5 --> Output: 0 +Input: n = 16, d = 6 --> Output: 0 +Input: n = 16, d = 7 --> Output: 0 +Input: n = 16, d = 8 --> Output: 1 +Input: n = 16, d = 9 --> Output: 0 +Input: n = 17, d = 1 --> Output: 1 +Input: n = 17, d = 2 --> Output: 0 +Input: n = 17, d = 3 --> Output: 0 +Input: n = 17, d = 4 --> Output: 0 +Input: n = 17, d = 5 --> Output: 0 +Input: n = 17, d = 6 --> Output: 0 +Input: n = 17, d = 7 --> Output: 0 +Input: n = 17, d = 8 --> Output: 0 +Input: n = 17, d = 9 --> Output: 0 +Input: n = 18, d = 1 --> Output: 1 +Input: n = 18, d = 2 --> Output: 1 +Input: n = 18, d = 3 --> Output: 1 +Input: n = 18, d = 4 --> Output: 1 +Input: n = 18, d = 5 --> Output: 0 +Input: n = 18, d = 6 --> Output: 1 +Input: n = 18, d = 7 --> Output: 0 +Input: n = 18, d = 8 --> Output: 0 +Input: n = 18, d = 9 --> Output: 1 +Input: n = 19, d = 1 --> Output: 1 +Input: n = 19, d = 2 --> Output: 0 +Input: n = 19, d = 3 --> Output: 1 +Input: n = 19, d = 4 --> Output: 0 +Input: n = 19, d = 5 --> Output: 0 +Input: n = 19, d = 6 --> Output: 0 +Input: n = 19, d = 7 --> Output: 0 +Input: n = 19, d = 8 --> Output: 0 +Input: n = 19, d = 9 --> Output: 0 +Input: n = 20, d = 1 --> Output: 1 +Input: n = 20, d = 2 --> Output: 1 +Input: n = 20, d = 3 --> Output: 0 +Input: n = 20, d = 4 --> Output: 1 +Input: n = 20, d = 5 --> Output: 1 +Input: n = 20, d = 6 --> Output: 0 +Input: n = 20, d = 7 --> Output: 0 +Input: n = 20, d = 8 --> Output: 0 +Input: n = 20, d = 9 --> Output: 0 +Input: n = 21, d = 1 --> Output: 1 +Input: n = 21, d = 2 --> Output: 0 +Input: n = 21, d = 3 --> Output: 1 +Input: n = 21, d = 4 --> Output: 0 +Input: n = 21, d = 5 --> Output: 0 +Input: n = 21, d = 6 --> Output: 0 +Input: n = 21, d = 7 --> Output: 1 +Input: n = 21, d = 8 --> Output: 0 +Input: n = 21, d = 9 --> Output: 0 +Input: n = 22, d = 1 --> Output: 1 +Input: n = 22, d = 2 --> Output: 1 +Input: n = 22, d = 3 --> Output: 1 +Input: n = 22, d = 4 --> Output: 1 +Input: n = 22, d = 5 --> Output: 0 +Input: n = 22, d = 6 --> Output: 1 +Input: n = 22, d = 7 --> Output: 0 +Input: n = 22, d = 8 --> Output: 0 +Input: n = 22, d = 9 --> Output: 0 +Input: n = 23, d = 1 --> Output: 1 +Input: n = 23, d = 2 --> Output: 1 +Input: n = 23, d = 3 --> Output: 0 +Input: n = 23, d = 4 --> Output: 0 +Input: n = 23, d = 5 --> Output: 0 +Input: n = 23, d = 6 --> Output: 0 +Input: n = 23, d = 7 --> Output: 0 +Input: n = 23, d = 8 --> Output: 0 +Input: n = 23, d = 9 --> Output: 0 +Input: n = 24, d = 1 --> Output: 1 +Input: n = 24, d = 2 --> Output: 1 +Input: n = 24, d = 3 --> Output: 1 +Input: n = 24, d = 4 --> Output: 1 +Input: n = 24, d = 5 --> Output: 0 +Input: n = 24, d = 6 --> Output: 1 +Input: n = 24, d = 7 --> Output: 1 +Input: n = 24, d = 8 --> Output: 1 +Input: n = 24, d = 9 --> Output: 0 +Input: n = 25, d = 1 --> Output: 1 +Input: n = 25, d = 2 --> Output: 1 +Input: n = 25, d = 3 --> Output: 1 +Input: n = 25, d = 4 --> Output: 0 +Input: n = 25, d = 5 --> Output: 1 +Input: n = 25, d = 6 --> Output: 0 +Input: n = 25, d = 7 --> Output: 0 +Input: n = 25, d = 8 --> Output: 0 +Input: n = 25, d = 9 --> Output: 0 diff --git a/challenge-113/dms061/perl/ch-1.pl b/challenge-113/dms061/perl/ch-1.pl index bbd861a700..ce2e8babb7 100644 --- a/challenge-113/dms061/perl/ch-1.pl +++ b/challenge-113/dms061/perl/ch-1.pl @@ -10,26 +10,13 @@ You are given a positive integer $N and a digit $D. Write a script to check if $N can be represented as a sum of positive integers having $D at least once. If check passes print 1 otherwise 0. -=head1 Question about question -Can the numbers repeat? E.g., if $D is 1, is 1 + 1 + ... + 1 = $N a valid answer? -It will make the problem more difficult, but I think yes... - -=head1 Method - -1) Create a list of (positive) integers with $D digit present that are < $N -2) Generate the power set of those digits -3) Sum the sets -4) Print all sets when the sum = $N +NOTE: I am allowing a number to occur more than once in the summation =head1 Optimizations TODO -=head1 links - -https://origin.geeksforgeeks.org/check-if-n-can-be-represented-as-sum-of-positive-integers-containing-digit-d-at-least-once/ - -=cut +=head1 Old Code (not used in solution) sub push2each{ my ($val, @arr) = @_; @@ -62,34 +49,71 @@ sub power_set{ #my @pa = power_set (@a); #print_nested @pa; -=pod +=head1 brute force brute function is ugly but effective. It generates summations using the values provided until $sum = $n or $sum > $n - =cut sub brute { my ($sum, $n, @vals) = @_; - print "In func, sum: $sum\n"; # Base cases: return 1 if $sum == $n; return 0 if $sum > $n; + # Try to add a number and see what happens for (@vals){ return 1 if brute ($sum + $_, $n, @vals); } return 0; } -# Get $n and $d. TODO add param checks on ARGV -my ($n, $d) = @ARGV; -print "$d\n"; -# collect all numbers with $d in them -my @nums = grep /\d*$d\d*/, 1..($n-1); -# print "All numbers with digit $d that are < $n:\n@nums\n"; -my $repr = brute 0, $n, @nums; -print "Output: $repr\n"; -#my @pset = power_set (@nums); -#print_nested @pset; +=pod +=head1 Optimization attempt... + +doesn't work for all cases... :< +specifically n = 28, d = 3 + +sub check { + my ($n, @nums) = @_; + my $rem = 0; + for my $i (0 .. $#nums){ + # check if $n is a multiple of $num[$i] + $rem = $n % $nums[$i]; + return 1 unless $rem; + # check if a some multiple of other @nums could be added to make $n + for (reverse(0 .. $i - 1)){ + $rem %= $nums[$_]; + return 1 unless $rem; + } + } + return 0; +} + +=cut + +# Get $n and $d. TODO add param checks on ARGV +if (@ARGV == 2){ + # run a specific input supplied in ARGV + my ($n, $d) = @ARGV; + # collect all numbers with $d in them + my @nums = grep /\d*$d\d*/, 1..($n-1); + print "Numbers: @nums\n"; + # print "All numbers with digit $d that are < $n:\n@nums\n"; + my $repr = brute 0, $n, @nums; + #my $repr2 = check $n, @nums; + print "Output: $repr\n"; +}else{ + # not enough input args (or too many), go into test mode + for my $n (10 .. 25){ + for my $d (1 .. 9){ + my @nums = grep /\d*$d\d*/, 1..($n-1); + my $b = brute 0, $n, @nums; + print "Input: n = $n, d = $d --> Output: $b\n"; + #my $c = check $n, @nums; + #print "$b ?= $c"; + #print "($b != $c) Failed n = $n, d = $d\n" unless $b == $c; + } + } +} diff --git a/challenge-113/dms061/perl/ch-2-example.txt b/challenge-113/dms061/perl/ch-2-example.txt new file mode 100644 index 0000000000..46fd02205e --- /dev/null +++ b/challenge-113/dms061/perl/ch-2-example.txt @@ -0,0 +1,17 @@ +dms@Zixzax:~/perlweeklychallenge-club/challenge-113/dms061/perl$ perl ch-2.pl +(Preorder) Original: +Val: 1 +Val: 2 +Val: 4 +Val: 7 +Val: 3 +Val: 5 +Val: 6 +(Preorder) Modified: +Val: 27 +Val: 26 +Val: 24 +Val: 21 +Val: 25 +Val: 23 +Val: 22 diff --git a/challenge-113/dms061/perl/ch-2.pl b/challenge-113/dms061/perl/ch-2.pl index fd80a64992..55af3aab4b 100644 --- a/challenge-113/dms061/perl/ch-2.pl +++ b/challenge-113/dms061/perl/ch-2.pl @@ -69,16 +69,16 @@ sub print_tree { preorder {print "Val: $_\n"; $_;} $node; } -my $test = new 10; -$test->{"left"} = new 20; -$test->{"right"} = new 30; +my $test = new 1, new (2, new (4, , new(7))), new (3, new (5), new (6)); +#$test->{"left"} = new 2; +#$test->{"right"} = new 3; -print "Original:\n"; +print "(Preorder) Original:\n"; print_tree $test; my $sum = 0; preorder {$sum += $_; $_;} $test; preorder {$sum - $_} $test; -print "Modified:\n"; +print "(Preorder) Modified:\n"; print_tree $test; #preorder &print, $test; -- cgit