The lucky sort

Weekly Challenge 284

Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Lucky Integer

Task

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.

My solution

This task is relatively straight forward, so doesn't require much explanation. I create a dict (hash in Perl) of the frequency of each integer, called freq. I then iterate through the keys of freq (highest value first). If the frequency of the integer is the same as the value, I return that number. If the iterator is exhausted, I return -1.

def lucky_integer(ints: list) -> str:
    freq = Counter(ints)

    for i in sorted(freq, reverse=True):
        if i == freq[i]:
            return i

    return -1

Examples

$ ./ch-1.py 2 2 3 4
2

$ ./ch-1.py 1 2 2 3 3 3
3

$ ./ch-1.py 1 1 1 3
-1

Task 2: Relative Sort

Task

You are given two list 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.

My solution

While Python does have the index function for lists, it will raise a ValueError exception if the item is not in the list. Therefore I have created a function called find_index that will return the position of val in lst if found, or return the length of the list if not.

def find_index(lst: list, val: int):
    return lst.index(val) if val in lst else len(lst)

The Perl solution also has the same function, and uses List::MoreUtil's first_index to find the position.

sub find_index( $lst, $val ) {
    my $idx = first_index { $_ == $val } @$lst;
    return $idx == -1 ? scalar(@$lst) : $idx;
}

I use the sorted function to sort the first list. Each item is sorted by a tuple of the index position and the integer. This ensures that the first part of the resulting list are sorted in accordance with the position in the second list, while the remaining values are sorted numerically.

def relative_sort(list1: list, list2: list) -> list:
    return sorted(list1, key=lambda i: (find_index(list2, i), i))

The Perl solution uses the same logic, but completely different syntax.

sub main ($lists) {
    my $list1 = $lists->[0];
    my $list2 = $lists->[1];

    my @solution = sort {
        find_index( $list2, $a ) <=> find_index( $list2, $b )
          or $a <=> $b
    } @$list1;
    say '(', join( ', ', @solution ), ')';
}

For input via the command line, I take a JSON string that should be a list of list of integers.

Examples

$ ./ch-2.py "[[2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5],[2, 1, 4, 3, 5, 6]]"
(2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)

$ ./ch-2.py "[[3, 3, 4, 6, 2, 4, 2, 1, 3],[1, 3, 2]]"
(1, 3, 3, 3, 2, 2, 4, 4, 6)

$ ./ch-2.py "[[3, 0, 5, 0, 2, 1, 4, 1, 1],[1, 0, 3, 2]]"
(1, 1, 1, 0, 0, 3, 2, 4, 5)