The weekly challenge nr 74

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 in this post, you can see how you can use the built-in Bag data type.
Task 1. Majority Element (Raku and C++ solutions). Task 2. First Non-Repeating Character (Raku solution).

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

You are given an array of integers of size $N. Write a script to find the majority element. If none found then print -1. The majority element in the list is the one that appears more than floor(size_of_list/2).

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:

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. 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’

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

One thought on “The weekly challenge nr 74”

  1. Nice solutions. Room to improve: Use maxpairs (Task #1) and triangular reduction (Task #2).

    Check out my solutions: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-074/markus-holzer/raku.
    Also interesting: https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-074/wambash/raku

    The sad thing is, us 3 are the only solutions that can count as raku-ish. As in using uniqe features of the language. The other, 9 or so solutions are really just ports from other languages.

Leave a Reply

Your email address will not be published. Required fields are marked *