10 January 2025 | Challenge 303 |
Earn Evenly
Task 1: 3-digits Even
Submitted by: Mohammad Sajid Anwar
You are given a list (3 or more) of positive integers, @ints
.
Write a script to return all even 3-digits integers that can be formed using the integers in the given list.
Example 1
Input: @ints = (2, 1, 3, 0)
Output: (102, 120, 130, 132, 210, 230, 302, 310, 312, 320)
Example 2
Input: @ints = (2, 2, 8, 8, 2)
Output: (222, 228, 282, 288, 822, 828, 882)
Solution
Instead of using a standard iterator over 3-combinations and filtering the result, here a specific iteration suiting the task is performed.
Firstly we split the given numbers into their decimal digits and transform these into a list of “flagged values”, i.e. the values combined with a flag that signal the availability of this value.
From this list we build two sublists:
- all nonzero elements as “head”
- all even elements as “tail”
As each element must be used only once in the resulting number, we flag an element that is in use as “not available”.
We may combine all unique available elements from “head”, the whole list and “tail” to get the desired numbers.
For the outermost loop we choose the “tail” list as this list is the most restricted one.
Second goes “head” that is restricted, too, and the inner loop goes over the unrestricted rest.
This arrangement ensures that almost all selected values in the outer loops will lead to a nonempty inner loop.
The only exception are the lists ([2468], 0, 0)
where the nonzero digit - when chosen as tail - does not leave anything for the head.
The “flagged values” are implemented as anonymous array refs with the value at 0
and the flag at 1
.
By local
izing the flag a value can be made unavailable and it will automagically re-appear at the end of the surrounding scope.
Though the task does not ask for a sorted result set, it is done here as the examples suggest.
use strict;
use warnings;
use List::UtilsBy 'uniq_by';
use List::Gather;
sub three_digit_even {
my @all = map [$_, 1], map split(//), @_;
my @head = grep $_->[0], @all;
my @tail = grep !($_->[0] % 2), @all;
return [] unless @all >= 3 && @head && @tail;
[sort {$a <=> $b} gather {
for my $d2 (uniq_by {$_->[0]} @tail) {
local $d2->[1];
for my $d0 (uniq_by {$_->[0]} grep $_->[1], @head) {
local $d0->[1];
for my $d1 (uniq_by {$_->[0]} grep $_->[1], @all) {
take $d0->[0].$d1->[0].$d2->[0];
}
}
}
}];
}
See the full solution to task 1.
Task 2: Delete and Earn
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints
.
Write a script to return the maximum number of points you can earn by applying the following operation some number of times.
Pick any ints[i] and delete it to earn ints[i] points.
Afterwards, you must delete every element equal to ints[i] - 1
and every element equal to ints[i] + 1.
Example 1
Input: @ints = (3, 4, 2)
Output: 6
Delete 4 to earn 4 points, consequently, 3 is also deleted.
Finally delete 2 to earn 2 points.
Example 2
Input: @ints = (2, 2, 3, 3, 3, 4)
Output: 9
Delete a 3 to earn 3 points. All 2's and 4's are also deleted too.
Delete a 3 again to earn 3 points.
Delete a 3 once more to earn 3 points.
Solution
We shall maximize the number of earned points, but we’ll look at the game from the opposite direction: Whatever we delete in a move without collecting it, will be irretrievably lost. Everything that does not get lost, will be earned.
Thus we minimize the possible loss in each move.
Interestingly, negative numbers are permitted in this task and @ints = (-1, -1, 0, 1)
looks nice.
Selecting one item, deleting the neighboring values and selecting the remaining items having the same value as the selected one can be regarded as a single move.
use v5.25;
use warnings;
use List::MoreUtils 'frequency';
use POSIX 'Inf';
sub delete_and_earn {
my %vals = frequency @_;
my $points;
outer:
while (%vals) {
my $ml = Inf;
my $sel;
for my $i (keys %vals) {
my $l = ($i - 1) * ($vals{$i - 1} // 0) +
($i + 1) * ($vals{$i + 1} // 0);
($sel, $ml) = ($i, $l) if $l < $ml;
}
$points += $sel * $vals{$sel};
delete @vals{$sel - 1, $sel, $sel + 1};
}
$points;
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.