Perl Weekly Challenge: Sort Languages to the Largest of Three

Yeah, yeah, it feels like a bit of a stretch this week, but when I saw the tasks, my brain read off “Largest of Three” to the tune of “Power of Two” by The Indigo Girls. No more of a stretch than Three of a Reverse Sum Pair was, I guess.

Task 1: Sort Language

You are given two array of languages and its popularity.

Write a script to sort the language based on popularity.

Example 1

Input: @lang = ('perl', 'c', 'python')
       @popularity = (2, 1, 3)
Output: ('c', 'perl', 'python')

Example 2

Input: @lang = ('c++', 'haskell', 'java')
       @popularity = (1, 3, 2)
Output: ('c++', 'java', 'haskell')

Approach

This could be done with a single loop, using the second array to assign values from the first array to particular indices in the output array:

for (i = 0; i < length(lang); i++) {
  output[ popularity[i]-1 ] = lang[i];
}

But this task is phrased as a sort, so let’s code it that way: the second array has the values we’ll use to compare the first array elements with in a custom sort.

Raku

sub sortLanguage(@lang, @popularity) {
  # build a hash associating @popularity with @lang
  my %lang_pop = map {
    @lang[$_] => @popularity[$_]
  }, @lang.keys;
  my @sorted = @lang.sort({
    # sort by %lang_pop, not @lang
    %lang_pop{$^a} <=> %lang_pop{$^b}
  });
  return @sorted;
}

I’m remembering my discovery last week that @lang.keys would give me the sequence 0, 1, 2.

View the entire Raku script for this task on GitHub.

Perl

Again, the changes from Raku to Perl aren’t Earth-shattering:

sub sortLanguage{
  my ($lang, $popularity) = @_;
  # build a hash associating @popularity with @lang
  my %lang_pop = map {
    $lang->[$_] => $popularity->[$_]
  } 0 .. $#{$lang};
  my @sorted = sort {
    # sort by %lang_pop, not @$lang
    $lang_pop{$a} <=> $lang_pop{$b}
  } @$lang;
  return @sorted;
}

View the entire Perl script for this task on GitHub.

Python

Python’s nifty sorted built-in makes this pretty easy.

def sortLanguage(lang, popularity):
    # build a dict associating popularity with lang
    lang_pop = {
        v: popularity[i] for i,v in enumerate(lang)
    }
    sorted_list = sorted(lang,
                         # sort by lang_pop, not lang
                         key=lambda x: (lang_pop[x]))
    return sorted_list

View the entire Python script for this task on GitHub.


Task 2: Largest of Three

You are given an array of integers >= 0.

Write a script to return the largest number formed by concatenating some of the given integers in any order which is also multiple of 3. Return -1 if none found.

Example 1

Input: @ints = (8, 1, 9)
Output: 981

981 % 3 == 0

Example 2

Input: @ints = (8, 6, 7, 1, 0)
Output: 8760

Example 3

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

Approach

Ok, it’s pretty obvious that the largest combination will have the digits sorted in descending order, so I’m guessing I want to sort the digits first, and then start making combinations until I either a) find a combination that’s a multiple of 3, or b) exhaust my combinations.

Raku

sub largestOfThree(@ints) {
  my $max = -1; # initialize our failure case
  for @ints.combinations -> @combo {
    next unless @combo.elems > 0; # not empty set
    # sort the digits in descending order,
    # join them, then convert to an Int
    my $num = @combo.sort.reverse.join('').Int;
    next unless $num > $max;   # not bigger than current max
    next unless $num % 3 == 0; # not divisible by 3
    $max = $num;
  }
  return $max;
}

View the entire Raku script for this task on GitHub.

Perl

Again,  Algorithm::Combinatorics’ combinations function comes to the rescue.

use Algorithm::Combinatorics qw( combinations );

sub largestOfThree {
  my @ints = @_;
  my $max = -1; # initialize our failure case
  my @combos = map {
    combinations(\@ints, $_)
  } 1 .. scalar(@ints);
  foreach my $combo ( @combos ) {
    # sort the digits in descending order,
    # join them, then convert to an Int
    my $num = join('', reverse sort @$combo) + 0;
    next unless $num > $max;   # not bigger than current max
    next unless $num % 3 == 0; # not divisible by 3
    $max = $num;
  }
  return $max;
}

View the entire Perl script for this task on GitHub.

Python

from itertools import combinations

def largestOfThree(ints):
    # generate a list of combinations
    combos = [
        c for i in range(1, len(ints)+1)
          for c in combinations(ints, i)
    ]
    maxval = -1 # initialize our failure case
    for combo in combos:
        combo_list = list(combo)
        combo_list.sort(reverse=True)
        num = int(''.join(map(str, combo_list)))
        if num <= maxval: # not bigger than current max
            continue
        if num % 3 != 0: # not divisible by 3
            continue
        maxval = num
    return maxval

At least this week I made the nested for loops to generate the combinations prettier.

View the entire Python script for this task on GitHub.


Here’s all my solutions in GItHub: https://github.com/packy/perlweeklychallenge-club/tree/master/challenge-245/packy-anderson