From f5048725469c295efaea25be5a1d3ea41fb3eaa6 Mon Sep 17 00:00:00 2001 From: boblied Date: Thu, 20 Aug 2020 07:51:51 -0500 Subject: Solutions for both tasks --- challenge-074/bob-lied/README | 15 +++++++++++ challenge-074/bob-lied/perl/ch-1.pl | 8 +++++- challenge-074/bob-lied/perl/ch-2.pl | 11 +++++++- challenge-074/bob-lied/perl/lib/FNR.pm | 31 ++++++++++++---------- challenge-074/bob-lied/perl/lib/MajorityElement.pm | 19 ++++++------- challenge-074/bob-lied/perl/t/FNR.t | 8 +++++- challenge-074/bob-lied/perl/t/MajorityElement.t | 6 ++++- 7 files changed, 69 insertions(+), 29 deletions(-) diff --git a/challenge-074/bob-lied/README b/challenge-074/bob-lied/README index 289b995df4..e3712fbb10 100644 --- a/challenge-074/bob-lied/README +++ b/challenge-074/bob-lied/README @@ -6,8 +6,12 @@ https://perlweeklychallenge.org/blog/perl-weekly-challenge-074/ ** Initial thoughts +This is going to be an exercise in hashes and grep. + ** Post Solution Thoughts +Use a hash to count to count elements, then use grep with a code block to select the match. + ** Problem Statement You are given an array of integers of size $N. @@ -20,8 +24,19 @@ Majority element in the list is the one that appears more than floor(size_of_lis ** Initial Thoughts +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 +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 string $S. diff --git a/challenge-074/bob-lied/perl/ch-1.pl b/challenge-074/bob-lied/perl/ch-1.pl index 57201dd4ff..fd0a1a51ee 100644 --- a/challenge-074/bob-lied/perl/ch-1.pl +++ b/challenge-074/bob-lied/perl/ch-1.pl @@ -9,11 +9,17 @@ #============================================================================= # 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 th one that appears more than floor($N/2). +# 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 index 64b3a88739..6dbfa34667 100644 --- a/challenge-074/bob-lied/perl/ch-2.pl +++ b/challenge-074/bob-lied/perl/ch-2.pl @@ -17,10 +17,19 @@ # 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" then FNR is 'c' +# 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 index c0cbae378d..ba53ff2f68 100644 --- a/challenge-074/bob-lied/perl/lib/FNR.pm +++ b/challenge-074/bob-lied/perl/lib/FNR.pm @@ -4,7 +4,7 @@ #============================================================================= # Copyright (c) 2020, Bob Lied #============================================================================= -# Description: +# Description: #============================================================================= package FNR; @@ -14,24 +14,27 @@ use warnings; require Exporter; our @ISA = qw(Exporter); -our @EXPORT = qw(); +our @EXPORT = qw(firstNonRepeat); our @EXPORT_OK = qw(); -sub new -{ - my $class = shift; - my $class = ref($class) || $class; - my $self = { - _name1 = $_[0], - }; - bless $self, $class; - return $self; -} - -sub FNR +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; } diff --git a/challenge-074/bob-lied/perl/lib/MajorityElement.pm b/challenge-074/bob-lied/perl/lib/MajorityElement.pm index 8a7dcb0192..a5c91ece97 100644 --- a/challenge-074/bob-lied/perl/lib/MajorityElement.pm +++ b/challenge-074/bob-lied/perl/lib/MajorityElement.pm @@ -17,21 +17,18 @@ our @ISA = qw(Exporter); our @EXPORT = qw(majorityElement); our @EXPORT_OK = qw(); -sub new -{ - my $class = shift; - my $class = ref($class) || $class; - my $self = { - _name1 = $_[0], - }; - bless $self, $class; - return $self; -} - 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; } diff --git a/challenge-074/bob-lied/perl/t/FNR.t b/challenge-074/bob-lied/perl/t/FNR.t index 1d4fdd9472..dab6d0d82d 100644 --- a/challenge-074/bob-lied/perl/t/FNR.t +++ b/challenge-074/bob-lied/perl/t/FNR.t @@ -8,7 +8,13 @@ use warnings; use Test2::V0; -use lib "../lib"; 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 index 7d1b4a22d8..e6d825cd38 100644 --- a/challenge-074/bob-lied/perl/t/MajorityElement.t +++ b/challenge-074/bob-lied/perl/t/MajorityElement.t @@ -8,7 +8,11 @@ use warnings; use Test2::V0; -use lib "../lib"; 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(); -- cgit