This is my response to the Perl Weekly Challenge #074.
$N.
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).
Input: @A = (1, 3, 1, 2, 4, 5)
Output: -1 as none of the elements appears more than floor(6/2).
An observation: «more than floor(size_of_list/2)» means more than half the values in the list, so we can only have 0 or 1 majority elements.
File: majority-element-wrongish
#! /usr/bin/env raku
unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ Int); # [1]
my $N = @A.elems; # [2]
my %count; # [3]
my $floor = floor($N / 2); # [4]
@A.map({ %count{$_}++ }); # [5]
my $value = %count.keys.grep({ %count{$_} > $floor })[0]; # [6]
say $value // '-1'; # [7]
[1] A slurpy array that gobbles up the values, from none to infinitely many. So we have to make sure that we get at least one element, and all of them must be integers.
[2] Compute this value, as the challenge named it.
[3] We are collecting the frquency of the values in this one.
[4] As specified in the challenge. Note that we could have used
Int($N / 2) instead, as the size of the array is positive.
[5] Count all the values.
[6] Get the value that occurs more than floor($N / 2) times,
[7] and print that value, or -1 if it does not exist.
See
docs.raku.org/routine/floor for
more information about floor.
Running it:
$ ./majority-element 1 1 1 2 2 2
-1
$ ./majority-element 1 1 1 2 2 2 2
2
$ ./majority-element -1 -1 -1 -1
-1
The last one shows what happens if we allow
negative numbers, especially -1 in the list. So we should disallow that,
even if the challenge didn't specify it. Zero is ok, though.
#! /usr/bin/env raku
subset NonNegativeInt of Int where * >= 0; # [1]
unit sub MAIN (*@A where @A.elems >= 1 && all(@A) ~~ NonNegativeInt); # [1]
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';
[1] The easiest way of ensuring positive values (including zero), is a custom type like this.
Running it with one or more negative values will cause an error:
$ ./majority-element -1 -1 -1 -1
Usage:
./majority-element [<A> ...]
$S.
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’
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 ‘#’
The description is unfortunately wrong. We are choosing the first non-repeating character from the right, and not from left to right (left -> right).
File: fnr-character-wrongish
#! /usr/bin/env raku
unit sub MAIN ($S where $S.chars >= 1, :v(:$verbose)); # [1]
my $length = $S.chars; # [2]
my $result; # [3]
for 1 .. $length -> $pass # [4]
{
my $substring = $S.substr(0, $pass); # [5]
my %count; # [6]
my @characters; # [7]
for $substring.comb.reverse -> $character # [8]
{
@characters.push($character) unless %count{$character}; # [9]
%count{$character}++; # [10]
}
my $found = '#'; # [11]
for @characters -> $character # [12]
{
if %count{$character} == 1 # [13]
{
$found = $character; # [14]
last; # [15]
}
}
$result ~= $found; # [16]
say ": Pass $pass: \"$substring\" FNR: $found" if $verbose;
}
say $result; # [17]
[1] At least one character in the string. Note that verbose mode has appeared again.
[2] The length of the string.
[3] The result is stored here, one character added at the time.
[4] Iterate over the number of characters to consider in each step.
[5] Get the substring.
[6] We are counting the characters.
[7] The order in which a new characters occur, as the order is vital when we choose which one to add to the result string.
[8] Iterate over the characters in the (sub)string, in reverse order so that the first one in the array is the one to use.
[9] The list of unique characters.
[10] The count.
[11] If not found, use the # character.
[12] For each unique character,
[13] if we only found 1,.
[14] • use that one,
[15] • and stop looking.
[16] Add the character to the result string.
[17] Print it.
Running it:
$ ./fnr-character-wrongish ababc
abb#c
$ ./fnr-character-wrongish xyzzyx
xyzyx#
With verbose mode:
$ ./fnr-character-wrongish -v ababc
: Pass 1: "a" FNR: a
: Pass 2: "ab" FNR: b
: Pass 3: "aba" FNR: b
: Pass 4: "abab" FNR: #
: Pass 5: "ababc" FNR: c
abb#c
$ ./fnr-character-wrongish -v xyzzyx
: Pass 1: "x" FNR: x
: Pass 2: "xy" FNR: y
: Pass 3: "xyz" FNR: z
: Pass 4: "xyzz" FNR: y
: Pass 5: "xyzzy" FNR: x
: Pass 6: "xyzzyx" FNR: #
xyzyx#
The program is not fussy about the characters, so # works quite well.
Until the user tries to interpret the output:
$ ./fnr-character-wrongish -v "#####"
: Pass 1: "#" FNR: #
: Pass 2: "##" FNR: #
: Pass 3: "###" FNR: #
: Pass 4: "####" FNR: #
: Pass 5: "#####" FNR: #
#####
We could allow characters only, but that is probably too restrictive (and not in the
spirit of the challenge). So I choose to exclude # only:
unit sub MAIN ($S where $S.chars >= 1 && ! $S.contains('#'), :v(:$verbose));
See
docs.raku.org/routine/contains for
more information about contains.
Running both versions with # in the input:
$ ./fnr-character-wrongish -v "1234#"
: Pass 1: "1" FNR: 1
: Pass 2: "12" FNR: 2
: Pass 3: "123" FNR: 3
: Pass 4: "1234" FNR: 4
: Pass 5: "1234#" FNR: #
1234#
$ ./fnr-character -v "1234#"
Usage:
./fnr-character [-v|--verbose=<Any>] <S>
And that's it.