The Weekly Challenge - 265 (April 15th 2024)
Task #1: 33% Appearance
You are given an array of integers, @ints.
Write a script to find an integer in the given array that appeared 33% or more. If more than one found, return the smallest. If none found then return undef.
Example 1
Input: @ints = (1,2,3,3,3,3,4,2) Output: 3
1 appeared 1 times; 2 appeared 2 times; 3 appeared 4 times.
3 appears 50% of the time so pick that.
Example 2
Input: @ints = (1,1) Output: 1
1 appears twice or 100% of the time so we pick that.
Example 3
Input: @ints = (1,2,3) Output: 1
1 appears 1 time, 2 appears 2 time, 3 appears 1 time.
Since all appear greater than 33% in the given array we pick the smallest value 1.
Solution
The first thing we do is compute the threshold – this is the size of the input multiplied by 0.33.
We then loop through all values:
- updating the count of each number seen.
- If that count becomes greater than the threshold
- We check to see if the new value is the lowest we have seen
- If it we update that lowest value
- Finally we return the lowest value.
challenge-265-task-1 - perl
sub appearance_33 {
my( $threshold, $lowest, %counts ) = 0.33 * @_;
( ! defined $lowest || $_<=$lowest )
&& ( ++$counts{$_} > $threshold )
&& ( $lowest = $_ )
for @_;
$lowest
}
Task #2: Completing Word
You are given a string, $str containing alphnumeric characters and array of strings (alphabetic characters only), @str.
Write a script to find the shortest completing word. If none found return empty string.
A completing word is a word that contains all the letters in the given string, ignoring space and number. If a letter appeared more than once in the given string then it must appear the same number or more in the word.
Example 1
Input: $str = 'aBc 11c'
@str = ('accbbb', 'abc', 'abbc')
Output: 'accbbb'
Our string contains 1 x a, 1 x b, 2 x v.
The only string that matches that is “accbbb”
Example 2
Input: $str = 'Da2 abc'
@str = ('abcm', 'baacd', 'abaadc')
Output: 'baacd'
Our string contains 2 x a, 1 x b, 1 x c, 1 x d.
Both ‘baacd’ & ‘abaadc’ match this requiment – but ‘baacd’ is shorter.
Example 3
Input: $str = 'JB 007'
@str = ('jj', 'bb', 'bjb')
Output: 'bjb'
Our sting contains 1 x j, 1 x b.
The only one that matches this is ‘bjb’
Solution
For all the words we create a frequency map – both the needle and all the entries in the list.
We then compare the frequency of each letter in the search string to see if is contained with the word. If it is we compare the length of the word to the current shortest word and if shorter return that.
This last step avoids any unnecessary sort.
We could use List::Util any and List::MoreUtils freq – but these were slower by roughly 20% & 50% respectively
challenge-265-task-2 - perl
sub completed_word {
my ( %needle, $shortest );
$needle{$_}++ for split //, (lc shift) =~ y{a-z}{}cdr;
O: for( @_ ) {
my %haystack;
$haystack{$_}++ for split //, lc;
$shortest = $_ unless
( defined $shortest && length $_ > length $shortest ) ||
grep { ! exists $haystack{$_} || $needle{$_} > $haystack{$_} }
keys %needle;
}
$shortest
}
About The Weekly Challenge
The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.
These are posted at: