diff options
Diffstat (limited to 'challenge-074')
92 files changed, 2329 insertions, 29 deletions
diff --git a/challenge-074/arne-sommer/blog.txt b/challenge-074/arne-sommer/blog.txt new file mode 100644 index 0000000000..e2c5b888ac --- /dev/null +++ b/challenge-074/arne-sommer/blog.txt @@ -0,0 +1 @@ +https://raku-musings.com/majority-character.html diff --git a/challenge-074/arne-sommer/raku/ch-1.raku b/challenge-074/arne-sommer/raku/ch-1.raku new file mode 100755 index 0000000000..cde35bbc87 --- /dev/null +++ b/challenge-074/arne-sommer/raku/ch-1.raku @@ -0,0 +1,17 @@ +#! /usr/bin/env raku + +subset NonNegativeInt of Int where * >= 0; + +unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ NonNegativeInt); + +my $N = @A.elems; + +my %count; + +my $floor = floor($N / 2); + +@A.map({ %count{$_}++ }); + +my $value = %count.keys.grep({ %count{$_} > $floor })[0]; + +say $value // '-1'; diff --git a/challenge-074/arne-sommer/raku/ch-2.raku b/challenge-074/arne-sommer/raku/ch-2.raku new file mode 100755 index 0000000000..a253fa6dd4 --- /dev/null +++ b/challenge-074/arne-sommer/raku/ch-2.raku @@ -0,0 +1,39 @@ +#! /usr/bin/env raku + +unit sub MAIN ($S where $S.chars >= 1 && ! $S.contains('#'), :v(:$verbose)); + +my $length = $S.chars; + +my $result; + +for 1 .. $length -> $pass +{ + my $substring = $S.substr(0, $pass); + + my %count; + my @characters; + + for $substring.comb.reverse -> $character + { + @characters.push($character) unless %count{$character}; + %count{$character}++; + } + + my $found = '#'; + + for @characters -> $character + { + if %count{$character} == 1 + { + $found = $character; + last; + } + } + + $result ~= $found; + + say ": Pass $pass: \"$substring\" FNR: $found" if $verbose; +} + +say $result; + diff --git a/challenge-074/arne-sommer/raku/fnr-character b/challenge-074/arne-sommer/raku/fnr-character new file mode 100755 index 0000000000..a253fa6dd4 --- /dev/null +++ b/challenge-074/arne-sommer/raku/fnr-character @@ -0,0 +1,39 @@ +#! /usr/bin/env raku + +unit sub MAIN ($S where $S.chars >= 1 && ! $S.contains('#'), :v(:$verbose)); + +my $length = $S.chars; + +my $result; + +for 1 .. $length -> $pass +{ + my $substring = $S.substr(0, $pass); + + my %count; + my @characters; + + for $substring.comb.reverse -> $character + { + @characters.push($character) unless %count{$character}; + %count{$character}++; + } + + my $found = '#'; + + for @characters -> $character + { + if %count{$character} == 1 + { + $found = $character; + last; + } + } + + $result ~= $found; + + say ": Pass $pass: \"$substring\" FNR: $found" if $verbose; +} + +say $result; + diff --git a/challenge-074/arne-sommer/raku/fnr-character-wrongish b/challenge-074/arne-sommer/raku/fnr-character-wrongish new file mode 100755 index 0000000000..035cda37cb --- /dev/null +++ b/challenge-074/arne-sommer/raku/fnr-character-wrongish @@ -0,0 +1,39 @@ +#! /usr/bin/env raku + +unit sub MAIN ($S where $S.chars >= 1, :v(:$verbose)); + +my $length = $S.chars; + +my $result; + +for 1 .. $length -> $pass +{ + my $substring = $S.substr(0, $pass); + + my %count; + my @characters; + + for $substring.comb.reverse -> $character + { + @characters.push($character) unless %count{$character}; + %count{$character}++; + } + + my $found = '#'; + + for @characters -> $character + { + if %count{$character} == 1 + { + $found = $character; + last; + } + } + + $result ~= $found; + + say ": Pass $pass: \"$substring\" FNR: $found" if $verbose; +} + +say $result; + diff --git a/challenge-074/arne-sommer/raku/majority-element b/challenge-074/arne-sommer/raku/majority-element new file mode 100755 index 0000000000..cde35bbc87 --- /dev/null +++ b/challenge-074/arne-sommer/raku/majority-element @@ -0,0 +1,17 @@ +#! /usr/bin/env raku + +subset NonNegativeInt of Int where * >= 0; + +unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ NonNegativeInt); + +my $N = @A.elems; + +my %count; + +my $floor = floor($N / 2); + +@A.map({ %count{$_}++ }); + +my $value = %count.keys.grep({ %count{$_} > $floor })[0]; + +say $value // '-1'; diff --git a/challenge-074/arne-sommer/raku/majority-element-wrongish b/challenge-074/arne-sommer/raku/majority-element-wrongish new file mode 100755 index 0000000000..73153a18d7 --- /dev/null +++ b/challenge-074/arne-sommer/raku/majority-element-wrongish @@ -0,0 +1,15 @@ +#! /usr/bin/env raku + +unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ Int); + +my $N = @A.elems; + +my %count; + +my $floor = floor($N / 2); + +@A.map({ %count{$_}++ }); + +my $value = %count.keys.grep({ %count{$_} > $floor })[0]; + +say $value // '-1'; diff --git a/challenge-074/ash/raku/ch-1.cpp b/challenge-074/ash/cpp/ch-1.cpp index 74d78a32c3..74d78a32c3 100644 --- a/challenge-074/ash/raku/ch-1.cpp +++ b/challenge-074/ash/cpp/ch-1.cpp diff --git a/challenge-074/brtastic/blog.txt b/challenge-074/brtastic/blog.txt new file mode 100644 index 0000000000..786fe5c2a5 --- /dev/null +++ b/challenge-074/brtastic/blog.txt @@ -0,0 +1 @@ +https://brtastic.xyz/blog/article/perl-weekly-74 diff --git a/challenge-074/brtastic/perl/ch-1.pl b/challenge-074/brtastic/perl/ch-1.pl new file mode 100644 index 0000000000..0bc8072171 --- /dev/null +++ b/challenge-074/brtastic/perl/ch-1.pl @@ -0,0 +1,28 @@ +use v5.30; +use warnings; + +# the solution is based on my own module Quantum::Superpositions::Lazy from CPAN +use Quantum::Superpositions::Lazy; + +sub get_majority +{ + # a superposition will automate all the counting for us + my $list = superpos(@_); + + # superpositions have a built in statistics module + # the result of most_probable is actually a new superposition, it can have multiple states + my ($state) = $list->stats->most_probable->states->@*; + + # we now know that this element is certainly most frequent, but does it have proper weight? + return $state->weight > 0.5 ? $state->value : -1; +} + +use Test::More; + +is get_majority(1, 1, 1, 2), 1; +is get_majority(1, 1, 2, 2), -1; +is get_majority(1, 1, 2, 2, 2), 2; +is get_majority(1, 2, 3, 4), -1; +is get_majority(6), 6; + +done_testing; diff --git a/challenge-074/brtastic/perl/ch-2.pl b/challenge-074/brtastic/perl/ch-2.pl new file mode 100644 index 0000000000..d1a93a1ffd --- /dev/null +++ b/challenge-074/brtastic/perl/ch-2.pl @@ -0,0 +1,43 @@ +use v5.30; +use warnings; +use List::Util qw(first); + +# the solution is based on my own module Quantum::Superpositions::Lazy from CPAN +use Quantum::Superpositions::Lazy; + +sub first_non_repeating +{ + my sub find_fnt + { + my @split = split "", shift; + + # a superposition will automate some of the counting for us + my $split_pos = superpos(@split); + + # the default weight for an element is 1, and weights are merged by values + my @non_repeating = grep { $_->weight == 1 } $split_pos->states->@*; + + return "#" if @non_repeating == 0; + return (shift @non_repeating)->value if @non_repeating == 1; + + # since we have a couple of non-repeating characters, we get the first one + # (the superposition here helps so that we solve this by a simple eq) + my $alternatives = superpos(@non_repeating); + return first { $_ eq $alternatives } @split; + } + + my ($string) = @_; + my $result = ""; + for (1 .. length $string) { + $result .= find_fnt(substr $string, 0, $_); + } + return $result; +} + +use Test::More; + +is first_non_repeating("ababc"), "aab#c"; +is first_non_repeating("xyzzyx"), "xxxxx#"; +is first_non_repeating("geeksforgeeksandgeeksquizfor"), "ggggggggkkksfffffffffffffora"; + +done_testing; diff --git a/challenge-074/cheok-yin-fung/blog.txt b/challenge-074/cheok-yin-fung/blog.txt new file mode 100644 index 0000000000..840701c3dc --- /dev/null +++ b/challenge-074/cheok-yin-fung/blog.txt @@ -0,0 +1 @@ +http://blogs.perl.org/users/c_y_fung/2020/08/self-challenge-and-weekly-challenge.html 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..0b67899143 --- /dev/null +++ b/challenge-074/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,49 @@ +#!/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) { + $c++ if $m==$_; + } + 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) { |