| 27 February 2024 | Challenge 219 |
Return of the Kit
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.
Preliminary Note
See note in challenge 216.
Solution
My comment from the Octave solution:
This task is very similar to task 2 from week 216. Again, it may be regarded as an integer linear programming task. Each travel day needs to be covered by at least one travel card. Let N be the number of days, then we have 3 * N possible travel cards: starting at each given day with a duration of 1, 7 or 30 days. This leads to N inequalities in 3 * N variables: The count of cards that are valid at each day must be at least one. The objective function as the sum of the prices of the selected cards shall be minimized.
The core of the formulation of an integer linear program is a ternary relation between a travel day \(d_i\), a travel card valid from day \(f_j\) having a duration \(d_k\) that yields true if the travel card is valid on that day.
We may build a \(\mathit{days} \times \mathit{fromdates} \times \mathit{cardtypes}\) 3-d “matrix” \(a_{ijk}^*\) representing this ternary relation. To arrive at an linear program we need to flatten the dimensions \(\mathit{fromdates}\;f_j\) and \(\mathit{cardtypes}\;d_k\) into a single dimension representing a travel card valid from \(f_j\) and valid for \(d_k\) days and yield a matrix \((a_{il})\). The inequalities right-hand-sides are all one, as we need at least one valid travel card per travel day and finally the prices \(c_l\) depend on the card type only.
This leads to the following binary linear program:
\[\begin{gathered} \text{minimize:}\hfill & \sum_l c_l x_l\\ \text{subject to:}\hfill & \sum_l a_{il} x_l & \ge 1\\ & x_l & \in \{0, 1\} \end{gathered}\]The PDL implementation follows this recipe by creating the 3-d relation ndarray, flatten it to 2-d
and building the objecive function coefficients as \(\mathit{days}\)-long blocks of the card prices.
Input args are an AoA holding a list of card duration and price and an array of travel days.
use PDL;
use PDL::NiceSlice;
use PDL::Opt::GLPK;
use feature 'signatures';
sub travel_cost ($crd, $dy) {
my $cards = long @$crd;
my $days = long $dy;
my $from = $days->dummy(1);
my $to = $from + $cards((0))->dummy(0);
my $valid = ($days->dummy(1) >= $from->dummy(0)) &
($days->dummy(1) < $to->dummy(0));
my $a = $valid->clump(1,2)->xchg(0,1);
my $b = ones($days);
my $c = $cards((1))->dummy(0,$days->dim(0))->clump(-1);
my $xopt = null;
my $fopt = null;
my $status = null;
glpk($c, $a, $b, zeros($c), zeros($c), GLP_LO * ones($b),
GLP_BV * ones($c), GLP_MIN, $xopt, $fopt, $status);
my $selection = $xopt->reshape($to->dims);
my $solution = whichND $selection;
($days->dice($solution((0)))->dummy(0)
->glue(0, $cards->dice('X', $solution((1))))->qsortvec->unpdl, $fopt);
}
See the full solution.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.