Any more fares, please?

Weekly challenge 219 — 29 May 2023

Week 219 - 29 May 2023

Task 2

You are given two lists, @costs and @days.

@costs contains the cost of three different types of travel cards you can buy: for example @costs = (5, 30, 90), representing the cost (say in £) of a ticket for 1, 7 and 30 days' travel. So a 7 day ticket costs £30.

@days contains the day number you want to travel in the year: for example: @days = (1, 3, 4, 5, 6), meaning that 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.

For this type of problem we face the choice between:

- A recursive solution looking at all the possibilities.
- An ingenious analysis of the problem showing how it can be solved in a single pass.
- A solution involving a push/pop stack that does the same as recursion, but without using Perl's (rather slow) recursion facility.

I went for 'a' on the grounds that it's easy to do (and I couldn't think of a 'b' solution).

So my solution involves a `sub buy_tickets`

that takes as input
a list of days, a cost so far (initially 0) and an explanation so far (initially '').
It tries one of each of the three ticket types, each starting on the first day
in the list.

If the list can be covered completely by the ticket under conderation, it compares the total price with the best price seen so far, and if it's better, it updates global variables with the current best price and its explanation.

If the list can't be covered completely by one of the ticket types, then if the price so far exceeds the best price so far (for the whole list) it abandons that option, and otherwise it calls itself recursively with the remaining list, the cost so far, and the explanation of that cost.

The recursion will always converge, because there is always a solution of buying a 1-day ticket for each day of travel.

#!/usr/bin/perl use v5.16; # The Weekly Challenge - 2023-05-29 use utf8; # Week 219 task 2 - Travel expenditure use strict; # Peter Campbell Smith use warnings; # Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge my (@costs, @periods, @days, $best_cost, $best_explain); travel_exps([2, 7, 25], [1, 7, 30], [1, 5, 6, 7, 9, 15]); travel_exps([2, 7, 25], [1, 7, 30], [1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31]); travel_exps([2, 7, 13], [1, 7, 14], [1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31]); # generate longer example my ($j, @daysx); for $j (1 .. 100) { push @daysx, $j if rand(1) < 0.4; } travel_exps([2, 7, 13], [1, 7, 14], \@daysx); sub travel_exps { # initialise @costs = @{$_[0]}; @periods = @{$_[1]}; @days = @{$_[2]}; $best_explain = ''; $best_cost = 99999; # start recursive solution buy_tickets(\@days, 0, ''); # show results say qq[\nInput: \@costs = (] . join(', ', @costs) . ')'; say qq[ \@periods = (] . join (', ', @periods) . ')'; say qq[ \@days = (] . join (', ', @days) . ')'; say qq[Output: $best_cost = ] . substr($best_explain, 0, -2); } sub buy_tickets { my (@days_left, $cost, $purchase_day, $j, $valid_until, $explain, $explain2, $cost2, @days_left2); # initialise @days_left = @{$_[0]}; $cost = $_[1]; $explain = $_[2]; # try buying each type of ticket and see which days it covers for ($j = 2; $j >= 0; $j --) { $cost2 = $cost + $costs[$j]; @days_left2 = @days_left; $purchase_day = $days_left2[0]; $explain2 = qq[$explain$periods[$j] day ticket on day $purchase_day, ]; $valid_until = $purchase_day + $periods[$j] - 1; # remove days now paid for while (@days_left2 and $days_left2[0] <= $valid_until) { shift @days_left2; } # have we finished? if (scalar @days_left2 == 0) { # is this the best deal if ($cost2 < $best_cost) { $best_cost = $cost2; $best_explain = $explain2; } # buy more tickets to cover remaining days } elsif ($cost2 < $best_cost) { buy_tickets(\@days_left2, $cost2, $explain2); } } }

Input: @costs = (2, 7, 25) @periods = (1, 7, 30) @days = (1, 5, 6, 7, 9, 15) Output: 11 = 7 day ticket on day 1, 1 day ticket on day 9, 1 day ticket on day 15 Input: @costs = (2, 7, 25) @periods = (1, 7, 30) @days = (1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31) Output: 20 = 7 day ticket on day 1, 7 day ticket on day 10, 1 day ticket on day 20, 1 day ticket on day 30, 1 day ticket on day 31 Input: @costs = (2, 7, 13) @periods = (1, 7, 14) @days = (1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31) Output: 19 = 14 day ticket on day 1, 1 day ticket on day 20, 1 day ticket on day 30, 1 day ticket on day 31 Input: @costs = (2, 7, 13) @periods = (1, 7, 14) @days = (1, 4, 6, 8, 9, 10, 11, 13, 17, 18, 21, 22, 26, 28, 29, 30, 32, 38, 40, 41, 44, 50, 51, 52, 55, 56, 58, 61, 62, 64, 66, 67, 69, 71, 73, 74, 76, 77, 79, 83, 84, 89, 98, 99, 100) Output: 73 = 14 day ticket on day 1, 7 day ticket on day 17, 7 day ticket on day 26, 7 day ticket on day 38, 7 day ticket on day 50, 14 day ticket on day 58, 7 day ticket on day 73, 1 day ticket on day 83, 1 day ticket on day 84, 1 day ticket on day 89, 1 day ticket on day 98, 1 day ticket on day 99, 1 day ticket on day 100

The content of this website which has been created by

Peter Campbell Smith is hereby placed in the public domain

Peter Campbell Smith is hereby placed in the public domain