diff options
29 files changed, 651 insertions, 63 deletions
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)) +end diff --git a/challenge-112/abigail/node/ch-1.js b/challenge-112/abigail/node/ch-1.js new file mode 100644 index 0000000000..ce79942bfe --- /dev/null +++ b/challenge-112/abigail/node/ch-1.js @@ -0,0 +1,28 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => { + let parts = _ . split (/\/+/) // Split on slash. + let parts2 = [] + parts . every (_ => { + if (_ == "." || _ == "") { // Skip current directory, + return true // and empty parts. + } + if (_ == "..") { // Pop parent directory. + parts2 . pop () + return true + } + parts2 . push (_) // Copy part. + return true + }) + console . log ("/" + parts2 . join ("/")) // Print result. +}) diff --git a/challenge-112/abigail/node/ch-2.js b/challenge-112/abigail/node/ch-2.js new file mode 100644 index 0000000000..2c06c8fdcd --- /dev/null +++ b/challenge-112/abigail/node/ch-2.js @@ -0,0 +1,18 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js < input-file +// + +let SQRT5 = Math . sqrt (5) +let PHI = (1 + SQRT5) / 2 + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => console . log ( + Math . round (Math . pow (PHI, +_ + 1) / SQRT5) +)) diff --git a/challenge-112/abigail/pascal/ch-2.p b/challenge-112/abigail/pascal/ch-2.p new file mode 100644 index 0000000000..40c2427265 --- /dev/null +++ b/challenge-112/abigail/pascal/ch-2.p @@ -0,0 +1,26 @@ +Program StairCase; + +(* *) +(* See ../README.md *) +(* *) + +(* *) +(* Run as: fpc -och-2.out ch-2.p; ./ch-2.out < input-file *) +(* *) + +uses math; + +const + sqrt5 = sqrt (5); + phi = (1 + sqrt5) / 2; + +var + n: integer; + +begin + while not eof () do + begin + readln (n); + writeln (round (power (phi, n + 1) / sqrt5)); + end +end. diff --git a/challenge-112/abigail/perl/ch-1.pl b/challenge-112/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..b68a966191 --- /dev/null +++ b/challenge-112/abigail/perl/ch-1.pl @@ -0,0 +1,43 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-1.pl < input-file +# + +while (<>) { + chomp; + + # Remove duplicate slashes + s !/\K/+!!g; + + # Add a trailing slash; this makes it easier to deal + # with the cases below. + $_ .= "/"; + + # Remove single period + s !/\.(?=/)!!g; + + # Remove double period + 1 while s !/[^/]+/\.\.(?=/)!!; + + # Remove any leading /../ + 1 while s !^/\.\./!/!; + + # Remove trailing slashes + s !/+$!!; + + say $_ || '/'; +} diff --git a/challenge-112/abigail/perl/ch-2.pl b/challenge-112/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..09c5717d1c --- /dev/null +++ b/challenge-112/abigail/perl/ch-2.pl @@ -0,0 +1,37 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# See ../README.md +# + +# +# Run as: perl ch-2.pl < input-file +# + +# +# This is just the Fibonacci numbers. For a staircase of n steps, +# we need F_(n + 1), where F_n is the nearest integer to +# +# n +# phi +# ---- +# 1/2 +# 5 +# 1/2 +# 1 + 5 +# where phi equals -------- (the golden ratio). +# 2 +# +# +my $SQRT5 = sqrt (5); +my $PHI = (1 + $SQRT5) / 2; +say int (1 / 2 + $PHI ** ($_ + 1) / $SQRT5) for <>; diff --git a/challenge-112/abigail/python/ch-1.py b/challenge-112/abigail/python/ch-1.py new file mode 100644 index 0000000000..bf52e6d83c --- /dev/null +++ b/challenge-112/abigail/python/ch-1.py @@ -0,0 +1,24 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-1.py < input-file +# + +import fileinput + +for line in fileinput . input (): + parts = line . rstrip () . split ("/") # Split input on / + parts2 = [] + for part in parts: + if part == "" or part == ".": # Skip empty parts, + continue # and current directory. + if part == "..": # Pop parent directory + if len (parts2): + parts2 . pop () + continue + parts2 . append (part) # Else, append. + print ("/" + "/" . join (parts2)) # Print result. diff --git a/challenge-112/abigail/python/ch-2.py b/challenge-112/abigail/python/ch-2.py new file mode 100644 index 0000000000..da542b06f2 --- /dev/null +++ b/challenge-112/abigail/python/ch-2.py @@ -0,0 +1,18 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-2.py < input-file +# + +import fileinput +from math import sqrt + +SQRT5 = sqrt (5) +PHI = (1 + SQRT5) / 2 + +for line in fileinput . input (): + print (round (pow (PHI, int (line) + 1) / SQRT5)) diff --git a/challenge-112/abigail/ruby/ch-1.rb b/challenge-112/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..e26463cb68 --- /dev/null +++ b/challenge-112/abigail/ruby/ch-1.rb @@ -0,0 +1,27 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-1.rb < input-file +# + +ARGF . each_line do + | line | + parts = line . strip() . split (/\/+/) + parts2 = [] + parts . each do + | part | + if part == "" or part == "." # Skip empty parts and current directory + next + end + if part == ".." # Remove parent directory + parts2 . pop + next + end + parts2 . push (part) # Add part + end + puts ("/" + parts2 . join("/")) # Print result +end diff --git a/challenge-112/abigail/ruby/ch-2.rb b/challenge-112/abigail/ruby/ch-2.rb new file mode 100644 index 0000000000..003d99288f --- /dev/null +++ b/challenge-112/abigail/ruby/ch-2.rb @@ -0,0 +1,17 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-2.rb < input-file +# + +SQRT5 = Math . sqrt 5 +PHI = (1 + SQRT5) / 2 + +ARGF . each_line do + | n | + puts ((PHI ** (n . to_i + 1) / SQRT5) . round) +end diff --git a/challenge-112/abigail/scheme/ch-2.scm b/challenge-112/abigail/scheme/ch-2.scm new file mode 100644 index 0000000000..1223c8719b --- /dev/null +++ b/challenge-112/abigail/scheme/ch-2.scm @@ -0,0 +1,25 @@ +;;; +;;; See ../README.md +;;; + +;;; +;;; Run as: guile --no-auto-compile ch-2.scm +;;; + +(use-modules (ice-9 format)) + +(define sqrt5 (sqrt 5)) +(define phi (/ (+ 1 sqrt5) 2)) + +(define (stairs) + (define n (read)) + (if (not (eof-object? n)) + (begin + (format #t "~d\n" + (inexact->exact (round (/ (expt phi (+ n 1)) sqrt5)))) + (stairs) + ) + ) +) + +(stairs) diff --git a/challenge-112/abigail/t/ctest.ini b/challenge-112/abigail/t/ctest.ini new file mode 100644 index 0000000000..ad939f9ac3 --- /dev/null +++ b/challenge-112/abigail/t/ctest.ini @@ -0,0 +1,10 @@ +#
+# Configuration file for running tests, using ctest.
+# See https://github.com/Abigail/Misc/blob/master/ctest
+#
+
+[names]
+1-1 = Given examples
+1-2 = More tests
+1-3 = Root directory
+2-1 = Given examples
diff --git a/challenge-112/abigail/t/input-1-1 b/challenge-112/abigail/t/input-1-1 new file mode 100644 index 0000000000..21654c1df7 --- /dev/null +++ b/challenge-112/abigail/t/input-1-1 @@ -0,0 +1,3 @@ +/a/ +/a/b//c/ +/a/b/c/../.. diff --git a/challenge-112/abigail/t/input-1-2 b/challenge-112/abigail/t/input-1-2 new file mode 100644 index 0000000000..e56eb484ba --- /dev/null +++ b/challenge-112/abigail/t/input-1-2 @@ -0,0 +1,3 @@ +/../../foo +/a/.////./b// +/a/..../b diff --git a/challenge-112/abigail/t/input-1-3 b/challenge-112/abigail/t/input-1-3 new file mode 100644 index 0000000000..91d300fffc --- /dev/null +++ b/challenge-112/abigail/t/input-1-3 @@ -0,0 +1,7 @@ +/ +/// +/././././ +/. +/../../.. +/foo/../.. +/bar/../ diff --git a/challenge-112/abigail/t/input-2-1 b/challenge-112/abigail/t/input-2-1 new file mode 100644 index 0000000000..b94473479c --- /dev/null +++ b/challenge-112/abigail/t/input-2-1 @@ -0,0 +1,2 @@ +3 +4 diff --git a/challenge-112/abigail/t/output-1-1.exp b/challenge-112/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..088085a167 --- /dev/null +++ b/challenge-112/abigail/t/output-1-1.exp @@ -0,0 +1,3 @@ +/a +/a/b/c +/a diff --git a/challenge-112/abigail/t/output-1-2.exp b/challenge-112/abigail/t/output-1-2.exp new file mode 100644 index 0000000000..4baf181d18 --- /dev/null +++ b/challenge-112/abigail/t/output-1-2.exp @@ -0,0 +1,3 @@ +/foo +/a/b +/a/..../b diff --git a/challenge-112/abigail/t/output-1-3.exp b/challenge-112/abigail/t/output-1-3.exp new file mode 100644 index 0000000000..1472c679b8 --- /dev/null +++ b/challenge-112/abigail/t/output-1-3.exp @@ -0,0 +1,7 @@ +/ +/ +/ +/ +/ +/ +/ diff --git a/challenge-112/abigail/t/output-2-1.exp b/challenge-112/abigail/t/output-2-1.exp new file mode 100644 index 0000000000..7ee0007bf1 --- /dev/null +++ b/challenge-112/abigail/t/output-2-1.exp @@ -0,0 +1,2 @@ +3 +5 |