Majority Character with Raku

by Arne Sommer

Majority Character with Raku

[88] Published 23. August 2020.

This is my response to the Perl Weekly Challenge #074.

Challenge #074.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(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).

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.

File: majority-element
#! /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> ...]

Challenge #074.2: FNR Character

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 ‘#’

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:

File: fnr-character (changes 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.