Perl Weekly Challenge: Week 284

Challenge 1:

Lucky Integer

You are given an array of integers, @ints.

Write a script to find the lucky integer if found otherwise return -1. If there are more than one then return the largest.

A lucky integer is an integer that has a frequency in the array equal to its value.

Example 1

Input: @ints = (2, 2, 3, 4)
Output: 2

Example 2

Input: @ints = (1, 2, 2, 3, 3, 3)
Output: 3

Example 3

Input: @ints = (1, 1, 1, 3)
Output: -1

It has now almost become a tradition that I solve the first task of the week as a Raku one-liner. This week is no exception.

my %h = @*ARGS.classify({$_}); say (%h.keys.grep({ $_ == %h{$_}.elems }).sort)[*-1] // -1

(Full code on Github.)

We take the input as a series of command-line arguments. They are converted, using classify() into a hash whose keys are unique numbers in the input and the values are each instance of their occurrence. I thought that I could save a few characters by using the default hash %_ but it clashed with the use of $_ later on so instead I assigned it to a new variable called %h. Next, we .grep() through the keys of %h (with .keys()) and find the one with an equal number of values. This would be enough in most cases but the spec also says that in the event of more than one answer, we should return the largest. So we .sort() the results, wrapping the whole statement we have so far in parentheses to make the results a list and take the last element of the list ([*-1]) The last thing we need to do is output -1 if no lucky integers were found. This is done with the defined-or operator //. Whatever answer is found, it is output with say().

The Perl, as so often happens, is a bit longer due to a lack of features that are standard in Raku.

These lines emulate the behaviour of Rakus' .classify() with one difference; the values of the created hash keys are the count of occurrences of integers in the input not the integers themselves.

my %count;

for my $int (@ints) {
    $count{$int}++;
}

The rest of the code is a straight copy of the equivalent Raku. It can also be contained in one line.

say [sort { $b <=> $a} grep { $_ == $count{$_} } keys %count]->[0] // -1;

(Full code on Github.)

Challenge 2:

Relative Sort

You are given two lists of integers, @list1 and @list2. The elements in the @list2 are distinct and also in the @list1.

Write a script to sort the elements in the @list1 such that the relative order of items in @list1 is same as in the @list2. Elements that is missing in @list2 should be placed at the end of @list1 in ascending order.

Example 1

Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5)
       @list2 = (2, 1, 4, 3, 5, 6)
Output: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)

Example 2

Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3)
       @list2 = (1, 3, 2)
Output: (1, 3, 3, 3, 2, 2, 4, 4, 6)

Example 3

Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
       @list2 = (1, 0, 3, 2)
Output: (1, 1, 1, 0, 0, 3, 2, 4, 5)

The input is taken as two command-line parameters which are strings consisting of numbers separated by spaces. They are converted into Lists using .words().

    my @list1 = $l1.words;
    my @list2 = $l2.words;

The naive algorithm would be to iterate through @list2 and for each number, find the elements in @list1 that match it, and then add them to a list of results. However, this would require multiple traversals through @list1 so would be very inefficient.

We can do better by transforming @list1 into a Hash where the keys are unique numbers and the values are the instances of those numbers. This is the perfect job for .classify().

    my %elems = @list1.classify({ $_ });

We create storage for the results.

    my @result;

Now we iterate through @list2 and for each number we find the appropriate key from the %elems hash. The values associated with that key are added to the @results list making sure to "flatten" them with | so we get individual values instead of a list reference.

    for @list2 -> $e {
        @result.push(| %elems{$e});

We then delete that key from the hash.

        %elems{$e}:delete;
    }

At this point all we have left in %elems are the keys that do not match elements of @list2. These keys are sorted into ascending numeric order and their values are added to @results in a similar fashion to the loop above.

    for %elems.keys.sort -> $e {
        @result.push(| %elems{$e});
        %elems{$e}:delete;
    }

Finally the results are printed out in the same style as in the spec.

    say q{(}, @result.join(q{, }), q{)};
}

(Full code on Github.)

This is the Perl version.

my @list1 = split /\s*/, $ARGV[0];
my @list2 = split /\s*/, $ARGV[1];

As in the previous task, we need to work around the lack of .classify().

my %elems;
for my $int (@list1) {
    push @{$elems{$int}}, $int;
}

The rest of the code works the same as in the Raku version.

my @result;

for my $e (@list2) {
    push @result,  @{$elems{$e}};
    delete $elems{$e};
}

for my $e (sort { $a <=> $b } keys %elems) {
    push @result,  @{$elems{$e}};
    delete $elems{$e};
}

say q{(}, (join q{, }, @result), q{)};

(Full code on Github.)