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:
Set
,Bag
, andMix
are immutable types. Use the mutable variantsSetHash
,BagHash
, andMixHash
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