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

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);`

`-*.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

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```

## One thought on “The weekly challenge nr 74”

1. Holli says:

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

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.