AWK, Bash, C, Lua, Node.js, Perl, Python and Ruby solutions for week 115, part 1

9 files changed, 506 insertions, 0 deletions

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 <stdlib.h>
+# include <stdio.h>
+# include <string.h>
+# include <stdbool.h>
+# include <ctype.h>
+
+/*
+ * 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