Merge pull request #2093 from shawnw/challenge-074-solution

Solutions for challenge 074.

7 files changed, 173 insertions, 1 deletions

diff --git a/challenge-074/shawn-wagner/README b/challenge-074/shawn-wagner/README
index 8133463776..36629c7ac2 100644
--- a/challenge-074/shawn-wagner/README
+++ b/challenge-074/shawn-wagner/README
@@ -1 +1 @@
-Solution by Shawn Wagner
+Solutions by Shawn Wagner
diff --git a/challenge-074/shawn-wagner/java/ch1.java b/challenge-074/shawn-wagner/java/ch1.java
new file mode 100644
index 0000000000..7d14236d22
--- /dev/null
+++ b/challenge-074/shawn-wagner/java/ch1.java
@@ -0,0 +1,26 @@
+// Use streams to calculate the count of distinct elements in an array and
+// filter out just the first one above the cutoff.
+
+// I'm particularly proud of this one.
+
+import java.util.*;
+import java.util.stream.*;
+import java.util.function.Function;
+
+class ch1 {
+    private static void task1(int[] a) {
+        int cutoff = (int)Math.floor(a.length / 2.0);
+        int over_cutoff =
+            Arrays.stream(a).boxed()
+            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
+            .entrySet().stream()
+            .filter(entry -> entry.getValue() > cutoff)
+            .findFirst().map(entry -> entry.getKey()).orElse(-1);
+        System.out.println(over_cutoff);
+    }
+
+    public static void main(String[] args) {
+        task1(new int[] {1, 2, 2, 3, 2, 4, 2});
+        task1(new int[] {1, 3, 1, 2, 4, 5});
+    }
+}
diff --git a/challenge-074/shawn-wagner/java/ch2.java b/challenge-074/shawn-wagner/java/ch2.java
new file mode 100644
index 0000000000..65a8a04a67
--- /dev/null
+++ b/challenge-074/shawn-wagner/java/ch2.java
@@ -0,0 +1,31 @@
+// Same algorithm as the perl version, using a LinkedHashMap to
+// preserve order of keys, and streams to avoid most loops.
+
+import java.util.*;
+
+class ch2 {
+    private static void task2(String s) {
+        ArrayList<Character> chars = new ArrayList<Character>();
+        chars.ensureCapacity(s.length());
+        s.chars().forEach(ch -> chars.add((char)ch));
+        Collections.reverse(chars);
+        StringBuilder sb = new StringBuilder();
+        while (chars.size() > 0) {
+            HashMap<Character, Integer> counts =
+                new LinkedHashMap<Character, Integer>();
+            chars.stream().forEach(ch -> counts.put(ch, counts.getOrDefault(ch, 0) + 1));
+            char fnr = counts.entrySet().stream()
+                .filter(entry -> entry.getValue() == 1)
+                .findFirst().map(entry -> entry.getKey()).orElse('#');
+            sb.append(fnr);
+            chars.remove(0);
+        }
+        sb.reverse();
+        System.out.println(sb);
+    }
+
+    public static void main(String[] args) {
+        task2("ababc");
+        task2("xyzzyx");
+    }
+}
diff --git a/challenge-074/shawn-wagner/perl/ch-1.pl b/challenge-074/shawn-wagner/perl/ch-1.pl
new file mode 100755
index 0000000000..653ad2be7e
--- /dev/null
+++ b/challenge-074/shawn-wagner/perl/ch-1.pl
@@ -0,0 +1,27 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use feature qw/say/;
+use POSIX qw/floor/;
+
+# Basic strategy: Use a hash to keep track of the number of occurences
+# of each element, and the first one that's greater than the
+# ⌊$N/2⌋ limit, display it and stop.
+
+sub task1 {
+  my @A = @_;
+
+  my $cutoff = floor(@A / 2.0);
+  my %counts;
+  for my $elem (@A) {
+    $counts{$elem}++;
+    if ($counts{$elem} > $cutoff) {
+      say $elem;
+      return;
+    }
+  }
+  say -1;
+}
+
+task1 1, 2, 2, 3, 2, 4, 2;
+task1 1, 3, 1, 2, 4, 5;
diff --git a/challenge-074/shawn-wagner/perl/ch-2.pl b/challenge-074/shawn-wagner/perl/ch-2.pl
new file mode 100755
index 0000000000..4d3e2fd78b
--- /dev/null
+++ b/challenge-074/shawn-wagner/perl/ch-2.pl
@@ -0,0 +1,34 @@
+#!/usr/bin/env perl
+use warnings;
+use strict;
+use feature qw/say/;
+use Tie::IxHash;
+
+# Iterate over the string in reverse order, dropping the last character each time.
+# Use an order-preserving hash to record frequency counts, and pick the first one that
+# is 1.
+
+sub task2 {
+  my @S = reverse split //, shift;
+  my $res = "";
+  while (@S) {
+    tie my %counts, 'Tie::IxHash';
+    for my $elem (@S) {
+      $counts{$elem}++;
+    }
+    my $found = 0;
+    while (my ($char, $count) = each %counts) {
+      if ($count == 1) {
+        $res .= $char;
+        $found = 1;
+        last;
+      }
+    }
+    $res .= "#" unless $found;
+    shift @S;
+  }
+  say scalar reverse $res;
+}
+
+task2 'ababc';
+task2 'xyzzyx';
diff --git a/challenge-074/shawn-wagner/tcl/ch-1.tcl b/challenge-074/shawn-wagner/tcl/ch-1.tcl
new file mode 100755
index 0000000000..cc475c5cb9
--- /dev/null
+++ b/challenge-074/shawn-wagner/tcl/ch-1.tcl
@@ -0,0 +1,19 @@
+#!/usr/bin/env tclsh
+
+# Just like the perl version, store counts in a hash table and stop
+# at the first over the cutoff.
+
+proc task1 args {
+    set cutoff [expr {floor([llength $args] / 2.0)}]
+    foreach elem $args {
+        dict incr counts $elem
+        if {[dict get $counts $elem] > $cutoff} {
+            puts $elem
+            return
+        }
+    }
+    puts -1
+}
+
+task1 1 2 2 3 2 4 2
+task1 1 3 1 2 4 5
diff --git a/challenge-074/shawn-wagner/tcl/ch-2.tcl b/challenge-074/shawn-wagner/tcl/ch-2.tcl
new file mode 100755
index 0000000000..6c7e698c67
--- /dev/null
+++ b/challenge-074/shawn-wagner/tcl/ch-2.tcl
@@ -0,0 +1,35 @@
+#!/usr/bin/env tclsh
+
+# Same approach as the perl version.
+# tcl dicts preserve order of keys, making it easy.
+
+proc lshift {lstv} {
+    upvar 1 $lstv lst
+    set lst [lreplace $lst 0 0]
+}
+
+proc task2 {S} {
+    set S [lreverse [split $S ""]]
+    while {[llength $S] > 0} {
+        foreach elem $S {
+            dict incr counts $elem
+        }
+        set found false
+        dict for {char count} $counts {
+            if {$count == 1} {
+                set found true
+                append res $char
+                break
+            }
+        }
+        if {!$found} {
+            append res "#"
+        }
+        unset counts
+        lshift S
+    }
+    puts [string reverse $res]
+}
+
+task2 ababc
+task2 xyzzyx