Perl Weekly Challenge: Week 219
Challenge 1:
Sorted Squares
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)
Perl first for a change.
We can solve this easily as a one-liner. I chose to express the input list as a series of command line arguments. I ran into a problem that negative numbers got treated by the shell (or is it by perl itself?) as switches to the script. I thought it would be enough to enclose such arguments in double quotes e.g. "-2" but that wasn't enough. The solution is to have -- as the first argument which turns off that behaviour. So the way to run example 1 would be: ./ch-1.sh -- "-2" "-1" 0 3 4
@ARGV contains the command-line arguments. map() is used to square each argument. The resulting array is
sorted in ascending numeric order with sort() and join() joins up the result with commas and spaces in between.
say() prints it all out. The additional q{(} and q{)} are only to make the output look like that in the
examples.
say q{(}, (join q{, }, sort { $a <=> $b } map { $_ * $_ } @ARGV), q{)};
The Raku version is also a one-liner. Raku doesn't require -- as the first argument or double-quoting to deal with
negative numbers as arguments. Rakus' .sort() method deal with numeric sorting without special handling.
say q{(}, @*ARGS.map({ $_ * $_ }).sort.join(q{, }), q{)};
Challenge 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.
The first order of business is to provide a way to input cost and days data into the
script from the command-line. I chose to do this by having the first argument be a
string of space-separated numbers representing the days. The other arguments will be
the costs. So for example 1, the arguments would look like this: "1 5 6 7 9 15" 2 7 25.
In Raku, we convert that string of days back into an array like this:
my @days = $days.split(/ \s+ /).map({ $_.Num }).sort;
First the string is broken up based on whitespace with .split(). Then .map() is
used to convert all those substrings back into numbers. (In hindsight Ishould have used .Int as the
day numbers are integers.) Finally the list of days is sorted just in case they were input out of order.
I wanted to represent the costs as a hash where the keys are the number of days the pass is good for and the
values are the cost for the pass. As the number of days is fixed, I just have to assign an element of @costs
to each one.
my %costs;
%costs{'1'} = @costs[0];
%costs{'7'} = @costs[1];
%costs{'30'} = @costs[2];
Now to find the lowest cost we have to try every combination of costs which can be represented as a tree on which a breadth-first search is to be performed. Each node of that tree will be a particular combination of the number of days covered by passes and the total cost of those passes.
We need a FIFO (First In First Out) queue to contain the nodes of the tree. I am just using a standard array for this.
my @q;
The root node of the tree contains all the days and no passes therefore no cost has been assigned yet.
@q.push({ cost => 0, days => @days });
We also need a variable to store the lowest cost found so far. We start it off with the most naive combination—one-day passes for every day.
my $lowestCost = @days.elems * %costs{'1'};
Now while we still have nodes to process in the queue...
while (@q.elems) {
...We pop off the first node in the queue.
my %entry = @q.shift;
If the list of days in that node is empty, it is a leaf node.
if ( %entry{'days'}.elems == 0 ) {
We look at its cost field to see if it lower than the current lowest cost. If it is, it becomes the new lowest cost.
if ( %entry{'cost'} < $lowestCost ) {
$lowestCost = %entry{'cost'};
}
If the list of days in the node is not empty, it means we still need to add some more passes to cover the remaining days.
} else {
However if the cost is greater than the current lowest cost, it is pointless to continue down this branch of the tree so we move on to the next node in the queue if any.
if ( %entry{'cost'} >= $lowestCost ) {
next;
}
For each of the three pass lengths, we calculate the extra days that would be covered by that pass and the additional cost.
my $start = %entry{'days'}[0];
for %costs.keys -> $interval {
my $end = $start + $interval - 1;
my $cost = %entry{'cost'} + %costs{$interval};
The new cost and the remaining days yet uncovered are added as a new node to the end of the queue.
@q.push({
cost => $cost,
days => %entry{'days'}.grep({ $_ > $end })
});
}
}
}
By the time we have fully traversed the tree, we should have the lowest possible cost. We can print it out.
say $lowestCost;
This is the Perl version. The only problem I had in translating it from Raku is having to make the days key of a tree node a list reference instead of a list. I was getting confusing errors without that change.
my @days = sort {$a <=> $b } map { 0 + $_ } split /\s+/, $days;
my %costs;
$costs{1} = $costs[0];
$costs{7} = $costs[1];
$costs{30} = $costs[2];
my @q;
push @q, { cost => 0, days => \@days };
my $lowestCost = (scalar @days) * $costs{'1'};
while (scalar @q) {
my %entry = %{ shift @q };
if ( scalar @{$entry{days}} == 0 ) {
if ( $entry{cost} < $lowestCost ) {
$lowestCost = $entry{cost};
}
} else {
if ( $entry{cost} >= $lowestCost ) {
next;
}
my $start = $entry{days}->[0];
for my $interval (keys %costs) {
my $end = $start + $interval - 1;
my $cost = $entry{cost} + $costs{$interval};
push @q, {
cost => $cost,
days => [ grep { $_ > $end } @{$entry{days}} ]
};
}
}
}
say $lowestCost;