Merge pull request #2113 from boblied/master

Solutions for challenge 074

7 files changed, 206 insertions, 42 deletions

diff --git a/challenge-074/bob-lied/README b/challenge-074/bob-lied/README
index be171d638e..e3712fbb10 100644
--- a/challenge-074/bob-lied/README
+++ b/challenge-074/bob-lied/README
@@ -1,65 +1,53 @@
-Solutions to weekly challenge 72 by Bob Lied.
+Solutions to weekly challenge 74 by Bob Lied.
 
-https://perlweeklychallenge.org/blog/perl-weekly-challenge-072/
+https://perlweeklychallenge.org/blog/perl-weekly-challenge-074/
 
-This week, I would like to add two personal elements to the problem:
-(1) create a template for perl-vim that sets up these weekly challenges
-(includes Test::More, a skeleton for checking ARGV, and whatever else
-is quickly becoming a pattern; and (2) use a github issue in the submission
-process, just to learn more about using git and github.
-
-* TASK #1 > Trailing Zeroes
+* TASK #1 > Majority Element
 
 ** Initial thoughts
 
-Too easy, unless I'm missing something.  The result gets a zero on the end every time
-it's multiplied by 10, and since we're doing factorials, that will happen every time N
-rolls past a multiple of 5.  The answer is int(N/5), I think, but I'll need to convince
-myself completely.
-
-We could make it a little tougher by actually calculating N!, and maybe using Memoize
-as an optimization.  And maybe finding out how high N can be until overflow or waiting time
-make it impractical.
+This is going to be an exercise in hashes and grep.
 
 ** Post Solution Thoughts
 
-Yep, it was really that easy.  I implemented the factorial using Memoize just
-for fun.  The highest number that didn't roll over to floating point was 20!.
-
+Use a hash to count to count elements, then use grep with a code block to select the match.
 
 ** Problem Statement
 
-You are given a positive integer $N (<= 10).
+You are given an array of integers of size $N.
+Write a script to find the majority element. If none found then print -1.
+Majority element in the list is the one that appears more than floor(size_of_list/2).
+
 
-Write a script to print number of trailing zeroes in $N!.
 
-* TASK #2 > Lines Range
+* TASK #2 > FNR Character
 
 ** Initial Thoughts
 
-This has come up often enough that I know I've done it in sed and awk; and in
-a pipeline with head and tail.  The flip-flop operator comes to mind, but
-there'll be some experimentation for boundary conditions.  Also some test
-cases for A or B being outside the range of the file or having an empty file.
+The specification is a little odd and doesn't match the example.  But, OK, whatever.
+Similar to the first task, another hash to count occurrences and grep to find the answers.
 
 ** Post Solution Thoughts
 
-The hardest part of this turned out to be how to set up tests.  I wanted the
-testing to be self-contained, so I put the test data into __DATA__.  But then
-re-reading that repeatedly for different tests required seeking back to the
-start and also resetting $.  A couple of trips to Google there.
-
-I also wanted to capture the output in a variable and not just print to the
-console.  I knew that a string could be opened as a file handle using a
-reference to the string.  It should have been easy; but I spent a long time
-debugging before I realized that I had typed \&TestResult instead of
-\$TestResult.
+Going through the string could be either done with substr one character at a time,
+or splitting the string into an array of characters.  Finding the first char could be
+a search through the character positions, or a sort and picking off the first element.
+Sort is the easy answer, but I'm always wary of scaling.  Like in many of these
+problems, it's not an issue for "reasonable" strings, but could become a performance
+question if the strings were a thousand or a million times bigger.
 
 
 ** Problem Statement
 
-You are given a text file name $file and range $A - $B where $A <= $B.
-
-Write a script to display lines range $A and $B in the given file.
-
-(That's A and B inclusive, from the examples.)
+You are given a string $S.
+
+Write a script to print the series of first non-repeating character
+(left -> right) for the given string. Print # if none found.
+Example 1
+Input: $S = ‘ababc’
+Output: ‘abb#c’
+Pass 1: “a”, the FNR character is ‘a’
+Pass 2: “ab”, the FNR character is ‘b’
+Pass 3: “aba”, the FNR character is ‘b’
+Pass 4: “abab”, no FNR found, hence ‘#’
+Pass 5: “ababc” the FNR character is ‘c’
diff --git a/challenge-074/bob-lied/perl/ch-1.pl b/challenge-074/bob-lied/perl/ch-1.pl
new file mode 100644
index 0000000000..fd0a1a51ee
--- /dev/null
+++ b/challenge-074/bob-lied/perl/ch-1.pl
@@ -0,0 +1,25 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-1.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge 074 Task #1 > Majority Element
+#=============================================================================
+# You are given an array of integers of size $N.
+# Write a script to find the majority element.  If none found, then print -1.
+# Majority element in the list is the one that appears more than floor($N/2).
+
+use strict;
+use warnings;
+use feature qw(say);
+
+use lib "lib";
+use MajorityElement;
+
+my @ARR = @ARGV;
+
+die "Give a list of integers" unless @ARR;
+
+say majorityElement(@ARR);
diff --git a/challenge-074/bob-lied/perl/ch-2.pl b/challenge-074/bob-lied/perl/ch-2.pl
new file mode 100644
index 0000000000..6dbfa34667
--- /dev/null
+++ b/challenge-074/bob-lied/perl/ch-2.pl
@@ -0,0 +1,35 @@
+#!/usr/bin/env perl
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# ch-2.pl
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Perl Weekly Challenge Task #2 > FNR Character
+#=============================================================================
+# You are given a string $S.
+# Write a script to print the series of first non-repeating character (left
+# to right) for the given string.  Print # if none found
+# Example:
+# Input: $S = 'ababc'
+# Output: 'abb#c'
+# Pass 1: "a"     the FNR character is 'a'
+# Pass 2: "ab"    the FNR is 'b'
+# Pass 3: "aba"   the FNR is 'b'
+# Pass 4: "abab"  the FNR is '#' (all chars repeat)
+# Pass 5: "ababc" the FNR is 'c'
+#
+# Note that this example is actually taking the right-most character as
+# the first non-repeater, which is counter-intuitive to the specification.
+
+use strict;
+use warnings;
+
+use lib "lib";
+use FNR qw(firstNonRepeat);
+
+my $S = shift;
+
+die "Need a string" unless $S;
+
+say firstNonRepeat($S);
diff --git a/challenge-074/bob-lied/perl/lib/FNR.pm b/challenge-074/bob-lied/perl/lib/FNR.pm
new file mode 100644
index 0000000000..ba53ff2f68
--- /dev/null
+++ b/challenge-074/bob-lied/perl/lib/FNR.pm
@@ -0,0 +1,42 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# FNR.pm
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Description: 
+#=============================================================================
+
+package FNR;
+
+use strict;
+use warnings;
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw(firstNonRepeat);
+our @EXPORT_OK = qw();
+
+sub firstNonRepeat
+{
+    my ($s) = @_;
+    my $result = "";
+    my %charData;   # Save position and count of letters
+
+    for my $i ( 0 .. length($s)-1 )
+    {
+        my $char = substr($s, $i, 1);
+        $charData{$char}{cnt}++;
+        $charData{$char}{pos} = $i unless exists $charData{$char}{pos};
+
+        # Select non-repeating characters and sort by position
+        my @nr = sort { $charData{$a}{pos} lt $charData{$b}{pos} }
+                    grep { $charData{$_}{cnt} == 1 } keys %charData;
+
+        $result .= $nr[0] // '#';
+    }
+
+    return $result;
+}
+
+1;
diff --git a/challenge-074/bob-lied/perl/lib/MajorityElement.pm b/challenge-074/bob-lied/perl/lib/MajorityElement.pm
new file mode 100644
index 0000000000..a5c91ece97
--- /dev/null
+++ b/challenge-074/bob-lied/perl/lib/MajorityElement.pm
@@ -0,0 +1,36 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#=============================================================================
+# MajorityElement.pm
+#=============================================================================
+# Copyright (c) 2020, Bob Lied
+#=============================================================================
+# Description:
+#=============================================================================
+
+package MajorityElement;
+
+use strict;
+use warnings;
+
+require Exporter;
+our @ISA = qw(Exporter);
+our @EXPORT = qw(majorityElement);
+our @EXPORT_OK = qw();
+
+sub majorityElement
+{
+    my (@arr) = @_;
+    my $result = -1;
+    my %presence;
+    my $majorityThreshold = int(scalar(@arr)/2);
+
+    # Count the repetitions.
+    $presence{$_}++ foreach @arr;
+
+    # Select the one that passes the threshold.  There can only be one or none.
+    $result = (grep { $presence{$_} > $majorityThreshold } keys %presence)[0] // -1;
+
+    return $result;
+}
+
+1;
diff --git a/challenge-074/bob-lied/perl/t/FNR.t b/challenge-074/bob-lied/perl/t/FNR.t
new file mode 100644
index 0000000000..dab6d0d82d
--- /dev/null
+++ b/challenge-074/bob-lied/perl/t/FNR.t
@@ -0,0 +1,20 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#===============================================================================
+# FILE: FNR.t
+#===============================================================================
+
+use strict;
+use warnings;
+
+use Test2::V0;
+
+use FNR;
+
+is( firstNonRepeat('ababc'),
+                   'abb#c',    "Example 1");
+is( firstNonRepeat('xyzzyx'),
+                   'xyzyx#', "Example 2 as given");
+#is( firstNonRepeat('xyzzyx'),
+#                   'xxxxx#', "Example 2 as specified");
+
+done_testing();
diff --git a/challenge-074/bob-lied/perl/t/MajorityElement.t b/challenge-074/bob-lied/perl/t/MajorityElement.t
new file mode 100644
index 0000000000..e6d825cd38
--- /dev/null
+++ b/challenge-074/bob-lied/perl/t/MajorityElement.t
@@ -0,0 +1,18 @@
+# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu:
+#===============================================================================
+# FILE: MajorityElement.t
+#===============================================================================
+
+use strict;
+use warnings;
+
+use Test2::V0;
+
+use MajorityElement;
+
+is( majorityElement(1,2,2,3,2,4,2),  2, "Example 1");
+is( majorityElement(1,3,1,2,4,5),   -1, "Example 2");
+
+is( majorityElement(1),              1, "Single element");
+
+done_testing();