From e77f5b4c2fd92595000fb92dde051534a1ff299b Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Mon, 17 Aug 2020 19:47:14 -0400 Subject: perl solution for challenge 74 task 1 --- challenge-074/walt-mankowski/perl/ch-1.pl | 36 +++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) create mode 100644 challenge-074/walt-mankowski/perl/ch-1.pl diff --git a/challenge-074/walt-mankowski/perl/ch-1.pl b/challenge-074/walt-mankowski/perl/ch-1.pl new file mode 100644 index 0000000000..3ad5aa7da7 --- /dev/null +++ b/challenge-074/walt-mankowski/perl/ch-1.pl @@ -0,0 +1,36 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use feature qw(:5.32); +use experimental qw(signatures); + +# TASK #1 › Majority Element +# Submitted by: Mohammad S Anwar +# +# 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). +# +# Example 1 +# Input: @A = (1, 2, 2, 3, 2, 4, 2) +# Output: 2, as 2 appears 4 times in the list which is more than floor(7/2). +# +# Example 2 +# Input: @A = (1, 3, 1, 2, 4, 5) +# Output: -1 as none of the elements appears more than floor(6/2). + +my @a = @ARGV; +my $target = @a / 2; +my $result = -1; +my %cnt; + +for my $x (@a) { + if (++$cnt{$x} > $target) { + $result = $x; + last; + } +} + +say $result; -- cgit From fe25e16220e9e1b20432555ee201fc6da121058d Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Mon, 17 Aug 2020 20:03:09 -0400 Subject: perl solution for challenge 74 task 2 --- challenge-074/walt-mankowski/perl/ch-2.pl | 60 +++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 challenge-074/walt-mankowski/perl/ch-2.pl diff --git a/challenge-074/walt-mankowski/perl/ch-2.pl b/challenge-074/walt-mankowski/perl/ch-2.pl new file mode 100644 index 0000000000..01a73a12cd --- /dev/null +++ b/challenge-074/walt-mankowski/perl/ch-2.pl @@ -0,0 +1,60 @@ +#!/usr/bin/env perl +use strict; +use warnings; +use feature qw(:5.32); +use experimental qw(signatures); + +# TASK #2 › FNR Character +# Submitted by: Mohammad S Anwar +# +# 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’ +# +# Example 2 +# Input: $S = ‘xyzzyx’ +# Output: ‘xyzyx#’ +# Pass 1: “x”, the FNR character is “x” +# Pass 2: “xy”, the FNR character is “y” +# Pass 3: “xyz”, the FNR character is “z” +# Pass 4: “xyzz”, the FNR character is “y” +# Pass 5: “xyzzy”, the FNR character is “x” +# Pass 6: “xyzzyx”, no FNR found, hence ‘#’ + +my $s = $ARGV[0]; +my @c = split //, $s; +my %seen; +my @nr; +my @out; + +for my $c (@c) { + # have we seen $c before? + unless (defined $seen{$c}) { + # add $c to @nr + $seen{$c} = 1; + push @nr, $c; + } else { + # remove $c from @nr + for my $i (0..$#nr) { + if ($nr[$i] eq $c) { + splice @nr, $i, 1; + last; + } + } + } + + # now the FNR is either the last element of @nr, or # + push @out, @nr ? $nr[-1] : '#'; +} + +say join '', @out; -- cgit From 0009002a99e654fb6c1f924c9d8e0169b0ffea64 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Mon, 17 Aug 2020 20:13:03 -0400 Subject: python solution for challenge 74 task 1 --- challenge-074/walt-mankowski/python/ch-1.py | 15 +++++++++++++++ 1 file changed, 15 insertions(+) create mode 100644 challenge-074/walt-mankowski/python/ch-1.py diff --git a/challenge-074/walt-mankowski/python/ch-1.py b/challenge-074/walt-mankowski/python/ch-1.py new file mode 100644 index 0000000000..7af167d60a --- /dev/null +++ b/challenge-074/walt-mankowski/python/ch-1.py @@ -0,0 +1,15 @@ +from sys import argv +from collections import defaultdict + +a = [int(x) for x in argv[1:]] +target = len(a) / 2 +result = -1 +cnt = defaultdict(int) + +for x in a: + cnt[x] += 1 + if cnt[x] > target: + result = x + break + +print(result) -- cgit From f4168e34a79c5fe50d8831a1cdd9e91584cbab0c Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Mon, 17 Aug 2020 20:20:17 -0400 Subject: python solution for challenge 74 task 2 --- challenge-074/walt-mankowski/python/ch-2.py | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 challenge-074/walt-mankowski/python/ch-2.py diff --git a/challenge-074/walt-mankowski/python/ch-2.py b/challenge-074/walt-mankowski/python/ch-2.py new file mode 100644 index 0000000000..1c1d4e1609 --- /dev/null +++ b/challenge-074/walt-mankowski/python/ch-2.py @@ -0,0 +1,21 @@ +from sys import argv + +s = argv[1] +seen = set() +nr = [] +out = [] + +for c in s: + # have we seen c before? + if c not in seen: + # add c to nr + seen.add(c) + nr.append(c) + else: + # remove c from nr + nr.remove(c) + + # now the FNR is either the last element of nr, or # + out.append(nr[-1] if nr else '#') + +print(''.join(out)) -- cgit From 3578a4e6eb5649837c11180ba0f3c762cb469b77 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 11:38:15 -0400 Subject: c++ solution for challenge 74 task 1 --- challenge-074/walt-mankowski/cpp/ch-1.cpp | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 challenge-074/walt-mankowski/cpp/ch-1.cpp diff --git a/challenge-074/walt-mankowski/cpp/ch-1.cpp b/challenge-074/walt-mankowski/cpp/ch-1.cpp new file mode 100644 index 0000000000..ebb0563a3a --- /dev/null +++ b/challenge-074/walt-mankowski/cpp/ch-1.cpp @@ -0,0 +1,24 @@ +#include +#include +#include + +using namespace std; + +int main(int argc, char *argv[]) { + int target = (argc-1) / 2; + int result = -1; + map cnt; + + for (int i = 1; i < argc; i++) { + int x = atoi(argv[i]); + if (++cnt[x] > target) { + result = x; + break; + } + } + + cout << result << endl; +} + + + -- cgit From def033119a52ddd4a71bdc31fc2baa7adb0a7c44 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:33:55 -0400 Subject: c++ solution for challenge 74 task 2 --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 39 +++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+) create mode 100644 challenge-074/walt-mankowski/cpp/ch-2.cpp diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp new file mode 100644 index 0000000000..dc94578e19 --- /dev/null +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -0,0 +1,39 @@ +#include +#include +#include +#include + +using namespace std; + +int main(int argc, char *argv[]) { + const char *s = argv[1]; + set seen; + list nr; + char *out = new char[strlen(s)+1]; + out[strlen(s)] = '\0'; + + for (size_t i = 0; i < strlen(s); i++) { + const char c = s[i]; + + // have we seen c before? + if (seen.find(c) == seen.end()) { + seen.insert(c); + nr.push_back(c); + } else { + // remove c from nr + for (auto x = nr.begin(); x != nr.end(); x++) + if (*x == c) { + nr.erase(x); + break; + } + } + + if (nr.empty()) + out[i] = '#'; + else { + auto p = *(nr.crbegin()); + out[i] = p; + } + } + cout << out << endl; +} -- cgit From 2939a88fedf20679bde35a93e9b6c74c79d33d1d Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:47:01 -0400 Subject: use std::find() to find c in nr Nicer than doing it by hand! --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index dc94578e19..c25f4cbe62 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -2,6 +2,7 @@ #include #include #include +#include using namespace std; @@ -21,13 +22,10 @@ int main(int argc, char *argv[]) { nr.push_back(c); } else { // remove c from nr - for (auto x = nr.begin(); x != nr.end(); x++) - if (*x == c) { - nr.erase(x); - break; - } + nr.erase(find(nr.cbegin(), nr.cend(), c)); } + // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; else { -- cgit From 46ddf5d35dabc0db6e3cec7fef93e0ec554a3d7f Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:48:34 -0400 Subject: Makefile for C++ code for challenge 74 --- challenge-074/walt-mankowski/cpp/Makefile | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) create mode 100644 challenge-074/walt-mankowski/cpp/Makefile diff --git a/challenge-074/walt-mankowski/cpp/Makefile b/challenge-074/walt-mankowski/cpp/Makefile new file mode 100644 index 0000000000..0192513d07 --- /dev/null +++ b/challenge-074/walt-mankowski/cpp/Makefile @@ -0,0 +1,23 @@ +CPP = /usr/bin/c++ +INCLDIRS = +LIBDIRS = +LIBS = +CFLAGS = -std=c++17 -Wall -O3 $(INCLDIRS) +OBJECTS1 = ch-1.o +OBJECTS2 = ch-2.o + +all: ch-1 ch-2 + +%.o: %.cpp + $(CPP) $(CFLAGS) -c $< + +ch-1: $(OBJECTS1) + $(CPP) -o $@ $(OBJECTS1) $(LIBDIRS) $(LIBS) + +ch-2: $(OBJECTS2) + $(CPP) -o $@ $(OBJECTS2) $(LIBDIRS) $(LIBS) + +clean: + rm -f *~ + rm -f *.o + rm -f ch-1 ch-2 -- cgit From 8f23cc2dd5289e0a191417a13c94dbf552be0b8c Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:50:54 -0400 Subject: removed unneeded braces --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index c25f4cbe62..9e9822fc95 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -20,10 +20,9 @@ int main(int argc, char *argv[]) { if (seen.find(c) == seen.end()) { seen.insert(c); nr.push_back(c); - } else { + } else // remove c from nr nr.erase(find(nr.cbegin(), nr.cend(), c)); - } // now the FNR is either the last element of nr, or # if (nr.empty()) -- cgit From 0ca8c6f59ae500add88481add595ab8889b99f9d Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Tue, 18 Aug 2020 19:52:44 -0400 Subject: removed unneeded temp variable --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 6 ++---- 1 file changed, 2 insertions(+), 4 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index 9e9822fc95..efb1aa1225 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -27,10 +27,8 @@ int main(int argc, char *argv[]) { // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; - else { - auto p = *(nr.crbegin()); - out[i] = p; - } + else + out[i] = *(nr.crbegin()); } cout << out << endl; } -- cgit From 3a85a00c68fe0718ec916493826ea63e0f8a7066 Mon Sep 17 00:00:00 2001 From: Fung Cheok Yin <61836418+E7-87-83@users.noreply.github.com> Date: Wed, 19 Aug 2020 10:24:43 +0800 Subject: Add files via upload --- ch-1.pl | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ ch-2.pl | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 102 insertions(+) create mode 100644 ch-1.pl create mode 100644 ch-2.pl diff --git a/ch-1.pl b/ch-1.pl new file mode 100644 index 0000000000..feb190e26c --- /dev/null +++ b/ch-1.pl @@ -0,0 +1,54 @@ +#!/usr/bin/perl +# ref: +# https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm +# Perl Weekly Challenge #074 Task 1 Majority Element +# task statement: +# Write a script to find the majority element. +# If none found then print -1. +# Usage: ch-1.pl [ARRAY] +use strict; +use warnings; +#use Test::More tests => 3; + + +sub verify { + my @array = @{$_[0]}; + my $m = $_[1]; + my $c = 0; + for (@array) { + if ($m==$_) { + $c++; + } + } + return ($c > (scalar @array)/2.0 ? 1 : undef); +} + +sub bm_majority_vote_alg { + my @array = @{$_[0]}; + my $i = 0; + my $m; + for (@array) { + if ($i == 0) { + $m = $_; + $i++ + } + elsif ($m == $_) { + $i++; + } + else { + $i--; + } + } + + + return ( verify(\@array, $m) ? $m : -1 ); +} + + +print bm_majority_vote_alg(\@ARGV); + +=pod +is_deeply( bm_majority_vote_alg( [1, 2, 2, 3, 2, 4, 2] ) , "2", "example1 provided"); +is_deeply( bm_majority_vote_alg( [1, 3, 1, 2, 4, 5] ) , "-1", "example2 provided"); +is_deeply( bm_majority_vote_alg( [2, 2, 2, 3, 1, 3, 4] ) , "-1", "array: 2223134"); +=cut diff --git a/ch-2.pl b/ch-2.pl new file mode 100644 index 0000000000..bae04b73b3 --- /dev/null +++ b/ch-2.pl @@ -0,0 +1,48 @@ +#!/usr/bin/perl +# Perl Weekly Challenge #074 Task 2 FNR character +# task statement: +# 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. +# Usage: ch-2.pl [string] + +use strict; +use warnings; +#use Test::More tests => 5; + +sub fnr { + my @uniquestack; + my %charcount; + my $ans = ""; + my @characters = split //, $_[0]; + for my $char (@characters) { + if (!exists $charcount{$char} ) { + push @uniquestack , $char; + $charcount{$char} = 1; + $ans .= $char; + } + else { + $charcount{$char}++; + @uniquestack = grep { $charcount{$_} == 1 } @uniquestack; + $ans .= (scalar @uniquestack != 0) ? $uniquestack[-1] : "#"; + } + } + return $ans; + +} + +print fnr("$ARGV[0]"); + +=pod +is_deeply( fnr("ababc") , "abb#c", "example1 provided"); +is_deeply( fnr("xyzzyx") , "xyzyx#", "example2 provided"); +is_deeply( fnr("abcdef") , "abcdef", "trival"); +is_deeply( fnr("aaabbb") , "a##b##", "repeats"); +is_deeply( fnr( + "thequickbrownfoxjumpsoverthelazydog") , + "thequickbrownffxjjmpssvvvvvvlazyddg", + "long sentence" +); +=cut -- cgit From fec0a3a9a3e9aa82ae07a08b9d9d91571e2f5f0f Mon Sep 17 00:00:00 2001 From: Fung Cheok Yin <61836418+E7-87-83@users.noreply.github.com> Date: Wed, 19 Aug 2020 10:25:23 +0800 Subject: Rename ch-2.pl to challenge-074/cheok-yin-fung/perl/ch-2.pl --- ch-2.pl | 48 ------------------------------- challenge-074/cheok-yin-fung/perl/ch-2.pl | 48 +++++++++++++++++++++++++++++++ 2 files changed, 48 insertions(+), 48 deletions(-) delete mode 100644 ch-2.pl create mode 100644 challenge-074/cheok-yin-fung/perl/ch-2.pl diff --git a/ch-2.pl b/ch-2.pl deleted file mode 100644 index bae04b73b3..0000000000 --- a/ch-2.pl +++ /dev/null @@ -1,48 +0,0 @@ -#!/usr/bin/perl -# Perl Weekly Challenge #074 Task 2 FNR character -# task statement: -# 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. -# Usage: ch-2.pl [string] - -use strict; -use warnings; -#use Test::More tests => 5; - -sub fnr { - my @uniquestack; - my %charcount; - my $ans = ""; - my @characters = split //, $_[0]; - for my $char (@characters) { - if (!exists $charcount{$char} ) { - push @uniquestack , $char; - $charcount{$char} = 1; - $ans .= $char; - } - else { - $charcount{$char}++; - @uniquestack = grep { $charcount{$_} == 1 } @uniquestack; - $ans .= (scalar @uniquestack != 0) ? $uniquestack[-1] : "#"; - } - } - return $ans; - -} - -print fnr("$ARGV[0]"); - -=pod -is_deeply( fnr("ababc") , "abb#c", "example1 provided"); -is_deeply( fnr("xyzzyx") , "xyzyx#", "example2 provided"); -is_deeply( fnr("abcdef") , "abcdef", "trival"); -is_deeply( fnr("aaabbb") , "a##b##", "repeats"); -is_deeply( fnr( - "thequickbrownfoxjumpsoverthelazydog") , - "thequickbrownffxjjmpssvvvvvvlazyddg", - "long sentence" -); -=cut diff --git a/challenge-074/cheok-yin-fung/perl/ch-2.pl b/challenge-074/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..bae04b73b3 --- /dev/null +++ b/challenge-074/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,48 @@ +#!/usr/bin/perl +# Perl Weekly Challenge #074 Task 2 FNR character +# task statement: +# 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. +# Usage: ch-2.pl [string] + +use strict; +use warnings; +#use Test::More tests => 5; + +sub fnr { + my @uniquestack; + my %charcount; + my $ans = ""; + my @characters = split //, $_[0]; + for my $char (@characters) { + if (!exists $charcount{$char} ) { + push @uniquestack , $char; + $charcount{$char} = 1; + $ans .= $char; + } + else { + $charcount{$char}++; + @uniquestack = grep { $charcount{$_} == 1 } @uniquestack; + $ans .= (scalar @uniquestack != 0) ? $uniquestack[-1] : "#"; + } + } + return $ans; + +} + +print fnr("$ARGV[0]"); + +=pod +is_deeply( fnr("ababc") , "abb#c", "example1 provided"); +is_deeply( fnr("xyzzyx") , "xyzyx#", "example2 provided"); +is_deeply( fnr("abcdef") , "abcdef", "trival"); +is_deeply( fnr("aaabbb") , "a##b##", "repeats"); +is_deeply( fnr( + "thequickbrownfoxjumpsoverthelazydog") , + "thequickbrownffxjjmpssvvvvvvlazyddg", + "long sentence" +); +=cut -- cgit From 0dc9a9f30184ec760f442d60aec1fdf9b92dbbaf Mon Sep 17 00:00:00 2001 From: Fung Cheok Yin <61836418+E7-87-83@users.noreply.github.com> Date: Wed, 19 Aug 2020 10:25:59 +0800 Subject: Rename ch-1.pl to challenge-074/cheok-yin-fung/perl/ch-1.pl --- ch-1.pl | 54 ------------------------------- challenge-074/cheok-yin-fung/perl/ch-1.pl | 54 +++++++++++++++++++++++++++++++ 2 files changed, 54 insertions(+), 54 deletions(-) delete mode 100644 ch-1.pl create mode 100644 challenge-074/cheok-yin-fung/perl/ch-1.pl diff --git a/ch-1.pl b/ch-1.pl deleted file mode 100644 index feb190e26c..0000000000 --- a/ch-1.pl +++ /dev/null @@ -1,54 +0,0 @@ -#!/usr/bin/perl -# ref: -# https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm -# Perl Weekly Challenge #074 Task 1 Majority Element -# task statement: -# Write a script to find the majority element. -# If none found then print -1. -# Usage: ch-1.pl [ARRAY] -use strict; -use warnings; -#use Test::More tests => 3; - - -sub verify { - my @array = @{$_[0]}; - my $m = $_[1]; - my $c = 0; - for (@array) { - if ($m==$_) { - $c++; - } - } - return ($c > (scalar @array)/2.0 ? 1 : undef); -} - -sub bm_majority_vote_alg { - my @array = @{$_[0]}; - my $i = 0; - my $m; - for (@array) { - if ($i == 0) { - $m = $_; - $i++ - } - elsif ($m == $_) { - $i++; - } - else { - $i--; - } - } - - - return ( verify(\@array, $m) ? $m : -1 ); -} - - -print bm_majority_vote_alg(\@ARGV); - -=pod -is_deeply( bm_majority_vote_alg( [1, 2, 2, 3, 2, 4, 2] ) , "2", "example1 provided"); -is_deeply( bm_majority_vote_alg( [1, 3, 1, 2, 4, 5] ) , "-1", "example2 provided"); -is_deeply( bm_majority_vote_alg( [2, 2, 2, 3, 1, 3, 4] ) , "-1", "array: 2223134"); -=cut diff --git a/challenge-074/cheok-yin-fung/perl/ch-1.pl b/challenge-074/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..feb190e26c --- /dev/null +++ b/challenge-074/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,54 @@ +#!/usr/bin/perl +# ref: +# https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm +# Perl Weekly Challenge #074 Task 1 Majority Element +# task statement: +# Write a script to find the majority element. +# If none found then print -1. +# Usage: ch-1.pl [ARRAY] +use strict; +use warnings; +#use Test::More tests => 3; + + +sub verify { + my @array = @{$_[0]}; + my $m = $_[1]; + my $c = 0; + for (@array) { + if ($m==$_) { + $c++; + } + } + return ($c > (scalar @array)/2.0 ? 1 : undef); +} + +sub bm_majority_vote_alg { + my @array = @{$_[0]}; + my $i = 0; + my $m; + for (@array) { + if ($i == 0) { + $m = $_; + $i++ + } + elsif ($m == $_) { + $i++; + } + else { + $i--; + } + } + + + return ( verify(\@array, $m) ? $m : -1 ); +} + + +print bm_majority_vote_alg(\@ARGV); + +=pod +is_deeply( bm_majority_vote_alg( [1, 2, 2, 3, 2, 4, 2] ) , "2", "example1 provided"); +is_deeply( bm_majority_vote_alg( [1, 3, 1, 2, 4, 5] ) , "-1", "example2 provided"); +is_deeply( bm_majority_vote_alg( [2, 2, 2, 3, 1, 3, 4] ) , "-1", "array: 2223134"); +=cut -- cgit From 58a0d9119903d53470dce47142017d76aedb5e5e Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Wed, 19 Aug 2020 22:05:54 -0400 Subject: Store iterators to the positions in the list in a map This saves me having to find() each element -- now I can jump right to them. But I had to store the list in the opposite order since erase() doesn't like reverse iterators. --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index efb1aa1225..01fb9a916b 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -1,6 +1,6 @@ #include #include -#include +#include #include #include @@ -8,7 +8,7 @@ using namespace std; int main(int argc, char *argv[]) { const char *s = argv[1]; - set seen; + map::const_iterator> seen; list nr; char *out = new char[strlen(s)+1]; out[strlen(s)] = '\0'; @@ -18,17 +18,17 @@ int main(int argc, char *argv[]) { // have we seen c before? if (seen.find(c) == seen.end()) { - seen.insert(c); - nr.push_back(c); + nr.push_front(c); + seen[c] = nr.cbegin(); } else // remove c from nr - nr.erase(find(nr.cbegin(), nr.cend(), c)); + nr.erase(seen[c]); // now the FNR is either the last element of nr, or # if (nr.empty()) out[i] = '#'; else - out[i] = *(nr.crbegin()); + out[i] = *(nr.cbegin()); } cout << out << endl; } -- cgit From 13cdfa88e53569f70d9094b2d858490224a6cb25 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 20:53:47 -0400 Subject: check for double-delete when removing c from nr After it's been removed, set the value in seen to end() so we know not to erase it again. --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index 01fb9a916b..b5f32cc7a4 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -20,9 +20,13 @@ int main(int argc, char *argv[]) { if (seen.find(c) == seen.end()) { nr.push_front(c); seen[c] = nr.cbegin(); - } else + } else { // remove c from nr - nr.erase(seen[c]); + if (seen[c] != nr.end()) { + nr.erase(seen[c]); + seen[c] = nr.end(); + } + } // now the FNR is either the last element of nr, or # if (nr.empty()) -- cgit From e519ffe2910e017d481548eec99c0590d748f82b Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 21:26:15 -0400 Subject: use strings instead of char *'s --- challenge-074/walt-mankowski/cpp/ch-2.cpp | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) diff --git a/challenge-074/walt-mankowski/cpp/ch-2.cpp b/challenge-074/walt-mankowski/cpp/ch-2.cpp index b5f32cc7a4..df7aec5325 100644 --- a/challenge-074/walt-mankowski/cpp/ch-2.cpp +++ b/challenge-074/walt-mankowski/cpp/ch-2.cpp @@ -1,4 +1,4 @@ -#include +#include #include #include #include @@ -7,13 +7,12 @@ using namespace std; int main(int argc, char *argv[]) { - const char *s = argv[1]; + const string s(argv[1]); + string out = string(s.length(), ' '); map::const_iterator> seen; list nr; - char *out = new char[strlen(s)+1]; - out[strlen(s)] = '\0'; - for (size_t i = 0; i < strlen(s); i++) { + for (size_t i = 0; i < s.length(); i++) { const char c = s[i]; // have we seen c before? -- cgit From bd68cb43ac04ad8ec10f49cadd65af94fe7b9629 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 21:30:15 -0400 Subject: only delete c from nr once --- challenge-074/walt-mankowski/python/ch-2.py | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) diff --git a/challenge-074/walt-mankowski/python/ch-2.py b/challenge-074/walt-mankowski/python/ch-2.py index 1c1d4e1609..e80b5b0246 100644 --- a/challenge-074/walt-mankowski/python/ch-2.py +++ b/challenge-074/walt-mankowski/python/ch-2.py @@ -1,7 +1,7 @@ from sys import argv s = argv[1] -seen = set() +seen = {} nr = [] out = [] @@ -9,11 +9,13 @@ for c in s: # have we seen c before? if c not in seen: # add c to nr - seen.add(c) + seen[c] = True nr.append(c) else: # remove c from nr - nr.remove(c) + if seen[c]: + nr.remove(c) + seen[c] = False # now the FNR is either the last element of nr, or # out.append(nr[-1] if nr else '#') -- cgit From 5b8dcdcf9ff65c0cc862bd7f27b4d8ed0f465040 Mon Sep 17 00:00:00 2001 From: Walt Mankowski Date: Thu, 20 Aug 2020 21:33:16 -0400 Subject: only try to erase c from nr once --- challenge-074/walt-mankowski/perl/ch-2.pl | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) diff --git a/challenge-074/walt-mankowski/perl/ch-2.pl b/challenge-074/walt-mankowski/perl/ch-2.pl index 01a73a12cd..7410b1714b 100644 --- a/challenge-074/walt-mankowski/perl/ch-2.pl +++ b/challenge-074/walt-mankowski/perl/ch-2.pl @@ -45,11 +45,14 @@ for my $c (@c) { push @nr, $c; } else { # remove $c from @nr - for my $i (0..$#nr) { - if ($nr[$i] eq $c) { - splice @nr, $i, 1; - last; + if ($seen{$c}) { + for my $i (0..$#nr) { + if ($nr[$i] eq $c) { + splice @nr, $i, 1; + last; + } } + $seen{$c} = 0; } } -- cgit From 62943d0e58e339fa565b1d25c84b4dcacb99545f Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Tue, 18 Aug 2020 23:09:38 -0700 Subject: add my solutions to challenge #074 --- challenge-074/tyler-wardhaugh/clojure/.gitignore | 11 ++ challenge-074/tyler-wardhaugh/clojure/LICENSE | 214 +++++++++++++++++++++ challenge-074/tyler-wardhaugh/clojure/README.md | 37 ++++ challenge-074/tyler-wardhaugh/clojure/deps.edn | 15 ++ challenge-074/tyler-wardhaugh/clojure/pom.xml | 38 ++++ .../tyler-wardhaugh/clojure/src/tw/weekly/c74.clj | 12 ++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj | 20 ++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj | 33 ++++ .../clojure/test/tw/weekly/c74_test.clj | 14 ++ 9 files changed, 394 insertions(+) create mode 100644 challenge-074/tyler-wardhaugh/clojure/.gitignore create mode 100644 challenge-074/tyler-wardhaugh/clojure/LICENSE create mode 100644 challenge-074/tyler-wardhaugh/clojure/README.md create mode 100644 challenge-074/tyler-wardhaugh/clojure/deps.edn create mode 100644 challenge-074/tyler-wardhaugh/clojure/pom.xml create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/c74.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/test/tw/weekly/c74_test.clj diff --git a/challenge-074/tyler-wardhaugh/clojure/.gitignore b/challenge-074/tyler-wardhaugh/clojure/.gitignore new file mode 100644 index 0000000000..bb6ba94a82 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/.gitignore @@ -0,0 +1,11 @@ +/target +/classes +/checkouts +*.jar +*.class +/.cpcache +/.lein-* +/.nrepl-history +/.nrepl-port +.hgignore +.hg/ diff --git a/challenge-074/tyler-wardhaugh/clojure/LICENSE b/challenge-074/tyler-wardhaugh/clojure/LICENSE new file mode 100644 index 0000000000..7689f30efd --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/LICENSE @@ -0,0 +1,214 @@ +THE ACCOMPANYING PROGRAM IS PROVIDED UNDER THE TERMS OF THIS ECLIPSE PUBLIC +LICENSE ("AGREEMENT"). ANY USE, REPRODUCTION OR DISTRIBUTION OF THE PROGRAM +CONSTITUTES RECIPIENT'S ACCEPTANCE OF THIS AGREEMENT. + +1. DEFINITIONS + +"Contribution" means: + +a) in the case of the initial Contributor, the initial code and +documentation distributed under this Agreement, and + +b) in the case of each subsequent Contributor: + +i) changes to the Program, and + +ii) additions to the Program; + +where such changes and/or additions to the Program originate from and are +distributed by that particular Contributor. A Contribution 'originates' from +a Contributor if it was added to the Program by such Contributor itself or +anyone acting on such Contributor's behalf. Contributions do not include +additions to the Program which: (i) are separate modules of software +distributed in conjunction with the Program under their own license +agreement, and (ii) are not derivative works of the Program. + +"Contributor" means any person or entity that distributes the Program. + +"Licensed Patents" mean patent claims licensable by a Contributor which are +necessarily infringed by the use or sale of its Contribution alone or when +combined with the Program. + +"Program" means the Contributions distributed in accordance with this +Agreement. + +"Recipient" means anyone who receives the Program under this Agreement, +including all Contributors. + +2. GRANT OF RIGHTS + +a) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free copyright license to +reproduce, prepare derivative works of, publicly display, publicly perform, +distribute and sublicense the Contribution of such Contributor, if any, and +such derivative works, in source code and object code form. + +b) Subject to the terms of this Agreement, each Contributor hereby grants +Recipient a non-exclusive, worldwide, royalty-free patent license under +Licensed Patents to make, use, sell, offer to sell, import and otherwise +transfer the Contribution of such Contributor, if any, in source code and +object code form. This patent license shall apply to the combination of the +Contribution and the Program if, at the time the Contribution is added by the +Contributor, such addition of the Contribution causes such combination to be +covered by the Licensed Patents. The patent license shall not apply to any +other combinations which include the Contribution. No hardware per se is +licensed hereunder. + +c) Recipient understands that although each Contributor grants the licenses +to its Contributions set forth herein, no assurances are provided by any +Contributor that the Program does not infringe the patent or other +intellectual property rights of any other entity. Each Contributor disclaims +any liability to Recipient for claims brought by any other entity based on +infringement of intellectual property rights or otherwise. As a condition to +exercising the rights and licenses granted hereunder, each Recipient hereby +assumes sole responsibility to secure any other intellectual property rights +needed, if any. For example, if a third party patent license is required to +allow Recipient to distribute the Program, it is Recipient's responsibility +to acquire that license before distributing the Program. + +d) Each Contributor represents that to its knowledge it has sufficient +copyright rights in its Contribution, if any, to grant the copyright license +set forth in this Agreement. + +3. REQUIREMENTS + +A Contributor may choose to distribute the Program in object code form under +its own license agreement, provided that: + +a) it complies with the terms and conditions of this Agreement; and + +b) its license agreement: + +i) effectively disclaims on behalf of all Contributors all warranties and +conditions, express and implied, including warranties or conditions of title +and non-infringement, and implied warranties or conditions of merchantability +and fitness for a particular purpose; + +ii) effectively excludes on behalf of all Contributors all liability for +damages, including direct, indirect, special, incidental and consequential +damages, such as lost profits; + +iii) states that any provisions which differ from this Agreement are offered +by that Contributor alone and not by any other party; and + +iv) states that source code for the Program is available from such +Contributor, and informs licensees how to obtain it in a reasonable manner on +or through a medium customarily used for software exchange. + +When the Program is made available in source code form: + +a) it must be made available under this Agreement; and + +b) a copy of this Agreement must be included with each copy of the Program. + +Contributors may not remove or alter any copyright notices contained within +the Program. + +Each Contributor must identify itself as the originator of its Contribution, +if any, in a manner that reasonably allows subsequent Recipients to identify +the originator of the Contribution. + +4. COMMERCIAL DISTRIBUTION + +Commercial distributors of software may accept certain responsibilities with +respect to end users, business partners and the like. While this license is +intended to facilitate the commercial use of the Program, the Contributor who +includes the Program in a commercial product offering should do so in a +manner which does not create potential liability for other Contributors. +Therefore, if a Contributor includes the Program in a commercial product +offering, such Contributor ("Commercial Contributor") hereby agrees to defend +and indemnify every other Contributor ("Indemnified Contributor") against any +losses, damages and costs (collectively "Losses") arising from claims, +lawsuits and other legal actions brought by a third party against the +Indemnified Contributor to the extent caused by the acts or omissions of such +Commercial Contributor in connection with its distribution of the Program in +a commercial product offering. The obligations in this section do not apply +to any claims or Losses relating to any actual or alleged intellectual +property infringement. In order to qualify, an Indemnified Contributor must: +a) promptly notify the Commercial Contributor in writing of such claim, and +b) allow the Commercial Contributor tocontrol, and cooperate with the +Commercial Contributor in, the defense and any related settlement +negotiations. The Indemnified Contributor may participate in any such claim +at its own expense. + +For example, a Contributor might include the Program in a commercial product +offering, Product X. That Contributor is then a Commercial Contributor. If +that Commercial Contributor then makes performance claims, or offers +warranties related to Product X, those performance claims and warranties are +such Commercial Contributor's responsibility alone. Under this section, the +Commercial Contributor would have to defend claims against the other +Contributors related to those performance claims and warranties, and if a +court requires any other Contributor to pay any damages as a result, the +Commercial Contributor must pay those damages. + +5. NO WARRANTY + +EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, THE PROGRAM IS PROVIDED ON +AN "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, EITHER +EXPRESS OR IMPLIED INCLUDING, WITHOUT LIMITATION, ANY WARRANTIES OR +CONDITIONS OF TITLE, NON-INFRINGEMENT, MERCHANTABILITY OR FITNESS FOR A +PARTICULAR PURPOSE. Each Recipient is solely responsible for determining the +appropriateness of using and distributing the Program and assumes all risks +associated with its exercise of rights under this Agreement , including but +not limited to the risks and costs of program errors, compliance with +applicable laws, damage to or loss of data, programs or equipment, and +unavailability or interruption of operations. + +6. DISCLAIMER OF LIABILITY + +EXCEPT AS EXPRESSLY SET FORTH IN THIS AGREEMENT, NEITHER RECIPIENT NOR ANY +CONTRIBUTORS SHALL HAVE ANY LIABILITY FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING WITHOUT LIMITATION +LOST PROFITS), HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OR DISTRIBUTION OF THE PROGRAM OR THE +EXERCISE OF ANY RIGHTS GRANTED HEREUNDER, EVEN IF ADVISED OF THE POSSIBILITY +OF SUCH DAMAGES. + +7. GENERAL + +If any provision of this Agreement is invalid or unenforceable under +applicable law, it shall not affect the validity or enforceability of the +remainder of the terms of this Agreement, and without further action by the +parties hereto, such provision shall be reformed to the minimum extent +necessary to make such provision valid and enforceable. + +If Recipient institutes patent litigation against any entity (including a +cross-claim or counterclaim in a lawsuit) alleging that the Program itself +(excluding combinations of the Program with other software or hardware) +infringes such Recipient's patent(s), then such Recipient's rights granted +under Section 2(b) shall terminate as of the date such litigation is filed. + +All Recipient's rights under this Agreement shall terminate if it fails to +comply with any of the material terms or conditions of this Agreement and +does not cure such failure in a reasonable period of time after becoming +aware of such noncompliance. If all Recipient's rights under this Agreement +terminate, Recipient agrees to cease use and distribution of the Program as +soon as reasonably practicable. However, Recipient's obligations under this +Agreement and any licenses granted by Recipient relating to the Program shall +continue and survive. + +Everyone is permitted to copy and distribute copies of this Agreement, but in +order to avoid inconsistency the Agreement is copyrighted and may only be +modified in the following manner. The Agreement Steward reserves the right to +publish new versions (including revisions) of this Agreement from time to +time. No one other than the Agreement Steward has the right to modify this +Agreement. The Eclipse Foundation is the initial Agreement Steward. The +Eclipse Foundation may assign the responsibility to serve as the Agreement +Steward to a suitable separate entity. Each new version of the Agreement will +be given a distinguishing version number. The Program (including +Contributions) may always be distributed subject to the version of the +Agreement under which it was received. In addition, after a new version of +the Agreement is published, Contributor may elect to distribute the Program +(including its Contributions) under the new version. Except as expressly +stated in Sections 2(a) and 2(b) above, Recipient receives no rights or +licenses to the intellectual property of any Contributor under this +Agreement, whether expressly, by implication, estoppel or otherwise. All +rights in the Program not expressly granted under this Agreement are +reserved. + +This Agreement is governed by the laws of the State of New York and the +intellectual property laws of the United States of America. No party to this +Agreement will bring a legal action under this Agreement more than one year +after the cause of action arose. Each party waives its rights to a jury trial +in any resulting litigation. diff --git a/challenge-074/tyler-wardhaugh/clojure/README.md b/challenge-074/tyler-wardhaugh/clojure/README.md new file mode 100644 index 0000000000..fd66db9c43 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/README.md @@ -0,0 +1,37 @@ +# tw.weekly.c74 + + +The Weekly Challenge - #074 - Tyler Wardhaugh + +## Usage + +Run the project directly (shows default output from both tasks): + + $ clojure -m tw.weekly.c74 + +Run the project's tests (which are samples from the task descriptions): + + $ clojure -A:test:runner + +Run Task #1 with input: + + $ clojure -m tw.weekly.ch-1 8 8 8 7 9 + +Run Task #2 with input: + + $ clojure -m tw.weekly.ch-2 "asdjfklsfasdjfklq" + +## Project Template + +I used Sean Corfield's clj-new to generate the project template + + $ clj -A:new app tw.weekly.c74 + +See [seancorfield/clj-new: Generate new projects based on clj, Boot, or Leiningen Templates!](https://github.com/seancorfield/clj-new) for more information. + +## License + +Copyright © 2020 Tyler Wardhaugh + +Distributed under the Eclipse Public License either version 1.0 or (at +your option) any later version. diff --git a/challenge-074/tyler-wardhaugh/clojure/deps.edn b/challenge-074/tyler-wardhaugh/clojure/deps.edn new file mode 100644 index 0000000000..a821029408 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/deps.edn @@ -0,0 +1,15 @@ +{:paths ["src" "resources"] + :deps {org.clojure/clojure {:mvn/version "1.10.1"} + org.flatland/ordered {:mvn/version "1.5.9"}} + :aliases + {:test {:extra-paths ["test"] + :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}} + :runner + {:extra-deps {com.cognitect/test-runner + {:git/url "https://github.com/cognitect-labs/test-runner" + :sha "f7ef16dc3b8332b0d77bc0274578ad5270fbfedd"}} + :main-opts ["-m" "cognitect.test-runner" + "-d" "test"]} + :uberjar {:extra-deps {seancorfield/depstar {:mvn/version "1.0.94"}} + :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c74.jar" + "-C" "-m" "tw.weekly.c74"]}}} diff --git a/challenge-074/tyler-wardhaugh/clojure/pom.xml b/challenge-074/tyler-wardhaugh/clojure/pom.xml new file mode 100644 index 0000000000..c36c8abbcd --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/pom.xml @@ -0,0 +1,38 @@ + + + 4.0.0 + tw.weekly + tw.weekly.c74 + 0.1.0-SNAPSHOT + tw.weekly.c74 + The Weekly Challenge - #074 + https://github.com/manwar/perlweeklychallenge-club + + + Eclipse Public License + http://www.eclipse.org/legal/epl-v10.html + + + + + Tyler Wardhaugh + + + + + org.clojure + clojure + 1.10.1 + + + org.flatland + ordered + 1.5.9 + + + + + src + + + diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/c74.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/c74.clj new file mode 100644 index 0000000000..8925e00749 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/c74.clj @@ -0,0 +1,12 @@ +(ns tw.weekly.c74 + (:require [tw.weekly.ch-1 :as ch-1]) + (:require [tw.weekly.ch-2 :as ch-2]) + (:gen-class)) + +(defn -main + "Run both tasks." + [& args] + (println "Task #1") + (ch-1/-main) + (println "\n\nTask #2") + (ch-2/-main)) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj new file mode 100644 index 0000000000..416d2a1d85 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj @@ -0,0 +1,20 @@ +(ns tw.weekly.ch-1) + +(defn majority + "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found." + [coll] + (let [minimum (Math/floor (/ (count coll) 2)) + maj (->> coll + frequencies + (filter (comp #(> % minimum) second)) + (sort second) + ffirst)] + (or maj -1))) + +(defn -main + "Run Task 1 with a list of integers, defaulting to the sample given in the task description." + [& args] + (let [N (if (not-empty args) + (map clojure.edn/read-string args) + [2, 2, 2, 3, 2, 4, 2])] + (println (majority N)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj new file mode 100644 index 0000000000..299ab63690 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj @@ -0,0 +1,33 @@ +(ns tw.weekly.ch-2 + (:require [clojure.string :as str]) + (:require [flatland.ordered.map :as fo])) + +(defn ordered-frequencies + "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear." + [coll] + (persistent! + (reduce (fn [counts x] + (assoc! counts x (inc (get counts x 0)))) + (transient (fo/ordered-map)) coll))) + +(defn find-fnr [string] + "Find the first non-repeating character (FNR) for a string." + (let [counts (ordered-frequencies string) + non-repeaters (filter (comp #(= 1 %) second) counts)] + (-> non-repeaters last first))) + +(defn find-fnr-over-string + "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string." + [string] + (->> string + (reductions str "") + (drop 1) + (map find-fnr) + (map #(or % \#)) + str/join)) + +(defn -main + "Run Task 2 with a string, defaulting to the sample given in the task description." + [& args] + (let [S (or (-> args first) "ababc")] + (println (find-fnr-over-string S)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/test/tw/weekly/c74_test.clj b/challenge-074/tyler-wardhaugh/clojure/test/tw/weekly/c74_test.clj new file mode 100644 index 0000000000..fd1a30cc87 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/test/tw/weekly/c74_test.clj @@ -0,0 +1,14 @@ +(ns tw.weekly.c74-test + (:require [clojure.test :refer :all] + [tw.weekly.ch-1 :refer [majority]] + [tw.weekly.ch-2 :refer [find-fnr-over-string]])) + +(deftest ch-1 + (testing "Task 1" + (is (= 2 (majority (list 1, 2, 2, 3, 2, 4, 2)))) + (is (= -1 (majority (list 1, 3, 1, 2, 4, 5)))))) + +(deftest ch-2 + (testing "Task 2" + (is (= "abb#c" (find-fnr-over-string "ababc"))) + (is (= "xyzyx#" (find-fnr-over-string "xyzzyx"))))) -- cgit From 538a7cc8f9a9edf038f797f9c4406750e089abde Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Fri, 21 Aug 2020 13:36:11 +0100 Subject: - Added guest Tyler Wardhaugh. --- guests.json | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/guests.json b/guests.json index 8a59b11cab..5b45c26c9c 100644 --- a/guests.json +++ b/guests.json @@ -1,4 +1,5 @@ { "orestis-zekai" : "Orestis Zekai", - "shawak" : "Shawak" + "shawak" : "Shawak", + "tyler-wardhaugh" : "Tyler Wardhaugh" } -- cgit From fc7f885064f20aa578b41dd1215de3251c9d7897 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Fri, 21 Aug 2020 13:41:42 +0100 Subject: - Tidied up contributins by Tyle Wardhaugh. --- challenge-074/tyler-wardhaugh/README | 1 + .../tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj | 20 +++++++++++++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj | 33 ++++++++++++++++++++++ .../tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj | 20 ------------- .../tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj | 33 ---------------------- 5 files changed, 54 insertions(+), 53 deletions(-) create mode 100644 challenge-074/tyler-wardhaugh/README create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj create mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj delete mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj delete mode 100644 challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj diff --git a/challenge-074/tyler-wardhaugh/README b/challenge-074/tyler-wardhaugh/README new file mode 100644 index 0000000000..0f34ede8e7 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/README @@ -0,0 +1 @@ +Solutions by Tyler Wardhaugh. diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj new file mode 100644 index 0000000000..416d2a1d85 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-1.clj @@ -0,0 +1,20 @@ +(ns tw.weekly.ch-1) + +(defn majority + "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found." + [coll] + (let [minimum (Math/floor (/ (count coll) 2)) + maj (->> coll + frequencies + (filter (comp #(> % minimum) second)) + (sort second) + ffirst)] + (or maj -1))) + +(defn -main + "Run Task 1 with a list of integers, defaulting to the sample given in the task description." + [& args] + (let [N (if (not-empty args) + (map clojure.edn/read-string args) + [2, 2, 2, 3, 2, 4, 2])] + (println (majority N)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj new file mode 100644 index 0000000000..299ab63690 --- /dev/null +++ b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch-2.clj @@ -0,0 +1,33 @@ +(ns tw.weekly.ch-2 + (:require [clojure.string :as str]) + (:require [flatland.ordered.map :as fo])) + +(defn ordered-frequencies + "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear." + [coll] + (persistent! + (reduce (fn [counts x] + (assoc! counts x (inc (get counts x 0)))) + (transient (fo/ordered-map)) coll))) + +(defn find-fnr [string] + "Find the first non-repeating character (FNR) for a string." + (let [counts (ordered-frequencies string) + non-repeaters (filter (comp #(= 1 %) second) counts)] + (-> non-repeaters last first))) + +(defn find-fnr-over-string + "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string." + [string] + (->> string + (reductions str "") + (drop 1) + (map find-fnr) + (map #(or % \#)) + str/join)) + +(defn -main + "Run Task 2 with a string, defaulting to the sample given in the task description." + [& args] + (let [S (or (-> args first) "ababc")] + (println (find-fnr-over-string S)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj deleted file mode 100644 index 416d2a1d85..0000000000 --- a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj +++ /dev/null @@ -1,20 +0,0 @@ -(ns tw.weekly.ch-1) - -(defn majority - "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found." - [coll] - (let [minimum (Math/floor (/ (count coll) 2)) - maj (->> coll - frequencies - (filter (comp #(> % minimum) second)) - (sort second) - ffirst)] - (or maj -1))) - -(defn -main - "Run Task 1 with a list of integers, defaulting to the sample given in the task description." - [& args] - (let [N (if (not-empty args) - (map clojure.edn/read-string args) - [2, 2, 2, 3, 2, 4, 2])] - (println (majority N)))) diff --git a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj b/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj deleted file mode 100644 index 299ab63690..0000000000 --- a/challenge-074/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj +++ /dev/null @@ -1,33 +0,0 @@ -(ns tw.weekly.ch-2 - (:require [clojure.string :as str]) - (:require [flatland.ordered.map :as fo])) - -(defn ordered-frequencies - "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear." - [coll] - (persistent! - (reduce (fn [counts x] - (assoc! counts x (inc (get counts x 0)))) - (transient (fo/ordered-map)) coll))) - -(defn find-fnr [string] - "Find the first non-repeating character (FNR) for a string." - (let [counts (ordered-frequencies string) - non-repeaters (filter (comp #(= 1 %) second) counts)] - (-> non-repeaters last first))) - -(defn find-fnr-over-string - "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string." - [string] - (->> string - (reductions str "") - (drop 1) - (map find-fnr) - (map #(or % \#)) - str/join)) - -(defn -main - "Run Task 2 with a string, defaulting to the sample given in the task description." - [& args] - (let [S (or (-> args first) "ababc")] - (println (find-fnr-over-string S)))) -- cgit From 55a1360f1401282d22c925a4c83c212d3f810148 Mon Sep 17 00:00:00 2001 From: Mohammad S Anwar Date: Fri, 21 Aug 2020 15:53:11 +0100 Subject: - Added solutions by Colin Crain. --- challenge-074/colin-crain/blog.txt | 1 + challenge-074/colin-crain/perl/ch-1.pl | 55 ++ challenge-074/colin-crain/perl/ch-2.pl | 102 +++ challenge-074/colin-crain/raku/ch-1.raku | 38 + challenge-074/colin-crain/raku/ch-2.raku | 86 +++ stats/pwc-current.json | 177 +++-- stats/pwc-language-breakdown-summary.json | 50 +- stats/pwc-language-breakdown.json | 1088 ++++++++++++++--------------- stats/pwc-leaders.json | 730 +++++++++---------- stats/pwc-summary-1-30.json | 42 +- stats/pwc-summary-121-150.json | 42 +- stats/pwc-summary-151-180.json | 42 +- stats/pwc-summary-181-210.json | 38 +- stats/pwc-summary-31-60.json | 106 +-- stats/pwc-summary-61-90.json | 116 +-- stats/pwc-summary-91-120.json | 100 +-- stats/pwc-summary.json | 56 +- 17 files changed, 1587 insertions(+), 1282 deletions(-) create mode 100644 challenge-074/colin-crain/blog.txt create mode 100644 challenge-074/colin-crain/perl/ch-1.pl create mode 100644 challenge-074/colin-crain/perl/ch-2.pl create mode 100644 challenge-074/colin-crain/raku/ch-1.raku create mode 100644 challenge-074/colin-crain/raku/ch-2.raku diff --git a/challenge-074/colin-crain/blog.txt b/challenge-074/colin-crain/blog.txt new file mode 100644 index 0000000000..1355e7910f --- /dev/null +++ b/challenge-074/colin-crain/blog.txt @@ -0,0 +1 @@ +https://colincrain.wordpress.com/2020/08/21/when-majority-rule-plays-finders-keepers/ diff --git a/challenge-074/colin-crain/perl/ch-1.pl b/challenge-074/colin-crain/perl/ch-1.pl new file mode 100644 index 0000000000..8536654751 --- /dev/null +++ b/challenge-074/colin-crain/perl/ch-1.pl @@ -0,0 +1,55 @@ +#! /opt/local/bin/perl +# +# majority_ruler.pl +# +# TASK #1 › Majority Element +# Submitted by: Mohammad S Anwar +# 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). +# +# Example 1 +# Input: @A = (1, 2, 2, 3, 2, 4, 2) +# Output: 2, as 2 appears 4 times in the list which is more than floor(7/2). +# +# Example 2 +# Input: @A = (1, 3, 1, 2, 4, 5) +# Output: -1 as none of the elements appears more than floor(6/2). +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + +use warnings; +use strict; +use feature ":5.26"; + +## ## ## ## ## MAIN: + +my @A = @ARGV; +@A = (1, 2, 2, 3, 3, 4, 2, 2, 2) if scalar @A == 0; +say "input: @A"; + +my %count; +$count{$_}++ for @A; + +# version 1: +# is first elem count larger than half list size? +my $max = ( sort { $count{$b} <=> $count{$a} } keys %count )[0]; +say "ver 1: ", $count{$max} > int(@A/2) ? $max : -1; + +## version 2: +## if first elem same at far side of center? +my @sorted = sort {$count{$b} <=> $count{$a}} @A; +say "ver 2: ", $sorted[0] eq $sorted[int(@A/2)] ? $sorted[0] : -1; + +## version 3: +## is maximum count greater than the sum for all other values? +use List::Util qw(sum); +my ($candidate, $count) = ($sorted[0], $count{$sorted[0]}); +delete $count{$sorted[0]}; +my $others = sum values %count; +say "ver 3: ", $count > $others ? $candidate : -1; \ No newline at end of file diff --git a/challenge-074/colin-crain/perl/ch-2.pl b/challenge-074/colin-crain/perl/ch-2.pl new file mode 100644 index 0000000000..438fb8a681 --- /dev/null +++ b/challenge-074/colin-crain/perl/ch-2.pl @@ -0,0 +1,102 @@ +#! /opt/local/bin/perl +# +# finders_keepers.pl +# +# TASK #2 › FNR Character +# Submitted by: Mohammad S Anwar +# You are given a string $S. +# +# Write a script to print the series of first +# non-repeating character 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’ +# +# Example 2 +# Input: $S = ‘xyzzyx’ +# Output: ‘xyzyx#’ +# Pass 1: “x”, the FNR character is “x” +# Pass 2: “xy”, the FNR character is “y” +# Pass 3: “xyz”, the FNR character is “z” +# Pass 4: “xyzz”, the FNR character is “y” +# Pass 5: “xyzzy”, the FNR character is “x” +# Pass 6: “xyzzyx”, no FNR found, hence ‘#’ +# +# method: +# Again with the misdirecting name, wouldn't this be the "last" +# non-repeating character? "first non-repeating character looking +# backwards from a given point in a string". Bit wordy, that one. +# But we're compiling a string of these, so "first non-repeating +# character looking backwards from each character in a string". In a +# sense, though, I like that figuring out what the task is becomes +# part of the puzzle. In this sense the challenges mimic the real +# world. +# +# In any case the first order of business is to plot out the action. +# +# I believe the only thing that makes sense is for '#' to be an +# excluded character from the input, but didn't do that. +# +# the list is iterated through one character at a time +# each char when evaluated replaces the fnr unless that char is not unique, +# the prev fnr goes on the stack, unless it is '#' +# if the new char matches the fnr: +# the stack is rechecked for uniqueness +# the top element is popped of the stack: +# if the stack is empty the fnr is '#' +# --- +# pseudo-perl: +# +# list -> char: +# uniq{char}++ +# if uniq{char} == 1: +# push stack, fnr unless fnr == '#' +# fnr = char +# next +# if uniq{fnr} == 2: ## match to fnr +# stack = grep { uniq == 1 } stack +# if stack has elements: +# fnr = pop stack +# else +# fnr = '#' +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +use warnings; +use strict; +use feature ":5.26"; + +## ## ## ## ## MAIN: + +my $str = shift @ARGV // '#yzzy#w'; +my %uniq; +my $fnr = undef; +my @prev; +my $output; + +while (my $char = substr $str, 0, 1, '') { + $uniq{$char}++; + + if ($uniq{$char} == 1) { + push @prev, $fnr unless not defined $fnr; + $fnr = $char; + } + elsif ($uniq{$fnr} == 2) { + @prev = grep { $uniq{$_} == 1 } @prev; + $fnr = @prev ? pop @prev : undef; + } + $output .= $fnr // '#'; +} + +say $output; diff --git a/challenge-074/colin-crain/raku/ch-1.raku b/challenge-074/colin-crain/raku/ch-1.raku new file mode 100644 index 0000000000..b1d9cc78f3 --- /dev/null +++ b/challenge-074/colin-crain/raku/ch-1.raku @@ -0,0 +1,38 @@ +#!/usr/bin/env perl6 +# +# +# majority-ruler.raku +# +# TASK #1 › Majority Element +# Submitted by: Mohammad S Anwar +# 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). +# +# Example 1 +# Input: @A = (1, 2, 2, 3, 2, 4, 2) +# Output: 2, as 2 appears 4 times in the list which is more than floor(7/2). +# +# Example 2 +# Input: @A = (1, 3, 1, 2, 4, 5) +# Output: -1 as none of the elements appears more than floor(6/2). +# +# +# 2020 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +unit sub MAIN (*@A); + +@A = 1, 2, 2, 3, 2, 4, 2 if @A.elems == 0; +my %count; +%count{$_}++ for @A; + +# is count of first elem count larger than half list size? +my $max = @A.max({%count{$_}}); +say %count{$max} > (@A.elems/2).Int ?? $max !! -1 ; + + diff --git a/challenge-074/colin-crain/raku/ch-2