diff options
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.lua < input-file +-- + +for line in io . lines () do + -- + -- Split into parts + -- + local parts = {} + for part in line : gmatch ("[^/]+") do + table . insert (parts, part) + end + -- + -- Copy to new structure + -- + local parts2 = {} + for index, part in ipairs (parts) do + if part == "." then -- Current directory -> skip + goto continue + end + if part == ".." then -- Parent direction -> pop from new structure + table . remove (parts2) + goto continue + end + table . insert (parts2, part) -- Else, copy + ::continue:: + end + print ("/" .. table . concat (parts2, "/")) -- And print +end diff --git a/challenge-112/abigail/lua/ch-2.lua b/challenge-112/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..8932952bbd --- /dev/null +++ b/challenge-112/abigail/lua/ch-2.lua @@ -0,0 +1,16 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + +local SQRT5 = math . sqrt (5) +local PHI = (1 + SQRT5) / 2 + +for line in io . lines () do + print (math . floor (0.5 + PHI ^ (tonumber (line) + 1) / SQRT5)) |