Advent Calendar 2023
| Day 10 | Day 11 | Day 12 |
The gift is presented by W. Luis Mochan. Today he is talking about his solution to The Weekly Challenge - 219. This is re-produced for Advent Calendar 2023 from the original post.
Task 1: Sorted Squares
Write a script to square each number in the list and return the sorted list, increasing order.
Example 1
Input: @list = (-2, -1, 0, 3, 4)
Output: (0, 1, 4, 9, 16)
Example 2
Input: @list = (5, -4, -1, 3, 6)
Output: (1, 9, 16, 25, 36)
This can be solved by just following the instructions: square an sort. To that end we can use map and sort in a simple oneliner:
Example
perl -E 'say "@ARGV -> ", join " ", sort {$a<=>$b} map {$_**2} @ARGV' -- -2 -1 0 3 4
Results:
-2 -1 0 3 4 -> 0 1 4 9 16
The -- in the argument list is to indicate there are no switches, so I can input negative numbers.
Another example:
perl -E 'say "@ARGV -> ", join " ", sort {$a<=>$b} map {$_**2} @ARGV' -- 5 -4 -1 3 6
Results:
5 -4 -1 3 6 -> 1 9 16 25 36
The full code is almost identical:
use v5.36;
die <<~"FIN" unless @ARGV;
Usage: $0 -- N1 [N2...]
to square and sort the numbers N1 N2...
The -- is to allow negative numbers as arguments without
confusing them with options.
FIN
say "@ARGV -> ", join " ", sort {$a<=>$b} map {$_**2} @ARGV;
Examples:
./ch-1.pl -2 -1 0 3 4
./ch-1.pl 5 -4 -1 3 6
Results:
-2 -1 0 3 4 -> 0 1 4 9 16
5 -4 -1 3 6 -> 1 9 16 25 36
Task 2: Travel Expenditure
You are given two list, @costs and @days.
The list @costs contains the cost of three different types of travel cards you can buy.
For example @costs = (5, 30, 90)
Index 0 element represent the cost of 1 day travel card.
Index 1 element represent the cost of 7 days travel card.
Index 2 element represent the cost of 30 days travel card.
The list @days contains the day number you want to travel in the year.
For example: @days = (1, 3, 4, 5, 6)
The above example means you want to travel on day 1, day 3, day 4, day 5 and
day 6 of the year. Write a script to find the minimum travel cost.
Example 1:
Input: @costs = (2, 7, 25)
@days = (1, 5, 6, 7, 9, 15)
Output: 11
On day 1, we buy a one day pass for 2 which would cover the day 1.
On day 5, we buy seven days pass for 7 which would cover days 5 - 9.
On day 15, we buy a one day pass for 2 which would cover the day 15.
So the total cost is 2 + 7 + 2 => 11.
Example 2:
Input: @costs = (2, 7, 25)
@days = (1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31)
Output: 20
On day 1, we buy a seven days pass for 7 which would cover days 1 - 7.
On day 10, we buy a seven days pass for 7 which would cover days 10 - 14.
On day 20, we buy a one day pass for 2 which would cover day 20.
On day 30, we buy a one day pass for 2 which would cover day 30.
On day 31, we buy a one day pass for 2 which would cover day 31.
So the total cost is 7 + 7 + 2 + 2 + 2 => 20.
An exhaustive search would get expensive for large inputs, but it is simple and might be enough for many use cases. I use the fact that a subsequence of an optimum sequence is itself optimum, so that I can make a recursive search for the solution. I’ll assume that the days are positive and sorted for the short solution. I relax the assumptions for the full solution. I assume the input consists of the costs for the three kind of passes (1, 7, 30) followed by the travel days. The code fits a two-liner:
perl -MList::Util=min -E '@p=(1,7,30); @d=@ARGV; @c=splice @d,0,3; say "Costs: @c, Days @d, Tot: ",f(0, @d); sub f($u,@r){ shift @r while @r && $u>=$r[0]; return 0 unless @r; my $n=shift @r; return min map {$c[$_]+f($n+$p[$_]-1,@r)} 0..2;}' 2 7 25 1 5 6 7 9 15
Results:
Costs: 2 7 25, Days 1 5 6 7 9 15, Tot: 11
I leave the explanation to the full code.
Example 2:
perl -MList::Util=min -E '@p=(1,7,30); @d=@ARGV; @c=splice @d,0,3; say "Costs: @c, Days @d, Tot: ",f(0, @d); sub f($u,@r){ shift @r while @r && $u>=$r[0]; return 0 unless @r; my $n=shift @r; return min map {$c[$_]+f($n+$p[$_]-1,@r)} 0..2;}' 2 7 25 1 2 3 5 7 10 11 12 14 20 30 31
Results:
Costs: 2 7 25, Days 1 2 3 5 7 10 11 12 14 20 30 31, Tot: 20
The full code is:
use v5.36;
use List::Util qw(min);
die <<~"FIN" unless @ARGV > 3;
Usage: $0 C1 C7 C30 D1 [D2...]
to calculate the travel expenditure for days D1, D2...
given the costs C1 C7 and C30 for one, seven and thirty day passes
FIN
my @kinds=(1,7,30); # kinds of passes
my @days=@ARGV; # travel days from input
my @costs=splice @days, 0, 3; # the first three are the costs of the passes
my $expenditure=cost($days[0]-1, @days); # get cost for all days starting with no ticket
say "Costs: @costs, Days: @days, Expenditure: $expenditure";
# Recursively get the expeditures for the given @days, given a current ticket that
# cover up to the $current day
sub cost($current, @days){
shift @days while @days and $current >= $days[0]; # remove days already paid for
return 0 unless @days;
my $now=shift(@days);
# For each pass, get the remaining cost and choose best
my $cost=min map {$costs[$_]+cost($now+$kinds[$_]-1, @days)} 0..2;
return $cost;
}
Examples:
./ch-2.pl 2 7 25 1 5 6 7 9 15
./ch-2.pl 2 7 25 1 2 3 5 7 10 11 12 14 20 30 31
Results:
Costs: 2 7 25, Days: 1 5 6 7 9 15, Expenditure: 11
Costs: 2 7 25, Days: 1 2 3 5 7 10 11 12 14 20 30 31, Expenditure: 20
If you have any suggestion then please do share with us perlweeklychallenge@yahoo.com.