Perl Weekly Challenge 219.
My solutions (task 1 and task 2 ) to the The Weekly Challenge - 219.
Task 1: Sorted Squares
Submitted by: Mohammad S Anwar
You are given a list of numbers.
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:
1 # Perl weekly challenge 219
2 # Task 1: Sorted Squares
3 #
4 # See https://wlmb.github.io/2023/05/29/PWC219/#task-1-sorted-squares
5 use v5.36;
6 die <<~"FIN" unless @ARGV;
7 Usage: $0 -- N1 [N2...]
8 to square and sort the numbers N1 N2...
9 The -- is to allow negative numbers as arguments without
10 confusing them with options.
11 FIN
12 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
Submitted by: Mohammad S Anwar
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:
1 # Perl weekly challenge 219
2 # Task 2: Travel Expenditure
3 #
4 # See https://wlmb.github.io/2023/05/29/PWC219/#task-2-travel-expenditure
5 use v5.36;
6 use List::Util qw(min);
7 die <<~"FIN" unless @ARGV > 3;
8 Usage: $0 C1 C7 C30 D1 [D2...]
9 to calculate the travel expenditure for days D1, D2...
10 given the costs C1 C7 and C30 for one, seven and thirty day passes
11 FIN
12 my @kinds=(1,7,30); # kinds of passes
13 my @days=@ARGV; # travel days from input
14 my @costs=splice @days, 0, 3; # the first three are the costs of the passes
15 my $expenditure=cost($days[0]-1, @days); # get cost for all days starting with no ticket
16 say "Costs: @costs, Days: @days, Expenditure: $expenditure";
17
18 # Recursively get the expeditures for the given @days, given a current ticket that
19 # cover up to the $current day
20 sub cost($current, @days){
21 shift @days while @days and $current >= $days[0]; # remove days already paid for
22 return 0 unless @days;
23 my $now=shift(@days);
24 # For each pass, get the remaining cost and choose best
25 my $cost=min map {$costs[$_]+cost($now+$kinds[$_]-1, @days)} 0..2;
26 return $cost;
27 }
28
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
/;
Written on May 29, 2023