PWC 276 › Maximum Frequency and now my Day is Complete

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

I thought I’d take the rare (for me) step of implementing this week’s challenges in Python as well as Perl.

Happy Canada Day!

Task 1 – Complete Day

The first task has us look through a list of hours and count the number of pairs that add up to a multiple of 24.

Perl

My first version was done in a compact functional style, which may be more challenging for Perl novices:

sub complete_day {
    sum0 map { my $m = shift @$_; map { ($m + $_) % 24 == 0 } @$_ }
         map { [ @_[$_ .. $#_] ] } 0..$#_
}

Reading from bottom up as usual, we iterate through the indices of @_ (our hours array) and map { ... } each index to a list of array refs from index to end of list. So, given (1, 2, 3, 4, 5), we would expect to get the following list for this intermediate step:

(
    [ 1, 2, 3, 4, 5 ],
    [ 2, 3, 4, 5 ],
    [ 3, 4, 5 ],
    [ 4, 5 ],
    [ 5 ],
)

The first map { ... } then splits this into $m, with the rest of the values in @$_ (note the shift). $m and @$_ are effectively car and cdr if you recall your lisp (although not many of us still do, I suppose).

There is an inner map { ... } that then adds $m to every value in @$_, and maps to 1 if it is a multiple of 24 and 0 if it is not. sum0 from the core module List::Util simply adds them all up to get a count.

More readable example

A more readable version is as follows:

sub complete_day {
    my $count = 0;
    while (my $m = shift) {
        $count += sum0 map { ($m + $_) % 24 == 0 } @_
    }

    $count
}

This one simply maintains a $count as it goes, peeling off a new $m each time through the while() { ... } loop, with a similar inner map { ... } as before.

For Perl Weekly Challenge code, I like to show off some different programming styles. Which one I would actually use in production is another question entirely.

Python

I didn’t think too hard about this one:

def complete_day(hours):
    count = 0
    for i, m in enumerate(hours):
        for n in filter(lambda n: ((m + n) % 24 == 0), hours[i+1:]):
            count += 1

    return(count)

This works similarly to the second Perl example.

Task 2 – Maximum Frequency

The second task this week has us looking at a list of values, finding the maximum frequency of any particular value, and then returning the total number of items with that maximum frequency. This is best demonstrated by example.

Given (1, 2, 2, 4, 1, 5), both 1 and 2 occur twice, so the maximum frequency is 2. Since there are two different values with that frequency, we would return 2 x 2 = 4.

Given (1, 2, 2, 4, 6, 1, 5, 6), 1, 2, and 6 occur twice, so the maximum frequency is 2, but now there are three different values with that frequency, so we return 3 x 2 = 6.

Perl

sub max_freq {
    my %freq; # Frequency table
    $freq{$_}++ for @_;

    my $max_freq = max values %freq; # Maximal frequency
    
    $max_freq * grep { $_ == $max_freq } values %freq;
}

There are three essential steps here. First, we build a %frequency table, mapping values to the number of times they appear. Then we find the $max_freq with a quick pass through the values of that hash.

The final answer is generated by multiplying $max_freq by the count of values where the frequency is equal to $max_freq. Easy!

Python

def max_freq(ints):
    # Annoying special case for empty list
    if len(ints) == 0:
        return(0)

    # Build the frequency table (freq[n] = # of times n is in ints)
    freq = {} 
    for n in ints: freq[n] = freq.setdefault(n,0) + 1

    max_freq = max(freq.values()) # Maximal frequency

    return(sum(filter(lambda x: x == max_freq, freq.values())))

This roughly follows the Perl code, although we need a special case for empty lists (otherwise we get an error).