“Bag!” “Bag?”
“Bag! Bag!” “What do you mean, bag, bag?”
“Bag! Bag! Bag!” “What bag?”
“No bag!” “No bag?”
“Your bag! Suddenly! Here! Now—gone!”
When I saw the tasks for this week, my programming brain immediately screamed “Bag!” (it’s becoming my favorite class for PWC problems) and the moment that happened, my theater brain immediately went to Vicky and Roger in Noises Off. My wife, however, pointed out that Noises Off isn’t a musical, so she suggested this week’s musical theme, Papa’s Got a Brand New Bag. James Brown is certainly appropriate accompaniment to Perl Weekly Challenge 283…
Task 1: Unique Number
You are given an array of integers, @ints, where every elements appears more than once except one element.
Write a script to find the one element that appears exactly one time.
Example 1
Input: @ints = (3, 3, 1)
Output: 1
Example 2
Input: @ints = (3, 2, 4, 2, 4)
Output: 3
Example 3
Input: @ints = (1)
Output: 1
Example 4
Input: @ints = (4, 3, 1, 1, 1, 4)
Output: 3
Approach
Like I said at the top of this post, when I saw that this problem was all about counting elements in a set, I immediately thought of the Multiset/Bag. A Bag counts how many occurrences each element has, so then all we have to do is filter the bag to include only the keys that occur only once, and then we make a list of those keys, and we grab the only element in the list to print out the value. As a bonus, we can use the list size to catch bad input data: if the list is empty, none of the elements in the input list occur only once, and if the list is 2 or more elements long, more that one element occurred only once.
Raku
Raku makes it easy to so the heavy lifting in one long line of chained method calls: instantiate the Bag from the integer list, convert the Bag to a Seq of Pairs using the .pairs method, .grep through the Seq to include only the Pairs whose .value is 1, and then use .map to pull out just the .key from each Pair (I initially thought I could use .keys, but I realized when I tried it that .keys was operating on the Seq of Pairs, not the Pairs themselves).
sub uniqueNumber(@ints) {
my @keys = @ints.Bag # count occurrences
.pairs # get key/value pairs
.grep({ .value == 1 }) # keys that occur once
.map({ .key }); # return just the keys
# invalid input
return 'no element appears only once'
if @keys == 0;
return 'multiple elements appear only once'
if @keys > 1;
# return the one value
return @keys.shift;
}View the entire Raku script for this task on GitHub.
$ ./raku/ch-1.raku
Example 1:
Input: @ints = (3, 3, 1)
Output: 1
Example 2:
Input: @ints = (3, 2, 4, 2, 4)
Output: 3
Example 3:
Input: @ints = (1)
Output: 1
Example 4:
Input: @ints = (4, 3, 1, 1, 1, 4)
Output: 3
Invalid Input 1 (no element appears only once):
Input: @ints = (4, 1, 1, 1, 4)
Output: no element appears only once
Invalid Input 2 (multiple elements appear only once):
Input: @ints = (1, 2, 3, 4)
Output: multiple elements appear only oncePerl
Of course, in Perl I had to roll my own Bag using a perl hash. I iterate over both the keys and values at the same time (introduced in 5.36.0, made no longer experimental in 5.40.0), and I just do some simple operations to skip keys that occur more than once and put them in an array.
sub uniqueNumber(@ints) {
my %bag;
grep { $bag{$_}++ } @ints; # count occurrences
my @keys;
foreach my($key, $value) (%bag) { # get key/value pairs
next unless $value == 1; # just keys that occur once
push @keys, $key; # return just the keys
}
# invalid input
return 'no element appears only once'
if @keys == 0;
return 'multiple elements appear only once'
if @keys > 1;
# return the one value
return shift @keys;
}View the entire Perl script for this task on GitHub.
Note: reading some of the other solutions, I realized that List::MoreUtils::frequency can be used to instantiate a Bag-like hash:
use List::MoreUtils qw( frequency );
my %bag = frequency(@ints);Python
Once again, the Counter datatype in the collections module is essentially the same as a Bag.
from collections import Counter
def uniqueNumber(ints):
bag = Counter(ints) # count occurrences
keys = [
k # return just the keys
for k,v in bag.items() # get key/value pairs
if v == 1 # keys that occur once
]
# invalid input
if len(keys) == 0:
return 'no element appears only once'
if len(keys) > 1:
return 'multiple elements appear only once'
# return the one value
return keys.pop(0)View the entire Python script for this task on GitHub.
Elixir
My Elixir went through a couple iterations. At first, I had the code I currently have from lines 11-13 and then I had
keys = bag
|> Map.filter(fn {_, v} -> v == 1 end) # keys that occur once
|> Map.keysThen I realized I could make the bag as part of the piped statements:
keys = ints
|> Enum.map_reduce(%{}, fn i, bag ->
{ i, Map.put(bag, i, Map.get(bag, i, 0) + 1) }
end)
|> Kernel.elem(1)
|> Map.filter(fn {_, v} -> v == 1 end) # keys that occur once
|> Map.keysBut I didn’t like the way it looked, so I decided to pull the Enum.map_reduce/3 statement into its own function, at which point I ditched enum/2 and piping and went back to assigning the second value in the tuple returned by map_reduce to a variable and just returning that. I also wanted to play with @doc strings because the purpose of doing these solutions in Elixir is to make me learn more about the language.
@doc """
Helper function that accepts a list and generates a Multiset/
Bag implemented as a Map.
https://en.wikipedia.org/wiki/Multiset
"""
def makeBag(list) do
{_, bag} = Enum.map_reduce(list, %{}, fn i, bag ->
{ i, Map.put(bag, i, Map.get(bag, i, 0) + 1) }
end)
bag
end
@doc """
You are given an array of integers where every element
appears more than once except one element.
Find the one element that appears exactly one time.
"""
def uniqueNumber(ints) do
keys = ints
|> makeBag
|> Map.filter(fn {_, v} -> v == 1 end) # keys that occur once
|> Map.keys # return just the keys from the map
cond do
Kernel.length(keys) == 0 ->
"no element appears only once"
Kernel.length(keys) > 1 ->
"multiple elements appear only once"
true ->
keys |> List.first |> to_string
end
endView the entire Elixir script for this task on GitHub.
Task 2: Digit Count Value
You are given an array of positive integers, @ints.
Write a script to return true if for every index i in the range 0 <= i < size of array, the digit i occurs exactly the $ints[$i] times in the given array, otherwise return false.
Example 1
Input: @ints = (1, 2, 1, 0)
Output: true
$ints[0] = 1, the digit 0 occurs exactly 1 time.
$ints[1] = 2, the digit 1 occurs exactly 2 times.
$ints[2] = 1, the digit 2 occurs exactly 1 time.
$ints[3] = 0, the digit 3 occurs 0 time.
Example 2
Input: @ints = (0, 3, 0)
Output: false
$ints[0] = 0, the digit 0 occurs 2 times rather than 0 time.
$ints[1] = 3, the digit 1 occurs 0 time rather than 3 times.
$ints[2] = 0, the digit 2 occurs exactly 0 time.
Approach
As with task 1, I’m using a Bag to do the heavy lifting of the character counting. Then I loop through the indices of the array and test to see if value of the Bag using that index as the key is equal to the array value at that index.
Raku
This one didn’t lend itself to method chaining, mostly because I’m trying to produce the explanatory text that follows the boolean output.
sub digitCountValue(@ints) {
my %bag = @ints.Bag; # count occurrences
my @explain;
my $passes = True;
for 0 .. @ints.end -> $digit {
my $times = @ints[$digit];
my $occurs = %bag{$digit} // 0;
my $otimes = ($occurs == 0) ?? "0 times"
!! ($occurs >= 2) ?? "$occurs times"
!! "1 time";
if ($times == $occurs) {
@explain.push(
"\$ints[$digit] = $times, the digit $digit " ~
"occurs $otimes"
);
}
else {
$passes = False;
my $ttimes = ($times == 0) ?? "0 times"
!! ($times >= 2) ?? "$times times"
!! "1 time";
@explain.push(
"\$ints[$digit] = $times, the digit $digit " ~
"occurs $otimes rather than $ttimes"
);
}
}
return $passes, @explain.join("\n");
}View the entire Raku script for this task on GitHub.
$ raku/ch-2.raku
Example 1:
Input: @ints = (1, 2, 1, 0)
Output: True
$ints[0] = 1, the digit 0 occurs 1 time
$ints[1] = 2, the digit 1 occurs 2 times
$ints[2] = 1, the digit 2 occurs 1 time
$ints[3] = 0, the digit 3 occurs 0 times
Example 2:
Input: @ints = (0, 3, 0)
Output: False
$ints[0] = 0, the digit 0 occurs 2 times rather than 0 times
$ints[1] = 3, the digit 1 occurs 0 times rather than 3 times
$ints[2] = 0, the digit 2 occurs 0 times
Example 3:
Input: @ints = (0, 1, 2, 2)
Output: False
$ints[0] = 0, the digit 0 occurs 1 time rather than 0 times
$ints[1] = 1, the digit 1 occurs 1 time
$ints[2] = 2, the digit 2 occurs 2 times
$ints[3] = 2, the digit 3 occurs 0 times rather than 2 timesPerl
I used the same code from task 1 to make the Bag of integers. However, because I rolled it myself, it didn’t have one of the most important properties of a Bag: the value of $a{$b} if $b is not an element is 0. In Perl, if key $b doesn’t exist in hash %a, then the value of $a{$b} is undef. Adding the // defined-or operator to use the value 0 if $bag{$digit} is undefined solves that problem. The rest of the changes are just small syntax differences.
sub digitCountValue(@ints) {
my %bag;
grep { $bag{$_}++ } @ints; # count occurrences
my @explain;
my $passes = 1;
foreach my $digit ( 0 .. $#ints ) {
my $times = $ints[$digit];
my $occurs = $bag{$digit} // 0;
my $otimes = ($occurs == 0) ? "0 times"
: ($occurs >= 2) ? "$occurs times"
: "1 time";
if ($times == $occurs) {
push @explain,
"\$ints[$digit] = $times, the digit $digit " .
"occurs $otimes";
}
else {
$passes = 0;
my $ttimes = ($times == 0) ? "0 times"
: ($times >= 2) ? "$times times"
: "1 time";
push @explain,
"\$ints[$digit] = $times, the digit $digit " .
"occurs $otimes rather than $ttimes";
}
}
return $passes ? 'True' : 'False', join("\n", @explain);
}View the entire Perl script for this task on GitHub.
Python
The Counter shares one of the important properties of a Bag: they return a zero count for missing items.
from collections import Counter
def digitCountValue(ints):
bag = Counter(ints) # count occurrences
explain = []
passes = True
for digit in range(len(ints)):
times = ints[digit]
occurs = bag[digit]
otimes = (
"0 times" if occurs == 0 else
f"{occurs} times" if occurs >= 2 else
"1 time"
)
if times == occurs:
explain.append(
f"$ints[{digit}] = {times}, the digit {digit} " +
f"occurs {otimes}"
)
else:
passes = False
ttimes = (
"0 times" if times == 0 else
f"{times} times" if times >= 2 else
"1 time"
)
explain.append(
f"$ints[{digit}] = {times}, the digit {digit} " +
f"occurs {otimes} rather than {ttimes}"
)
return passes, "\n".join(explain)View the entire Python script for this task on GitHub.
Elixir
The big thing in the Elixir implementation is I’m using Enum.map/2 to loop through the indexes and produce a list of tuples containing the index, the number of times it appears, and the number of times the ints array says it should appear. Then I can use Enum.map/2 to build the explanation list from that, and Enum.all?/2 to determine if I’m returning true or false.
@doc """
Helper function that accepts a list and generates a Multiset/
Bag implemented as a Map.
https://en.wikipedia.org/wiki/Multiset
"""
def makeBag(list) do
{_, bag} = Enum.map_reduce(list, %{}, fn i, bag ->
{ i, Map.put(bag, i, Map.get(bag, i, 0) + 1) }
end)
bag
end
@doc """
Return true if for every index i in the range 0 <= i < size
of array, the digit i occurs exactly the $ints[$i] times in
the given array, otherwise return false.
"""
def digitCountValue(ints) do
bag = makeBag(ints)
results = Enum.map(0 .. length(ints)-1, fn digit ->
# return a tuple of {digit, occurrences, expected}
{ digit, Map.get(bag, digit, 0), Enum.at(ints, digit) }
end)
explain = Enum.map(results, fn tuple ->
digit = elem(tuple, 0)
occurs = elem(tuple, 1)
times = elem(tuple, 2)
otimes = cond do
occurs == 0 -> "0 times"
occurs >= 2 -> "#{occurs} times"
true -> "1 time"
end
ttimes = cond do
times == 0 -> "0 times"
times >= 2 -> "#{times} times"
true -> "1 time"
end
if occurs == times do
"$ints[#{digit}] = #{times}, the digit #{digit} " <>
"occurs #{otimes}"
else
"$ints[#{digit}] = #{times}, the digit #{digit} " <>
"occurs #{otimes} rather than #{ttimes}"
end
end)
|> Enum.join("\n")
passes = Enum.all?(results, fn tuple ->
elem(tuple, 1) == elem(tuple, 2)
end)
|> to_string
{passes, explain}
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-283/packy-anderson
Pingback: Perl Weekly Challenge: Relatively Lucky | Packy’s Place