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.

|   Advent Calendar 2023   |