Merge pull request #3212 from Abigail/abigail/week-094

Abigail/week 094

11 files changed, 249 insertions, 44 deletions

diff --git a/challenge-094/abigail/README.md b/challenge-094/abigail/README.md
index ce16bd000c..1ab213691e 100644
--- a/challenge-094/abigail/README.md
+++ b/challenge-094/abigail/README.md
@@ -1,70 +1,58 @@
 # Solution by Abigail
 
-## Task 1: Max Points
+## Task 1: Group Anagrams
 
-You are given set of co-ordinates `@N`.
+You are given an array of strings `@S`.
 
-Write a script to count maximum points on a straight line when given
-co-ordinates plotted on 2-d plane.
+Write a script to group Anagrams together in any random order.
 
 ### Examples
-~~~~
-|
-|     x
-|   x
-| x
-+ _ _ _ _
-
-Input: (1,1), (2,2), (3,3)
-Output: 3
-
 
-|
-|
-| x       x
-|   x
-| x   x
-+ _ _ _ _ _
+#### Example 1
+~~~~
+Input: ("opt", "bat", "saw", "tab", "pot", "top", "was")
+Output: [ ("bat", "tab"),
+          ("saw", "was"),
+          ("top", "pot", "opt") ]
+~~~~
 
-Input: (1,1), (2,2), (3,1), (1,3), (5,3)
-Output: 3
+#### Example 2
+~~~~
+Input: ("x")
+Output: [ ("x") ]
 ~~~~
 
+
 ### Solutions
+* [Node](node/ch-1.js)
 * [Perl](perl/ch-1.pl)
 
 
 
-## Task 2: Sum Path
+## Task 2: Binary Tree to Linked List
 
-You are given binary tree containing numbers `0-9` only.
+You are given a binary tree.
 
-Write a script to sum all possible paths from root to leaf.
+Write a script to represent the given binary tree as an object and
+flatten it to a linked list object. Finally print the linked list
+object.
 
 ### Examples
-~~~~
-Input:
-     1
-    /
-   2
-  / \
- 3   4
-
-Output: 13
-~~~~
-as sum two paths (1->2->3) and (1->2->4)
 
+#### Example 1
 ~~~~
 Input:
-     1
-    / \
-   2   3
-  /   / \
- 4   5   6
-
-Output: 26
+    1
+   / \
+  2   3
+ / \
+4   5
+   / \
+  6   7
+
+Output:
+    1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3
 ~~~~
-as sum three paths (1->2->4), (1->3->5) and (1->3->6)
 
 ### Solutions
 * [Perl](perl/ch-2.pl)
diff --git a/challenge-094/abigail/node/ch-1.js b/challenge-094/abigail/node/ch-1.js
new file mode 100644
index 0000000000..d790d52c0a
--- /dev/null
+++ b/challenge-094/abigail/node/ch-1.js
@@ -0,0 +1,44 @@
+//
+// Call as "node ch-1.js < ../t/input-1-X", for suitable X.
+//
+  require      ("fs")
+. readFileSync (0)               // Read all.
+. toString     ()                // Turn it into a string.
+. split        ("\n")            // Split on newlines.
+. filter       (_ => _ . length) // Filter out empty lines.
+    //
+    // Split each line on ', ', and remove the double quotes.
+    // We now have a list of words.
+    //
+. map          (_ => _ . split (/,\s*/)
+                       . map   (_ => _ . replace (/"/g, ''))
+               )
+    //
+    // Iterate over the list of words, find the canonical representation
+    // of each word (characters sorted), and store the words in a hash,
+    // keyed by their canonical representation. 
+    //
+. map          (_ => _ . reduce ((hash, word) => {
+                               let key = word . split ("")
+                                              . sort  ()
+                                              . join  ("");
+                               hash [key] = hash [key] || [];
+                               hash [key] . push (word);
+                               return (hash);
+                         }, {})
+               )
+    //
+    // Print the results: sorted by key, the words in the order
+    // of the input. Each word will be surrounded by double quotes
+    // and separated by commas.
+    //
+. map          (hash => Object . keys (hash)
+                               . sort ()
+                               . forEach (_ => {
+                                     console . log (
+                                         hash [_] . map (_ => '"' + _ + '"')
+                                                  . join (", ")
+                                         )
+                                 })
+               )
+;
diff --git a/challenge-094/abigail/perl/ch-1.pl b/challenge-094/abigail/perl/ch-1.pl
new file mode 100644
index 0000000000..c2fd0ddf8a
--- /dev/null
+++ b/challenge-094/abigail/perl/ch-1.pl
@@ -0,0 +1,38 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+while (<>) {
+    my %anagrams;
+    #
+    # Iterate over the words. We're assuming all the words are on
+    # a single line, and the words don't contain a double quote.
+    # (If we can't assume this, we could use a CSV parser instead).
+    #
+    foreach my $word (/"([^"]+)"/g) {
+        #
+        # Normalize each word: split into characters, sort them, join them.
+        # Note that we're splitting on characters, not graphemes, nor
+        # do we normalize the input. This may lead to unexpected results
+        # when using accented letters and/or combining characters. But
+        # that's what you get when using poor specifications.
+        #
+        my $normalized = join "" => sort split // => $word;
+        push @{$anagrams {$normalized}} => $word;
+    }
+    #
+    # Print them. We make this deterministic, so we can easily write tests
+    #
+    foreach my $key (sort keys %anagrams) {
+        say join ", " => map {qq {"$_"}} @{$anagrams {$key}};
+    }
+}
+
+__END__
diff --git a/challenge-094/abigail/perl/ch-2.pl b/challenge-094/abigail/perl/ch-2.pl
new file mode 100644
index 0000000000..a05c21f735
--- /dev/null
+++ b/challenge-094/abigail/perl/ch-2.pl
@@ -0,0 +1,123 @@
+#!/opt/perl/bin/perl
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+#
+# Run as "perl ch-2.pl < ../t/input-2-X", for suitable X.
+#
+
+#
+# A bit of a silly exercise to turn a tree into a linked list, then just
+# print the linked list. The linked list feels like a pointless detour;
+# traversing the tree inorderly leads to the same result.
+#
+
+my $T_LEFT  = 0;
+my $T_VALUE = 1;
+my $T_RIGHT = 2;
+my $L_VALUE = 0;
+my $L_NEXT  = 1;
+
+#
+# Turn the tree into a linked list; returns the head and end of the linked list.
+#
+sub inorder ($tree) {
+    return unless @$tree;   # Leaf, so no list.
+    
+    #
+    # Recurse
+    #
+    my ($left_head,  $left_tail)  = inorder ($$tree [$T_LEFT]);
+    my ($right_head, $right_tail) = inorder ($$tree [$T_RIGHT]);
+
+    #
+    # Create head of list; let tail point to this.
+    #
+    my $head = [];
+      $$head [$L_VALUE] = $$tree [$T_VALUE];
+    my $tail = $head;
+
+    #
+    # If either child is non-empty, add this to the list; update
+    # the tail if necessary.
+    #
+    if ($left_head) {
+        $$tail [$L_NEXT] = $left_head;
+        $tail            = $left_tail;
+    }
+    if ($right_head) {
+        $$tail [$L_NEXT] = $right_head;
+        $tail            = $right_tail;
+    }
+
+    #
+    # Return head and tail
+    #
+    ($head, $tail);
+}
+
+#
+# Flatten a linked list, recursively.
+#
+sub flatten ($list) {
+    $list ? ($$list [$L_VALUE], flatten ($$list [$L_NEXT])) : ();
+}
+
+#
+# Print the list: first flatten it, then print the result.
+#
+sub print_ll ($list) {
+    say join " -> " => flatten $list;
+}
+
+#
+# Did not want to parse the input as given in the example, it is not enough
+# to deduce how the input looks like in general -- for instance, if we have
+# a root with two children, which each has two children, how is it going to
+# look? 
+#
+# So, we're assuming the following grammar for a tree, in pseudo BNF:
+#
+#     value = [0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9] +
+#     tree  = '[' [ <tree> <value> <tree> ] ']'
+#
+# That is, leaf nodes look like '[]', and regular nodes consist of a tree,
+# followed by a value, followed by a tree, all surrounded by brackets.
+#
+
+while (<>) {
+    chomp;
+    my $count = 0;
+    my %cache;
+    #
+    # Parse the input, build a tree bottom to top.
+    #
+    # As long as we have something of the form:
+    #
+    #     [] or
+    #     [ Tnnn vvv Tmmm],  where Tnnn/Tmmm are a "T" followed by a
+    #                        number, and vvv a value
+    #
+    # we replace it by Tppp, where ppp is the next available number. We also
+    # add an entry Tppp to a cache, where $cache {Tppp} = [] in the former case,
+    # and $cache {Tppp} = [$cache {Tnnn}, vvv, $cache {Tmmm}] in the latter.
+    #
+    1 while s {\[ \s* (?:(T[0-9]+) \s+ ([0-9]+) \s+ (T[0-9]+))? \s* \]}
+              { $count ++;
+                $cache {"T$count"} = $1 ? [$cache {$1}, $2, $cache {$3}] : [];
+               "T$count"}ex;
+    #
+    # Final tree is now in the cache with key "T$count".
+    #
+    print_ll +(inorder $cache {"T$count"}) [0];  # Inorder returns two values,
+                                                 # we need only the first one.
+}
+
+__END__
diff --git a/challenge-094/abigail/t/ctest.ini b/challenge-094/abigail/t/ctest.ini
new file mode 100644
index 0000000000..a103f94dae
--- /dev/null
+++ b/challenge-094/abigail/t/ctest.ini
@@ -0,0 +1,4 @@
+[names]

+1-1 = Example 1

+1-2 = Example 2

+2-1 = Example 1

diff --git a/challenge-094/abigail/t/input-1-1 b/challenge-094/abigail/t/input-1-1
new file mode 100644
index 0000000000..b2536d46f1
--- /dev/null
+++ b/challenge-094/abigail/t/input-1-1
@@ -0,0 +1 @@
+"opt", "bat", "saw", "tab", "pot", "top", "was"
diff --git a/challenge-094/abigail/t/input-1-2 b/challenge-094/abigail/t/input-1-2
new file mode 100644
index 0000000000..92232f694a
--- /dev/null
+++ b/challenge-094/abigail/t/input-1-2
@@ -0,0 +1 @@
+"x"
diff --git a/challenge-094/abigail/t/input-2-1 b/challenge-094/abigail/t/input-2-1
new file mode 100644
index 0000000000..7684932fbb
--- /dev/null
+++ b/challenge-094/abigail/t/input-2-1
@@ -0,0 +1 @@
+[[[[] 4 []] 2 [[[] 6 []] 5 [[] 7 []]]] 1 [[] 3 []]]
diff --git a/challenge-094/abigail/t/output-1-1.exp b/challenge-094/abigail/t/output-1-1.exp
new file mode 100644
index 0000000000..b0b271a69f
--- /dev/null
+++ b/challenge-094/abigail/t/output-1-1.exp
@@ -0,0 +1,3 @@
+"bat", "tab"
+"saw", "was"
+"opt", "pot", "top"
diff --git a/challenge-094/abigail/t/output-1-2.exp b/challenge-094/abigail/t/output-1-2.exp
new file mode 100644
index 0000000000..92232f694a
--- /dev/null
+++ b/challenge-094/abigail/t/output-1-2.exp
@@ -0,0 +1 @@
+"x"
diff --git a/challenge-094/abigail/t/output-2-1.exp b/challenge-094/abigail/t/output-2-1.exp
new file mode 100644
index 0000000000..cfb75dc579
--- /dev/null
+++ b/challenge-094/abigail/t/output-2-1.exp
@@ -0,0 +1 @@
+1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3