Merge branch 'manwar:master' into challenge112

7 files changed, 397 insertions, 0 deletions

diff --git a/challenge-112/colin-crain/blog.txt b/challenge-112/colin-crain/blog.txt
new file mode 100644
index 0000000000..7b99215824
--- /dev/null
+++ b/challenge-112/colin-crain/blog.txt
@@ -0,0 +1 @@
+https://colincrain.com/2021/05/15/after-finding-our-bearings-one-two-and-up-we-go/
diff --git a/challenge-112/colin-crain/perl/ch-1.pl b/challenge-112/colin-crain/perl/ch-1.pl
new file mode 100644
index 0000000000..3a638cea0f
--- /dev/null
+++ b/challenge-112/colin-crain/perl/ch-1.pl
@@ -0,0 +1,107 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       where-am-i-where-are-my-friends.pl

+#

+#         Canonical Path

+#         Submitted by: Mohammad S Anwar

+#         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

+#  

+#         Example

+#             Input: "/a/"

+#             Output: "/a"

+# 

+#             Input: "/a/b//c/"

+#             Output: "/a/b/c"

+# 

+#             Input: "/a/b/c/../.."

+#             Output: "/a"

+# 

+#         method

+#             converting to a canonical path form is not quite as simple as

+#             restructuring dot file notaion into real directories and

+#             normalizing superfluous chaff such as '//', because a canonical

+#             path is always an absolute path and the relative path given may

+#             not be.

+# 

+#             Fortunately for us today we are defined as having been given an

+#             absolute path, sidestepping that mess. 

+# 

+#             However a canonical path also resolves soft links, which remains a 

+#             difficulty, as Perl is not a shell. There are ways involving a module

+#             to address this, but I'm going to assume this edge case is outside

+#             the scope of the problem.

+# 

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+

+use Cwd qw( abs_path );

+

+

+

+sub canonical ($path) {

+    $path =~ s{/\.?/}{/}g;

+    $path =~ s{/$}{};

+    

+    my @parts = split '/', $path;

+    my $pos = 0;

+    while (++$pos < @parts) {   

+        if ($parts[$pos] eq '..') {

+            splice @parts, $pos-1, 2;

+            $pos -= 2;            

+        }

+    }

+    join '/', @parts;

+}

+

+# this will resolve relative paths, and soft links, from the cwd, which doesn't

+# really solve that problem in a general way. We need to `chdir` over to 

+# the place in question, which would need to both exist and have the right permissions. 

+# The whole thing is a bit of a mess, really, and I don't think that's what Mohammad is

+# asking of us. 

+

+sub canonical_softlinks ($path) {

+    chdir $path;

+    return abs_path( $path );

+}

+

+## resolving the link from d -> e

+## yields /Users/colincrain/a/b/c/e

+

+my $path = '../../a/b/c/f/../d';

+say canonical_softlinks( $path );

+

+

+

+use Test::More;

+

+is canonical("/a/"), "/a"             , 'ex-1';

+is canonical("/a/b//c/"), "/a/b/c"    , 'ex-2';

+is canonical("/a/b/c/../.."), "/a"    , 'ex-3';

+

+done_testing();

+

diff --git a/challenge-112/colin-crain/perl/ch-2.pl b/challenge-112/colin-crain/perl/ch-2.pl
new file mode 100644
index 0000000000..3c09e7f2c9
--- /dev/null
+++ b/challenge-112/colin-crain/perl/ch-2.pl
@@ -0,0 +1,162 @@
+#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl

+#

+#       one-two-up-we-go.pl

+#

+#         Climb Stairs

+#         Submitted by: Mohammad S Anwar

+#         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.

+# 

+#         Example

+# 

+#             Input:  $n = 3

+#             Output: 3

+# 

+#                 Option 1: 1 step  + 1 step

+#                 Option 2: 1 step  + 2 steps

+#                 Option 3: 2 steps + 1 step

+# 

+#             Input:  $n = 4

+#             Output: 5

+# 

+#                 Option 1: 1 step  + 1 step  + 1 step  + 1 step

+#                 Option 2: 1 step  + 1 step  + 2 steps

+#                 Option 3: 2 steps + 1 step  + 1 step

+#                 Option 4: 1 step  + 2 steps + 1 step

+#                 Option 5: 2 steps + 2 steps

+# 

+#         method

+#             This was a fun one to think through. The first step involved 

+#             looking at the results for input 5 in the examples as ordered sets 

+#             of elements summed together:

+#             

+#             (1+1+1+1), (1+1+2), (2+1+1), (1+2+1), (2+2)

+#             

+#             What this looks like are integer compositions of the input value,

+#             with the added constraint that the maximum value is 2. A little

+#             thinking-through validates this, as we want every combination of 1

+#             and 2 that adds up to the correct number of steps. We're going to

+#             ignore the possibility of launching yourself off into space from

+#             the next-to-last step as though there were two to jump up, even

+#             though one could probably land it and not break your neck.

+#             Pretending there is more than one remaining step does not make it

+#             so. The sum must be exact. 

+#             

+#             Further analysis with a pencil and paper:

+#             

+#             input       compositions        C_2(n)

+#             1           1                   1

+#             2           1,1                 2

+#                         2

+#             3           1,1,1               3

+#                         2,1

+#                         1,2

+#             4           1,1,1,1             5

+#                         2,1,1

+#                         1,2,1

+#                         1,1,2

+#                         2,2

+#             5           1,1,1,1,1           8

+#                         2,1,1,1

+#                         1,2,1,1

+#                         1,1,2,1

+#                         2,2,1          __________ change here from 1 to 2

+#                         1,1,1,2       

+#                         2,1,2

+#                         1,2,2

+#             6           1,1,1,1,1,1         13

+#                         2,1,1,1,1

+#                         1,2,1,1,1

+#                         1,1,2,1,1

+#                         2,2,1,1

+#                         1,1,1,2,1

+#                         2,1,2,1

+#                         1,2,2,1        __________ change here from 1 to 2

+#                         1,1,1,1,2              

+#                         2,1,1,2

+#                         1,2,1,2

+#                         1,1,2,2

+#                         2,2,2

+# 

+#             And yes, although I didn't include it here, the compositions,

+#             enumerated, for the next term are 21.

+#                         

+#             So wait one cotton-picking minute — is that the Fibonacci

+#             sequence? And if so, why?

+# 

+#             Yes it is, and if you notice I've rearranged the sets to more

+#             clearly show the association: separate each composition part into

+#             a head and a tail, with the tail the last value. Now look at the

+#             head, and notice it is repeated in the set for a previous value.

+#             I've sorted things in each sequence entry so all the parts ending

+#             in 1 are followed by those ending in 2.

+# 

+#             There are only two available values for a member of a composition

+#             part: 1 and 2. Thus each part in a composition for a new number

+#             will be that of a previously calculated composition with either 1

+#             or 2 added. To make the sums correct, the previous compositions

+#             referenced will be those for C(n-1), plus an additional 1, and

+#             C(n-2), with an additional 2.

+# 

+#             Every composition set for a given value is already an exhaustive

+#             enumeration of possible arrangements for that number.

+# 

+#             So to propagate every part of the composition set for the previous

+#             value, we add the new element, 1 or 2, to the end to create a new

+#             part. It can be seen that any other placement of the new item will

+#             produce a duplication that will need to be removed, for although

+#             different ordering of the elements produces different parts, the

+#             parts counted are unique. This is the fundimantal difference

+#             between partitions and compositions, that the order of the

+#             elements matters.

+# 

+#             So for every number in the sequence we have a set of composition

+#             parts created from the immediately previous number with 1, and the

+#             second previous with 2. In other words, 

+#             

+#             C(n) = C(n-1) + C(n-2)

+#             

+#             which is the Fibonacci recurrence relation. With 

+#             

+#             C(1) = 1

+#             C(2) = 2

+#             

+#             the recurrence follows, setting the base pattern. Further, these values are

+#             themselves part of the Fibonacci sequence. So in other words:

+#             

+#             C(n) = F(n+1) ∀ n > 0

+# 

+#             So we'll make a memoized Fibonacci generator to calculate our

+#             values and call it a day. Good work lads, pack it in. 

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+use warnings;

+use strict;

+use feature ":5.26";

+use feature qw(signatures);

+no warnings 'experimental::signatures';

+use Lingua::EN::Inflexion;

+

+

+use Memoize;

+memoize qw( fib );

+

+sub fib ($n) {

+    return $n if $n < 2;

+    return fib($n-1) + fib($n-2);

+}

+

+

+for (1..21) {   

+    my $str = inflect("<#d:$_>For $_ <N:steps> there <V:is> ");

+    $str .= fib($_+1) . ' ';

+    $str .= inflect("<#d:$_>possible <N:ways> to climb <N:them>.");

+    say $str; 

+}

+

diff --git a/challenge-112/colin-crain/python/ch-1.py b/challenge-112/colin-crain/python/ch-1.py
new file mode 100644
index 0000000000..652c0710c0
--- /dev/null
+++ b/challenge-112/colin-crain/python/ch-1.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python3

+#

+#

+#       where-are-my-friends.py

+#

+#

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+import os

+import sys

+

+if len(sys.argv) > 1:

+    path = sys.argv[1]

+else:

+    path = '../../a/b/c///f/../d';

+

+canonical = os.path.realpath(path)

+  

+print(canonical )

diff --git a/challenge-112/colin-crain/python/ch-2.py b/challenge-112/colin-crain/python/ch-2.py
new file mode 100644
index 0000000000..750a165737
--- /dev/null
+++ b/challenge-112/colin-crain/python/ch-2.py
@@ -0,0 +1,27 @@
+#!/usr/bin/env python3

+#

+#

+#       one-two-up-we-go.py

+#

+#

+#

+#       © 2021 colin crain

+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##

+

+

+

+from functools import lru_cache

+

+@lru_cache(maxsize = 1000)

+def fib(n):

+    if n < 0:

+        return None

+    if n < 2:

+        return n

+    else:

+        return fib(n-1) + fib(n-2)

+

+

+for i in range(2, 21):

+    ways = fib(i+1)

+    print(f"for {i} steps there are {ways} ways to climb them")

diff --git a/challenge-112/colin-crain/raku/ch-1.raku b/challenge-112/colin-crain/raku/ch-1.raku
new file mode 100644
index 0000000000..9e0f0072c8
--- /dev/null
+++ b/challenge-112/colin-crain/raku/ch-1.raku
@@ -0,0 +1,29 @@
+#!/usr/bin/env perl6
+#
+#
+#       where-are-my-friends.raku
+#
+#
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN () ;
+
+
+use Test;
+plan 3;
+
+is canonical("/a/"), "/a"             , 'ex-1';
+is canonical("/a/b//c/"), "/a/b/c"    , 'ex-2';
+is canonical("/a/b/c/../.."), "/a"    , 'ex-3';
+
+
+sub canonical($path) {
+    my $clean = IO::Spec::Unix.canonpath("$path");
+    
+    repeat {} while $clean ~~ s| '/' <-[/]>* '/..' ||;
+    return $clean;
+}
diff --git a/challenge-112/colin-crain/raku/ch-2.raku b/challenge-112/colin-crain/raku/ch-2.raku
new file mode 100644
index 0000000000..74358e7015
--- /dev/null
+++ b/challenge-112/colin-crain/raku/ch-2.raku
@@ -0,0 +1,50 @@
+#!/usr/bin/env perl6
+#
+#
+#       one-two-up-we-go.raku
+#
+#
+#
+#       © 2021 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+unit sub MAIN () ;
+
+sub fib ( $n ){ 
+    state @fib;
+    return @fib[$n] when @fib[$n].defined;
+    return @fib[$n] = $n if $n < 2;
+    @fib[$n] = fib($n-1) + fib($n-2);
+}
+
+for 1..20 {
+    my ($s, $v, $p) = ('s', 'are', 'them');
+    $_ == 1 and ($s, $v, $p) = (' ', 'is ', 'it');
+    printf "for %2d step%s there %s %5d way%s to climb %s\n", 
+        $_, $s, $v, fib($_+1), $s, $p;
+
+}
+
+
+# for  1 step  there is      1 way  to climb it
+# for  2 steps there are     2 ways to climb them
+# for  3 steps there are     3 ways to climb them
+# for  4 steps there are     5 ways to climb them
+# for  5 steps there are     8 ways to climb them
+# for  6 steps there are    13 ways to climb them
+# for  7 steps there are    21 ways to climb them
+# for  8 steps there are    34 ways to climb them
+# for  9 steps there are    55 ways to climb them
+# for 10 steps there are    89 ways to climb them
+# for 11 steps there are   144 ways to climb them
+# for 12 steps there are   233 ways to climb them
+# for 13 steps there are   377 ways to climb them
+# for 14 steps there are   610 ways to climb them
+# for 15 steps there are   987 ways to climb them
+# for 16 steps there are  1597 ways to climb them
+# for 17 steps there are  2584 ways to climb them
+# for 18 steps there are  4181 ways to climb them
+# for 19 steps there are  6765 ways to climb them
+# for 20 steps there are 10946 ways to climb them