The weekly challenge nr 74

Hi, The Perl Weekly Challenge was renamed to The Weekly Challenge recently, so there’s a bigger chance that more solutions in other programming languages appear there.

In the two Raku solutions below, you can see how you can use the built-in Bag data type.

Task 1. Majority Element

A Raku solution

OK, fine, let’s take a sample array of integers:

my @a = 1, 2, 2, 3, 2, 4, 2;

Here, 2 is the major element as it appears 4 times and it is more than the half of the length. The only missing thing in the task is what if we have two or more such items? I decided to limit myself to the first such item only.

The traditional approach to count the items in Perl would require using a hash, but in Raku there’s another useful data type: Bag. It is a kind of a hash but if you create it from a list, its values are the number of repetitions of each item:

> dd (1, 2, 2, 3, 2, 4, 2).Bag
(3=>1,1=>1,2=>4,4=>1).Bag

So, we can count all the elements in a single go by converting an array to a bag. Then, sort it by the number of repetitions and take the first item.

my $most-frequent = (@a.Bag.sort: -*.value)[0];

-*.value sorts the bag in descending order. (Alternatively, we could sort with *.value and then take the last item [*-1].)

The main part of the problem is solved, just choose what to print now: either the element or -1. This check is actually longer than the above one-liner 🙂

say $most-frequent.value > @a.elems / 2 ?? $most-frequent.key !! -1;

For the given array, this program prints 2:

$ raku ch-1.raku
2

With another example of input data, 1, 3, 1, 2, 4, 5, the result is -1 as none of the elements is major.

A C++ solution

Here is my solution in another great language of all times, C++.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
    vector<int> data = {1, 2, 2, 3, 2, 4, 2};
    // vector<int> data = {1, 3, 1, 2, 4, 5};

    map<int, int> frequency;
    int max_frequency = 0;
    int major = 0;
    for (auto x : data) {
        if (++frequency[x] > max_frequency) {
            max_frequency = frequency[x];
            major = x;
        }
    }

    cout << (max_frequency > data.size() / 2 ? major : -1) << endl;
}

It uses a range-based for loop, so you need to compile the program against the new C++ standard:

$ g++ --std=c++17 ch-1.cpp

In this program, a map frequency keeps the number of occurrences of each unique integer, and while we are building this map, we are also keeping track of the maximum value max_frequency and its corresponding major element major, so there’s no need to scan the map again (even if I wanted to use some kind of sort algorithm first).

<

Task 2. First Non-Repeating Character

The second task reads as:

It sounds clear but the example is controversial. For the string ab, the first non-repeating character is a but not b. A direct question and the answer did not made it any more clear, so I guess you should read it as from right to left. (There’s an update now but still not clear.) Or something else was meant, which I cannot decipher from the example.

<

Raku solution

Let me just demonstrate the solution. I added reverse to make the result matching the given example.

my $s = 'ababc';
# my $s = 'xxyyzzyx';

for 1..$s.chars -> $pos {
    my $substr = $s.substr(0, $pos).join;
    print "In '$substr': ";
    my $b = bag $substr.comb;
    say $substr.comb.reverse.first({$b{$_} == 1}) // '#';
}

Nevertheless, notice how converting to a Bag is used here:

my $b = bag $substr.comb;

For example, for the string abac, the bag will have the following content:

> bag 'abac'.comb                
Bag(a(2), b, c)

So, we just counted all the letters in the string and prepared a table of their usage.

The program prints the following output:

$ raku ch-2.raku 
In 'a': a
In 'ab': b
In 'aba': b
In 'abab': #
In 'ababc': c

→ GitHub repository
→ Navigation to the Raku challenges post series