TL;DR

On with TASK #2 from The Weekly Challenge #219. Enjoy!

# The challenge

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 questions

One question might be how many days we might consider maximum. Thereâ€™s a reference to â€¦ in the year, so I guess it can go from 1 to 366 maximum.

# The solution

A basic brute force makes it for the examples:

#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';

my @days = @ARGV;
my @costs = splice @days, 0, 3;
say travel_expenditure(\@costs, @days);

sub travel_expenditure ($costs, @days) { state$spans = [1, 7, 30];
return 0 unless @days;
my $min; for my$i (0 .. 2) {
my ($first, @pool) = @days; shift @pool while @pool &&$pool[0] < $first +$spans->[$i]; my$cost = $costs->[$i] + __SUB__->($costs, @pool);$min = $cost if (! defined($min)) || ($cost <$min);
}
return $min; }  I like it because I get to use the mythical __SUB__. Anyway, this solution takes a bit too long (well, I donâ€™t know how much, actually) when dealing with the full 366 days, although [Memoize][] can come to the rescue and save the day in a few milliseconds. #!/usr/bin/env perl use v5.24; use warnings; use experimental 'signatures'; use Memoize; no warnings 'recursion'; my @days = @ARGV; my @costs = splice @days, 0, 3; memoize('travel_expenditure'); say travel_expenditure(\@costs, @days); sub travel_expenditure ($costs, @days) {
state $spans = [1, 7, 30]; return 0 unless @days; my$min;
for my $i (0 .. 2) { my ($first, @pool) = @days;
shift @pool while @pool && $pool[0] <$first + $spans->[$i];
my $cost =$costs->[$i] + travel_expenditure($costs, @pool);
$min =$cost if (! defined($min)) || ($cost < $min); } return$min;
}


The Raku version has caching baked in, directly:

#!/usr/bin/env raku
use v6;
sub MAIN (*@days is copy) {
put travel-expenditure(@days.splice(0, 3), @days);
}

sub travel-expenditure (@costs, @days) {
state @spans = 1, 7, 30;
state %cache;
return 0 unless @days;
my $key = @days.join(','); %cache{$key} //= (@costs Z @spans).map(-> ($cost,$span) {
my ($first, @pool) = @days; @pool.shift while @pool && @pool[0] <$first + $span;$cost + samewith(@costs, @pool);
}).min;
}


If you want to travel moreâ€¦ this will probably still work, altough it might syphon more memory. I arrived up to 5 full yearsâ€¦ and it didnâ€™t complain. If you can travel more, you have time to find a more efficient solution!

Stay safe!

Comments? Octodon, , GitHub, Reddit, or drop me a line!