Perl Weekly Challenge: Relatively Lucky

This week I’m having trouble locking in on a musical theme. With the tasks being “Lucky Integer” and “Relative Sort”, nothing really jumps out at me. I finally decided that “Lucky” was the key, and that made me think of Emerson, Lake, and Palmer’s Lucky Man.

Now that we have our musical accompaniment, we can work on Perl Weekly Challenge 284!

Task 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

Approach

Like Task 1 last week, we want to use a Bag to count the occurrences of the integers, and then we filter the Bag to keep only the values we want. Last week, we wanted to keep the values where the count was 1; this week, we want to keep the values where the count equals the value (these are the “lucky” integers). If we wind up with more than one “lucky” integer, we sort to find the largest one.

Raku

Also like Task 1 last week, I was able to get most of the work done in a single statement, but I broke it out into multiple lines so I could comment it and show what each clause was doing.

sub luckyInteger(@ints) {
  my @lucky =
    @ints.Bag                      # count occurrences
         .pairs                    # get key/value pairs
         .grep({ .value == .key }) # keys that match freq
         .map({ .key })            # return just the keys
         .sort({ .Int });          # sort by integer value
  return -1 if @lucky == 0; # return -1 if no lucky int was found
  return @lucky[*-1]; # return the largest lucky int
}

View the entire Raku script for this task on GitHub.

$ raku/ch-1.raku
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

Perl

First, I want to thank Niels van Dijke for last week asking why I was making my Bags with grep and not with for. And, honestly, the answer was that in my brain, I’d relegated postfix keywords to conditionals like if and unless. He even did a benchmark of the various methods, showing that for was the fastest way to build the hash that the Bag is made from:

I’m sure if I were more clever I could find a way to use map and grep to do the operations I have between lines 9-13, but I feel like what I’ve got is pretty clear, and I like to prioritize writing clear code over concise code.

sub luckyInteger(@ints) {
  # thanks to Niels van Dijke (https://github.com/PerlBoy1967)
  # for putting postfix "for" back in my brain!
  my %bag; $bag{$_}++ for @ints; # count occurrences

  my @lucky;
  foreach my($k, $v) (%bag) { # get key/value pairs
    next unless $k == $v; # skip keys that don't match freq
    push @lucky, $k;
  }

  return -1 if @lucky == 0; # return -1 if no lucky int was found
  return (sort @lucky)[-1]; # return the largest lucky int
}

View the entire Perl script for this task on GitHub.

Python

Once again, the Counter datatype in the collections module is essentially the same as a Bag.

from collections import Counter

def luckyInteger(ints):
  bag = Counter(ints)  # count occurrences
  keys = [
    k                      # return just the keys
    for k,v in bag.items() # get key/value pairs
    if v == k              # keys that match freq
  ]

  if len(keys) == 0:
    return -1  # return -1 if no lucky int was found

  return sorted(keys).pop(-1) # return the largest lucky int

View the entire Python script for this task on GitHub.

Elixir

I seem to be using Bags enough that I decided I wanted to create an Elixir module to create a Bag in a single call from my main code.

defmodule Bag do
  @moduledoc """
  Generates a Multiset/Bag implemented as a Map.

  https://en.wikipedia.org/wiki/Multiset
  """
  @moduledoc since: "1.0.0"

  @doc """
  Generates a Bag from an enum.
  """
  def from_enum(enum) do
    {_, bag} = Enum.map_reduce(enum, %{}, fn i, bag ->
      { i, Map.put(bag, i, Map.get(bag, i, 0) + 1) }
    end)
    bag
  end
end

With this new Bag module, making a bag is now as easy as Bag.from_enum(ints), making my code very short:

  def luckyInteger(ints) do
    bag = Bag.from_enum(ints)
    # filter for keys that match their frequency
    keys = Enum.filter(Map.keys(bag), fn k -> k == Map.get(bag, k) end)
    if length(keys) == 0 do
      -1 # return -1 if no lucky int was found
    else
      # return the largest lucky int
      keys |> Enum.sort |> List.last
    end
  end

View the entire Elixir script for this task on GitHub.


Task 2: Relative Sort

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.

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)

Approach

Here I’m making two Bags from the two input lists; we loop through list2‘s elements in the order that they’re in, get the count of that element from list1 from the Bag we made of it, and then push that element into our ordered list that number of times. Then once we’ve exhausted the elements from list2, we sort the remaining elements from list1 and push them onto the ordered list. So we can tell which elements from list1 that are left over once we’ve processed all of list2, I’m removing elements from list1‘s Bag once we add them to the ordered list.

Really, the only reason I’m making a Bag from list2 is so we can validate that the elements are distinct.

Raku

In Raku, the Bag class is immutable, so if I’m going to be deleting elements from it after I’ve created it, I need to use the BagHash class:

SetBag, and Mix are immutable types. Use the mutable variants SetHashBagHash, and MixHash if you want to add or remove elements after the container has been constructed.

I also had to look up how .all worked in Raku. Also note the use of Raku’s xx list repetition operator.

sub relativeSort(@list1, @list2) {
  my %bag1 = @list1.BagHash; # because we want to remove elements
  my %bag2 = @list2.Bag;

  # condition checking
  return '@list2 is not distinct'
    unless %bag2.values.all == 1;

  # build the sorted array
  my @sorted;
  for @list2 -> $l2 {
    return "$l2 ∈ \@list2 but $l2 ∉ \@list1"
      if %bag1{$l2}:!exists;

    # put the appropriate number into the list
    @sorted.push(Slip($l2 xx %bag1{$l2}));

    # remove $l2 from what's remaining in @list1
    %bag1{$l2}:delete;
  }

  # push the remaining numbers from @list1 that
  # weren't in @list2 into the output
  for %bag1.keys.sort -> $l1 {
    @sorted.push(Slip($l1 xx %bag1{$l1}));
  }

  return '(' ~ @sorted.join(', ') ~ ')';
} 

View the entire Raku script for this task on GitHub.

$ raku/ch-2.raku
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)

Error Condition 1:
Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
       @list2 = (1, 0, 3, 2, 0)
Output: @list2 is not distinct

Error Condition 2:
Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
       @list2 = (1, 0, 3, 2, 8)
Output: 8 ∈ @list2 but 8 ∉ @list1

Perl

Again, the Perl solution is pretty much beat-for-beat the same as the Raku solution. all comes courtesy of List::MoreUtils. We’re using Perl’s x repetition operator to push the appropriate number of elements into the ordered list.

use List::MoreUtils qw( all );

sub relativeSort($list1, $list2) {
  # thanks to Niels van Dijke (https://github.com/PerlBoy1967)
  # for putting postfix "for" back in my brain!
  my %bag1; $bag1{$_}++ for @$list1;
  my %bag2; $bag2{$_}++ for @$list2;

  # condition checking
  return '@list2 is not distinct'
    unless all {$_ == 1} values %bag2;

  # build the sorted array
  my @sorted;
  foreach my $l2 (@$list2) {
    return "$l2\@list2 but $l2\@list1"
      if ! exists $bag1{$l2};

    # put the appropriate number into the list
    push @sorted, $_ for ($l2) x $bag1{$l2};

    # remove $l2 from what's remaining in @list1
    delete $bag1{$l2};
  }

  # push the remaining numbers from @list1 that
  # weren't in @list2 into the output
  foreach my $l1 (sort keys %bag1) {
    push @sorted, $_ for ($l1) x $bag1{$l1};
  }

  return '(' . join(', ', @sorted) . ')';
}

View the entire Perl script for this task on GitHub.

Python

Here in Python, I don’t need the Counter to easily check if elements from list2 exist in list1; I can easily do that with in list1. I’m also using a list comprehension to simulate the behavior I’m getting from Raku/Perl repetition operators.

from collections import Counter

def comma_join(arr):
  return ', '.join(map(lambda i: str(i), arr))

def relativeSort(list1, list2):
  bag1 = Counter(list1)
  bag2 = Counter(list2)

  # condition checking
  if len([ k for k,v in bag2.items() if v != 1 ]):
    return '@list2 is not distinct'

  # build the sorted_list array
  sorted_list = []
  for l2 in list2:
    if l2 not in list1:
      return f"{l2} ∈ @list2 but {l2} ∉ @list1"

    # put the appropriate number into the list; if we
    # use .append, sorted_list will be a list of lists
    sorted_list.extend([ l2 for n in range(bag1[l2]) ])

    # remove l2 from what's remaining in list1
    bag1.pop(l2)

  # push the remaining numbers from list1 that
  # weren't in list2 into the output
  for l1 in sorted(bag1.keys()):
    sorted_list.extend([ l1 for n in range(bag1[l1]) ])

  return '(' + comma_join(sorted_list) + ')'

View the entire Python script for this task on GitHub.

Elixir

Like the last task, I’m using my new Bag module to make my Bags in a single statement. Adding an arbitrary number of elements to the ordered list was easily accomplished using Enum.map_reduce/3, but I’m doing it often enough I put it in its own function addToList. As usual, we’re using recursion to process list2, and once we’ve exhausted that list, we’re using another Enum.map_reduce/3 to put the remaining elements from list1 into the ordered list.

I got tired towards the end, so rather than going through the hoops to capture which element in list2 doesn’t exist in list1 for my second error condition, I just assert that some such element exists.

  @doc """
  Helper function to append the element "num"
  to a list "count" times.
  """
  def addToList(list, num, count) do
    {_, list} = Enum.map_reduce(
      1 .. count,
      list,
      fn n, acc -> {n, acc ++ [num]} end
    )
    list
  end

  # when we have exhausted list2, put the remaining elements
  # from list1 into the sorted list in numerical order
  def relativeSort([], bag1, sorted) do
    {_, sorted} = Enum.map_reduce(
      Enum.sort(Map.keys(bag1)),
      sorted,
      fn k, sorted ->
        { k, addToList(sorted, k, Map.get(bag1, k))}
      end
    )
    "(" <> Enum.join(sorted, ", ") <> ")"
  end

  # process list2 element by element, adding elements to
  # the sorted list as many times as they occur in list1
  def relativeSort([next | rest], bag1, sorted) do
    count = Map.get(bag1, next)
    relativeSort(
      rest,
      Map.delete(bag1, next),
      addToList(sorted, next, count)
    )
  end

  # process the two lists, check error conditions, then
  # recursively call relativeSort/3 to build the sorted output
  def relativeSort(list1, list2) do
    bag1 = Bag.from_enum(list1)
    bag2 = Bag.from_enum(list2)

    cond do
      Enum.any?(Map.values(bag2), fn x -> x != 1 end) ->
        "@list2 is not distinct"
      Enum.any?(Map.keys(bag2), fn k -> !Map.has_key?(bag1, k) end) ->
        "At least one element in @list2 is not in @list1"
      true ->
        relativeSort(list2, bag1, [])
    end
  end

View the entire Elixir script for this task on GitHub.


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