Merge branch 'master' of https://github.com/drbaggy/perlweeklychallenge-club

72 files changed, 2904 insertions, 1480 deletions

diff --git a/challenge-021/lakpatashi/README b/challenge-021/lakpatashi/README
new file mode 100644
index 0000000000..bc153bd576
--- /dev/null
+++ b/challenge-021/lakpatashi/README
@@ -0,0 +1 @@
+Solution by lakpatashi
diff --git a/challenge-021/lakpatashi/perl/ch-1.pl b/challenge-021/lakpatashi/perl/ch-1.pl
new file mode 100755
index 0000000000..c51c29b389
--- /dev/null
+++ b/challenge-021/lakpatashi/perl/ch-1.pl
@@ -0,0 +1,33 @@
+#!/usr/bin/perl
+
+use warnings;
+use strict;
+use Data::Dumper;
+use List::Util qw(max min sum);
+use feature qw(switch);
+use Memoize;
+memoize qw( factorial );
+#part 1
+my $e;
+my $iterLimit = 100;
+for my $i (0..$iterLimit){
+	$e += exponTerm( $i );	
+	if( $i == $iterLimit ){
+		print "value of e after $iterLimit iteration => $e\n" 
+	}
+}
+
+sub exponTerm{
+	my ($n) = @_;
+	return 1/factorial($n);
+}
+
+sub factorial{
+	my ($n) = @_;
+	if( $n < 2 ){
+		return 1;
+	}
+	return $n * factorial($n-1);
+}
+
+
diff --git a/challenge-112/abigail/README.md b/challenge-112/abigail/README.md
index 021fb3375e..aba06c6afa 100644
--- a/challenge-112/abigail/README.md
+++ b/challenge-112/abigail/README.md
@@ -1,37 +1,36 @@
 # Solutions by Abigail
-## [Search Matrix](https://perlweeklychallenge.org/blog/perl-weekly-challenge-111/#TASK1)
+## [Canonical Path](https://perlweeklychallenge.org/blog/perl-weekly-challenge-112/#TASK1)
 
-> You are given 5x5 matrix filled with integers such that each row is
-> sorted from left to right and the first integer of each row is greater
-> than the last integer of the previous row.
+> You are given a string path, starting with a slash `/`.
 >
-> Write a script to find a given integer in the matrix using an
-> efficient search algorithm.
-
-### Notes
-This challenge confuses me. We're basically asked to find a number
-in a sorted list. Which in languages without hashes one would solve
-with binary search (yielding an O (log N) solution), and in languages
-with hashes you'd use a hash (yielding an O (1) (expected) time solution).
-Sure, the hash takes linear preprocessing time, but since we're asked
-to write a script, we're spending linear time reading in the data
-anyway.
-
-Perhaps the intend was a subroutine which takes a matrix and a target
-number, but that was not what is being asked. The challenge explicitly
-asks for *a script*, which means we have to spend a linear amount of 
-time reading data anyway. So, that's what you get.
+> 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
 
-The only part where we use the fact we are given a matrix is for the
-input: the first five lines are assumed to contain the matrix. The
-rest of the input is taken as numbers to search for.
+### Example
+~~~~
+Input: "/a/"
+Output: "/a"
 
-Only for language lacking hashes/maps/dictionaries/tables, we will
-make use of the fact the input is sorted. For the majority of
-languages, the fact input is sorted does not offer additional benefits.
+Input: "/a/b//c/"
+Output: "/a/b/c"
 
-For Perl, we make two implementations: one based on a hash, the
-other using binary search.
+Input: "/a/b/c/../.."
+Output: "/a"
+~~~~
 
 ### Solutions
 * [AWK](awk/ch-1.awk)
@@ -39,60 +38,34 @@ other using binary search.
 * [C](c/ch-1.c)
 * [Lua](lua/ch-1.lua)
 * [Node.js](node/ch-1.js)
-* [Pascal](pascal/ch-1.p)
 * [Perl](perl/ch-1.pl)
 * [Python](python/ch-1.py)
 * [Ruby](ruby/ch-1.rb)
 
 ### Blog
-[Perl Weekly Challenge 111: Search Matrix](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-111-1.html)
 
-## [Ordered Letters](https://perlweeklychallenge.org/blog/perl-weekly-challenge-111/#TASK2)
+## [Climb Stairs](https://perlweeklychallenge.org/blog/perl-weekly-challenge-112/#TASK2)
 
-> Given a word, you can sort its letters alphabetically (case insensitive).
-> For example, 'beekeeper' becomes 'beeeeekpr' and 'dictionary' becomes
-> 'acdiinorty'.
+> You are given `$n` steps to climb
 >
-> Write a script to find the longest English words that don't change when
-> their letters are sorted.
+> 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.
 
 ### Notes
-We will grep the words from standard input which don't change
-if they are sorted; these are the words which match the pattern
-/^a*b*c*...z*$/i. We keep track of the longest word.
-
-If course, there does not have to be a unique word. It will depend
-on the word list used to search in. For instance, three different
-word list I used give different results:
-
-    infochimps.com     /usr/share/dict/words     enable.lst
-    --------------     ---------------------     ----------
-                                     Adelops
-          aegilops
-                                     alloquy
-                                     beefily        beefily
-                                     begorry
-                                     billowy        billowy
-                                     egilops
-
-Only one of them has a unique longest word.
-
-We will be reading a word list from standard input, and write
-the longest word where the letters are in alphabetical order
-to standard output. In case of ties, we print the first one found.
+This is just finding the `$n + 1` Fibonacci number.
 
 
 ### Solutions
-* [GNU AWK](awk/ch-2.gawk)
+* [AWK](awk/ch-2.awk)
 * [Bash](bash/ch-2.sh)
 * [C](c/ch-2.c)
+* [Go](go/ch-2.go)
 * [Lua](lua/ch-2.lua)
 * [Node.js](node/ch-2.js)
-* [Pascal](pascal/ch-2.p)
 * [Perl](perl/ch-2.pl)
+* [Pascal](pascal/ch-2.p)
 * [Python](python/ch-2.py)
 * [Ruby](ruby/ch-2.rb)
+* [Scheme](scheme/ch-2.scm)
 
 ### Blog
-[Perl Weekly Challenge 111: Ordered Letters](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-111-2.html)
-
diff --git a/challenge-112/abigail/awk/ch-1.awk b/challenge-112/abigail/awk/ch-1.awk
new file mode 100644
index 0000000000..5de385b451
--- /dev/null
+++ b/challenge-112/abigail/awk/ch-1.awk
@@ -0,0 +1,44 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-1.awk < input-file
+#
+
+BEGIN {
+    FS="/"   # So we split into directory parts
+}
+
+{
+    delete path
+    j = 0                            # Tracks the number of parts in
+                                     # the canonical part.
+    for (i = 1; i <= NF; i ++) {     # Loop over directory parts
+        if ($i == "") {              # Skip empty parts
+            continue;
+        }
+        if ($i == ".") {             # Skip current directory
+            continue;
+        }
+        if ($i == "..") {            # Back up to parent directory
+            if (j > 0) {
+                j --
+            }
+            continue;
+        }
+        path [j] = $i                # Copy
+        j ++
+    }
+    if (j == 0) {                    # Root directory
+        print "/"
+    }
+    else {                           # Print parts, preceeded by a /
+        for (k = 0; k < j; k ++) {
+            printf "/%s", path [k]
+        }
+        print ""
+    }
+}
diff --git a/challenge-112/abigail/awk/ch-2.awk b/challenge-112/abigail/awk/ch-2.awk
new file mode 100644
index 0000000000..57f4b8cc6f
--- /dev/null
+++ b/challenge-112/abigail/awk/ch-2.awk
@@ -0,0 +1,18 @@
+#!/usr/bin/awk
+
+#
+# See ../README.md
+#
+
+#
+# Run as: awk -f ch-2.awk < input-file
+#
+
+BEGIN {
+    SQRT5 = sqrt (5)
+    PHI   = (1 + SQRT5) / 2
+}
+
+{
+    print int (0.5 + PHI ^ ($1 + 1) / SQRT5)
+}
diff --git a/challenge-112/abigail/bash/ch-1.sh b/challenge-112/abigail/bash/ch-1.sh
new file mode 100644
index 0000000000..6f41950bc5
--- /dev/null
+++ b/challenge-112/abigail/bash/ch-1.sh
@@ -0,0 +1,41 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-1.sh < input-file
+#
+
+set -f
+
+IFS="/"
+
+while read -a i_parts
+do    declare -a o_parts
+      j=0
+      for ((i = 0; i < ${#i_parts[@]}; i ++))
+      do  if [ "X${i_parts[$i]}" == "X" ]       # Skip empty parts
+          then continue
+          fi
+          if [ "X${i_parts[$i]}" == "X." ]      # Skip current directory
+          then continue
+          fi
+          if [ "X${i_parts[$i]}" == "X.." ]     # Back up to parent directory
+          then if ((j > 0))
+               then ((j --))
+               fi
+               continue
+          fi
+          o_parts[$j]=${i_parts[$i]}            # Copy part
+          ((j ++))
+      done
+      if  ((j == 0))
+      then echo "/"                             # Root directory
+      else for ((k = 0; k < j; k ++))           # Canonical path
+           do  printf "/%s" ${o_parts[$k]}
+           done
+           echo
+      fi
+done
diff --git a/challenge-112/abigail/bash/ch-2.sh b/challenge-112/abigail/bash/ch-2.sh
new file mode 100644
index 0000000000..17f2d49b9b
--- /dev/null
+++ b/challenge-112/abigail/bash/ch-2.sh
@@ -0,0 +1,29 @@
+#!/bin/sh
+
+#
+# See ../README.md
+#
+
+#
+# Run as: bash ch-2.sh < input-file
+#
+
+declare -A cache
+cache[0]=1
+cache[1]=1
+
+function fib () {
+    local n=$1
+    if   [[ -z ${cache[$n]} ]]
+    then fib $((n - 1))
+         cache[$n]=$result
+         fib $((n - 2))
+         cache[$n]=$((cache[$n] + result))
+    fi
+    result=${cache[$n]}
+}
+
+while read n
+do    fib $n
+      echo $result
+done
diff --git a/challenge-112/abigail/c/ch-1.c b/challenge-112/abigail/c/ch-1.c
new file mode 100644
index 0000000000..d7445188a6
--- /dev/null
+++ b/challenge-112/abigail/c/ch-1.c
@@ -0,0 +1,78 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <stdbool.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file
+ */
+
+/*
+ * Here, we will "eliminate" parts (".", or ".." and its parent)
+ * by replacing the parts with slashes. Then we print the string,
+ * without printing 2 slashes in succession.
+ */
+
+int main (void) {
+    char *  line    = NULL;
+    size_t  len     = 0;
+    size_t  str_len;
+
+    while ((str_len = getline (&line, &len, stdin)) != -1) {
+        line [str_len - 1] = '/';
+        for (size_t i = 0; i < str_len; i ++) {
+            if (line [i] == '.' && line [i - 1] == '/') {
+                /* Component starts with a . */
+                if (line [i + 1] == '/') {
+                    line [i] = '/';  /* Current directory */
+                    continue;
+                }
+                else {
+                    if (line [i + 1] == '.' && line [i + 2] == '/') {
+                        /* Parent directory. */
+                        /* First wipe this component */
+                        line [i]     = '/';
+                        line [i + 1] = '/';
+                        /* Then wipe the previous component, if any. */
+                        /* First, skip the slashes */
+                        size_t j = i - 1;
+                        while (j && line [j] == '/') {
+                            j --;
+                        }
+                        /* Now, erase exactly one component */
+                        while (j && line [j] != '/') {
+                            line [j] = '/';
+                            j --;
+                        }
+                    }
+                }
+            }
+        }
+        /* Get rid of trailing slashes */
+        while (str_len > 1 && line [str_len - 1] == '/') {
+            str_len --;
+        }
+        /* Print string, eliminating double slashes */
+        bool slash = false;
+        for (size_t i = 0; i < str_len; i ++) {
+            if (line [i] == '/') {
+                if (slash) {
+                    continue;
+                }
+                slash = true;
+            }
+            else {
+                slash = false;
+            }
+            printf ("%c", line [i]);
+        }
+        printf ("\n");
+    }
+    free (line);
+
+    return (0);
+}
diff --git a/challenge-112/abigail/c/ch-2.c b/challenge-112/abigail/c/ch-2.c
new file mode 100644
index 0000000000..73344c2aa5
--- /dev/null
+++ b/challenge-112/abigail/c/ch-2.c
@@ -0,0 +1,24 @@
+# include <stdlib.h>
+# include <stdio.h>
+# include <math.h>
+
+/*
+ * See ../README.md
+ */
+
+/*
+ * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file
+ */
+
+# define SQRT5 (sqrt (5))
+# define PHI   ((1 + SQRT5) / 2)
+
+int main (void) {
+    int n;
+
+    while (scanf ("%d", &n) == 1) {
+        printf ("%lld\n", (long long) floor (0.5 + pow (PHI, n + 1) / SQRT5));
+    }
+
+    return (0);
+}
diff --git a/challenge-112/abigail/go/ch-2.go b/challenge-112/abigail/go/ch-2.go
new file mode 100644
index 0000000000..74225957db
--- /dev/null
+++ b/challenge-112/abigail/go/ch-2.go
@@ -0,0 +1,27 @@
+package main
+
+//
+// See ../README.md
+//
+
+//
+// Run as: go run ch-2.go
+//
+
+import "fmt"
+import "math"
+
+var SQRT5 float64 = math . Sqrt (5)
+var PHI   float64 = (1 + SQRT5) / 2
+
+func main () {
+    for {
+        var n, r float64
+        c, _ := fmt . Scanf ("%f", &n)
+        if (c != 1) {
+            break
+        }
+        r = math . Round (math . Pow (PHI, (n + 1)) / SQRT5)
+        fmt . Printf ("%d\n", (int) (r))
+    }
+}
diff --git a/challenge-112/abigail/lua/ch-1.lua b/challenge-112/abigail/lua/ch-1.lua
new file mode 100644
index 0000000000..2d866dd9bf
--- /dev/null
+++ b/challenge-112/abigail/lua/ch-1.lua
@@ -0,0 +1,35 @@
+#!/opt/local/bin/lua
+
+--
+-- See ../README.md
+--
+
+--
+-- Run as: lua ch-1.lu