laurent_r

These are some answers to the Week 74 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a few hours from now. This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 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).

Majority Element in Raku

For each list, we need to go through it to count the number of occurrences of each item. We will use a bag to store the histogram of the list, and the max built-in routine to find the most common element in the list. To find the “floor” of half the number of elements, we simply use the div integer division operator.

use v6;

my @A = 1, 2, 7, 7, 7, 2, 3, 2, 4, 2, 7, 7, 7, 8, 1;
my @B = 1, 7, 7, 7, 8, 1, 7, 7, 7;
for (@A, @B) -> $c {
    my Bag $b = $c.Bag;
    my $item = $b.kv.max({$b{$_}});
    my $count = $b{$item};
    say "Majority element for $c:";
    say $count > $c.elems div 2 ?? $item !! -1;
}

This is the output for the two lists of the script:

$ raku majority.raku
Majority element for 1 2 7 7 7 2 3 2 4 2 7 7 7 8 1:
-1
Majority element for 1 7 7 7 8 1 7 7 7:
7

Majority Element in Perl

Perl doesn’t have a Bag data type, but we can simply use a hash to store the histogram of input values. Also, Perl doesn’t have a max built-in, so we’ll implement it manually. Also note that the floor in the specification is kind of a red herring: it is just useless if the number of items in the list is even, and it is also not needed if the number of items is odd, since we can just compare the decimal value to the number of matching items.

use strict;
use warnings;
use feature qw/say/;

my @A = (1, 2, 2, 3, 2, 4, 2, 7, 8, 9, 10);
my %histogram;
$histogram{$_}++ for @A;
my $max = 0;
for my $key (keys %histogram) {
    $max = $key unless $max;
    $max = $key if $histogram{$key} > $histogram{$max};
}
say $histogram{$max} > ( @A / 2) ? $max : -1;

With the list coded in the script the result is as expected:

$ perl majority.pl
-1

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

Sorry: either I miss something, or the first non-repeating character is ill defined. Taking example 1, b is selected at pass 2 and 3. Admittedly, b is not yet repeating at pass 3. But, then, the FNR character at pass 2 should be a. Since I cannot really make sense of the examples provided, I’ll use my own interpretation of the FNR rules, rather that following my initial intention to simply skip the task. At least, Mohammad will not miss his targeted third 100 responses in a row because of me.

FNR Character in Raku

I know this is not what Mohammad Anwar is expecting, but, as I said, I made my own rules:

use v6;

# Note: IMHO, FNR is ill-defined. I'll use my own rules.
my $S = 'ababcbaddccaad';
my @chars = $S.comb;
my $result = "";
my %seen;
for (@chars) {
    my $fnr = "#";
    for @chars -> $char {
        $fnr = $char and last unless %seen{$char};
        $fnr = $char and last if %seen{$char} < 2;
    }
    $result ~= $fnr;
    %seen{$_}++;
}
say $result;

Result:

$ raku non-repeating.raku
aaabcccccc####

FNR Character in Perl

Same comment as before: I know this is not what Mohammad Anwar is expecting, but I made my own rules:

use strict;
use warnings;
use feature qw/say/;

# Note: IMHO, FNR is ill-defined. I'll use my own rules.
my $S = 'ababcbad';
my @chars = split //, $S;
my $result = "";
my %seen;
for (@chars) {
    my $fnr = "#";
    for my $char (@chars) {
        $fnr = $char and last unless $seen{$char};
        $fnr = $char and last if $seen{$char} < 2;
    }
    $result .= $fnr;
    $seen{$_} ++;
}
say $result;

Result:

$ perl non-repeating.pl
aaabcccccc####

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on Sunday, August 30, 2020. And, please, also spread the word about the Perl Weekly Challenge if you can.