Merge pull request #4128 from dms061/challenge113

David Schwartz challenge113 submission

4 files changed, 383 insertions, 0 deletions

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
new file mode 100644
index 0000000000..ce2e8babb7
--- /dev/null
+++ b/challenge-113/dms061/perl/ch-1.pl
@@ -0,0 +1,119 @@
+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.
+
+NOTE: I am allowing a number to occur more than once in the summation
+
+=head1 Optimizations
+
+TODO
+
+=head1 Old Code (not used in solution)
+
+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;
+
+=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) = @_;
+	# 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;
+}
+
+=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
new file mode 100644
index 0000000000..55af3aab4b
--- /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 1, new (2, new (4, , new(7))), new (3, new (5), new (6));
+#$test->{"left"} = new 2;
+#$test->{"right"} = new 3;
+
+print "(Preorder) Original:\n";
+print_tree $test;
+my $sum = 0;
+preorder {$sum += $_; $_;} $test;
+preorder {$sum - $_} $test;
+print "(Preorder) 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);
+