aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--challenge-112/dms061/perl/ch-1-example.txt3
-rw-r--r--challenge-112/dms061/perl/ch-1.pl36
-rw-r--r--challenge-112/dms061/perl/ch-2-example.pl117
-rw-r--r--challenge-112/dms061/perl/ch-2.pl177
-rw-r--r--challenge-112/dms061/perl/test.pl74
-rw-r--r--challenge-112/dms061/readme5
6 files changed, 409 insertions, 3 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
new file mode 100644
index 0000000000..856d208d40
--- /dev/null
+++ b/challenge-112/dms061/perl/ch-1.pl
@@ -0,0 +1,36 @@
+use strict;
+use warnings;
+
+# Question 1: You are given a string path, starting with a slash ‘/'.
+# Write a script to convert the given absolute path to the simplified canonical path.
+# In a Unix-style file system:
+# - A period '.' refers to the current directory
+# - A double period '..' refers to the directory up a level
+# - Multiple consecutive slashes ('//') are treated as a single slash '/'
+# The canonical path format:
+# - The path starts with a single slash '/'.
+# - Any two directories are separated by a single slash '/'.
+# - 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 = "/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
+# NOTE: this only performs the string conversion--it does not check it the path exists
+# It probably should die if the path tries to go back to a directory we don't know
+# E.g. "/../../t/" would got back past the directory structure we know from the string
+# This loop resolves that path to "/t", which isn't necessarily correct.
+# Nonetheless, this code works for valid path inputs.
+
+foreach ($path =~ m{/([^/]+)}g){
+ #print "pulled: $_\n";
+ if ($_ eq ".."){
+ pop @stack;
+ }else{
+ push @stack, "$_";
+ }
+}
+print "Path to parse: $path\n";
+my $canon_path = "/".join "/", @stack;
+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
new file mode 100644
index 0000000000..4521fb4489
--- /dev/null
+++ b/challenge-112/dms061/perl/ch-2.pl
@@ -0,0 +1,177 @@
+use strict;
+use warnings;
+
+# Question 2: You are given $n steps to climb
+# Write a script to find out the distinct ways to climb to the top.
+# You are allowed to climb either 1 or 2 steps at a time.
+
+# I know there is a better way to implement this. I remember hearing about this (or a similar question)
+# during a programming interview--albeit it was about counting the ways to climb $n stairs, and not
+# generating them. I believe the solution involved a recurrence relation, so I think there is a nice
+# way to determine the methods of climbing $n in terms of some lower $ns.
+# But first, I need some data on what f($n) is. Following some advice I was given: let the computer do the
+# work for you. This function will recursively generate all methods of climbing stairs and terminate after
+# we have climbed at least $n. It only will contribute to the final count if exactly $n stairs were climbed
+
+# Variables for checking effiency
+my $calls = 0;
+
+# The idea: we implement a recursive prefix search.
+# At any point we have to options to take -> 1 or 2 steps
+# We just take any and all paths (for n levels) adding valid paths as we go
+#sub brute {
+# my ($n, $cur) = @_;
+# $calls++;
+# #print "n = $n and cur = $cur\n";
+# return 1 if $n == $cur;
+# return 0 if $cur > $n;
+# return brute($n, $cur + 1) + brute($n, $cur + 2);
+#}
+# Example output:
+# f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8, f(6) = 13, f(7) = 21, f(8) = 34, f(9) = 55, f(10) = 89
+# ^ we can refactor this to be more like fib! Furthermore, fib would take less operations.
+# NOTE: BASE CASES ARE SLIGHTLY OFF, climb(n) = fib(n+1)
+# I could have implemented fib with altered base cases, but it felt weird, so climb is a separate function
+
+sub fib {
+ my $n = shift;
+ $calls++;
+ return $n if $n < 2;
+ return fib($n - 1) + fib($n - 2);
+}
+
+# ^ we can optimize further by memoizing!
+# The table of memoized values. I've added $fib[0] so there is no offset due to 0 indexing
+my @fib = (0, 1);
+sub fib_memo {
+ my $n = shift;
+ #$calls++;
+ if ($n > $#fib){
+ # oddity of perl, this works!
+ # normally, we would have to store new calculated value in a temporary
+ # variable because the other fib calls fill the table up to $n, thus
+ # allowing us to store the $nth fib value.
+ # However, perl doesn't seem to care (at least on my machine)
+ # as long as the value is initalized. You can have gaps between initialized values!
+ # Nonethless, we fill up the table by the end anyway
+ $fib[$n] = fib_memo($n - 1) + fib_memo($n - 2);
+ }
+ return $fib[$n];
+}
+
+sub climb {
+ my $n = shift;
+ return fib_memo($n + 1);
+}
+# Now we have a new problem (2b if you will) -> how do we get the order of the steps?
+# The example answer listed all the sequences of steps you could take. I have a really
+# nice way of calculating how many sequences you can take, but this does not calculate them
+# Theoretically, we can apply a similar method. We can store/calc the sequences for $fib[$n - 1] and
+# $fib[$n - 2] and then generate a new sequence that has a 1 and 2 step added (and shuffled) throughtour
+# the other sequences respectively
+
+# this func stores the order of the steps
+#sub brute_path {
+# my ($n, $cur, @order) = @_;
+# $calls++;
+# #return @order if $n == $cur;
+# if($cur == $n){
+# print "$_ + " foreach @order[0..$#order-1];
+# print "$order[$#order]\n";
+# return 1;
+# }elsif($cur > $n){
+# return 0;
+# }
+# #return () if $cur > $n;
+# $order[@order] = 1;
+# my $lbranch = brute_path($n, $cur + 1, @order);
+# $order[$#order] = 2;
+# return $lbranch + brute_path($n, $cur + 2, @order);
+#}
+
+# Test about how and when array warnings are generated
+# It will onlt throw warnings when trying to access uninitialized elements
+# You can assign to $test[10] without initialized 0..9 and will get no
+# errors or warnings as long as you only access elt 10
+#my @test = (1, 2, 3);
+#$test[10] = 9;
+#print "@test\n";
+#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 .. 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 "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;
+}
diff --git a/challenge-112/dms061/readme b/challenge-112/dms061/readme
index 5b4521ecae..e2684c7d25 100644
--- a/challenge-112/dms061/readme
+++ b/challenge-112/dms061/readme
@@ -1,9 +1,8 @@
Solutions by David Schwartz
-5/9/2021
+Last updated: 5/16/2021
Contains:
Solutions for questions 1 and 2 in perl.
- Solution for question 2 in python (3).
The folders also contain examples of output generated from running the program.
-Note, I am new to programming in perl--sorry if the solutions are sloppy!
+
generated by cgit (git 2.34.1) at 2026-07-01 13:51:50 +0000