# RogerBW's Blog

Perl Weekly Challenge 74: more songs about lists 23 August 2020

I’ve been doing the Perl Weekly Challenges. The latest involved finding minima in subsets of lists.

# 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(sizeoflist/2).

Well, obviously I'll use `max` from `List::Util`.

``````sub majority {
my @list=@_;
my %s;
``````

So first I break down the list into hash buckets: the bucket for `N` tells me how many times `N` appears.

``````  map {\$s{\$_}++} @list;
``````

Now look at the highest value in a bucket. If it's higher than half the list size (as required in the problem statement), we have a majority element.

``````  my \$m=max(values %s);
if (\$m > int((scalar @list)/2)) {
``````

So then we invert the hash: key → value becomes value → key. (This will lose data in the case of duplicate values, but we don't care, because we're in the "is a majority element" case, so there can be only one hash bucket with a value of `\$m` and that's the only one we'll be looking at.)

(Obviously this could be done iteratively – go through the hash keys and see which one has value `\$m` – but generally I find that Perl's hash functions are ferociously optimised and usefully fast.)

``````    my %q=map {\$s{\$_} => \$_} keys %s;
return \$q{\$m};
``````

(If I did care about retaining all the data I'd do something like ```map {push @{\$q{\$s{\$_}}},\$_} sort keys %s;``` instead and get a series of arrayrefs in `%q`.)

Otherwise we just return the specified error value.

``````  } else {
return -1;
}
}
``````

Raku works much the same way.

``````sub majority(@list) {
my %s;
map {%s{\$_}++}, @list;
my \$m=max(values %s);
if (\$m > floor(@list.elems/2)) {
my %q=map {%s{\$_} => \$_},keys %s;
return %q{\$m};
} else {
return -1;
}
}
``````

And for an additional challenge I thought I'd give it a go in Python. (I've been meaning to pick this up for a while, and the way I learn languages best is to use them.) Some of the inspirations for Perl6/Raku are obvious. I'll give this first one in full.

``````#! /usr/bin/python3

import unittest

def majority(list):
s=dict()
``````

We don't have autovivification of hash ("dict") elements, so I have to `setdefault` each one before incrementing it. (I'm going to miss that.)

``````    for x in list:
s.setdefault(x,0)
s[x] += 1
m=max(s.values())
if m > int(len(list)/2):
``````

The hash inversion works basically as before, even if I find `map` a more elegant way of doing it.

``````        q=dict()
for x in s.keys():
q[s[x]]=x
return q[m]
else:
return -1
``````

And here's some testing infrastructure, which works basically like the test frameworks in Perl. (I want to pass the whole list as one argument, hence the double parentheses.)

``````class TestMajority(unittest.TestCase):

def test_ex1(self):
self.assertEqual(majority((1, 2, 2, 3, 2, 4, 2)),2,'example 1')

def test_ex2(self):
self.assertEqual(majority((1, 3, 1, 2, 4, 5)),-1,'example 2')

unittest.main()
``````

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

(The examples make it clear that what's actually wanted is the last character that's only occurred once so far.)

``````sub fnr {
my \$in=shift;
my %s;
my @s;
my @o;
``````

So this is a bit fiddly. `@s` is the list of characters that's occurred so far which haven't repeated. `%s` is the mapping of those characters to their counts. And `@o` is the output list.

``````  foreach my \$c (split '',\$in) {
push @s,\$c;
\$s{\$c}++;
``````

Here we strip `@s` of anything which has occurred more than once.

``````    @s=grep {\$s{\$_}<2} @s;
``````

And the last character in `@s`, if any, is the one we want. (If it were really left-to-right, this would be `\$s`.)

``````    if (@s) {
push @o,\$s[-1];
} else {
push @o,'#';
}
}
return join('',@o);
}
``````

Raku is similar, though we can't use array index -1 any more.

``````sub fnr(\$in) {
my %s;
my @s;
my @o;
for \$in.comb -> \$c {
push @s,\$c;
%s{\$c}++;
@s=grep {%s{\$_} < 2},@s;
if (@s) {
push @o,@s[@s.end];
} else {
push @o,'#';
}
}
return join('',@o);
}
``````

And in Python. `ls` is the list-s, equivalent of `@s` above, while `s` is the `%s`. `in` is a reserved word.

``````def fnr(i):
s=dict()
ls=list()
o=list()
``````

Python strings think they're arrays. How quaint! But it makes it handy for splitting. (The actual `split` function can't do this.)

``````    for c in list(i):
ls.append(c)
s.setdefault(c,0)
s[c] += 1
``````

But this list comprehension is quite fun, a sort of composition of `map` and `grep` from perl. I can see I'll use this a lot.

``````        ls=[x for x in ls if s[x]<2]
if len(ls)>0:
o.append(ls[len(ls)-1])
else:
o.append('#')
``````

What a strange syntax for "join the elements of this list with the given separator". `o.join('')` (which is what Raku does) makes rather more sense to me. Hey ho.

``````    return ''.join(o)
``````

So far Python feels more verbose than Perl, but not in a bad way. We'll see.