From 973dd57dc4c70abf98cf65c4168e2f62d0fb4493 Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 31 May 2021 13:03:50 +0200 Subject: README for week 115 --- challenge-115/abigail/README.md | 58 +++++++++++++++++------------------------ 1 file changed, 24 insertions(+), 34 deletions(-) diff --git a/challenge-115/abigail/README.md b/challenge-115/abigail/README.md index 7548aee37d..75cec1ed8e 100644 --- a/challenge-115/abigail/README.md +++ b/challenge-115/abigail/README.md @@ -1,58 +1,48 @@ # Solutions by Abigail -## [Next Palindrome Number](https://perlweeklychallenge.org/blog/perl-weekly-challenge-114/#TASK1) +## [String Chain](https://perlweeklychallenge.org/blog/perl-weekly-challenge-115/#TASK1) -> You are given a positive integer `$N`. +> You are given an array of strings. +> +> Write a script to find out if the given strings can be chained +> to form a circle. Print `1` if found otherwise `0`. > -> Write a script to find out the next Palindrome Number higher than -> the given integer `$N`. +> > A string `$S` can be put before another string `$T` in circle +> > if the last character of `$S` is same as first character of `$T`. ### Example ~~~~ -Input: $N = 1234 -Output: 1331 +Input: @S = ("abc", "dea", "cd") +Output: 1 as we can form circle e.g. "abc", "cd", "dea". -Input: $N = 999 -Output: 1001 +Input: @S = ("ade", "cbd", "fgh") +Output: 0 as we can't form circle. ~~~~ ### Solutions -* [AWK](awk/ch-1.awk) -* [Bash](bash/ch-1.sh) -* [C](c/ch-1.c) -* [Perl](perl/ch-1.pl) ### Blog -[Next Palindrome Number](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-1.html) +[String Chain](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-115-1.html) -## [Higher Integer Set Bits](https://perlweeklychallenge.org/blog/perl-weekly-challenge-114/#TASK2) +## [Largest Multiple](https://perlweeklychallenge.org/blog/perl-weekly-challenge-115/#TASK2) -> You are given a positive integer `$N`. -> -> Write a script to find the next higher integer having the same number of -> `1` bits in binary representation as `$N`. +> You are given a list of positive integers `(0-9)`, single digit. +> +> Write a script to find the largest multiple of `2` that can be +> formed from the list. ### Examples ~~~~ -Input: $N = 3 -Output: 5 -~~~~ +Input: @N = (1, 0, 2, 6) +Output: 6210 -Binary representation of `$N` is `011`. There are two `1` bits. So the next -higher integer is `5` having the same the number of `1` bits i.e. `101`. +Input: @N = (1, 4, 2, 8) +Output: 8412 +Input: @N = (4, 1, 7, 6) +Output: 7614 ~~~~ -Input: $N = 12 -Output: 17 -~~~~ - -Binary representation of `$N` is `1100`. There are two `1` bits. So the next -higher integer is `17` having the same number of `1` bits i.e. `10001`. ### Solutions -* [GNU AWK](awk/ch-2.gawk) -* [Bash](bash/ch-2.sh) -* [C](c/ch-2.c) -* [Perl](perl/ch-2.pl) ### Blog -[Higher Integet Set Bits](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-114-2.html) +[String Chain](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-115-2.html) -- cgit From 9def9e9e8ab96a506f322adf88fbdb182fd9acb7 Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 31 May 2021 13:06:05 +0200 Subject: Tests for week 115 --- challenge-115/abigail/t/ctest.ini | 8 ++++++++ challenge-115/abigail/t/input-1-1 | 2 ++ challenge-115/abigail/t/input-2-1 | 3 +++ challenge-115/abigail/t/output-1-1.exp | 2 ++ challenge-115/abigail/t/output-2-1.exp | 3 +++ 5 files changed, 18 insertions(+) create mode 100644 challenge-115/abigail/t/ctest.ini create mode 100644 challenge-115/abigail/t/input-1-1 create mode 100644 challenge-115/abigail/t/input-2-1 create mode 100644 challenge-115/abigail/t/output-1-1.exp create mode 100644 challenge-115/abigail/t/output-2-1.exp diff --git a/challenge-115/abigail/t/ctest.ini b/challenge-115/abigail/t/ctest.ini new file mode 100644 index 0000000000..527781acbb --- /dev/null +++ b/challenge-115/abigail/t/ctest.ini @@ -0,0 +1,8 @@ +# +# Configuration file for running tests, using ctest. +# See https://github.com/Abigail/Misc/blob/master/ctest +# + +[names] +1-1 = Given Examples +2-1 = Given Examples diff --git a/challenge-115/abigail/t/input-1-1 b/challenge-115/abigail/t/input-1-1 new file mode 100644 index 0000000000..839d61045e --- /dev/null +++ b/challenge-115/abigail/t/input-1-1 @@ -0,0 +1,2 @@ +abc dea cd +ade cbd fgh diff --git a/challenge-115/abigail/t/input-2-1 b/challenge-115/abigail/t/input-2-1 new file mode 100644 index 0000000000..151a3fb733 --- /dev/null +++ b/challenge-115/abigail/t/input-2-1 @@ -0,0 +1,3 @@ +1 0 2 6 +1 4 2 8 +4 1 7 6 diff --git a/challenge-115/abigail/t/output-1-1.exp b/challenge-115/abigail/t/output-1-1.exp new file mode 100644 index 0000000000..b261da18d5 --- /dev/null +++ b/challenge-115/abigail/t/output-1-1.exp @@ -0,0 +1,2 @@ +1 +0 diff --git a/challenge-115/abigail/t/output-2-1.exp b/challenge-115/abigail/t/output-2-1.exp new file mode 100644 index 0000000000..8e6281d33b --- /dev/null +++ b/challenge-115/abigail/t/output-2-1.exp @@ -0,0 +1,3 @@ +6210 +8412 +7614 -- cgit From 4f04dab2323d4219a5eb906c4bbc28059fecb10c Mon Sep 17 00:00:00 2001 From: Abigail Date: Mon, 31 May 2021 20:16:50 +0200 Subject: AWK, Bash, C, Lua, Node.js, Perl, Python and Ruby solutions for week 115, part 2 --- challenge-115/abigail/README.md | 8 ++++ challenge-115/abigail/awk/ch-2.awk | 56 ++++++++++++++++++++++++++++ challenge-115/abigail/bash/ch-2.sh | 52 ++++++++++++++++++++++++++ challenge-115/abigail/c/ch-2.c | 71 ++++++++++++++++++++++++++++++++++++ challenge-115/abigail/lua/ch-2.lua | 59 ++++++++++++++++++++++++++++++ challenge-115/abigail/node/ch-2.js | 53 +++++++++++++++++++++++++++ challenge-115/abigail/perl/ch-2.pl | 44 ++++++++++++++++++++++ challenge-115/abigail/python/ch-2.py | 49 +++++++++++++++++++++++++ challenge-115/abigail/ruby/ch-2.rb | 57 +++++++++++++++++++++++++++++ 9 files changed, 449 insertions(+) create mode 100644 challenge-115/abigail/awk/ch-2.awk create mode 100644 challenge-115/abigail/bash/ch-2.sh create mode 100644 challenge-115/abigail/c/ch-2.c create mode 100644 challenge-115/abigail/lua/ch-2.lua create mode 100644 challenge-115/abigail/node/ch-2.js create mode 100644 challenge-115/abigail/perl/ch-2.pl create mode 100644 challenge-115/abigail/python/ch-2.py create mode 100644 challenge-115/abigail/ruby/ch-2.rb diff --git a/challenge-115/abigail/README.md b/challenge-115/abigail/README.md index 75cec1ed8e..0d966f083c 100644 --- a/challenge-115/abigail/README.md +++ b/challenge-115/abigail/README.md @@ -43,6 +43,14 @@ Output: 7614 ~~~~ ### Solutions +* [AWK](awk/ch-2.awk) +* [Bash](bash/ch-2.sh) +* [C](c/ch-2.c) +* [Lua](lua/ch-2.lua) +* [Node.js](node/ch-2.js) +* [Perl](perl/ch-2.pl) +* [Python](python/ch-2.py) +* [Ruby](ruby/ch-2.rb) ### Blog [String Chain](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-115-2.html) diff --git a/challenge-115/abigail/awk/ch-2.awk b/challenge-115/abigail/awk/ch-2.awk new file mode 100644 index 0000000000..2b2162d5f0 --- /dev/null +++ b/challenge-115/abigail/awk/ch-2.awk @@ -0,0 +1,56 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-2.awk < input-file +# + +{ + # + # Initialize digits array + # + for (i = 0; i < 10; i ++) { + digits [i] = 0 + } + + # + # Read in the data; count digits + # + for (i = 1; i <= NF; i ++) { + digits [$i] ++ + } + + # + # Find the smallest even number; this one goes last + # + last = -1 + for (i = 0; i < 10 && last < 0; i += 2) { + if (digits [i] > 0) { + last = i + digits [i] -- + } + } + + # + # Skip if the input does not contain an even digit + # + if (last < 0) { + next + } + + # + # Create the output: rest of digits are from highest to lowest + # + out = "" + for (i = 9; i >= 0; i --) { + while (digits [i] -- > 0) { + out = out i + } + } + print out last +} + + diff --git a/challenge-115/abigail/bash/ch-2.sh b/challenge-115/abigail/bash/ch-2.sh new file mode 100644 index 0000000000..3da1e61c2b --- /dev/null +++ b/challenge-115/abigail/bash/ch-2.sh @@ -0,0 +1,52 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-2.sh < input-file +# + +declare -a digits + +while read -a input +do # + # Count the digits of the input + # + unset digits + for ((i = 0; i < ${#input[@]}; i ++)) + do ((digits[input[i]] ++)) + done + + # + # Find smallest even number; this will be last number. + # + last=-1 + for ((i = 8; i >= 0; i -= 2)) + do if ((digits[i] > 0)) + then ((last = i)) + fi + done + + # + # Skip if the input doesn't contain an even digit + # + if ((last < 0)) + then continue + fi + + ((digits[last] --)) + + # + # Create the output + # + out="" + for ((i = 9; i >= 0; i --)) + do for ((j = 0; j < digits[i]; j ++)) + do out=$out$i + done + done + + echo $out$last +done diff --git a/challenge-115/abigail/c/ch-2.c b/challenge-115/abigail/c/ch-2.c new file mode 100644 index 0000000000..975aace0ef --- /dev/null +++ b/challenge-115/abigail/c/ch-2.c @@ -0,0 +1,71 @@ +# include +# include +# include +# include + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-2.o ch-2.c; ./ch-2.o < input-file + */ + +# define NR_OF_DIGITS 10 +# define ZERO '0' + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t str_len; + + while ((str_len = getline (&line, &len, stdin)) != -1) { + /* + * Read in a line of data. Count the number of digits, + * and put them in an array 'digits'. + */ + char * line_ptr = line; + int digits [NR_OF_DIGITS]; + for (size_t i = 0; i < NR_OF_DIGITS; i ++) { + digits [i] = 0; + } + while (* line_ptr) { + if (isdigit (* line_ptr)) { + digits [* line_ptr - ZERO] ++; + } + line_ptr ++; + } + + /* + * Find the lowest even digit. + */ + int last = -1; + for (ssize_t i = NR_OF_DIGITS - 2; i >= 0; i -= 2) { + if (digits [i]) { + last = i; + } + } + + /* + * Skip if the input does not contain an even digit. + */ + if (last < 0) { + continue; + } + digits [last] --; + + /* + * Print the output + */ + for (ssize_t i = NR_OF_DIGITS - 1; i >= 0; i --) { + for (int j = 0; j < digits [i]; j ++) { + printf ("%zu", i); + } + } + printf ("%d\n", last); + + } + free (line); + + return (0); +} diff --git a/challenge-115/abigail/lua/ch-2.lua b/challenge-115/abigail/lua/ch-2.lua new file mode 100644 index 0000000000..4b92535d53 --- /dev/null +++ b/challenge-115/abigail/lua/ch-2.lua @@ -0,0 +1,59 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + +local NR_OF_DIGITS = 10 + +for line in io . lines () do + + -- + -- Process the input, count digits + -- + local digits = {} + for i = 0, NR_OF_DIGITS - 1 + do digits [i] = 0 + end + for d in line : gmatch ("%d") + do d = tonumber (d) + digits [d] = digits [d] + 1 + end + + -- + -- Find the lowest even digit + -- + local last = -1 + for i = NR_OF_DIGITS - 2, 0, -2 + do if digits [i] > 0 + then last = i + end + end + + -- + -- Skip if there is no even digit in the input + -- + if last < 0 + then goto end_loop + end + + digits [last] = digits [last] - 1 + + -- + -- Create output: digits from high to low + -- + local out = "" + for i = NR_OF_DIGITS - 1, 0, -1 + do for j = 1, digits [i] + do out = out .. tostring (i) + end + end + + print (out .. tostring (last)) + + ::end_loop:: +end diff --git a/challenge-115/abigail/node/ch-2.js b/challenge-115/abigail/node/ch-2.js new file mode 100644 index 0000000000..3e76bf958c --- /dev/null +++ b/challenge-115/abigail/node/ch-2.js @@ -0,0 +1,53 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-2.js < input-file +// + +let NR_OF_DIGITS = 10 + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => { + // + // Parse the input: count the digits + // + let digits = [] + for (let i = 0; i < NR_OF_DIGITS; i ++) { + digits [i] = 0 + } + _ . split (/\s+/) . map (_ => {digits [+_] ++}) + + // + // Find the smallest even number + // + let last = -1; + for (let i = 0; i < NR_OF_DIGITS && last < 0; i += 2) { + if (digits [i] > 0) { + last = i + digits [i] -- + } + } + + // + // Skip if there are no even digits in the input + // + if (last < 0) { + return + } + + // + // Create the output: print the remaining numbers from high to low + // + let out = "" + for (let i = NR_OF_DIGITS - 1; i >= 0; i --) { + for (let j = 0; j < digits [i]; j ++) { + out = out + i . toString () + } + } + console . log (out + last . toString ()) +}) diff --git a/challenge-115/abigail/perl/ch-2.pl b/challenge-115/abigail/perl/ch-2.pl new file mode 100644 index 0000000000..c0adf3617f --- /dev/null +++ b/challenge-115/abigail/perl/ch-2.pl @@ -0,0 +1,44 @@ +#!/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 +# + +my @DIGITS = (0 .. 9); +my @EVENS = grep {$_ % 2 == 0} @DIGITS; + +while (<>) { + # + # Read in data, store counts of each digit. + # + my @digits = (0) x @DIGITS; + $digits [$_] ++ for do {local $" = ""; /[@DIGITS]/g}; + + # + # The last number of the output should be the smallest + # even number in the input. If there is no even number + # in the input, skip it. + # + my ($last) = grep {$digits [$_]} @EVENS; + next unless defined $last; + $digits [$last] --; + + # + # Print the result, with the highest numbers first. + # + print join "" => map {$_ x $digits [$_]} reverse @DIGITS; + say $last; +} diff --git a/challenge-115/abigail/python/ch-2.py b/challenge-115/abigail/python/ch-2.py new file mode 100644 index 0000000000..a3b040b832 --- /dev/null +++ b/challenge-115/abigail/python/ch-2.py @@ -0,0 +1,49 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-2.py < input-file +# + +import fileinput + +NR_OF_DIGITS = 10 + +for line in fileinput . input (): + # + # Parse the input, count digits + # + digits = [] + for d in range (NR_OF_DIGITS): + digits . append (0) + for d in line . split (): + d = int (d) + digits [d] = digits [d] + 1 + + # + # Find the smallest even number + # + last = -1 + + for d in range (NR_OF_DIGITS - 2, -1, -2): + if digits [d] > 0: + last = d + + # + # If we don't have an even number, skip + # + if last < 0: + continue + digits [last] = digits [last] - 1 + + # + # Print the rest of the digits, highest to lowest + # + for d in range (NR_OF_DIGITS - 1, 0, -1): + for i in range (digits [d]): + print (d, end = '') + + print (last) diff --git a/challenge-115/abigail/ruby/ch-2.rb b/challenge-115/abigail/ruby/ch-2.rb new file mode 100644 index 0000000000..e1e41a91fd --- /dev/null +++ b/challenge-115/abigail/ruby/ch-2.rb @@ -0,0 +1,57 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-2.rb < input-file +# + +nr_of_digits = 10 + +ARGF . each_line do + |line| + # + # Read the input and count the digits + # + digits = [] + for d in 0 .. nr_of_digits - 1 do + digits [d] = 0 + end + line . split() . each do + |d| + digits [d . to_i] += 1 + end + + # + # Find the lowest even number + # + last = -1 + for i in 1 .. nr_of_digits do + d = nr_of_digits - i + if d % 2 == 0 && digits [d] > 0 + then last = d + end + end + + # + # Skip if the input does not contain an even number + # + if last < 0 + then next + end + + digits [last] -= 1 + + # + # Print the digits, highest to lowest + # + for i in 1 .. nr_of_digits do + d = nr_of_digits - i + for j in 1 .. digits [d] do + print (d) + end + end + puts (last) +end -- cgit From 2fed574178675ba5e0cf2519e2696340ee608eed Mon Sep 17 00:00:00 2001 From: Abigail Date: Tue, 1 Jun 2021 19:36:31 +0200 Subject: AWK, Bash, C, Lua, Node.js, Perl, Python and Ruby solutions for week 115, part 1 --- challenge-115/abigail/README.md | 8 ++++ challenge-115/abigail/awk/ch-1.awk | 52 ++++++++++++++++++++++ challenge-115/abigail/bash/ch-1.sh | 55 +++++++++++++++++++++++ challenge-115/abigail/c/ch-1.c | 85 ++++++++++++++++++++++++++++++++++++ challenge-115/abigail/lua/ch-1.lua | 64 +++++++++++++++++++++++++++ challenge-115/abigail/node/ch-1.js | 68 +++++++++++++++++++++++++++++ challenge-115/abigail/perl/ch-1.pl | 63 ++++++++++++++++++++++++++ challenge-115/abigail/python/ch-1.py | 51 ++++++++++++++++++++++ challenge-115/abigail/ruby/ch-1.rb | 60 +++++++++++++++++++++++++ 9 files changed, 506 insertions(+) create mode 100644 challenge-115/abigail/awk/ch-1.awk create mode 100644 challenge-115/abigail/bash/ch-1.sh create mode 100644 challenge-115/abigail/c/ch-1.c create mode 100644 challenge-115/abigail/lua/ch-1.lua create mode 100644 challenge-115/abigail/node/ch-1.js create mode 100644 challenge-115/abigail/perl/ch-1.pl create mode 100644 challenge-115/abigail/python/ch-1.py create mode 100644 challenge-115/abigail/ruby/ch-1.rb diff --git a/challenge-115/abigail/README.md b/challenge-115/abigail/README.md index 0d966f083c..725668ba25 100644 --- a/challenge-115/abigail/README.md +++ b/challenge-115/abigail/README.md @@ -19,6 +19,14 @@ Output: 0 as we can't form circle. ~~~~ ### Solutions +* [AWK](awk/ch-1.awk) +* [Bash](bash/ch-1.sh) +* [C](c/ch-1.c) +* [Lua](lua/ch-1.lua) +* [Node.js](node/ch-1.js) +* [Perl](perl/ch-1.pl) +* [Python](python/ch-1.py) +* [Ruby](ruby/ch-1.rb) ### Blog [String Chain](https://abigail.github.io/HTML/Perl-Weekly-Challenge/week-115-1.html) diff --git a/challenge-115/abigail/awk/ch-1.awk b/challenge-115/abigail/awk/ch-1.awk new file mode 100644 index 0000000000..4ed9aae508 --- /dev/null +++ b/challenge-115/abigail/awk/ch-1.awk @@ -0,0 +1,52 @@ +#!/usr/bin/awk + +# +# See ../README.md +# + +# +# Run as: awk -f ch-1.awk < input-file +# + +{ + # + # Read the input, turn in into a graph: + # The first and last characters of the strings are the nodes. + # There is a directed edge in the graph from the first to the + # last character of a string. + # + delete graph + delete nodes + for (i = 1; i <= NF; i ++) { + first = substr ($i, 1, 1) + last = substr ($i, length ($i)) + graph [first, last] = 1 + nodes [first] = 1 + nodes [last] = 1 + } + + # + # Calculate the transitive closure using the Floyd-Warshall algorithm. + # + for (k in nodes) { + for (i in nodes) { + for (j in nodes) { + if (graph [k, j] > 0 && graph [i, k] > 0) { + graph [i, j] = 1 + } + } + } + } + + # + # There's a loop iff there is a node which is reachable from itself. + # + out = 0 + for (i in nodes) { + if (graph [i, i] > 0) { + out = 1 + } + } + + print (out) +} diff --git a/challenge-115/abigail/bash/ch-1.sh b/challenge-115/abigail/bash/ch-1.sh new file mode 100644 index 0000000000..989e4d1cce --- /dev/null +++ b/challenge-115/abigail/bash/ch-1.sh @@ -0,0 +1,55 @@ +#!/bin/sh + +# +# See ../README.md +# + +# +# Run as: bash ch-1.sh < input-file +# + +declare -A nodes +declare -A graph + +while read -a strings +do nodes=() + graph=() + # + # Read in the strings. Build a graph where the first and last + # characters of the strings are the nodes, and for each string + # we have a directed edge from the first character to its last. + # + for string in ${strings[@]} + do first=${string:0:1} + last=${string:$((${#string}-1)):1} + nodes[$first]=1 + nodes[$last]=1 + graph[$first$last]=1 + done + + # + # Calculate the transitive closure using the Floyd-Warshall algorithm. + # + for k in ${!nodes[@]} + do for i in ${!nodes[@]} + do for j in ${!nodes[@]} + do if [ X${graph[$k$j]} == X1 -a \ + X${graph[$i$k]} == X1 ] + then graph[$i$j]=1 + fi + done + done + done + + # + # There's a cycle iff there's a node which is reachable from itself. + # + out=0 + for i in ${!nodes[@]} + do if [ X${graph[$i$i]} == X1 ] + then out=1 + fi + done + + echo $out +done diff --git a/challenge-115/abigail/c/ch-1.c b/challenge-115/abigail/c/ch-1.c new file mode 100644 index 0000000000..b05a16a44f --- /dev/null +++ b/challenge-115/abigail/c/ch-1.c @@ -0,0 +1,85 @@ +# include +# include +# include +# include +# include + +/* + * See ../README.md + */ + +/* + * Run as: cc -o ch-1.o ch-1.c; ./ch-1.o < input-file + */ +# define NR_OF_LETTERS ('z' - 'a' + 1) + +int main (void) { + char * line = NULL; + size_t len = 0; + size_t str_len; + + bool graph [NR_OF_LETTERS] [NR_OF_LETTERS]; + + while ((str_len = getline (&line, &len, stdin)) != -1) { + char * line_ptr = line; + + /* + * Initialize the matrix to all false + */ + for (size_t i = 0; i < NR_OF_LETTERS; i ++) { + for (size_t j = 0; j < NR_OF_LETTERS; j ++) { + graph [i] [j] = false; + } + } + + /* + * Scan the input line for beginning and end letters; + * build a graph out of them. + */ + while (*line_ptr) { + while (*line_ptr && !islower (*line_ptr)) { + line_ptr ++; /* Skip whitespace */ + } + if (!*line_ptr) { + break; /* End of string reached */ + } + char start = *line_ptr; + char end = *line_ptr ++; + while (*line_ptr && islower (*line_ptr)) { + end = *line_ptr ++; + } + graph [start - 'a'] [end - 'a'] = true; + } + + /* + * Create the transistive closure of the graph using + * the Floyd Warshall algorithm. + */ + for (size_t k = 0; k < NR_OF_LETTERS; k ++) { + for (size_t i = 0; i < NR_OF_LETTERS; i ++) { + for (size_t j = 0; j < NR_OF_LETTERS; j ++) { + graph [i] [j] = graph [i] [j] || + (graph [k] [j] && graph [i] [k]); + } + } + } + + /* + * We have a loop if there is at least one node which can + * be reached from itself. + */ + short out = 0; + for (size_t i = 0; i < NR_OF_LETTERS; i ++) { + if (graph [i] [i]) { + out = 1; + break; + } + } + + printf ("%d\n", out); + + } + free (line); + + return (0); +} diff --git a/challenge-115/abigail/lua/ch-1.lua b/challenge-115/abigail/lua/ch-1.lua new file mode 100644 index 0000000000..650c2e1c1b --- /dev/null +++ b/challenge-115/abigail/lua/ch-1.lua @@ -0,0 +1,64 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-1.lua < input-file +-- + +for line in io . lines () do + local graph = {} + local nodes = {} + for s in line : gmatch ("%S+") + do local first = s : sub ( 1, 1) + local last = s : sub (-1, -1) + if graph [first] == nil + then graph [first] = {} + end + graph [first] [last] = 1 + nodes [first] = 1 + nodes [last] = 1 + end + + -- + -- Make sure all entries exists, as lua doesn't autovivify + -- + for node1 in pairs (nodes) + do for node2 in pairs (nodes) + do if graph [node1] == nil + then graph [node1] = {} + end + if graph [node1] [node2] == nil + then graph [node1] [node2] = 0 + end + end + end + + -- + -- Calculate the transitive closure + -- + for k in pairs (nodes) + do for i in pairs (nodes) + do for j in pairs (nodes) + do if graph [i] [j] == 0 and graph [k] [j] == 1 and + graph [i] [k] == 1 + then graph [i] [j] = 1 + end + end + end + end + + -- + -- We have a loop iff there is a node which is reachable from itself + -- + local out = 0 + for i in pairs (nodes) + do if graph [i] [i] == 1 + then out = 1 + end + end + + print (out) +end diff --git a/challenge-115/abigail/node/ch-1.js b/challenge-115/abigail/node/ch-1.js new file mode 100644 index 0000000000..184192256c --- /dev/null +++ b/challenge-115/abigail/node/ch-1.js @@ -0,0 +1,68 @@ +#!/usr/local/bin/node + +// +// See ../README.md +// + +// +// Run as: node ch-1.js < input-file +// + + require ('readline') +. createInterface ({input: process . stdin}) +. on ('line', _ => check_for_cycl (_)) +; + + +function check_for_cycl (line) { + // + // Read in the data, build a graph where the first and last + // characters of the strings form the nodes, and we have a + // directed edge from the beginning to the end of a string. + // + let strings = line . split (/\s+/) + let nodes = {} // Keep track of all the nodes + let graph = {} + strings . forEach (_ => { + let first = _ . substr ( 0, 1) + let last = _ . substr (-1, 1) + nodes [first] = 1 + nodes [last] = 1 + if (!graph [first]) { + graph [first] = {} // No autovivification in Node.js + } + if (!graph [last]) { + graph [last] = {} // No autovivification in Node.js + } + graph [first] [last] = 1 // Add a node + }) + + + // + // Calculate the transitive closure of the graph using + // the Floyd-Warshall algorithm + // + nodes = Object . keys (nodes) + nodes . forEach (k => { + nodes . forEach (i => { + nodes . forEach (j => { + if (!graph [i] [j] && graph [k] [j] && graph [i] [k]) { + graph [i] [j] = 1 + } + }) + }) + }) + + // + // We have a loop iff there is at least one node which is + // reachable from itself. + // + let out = 0 + nodes . forEach (i => { + if (graph [i] [i]) { + out = 1 + } + }) + + console . log (out) +} diff --git a/challenge-115/abigail/perl/ch-1.pl b/challenge-115/abigail/perl/ch-1.pl new file mode 100644 index 0000000000..2b26121b56 --- /dev/null +++ b/challenge-115/abigail/perl/ch-1.pl @@ -0,0 +1,63 @@ +#!/opt/perl/bin/perl + +use 5.032; + +use strict; +use warnings; +no warnings 'syntax'; + +use experimental 'signatures'; +use experimental 'lexical_subs'; + +# +# I usually don't use stuff from CPAN which implements most or +# all of the challenge, but I do make an exception for modules +# I authored myself. Even if it's from 1998. +# +use Algorithm::Graphs::TransitiveClosure qw [floyd_warshall]; + +# +# See ../README.md +# + +# +# Run as: perl ch-1.pl < input-file +# + +# +# The challenge description doesn't make it clear whether we're +# looking for a cycle consisting of all strings, or whether +# any loop is sufficient. As is often the case, the examples aren't helpful, +# as they either contain cycles with all strings, or without any cycles. +# +# We will output 1 if there is *any* cycle. Including looping back to +# itself. So, if the input contains the word "eye", we will return 1. +# + +while (<>) { + # + # Read in the words, store them bucketed by first letter, + # and in a list. We're assuming each set is on a separate + # line separated by white space. + # + # We will create a (directed) graph from the strings in a + # set; each string gives us an edge from the first letter + # of the string to the last letter. (Hence, the nodes in + # this graph are the first and last letters of the strings). + # + my $graph; + foreach my $node (split) { + $$graph {substr $node, 0, 1} {substr $node, -1} = 1; + } + + # + # Calculate the transitive closure. + # + floyd_warshall $graph; + + # + # We do have a loop iff we have a node which can reach itself. + # + say grep ({$$graph {$_} {$_}} keys %$graph) ? 1 : 0; +} + diff --git a/challenge-115/abigail/python/ch-1.py b/challenge-115/abigail/python/ch-1.py new file mode 100644 index 0000000000..25e5541513 --- /dev/null +++ b/challenge-115/abigail/python/ch-1.py @@ -0,0 +1,51 @@ +#!/opt/local/bin/python + +# +# See ../README.md +# + +# +# Run as: python ch-1.py < input-file +# + +import fileinput + +for line in fileinput . input (): + # + # Read in the data; create a graph: the first and last character + # of each string are the nodes, and there is a directed edge + # from the beginning to the end of the string. + # + strings = line . split () + nodes = {} + graph = {} + for string in strings: + first = string [:1] + last = string [-1:] + nodes [first] = 1 + nodes [last] = 1 + if not first in graph: + graph [first] = {} + if not last in graph: + graph [last] = {} + graph [first] [last] = 1 + + # + # Calculate the transitive closure using Floyd-Warshall + # + for k in nodes: + for i in nodes: + for j in nodes: + if not j in graph [j]: + if k in graph [i] and j in graph [k]: + graph [i] [j] = 1 + + # + # There is a cycle iff at least one node can be reached from itself + # + out = 0 + for i in nodes: + if i in graph [i]: + out = 1 + + print (out) diff --git a/challenge-115/abigail/ruby/ch-1.rb b/challenge-115/abigail/ruby/ch-1.rb new file mode 100644 index 0000000000..0ddb500b8d --- /dev/null +++ b/challenge-115/abigail/ruby/ch-1.rb @@ -0,0 +1,60 @@ +#!/usr/bin/ruby + +# +# See ../README.md +# + +# +# Run as: ruby ch-1.rb < input-file +# + +ARGF . each_line do + |line| + # + # Read the data; turn the strings into a graph, where the first + # and last character of each string are the nodes, and we have + # a directed edge from the beginning to the end of a string. + # + nodes = {} + graph = {} + line . split . each do + |string| + first = string [0, 1] + last = string [-1, 1] + nodes [first] = 1 + nodes [last] = 1 + graph [first] ||= {} + graph [last] ||= {} + graph [first] [last] = 1 + end + + # + # Calculate the transitive closure of the graph using the + # Floyd Warshall algorithm. + # + nodes . each do + |k, _| + nodes . each do + |i, _| + nodes . each do + |j, _| + if graph [i] [k] and graph [k] [j] + then graph [i] [j] = 1 + end + end + end + end + + # + # We have a loop iff there is node which is reachable from itself. + # + out = 0 + nodes . each do + |i, _| + if graph [i] [i] + then out = 1 + end + end + + puts (out) +end -- cgit