Challenge 112 done

5 files changed, 271 insertions, 6 deletions

diff --git a/challenge-112/dms061/perl/ch-1-example.txt b/challenge-112/dms061/perl/ch-1-example.txt
new file mode 100644
index 0000000000..fef08e952b
--- /dev/null
+++ b/challenge-112/dms061/perl/ch-1-example.txt
@@ -0,0 +1,3 @@
+> perl ch-1.pl
+Path to parse: /elephant/dog/cat/../phoenix/../mouse/
+Canonical path: /elephant/dog/mouse
diff --git a/challenge-112/dms061/perl/ch-1.pl b/challenge-112/dms061/perl/ch-1.pl
index 6a49f555d5..856d208d40 100644
--- a/challenge-112/dms061/perl/ch-1.pl
+++ b/challenge-112/dms061/perl/ch-1.pl
@@ -13,7 +13,7 @@ use warnings;
 # - The path does not end with a trailing '/'.
 #- The path only contains the directories on the path from the root directory to the target file or directory
 
-my $path = "test/dog/cat/../phoenix/../t/"; #"/a/b//c/../..";
+my $path = "/elephant/dog/cat/../phoenix/../mouse/"; #"/a/b//c/../..";
 my @stack = ();
 # Build the canonical path by extracting directory names and storing them on a stack 
 # unless we encounter a .., in which case we pop an element off the stack
@@ -31,5 +31,6 @@ foreach ($path =~ m{/([^/]+)}g){
 		push @stack, "$_";
 	}
 }
+print "Path to parse: $path\n";
 my $canon_path = "/".join "/", @stack;
-print "$canon_path\n";
+print "Canonical path: $canon_path\n";
diff --git a/challenge-112/dms061/perl/ch-2-example.pl b/challenge-112/dms061/perl/ch-2-example.pl
new file mode 100644
index 0000000000..61f73e3585
--- /dev/null
+++ b/challenge-112/dms061/perl/ch-2-example.pl
@@ -0,0 +1,117 @@
+> perl ch-2.pl
+
+n = 1 => 1 ways:
+        [1]
+n = 2 => 2 ways:
+        [1 1]
+        [2]
+n = 3 => 3 ways:
+        [1 1]
+        [1 1 2]
+        [2 2]
+n = 4 => 3 ways:
+        [1 1 1]
+        [2 1]
+        [1 2]
+n = 5 => 5 ways:
+        [1 1 1]
+        [1 1 2 1]
+        [2 2 1]
+        [1 1 2]
+        [2 2]
+Switching to count only method, omitting the sequences...
+n = 6 => 13 ways
+n = 7 => 21 ways
+n = 8 => 34 ways
+n = 9 => 55 ways
+n = 10 => 89 ways
+n = 11 => 144 ways
+n = 12 => 233 ways
+n = 13 => 377 ways
+n = 14 => 610 ways
+n = 15 => 987 ways
+n = 16 => 1597 ways
+n = 17 => 2584 ways
+n = 18 => 4181 ways
+n = 19 => 6765 ways
+n = 20 => 10946 ways
+n = 21 => 17711 ways
+n = 22 => 28657 ways
+n = 23 => 46368 ways
+n = 24 => 75025 ways
+n = 25 => 121393 ways
+n = 26 => 196418 ways
+n = 27 => 317811 ways
+n = 28 => 514229 ways
+n = 29 => 832040 ways
+n = 30 => 1346269 ways
+n = 31 => 2178309 ways
+n = 32 => 3524578 ways
+n = 33 => 5702887 ways
+n = 34 => 9227465 ways
+n = 35 => 14930352 ways
+n = 36 => 24157817 ways
+n = 37 => 39088169 ways
+n = 38 => 63245986 ways
+n = 39 => 102334155 ways
+n = 40 => 165580141 ways
+n = 41 => 267914296 ways
+n = 42 => 433494437 ways
+n = 43 => 701408733 ways
+n = 44 => 1134903170 ways
+n = 45 => 1836311903 ways
+n = 46 => 2971215073 ways
+n = 47 => 4807526976 ways
+n = 48 => 7778742049 ways
+n = 49 => 12586269025 ways
+n = 50 => 20365011074 ways
+n = 51 => 32951280099 ways
+n = 52 => 53316291173 ways
+n = 53 => 86267571272 ways
+n = 54 => 139583862445 ways
+n = 55 => 225851433717 ways
+n = 56 => 365435296162 ways
+n = 57 => 591286729879 ways
+n = 58 => 956722026041 ways
+n = 59 => 1548008755920 ways
+n = 60 => 2504730781961 ways
+n = 61 => 4052739537881 ways
+n = 62 => 6557470319842 ways
+n = 63 => 10610209857723 ways
+n = 64 => 17167680177565 ways
+n = 65 => 27777890035288 ways
+n = 66 => 44945570212853 ways
+n = 67 => 72723460248141 ways
+n = 68 => 117669030460994 ways
+n = 69 => 190392490709135 ways
+n = 70 => 308061521170129 ways
+n = 71 => 498454011879264 ways
+n = 72 => 806515533049393 ways
+n = 73 => 1304969544928657 ways
+n = 74 => 2111485077978050 ways
+n = 75 => 3416454622906707 ways
+n = 76 => 5527939700884757 ways
+n = 77 => 8944394323791464 ways
+n = 78 => 14472334024676221 ways
+n = 79 => 23416728348467685 ways
+n = 80 => 37889062373143906 ways
+n = 81 => 61305790721611591 ways
+n = 82 => 99194853094755497 ways
+n = 83 => 160500643816367088 ways
+n = 84 => 259695496911122585 ways
+n = 85 => 420196140727489673 ways
+n = 86 => 679891637638612258 ways
+n = 87 => 1100087778366101931 ways
+n = 88 => 1779979416004714189 ways
+n = 89 => 2880067194370816120 ways
+n = 90 => 4660046610375530309 ways
+n = 91 => 7540113804746346429 ways
+n = 92 => 12200160415121876738 ways
+n = 93 => 1.97402742198682e+19 ways
+n = 94 => 3.19404346349901e+19 ways
+n = 95 => 5.16807088548583e+19 ways
+n = 96 => 8.36211434898484e+19 ways
+n = 97 => 1.35301852344707e+20 ways
+n = 98 => 2.18922995834555e+20 ways
+n = 99 => 3.54224848179262e+20 ways
+n = 100 => 5.73147844013817e+20 ways
diff --git a/challenge-112/dms061/perl/ch-2.pl b/challenge-112/dms061/perl/ch-2.pl
index 38096f2e23..4521fb4489 100644
--- a/challenge-112/dms061/perl/ch-2.pl
+++ b/challenge-112/dms061/perl/ch-2.pl
@@ -45,7 +45,7 @@ sub fib {
 my @fib = (0, 1);
 sub fib_memo {
 	my $n = shift;
-	$calls++;
+	#$calls++;
 	if ($n > $#fib){
 		# oddity of perl, this works!
 		# normally, we would have to store new calculated value in a temporary
@@ -99,9 +99,79 @@ sub climb {
 #print "$test[3]\n";
 #print "$test[10]\n";
 
+# helper function
+#sub push_to_copy{
+#	my $elt, @arr = @_;
+#	
+#}
+
+# Okay so now I have to work on outputing the path like in the sample
+# Based on the counting solution, I know f(n) = f(n-1) + f(n-2)
+# So we just need to take the last step
+# Add a 1 to end of f(n-1) paths
+# Add a 2 to end of f(n-2) paths
+# Going to try to memoize this
+
+# Pushes a value on each array stored within the reference based in
+sub push2each{
+        my ($val, @arefs) = @_;
+        my @arrs;
+        foreach (@arefs){
+		# Make a copy by creating a new array based on the value of the reference
+                my @cp = @{$_};
+                push @cp, $val;
+		# push a reference!
+                push @arrs, \@cp;
+        }
+        return @arrs;
+}
+
+# Contains the paths for climb n-1 stairs
+# Used for memoizing
+my @paths = (
+        [[1]],
+        [[1,1], [2]]
+);
+
+# Memoized climb subroutine
+# NOTE: This takes a ton of memory
+# TODO: Look into alternate ways to represent the sequence of steps
+# 	e.g., store the indices where the number of steps change?
+sub climb_paths{
+        my $n = shift;
+	--$n; #index is offset! n = 1 path stored at index 0
+        if($n > $#paths){
+                my @new_paths = push2each(1, @{climb_paths($n-1)});
+                push @new_paths, push2each(2, @{climb_paths($n-2)});
+                $paths[$n] = \@new_paths;
+        }
+        return $paths[$n];
+}
+
+# Print's all of the arrays stored in a refence passed in
+sub print_paths{
+	my $pref = shift;
+	foreach my $aref (@{$pref}){
+		print "\t[@{$aref}]\n";
+	}
+}
+
+# Calculate and print the paths to climb n stairs
+# Do this up to $n = 5 because the output becomes too long 
+# and the method chews up a lot of memory
 my $count = 0;
-for (1 .. 100){
+for (1 .. 5){
+	my $ref = climb_paths $_;
+	$count = @{$ref};
+	print "n = $_ => $count ways:\n";
+	print_paths $ref;
+}
+
+# Switch to the method that counts the number of ways (without determine
+# the sequence of steps to compute faster and with less memory)
+print "Switching to count only method, omitting the sequences...\n";
+for (6 .. 100){
 	$count = climb $_;
-	print "climb($_) = $count with $calls funcalls\n";
-	$calls = 0;
+	print "n = $_ => $count ways\n" # with $calls funcalls\n";
+	#$calls = 0;
 }
diff --git a/challenge-112/dms061/perl/test.pl b/challenge-112/dms061/perl/test.pl
new file mode 100644
index 0000000000..53d51c2ab0
--- /dev/null
+++ b/challenge-112/dms061/perl/test.pl
@@ -0,0 +1,74 @@
+use strict;
+use warnings;
+
+#my $aref = [1, 2, 3];
+#my @arr = @{$aref};
+
+#push @{$aref}, 9;
+#push @arr, 10;
+
+#print "@{$aref}\n";
+#print "@arr\n";
+
+sub push2each{
+	my ($val, @arefs) = @_;
+	my @arrs;
+	foreach (@arefs){
+		my @cp = @{$_};
+		push @cp, $val;
+		push @arrs, \@cp;
+	}
+	return @arrs;
+}
+
+my @paths = (
+	[[1]],
+	[[1,1], [2]]
+);
+
+#my $aref = $paths[0];
+#my $aref2 = $paths[1];
+
+my @new_paths;
+
+#foreach my $ref (@{$aref}){
+#	my @arr = @{$ref};
+#	push @arr, 2;
+#	push @new_paths, \@arr;	
+#}
+sub climb{
+	my $n = shift;
+	if($n > $#paths){
+		my @new_paths = push2each(2, @{climb($n-2)});
+		push @new_paths, push2each(1, @{climb($n-1)});
+		$paths[$n] = \@new_paths;
+	}
+	return $paths[$n];
+}
+#push @new_paths, push2each (2, @{$paths[$#paths-1]});
+#push @new_paths, push2each (1, @{$paths[$#paths]});
+#push(@new_paths, push2each @{$aref2}, 1);
+#foreach my $ref (@{$aref2}){
+#	my @arr = @{$ref};
+#	push @arr, 1;
+#	push @new_paths, \@arr;
+#}
+
+#$paths[@paths] = \@new_paths;
+
+climb(10);
+my $i = 0;
+foreach my $pref (@paths){
+	my $count = @{$paths[$i]};
+	print "Counts: $count";
+	if($count < 50){
+		print ", ways:\n";
+		foreach my $aref (@{$pref}){
+			print "[@{$aref}] ";
+		}
+		print "\n";
+	}else{
+		print ", ways ommited\n";
+	}
+	++$i;
+}