The weekly challenge 219 - task 2: travel expenditure

  1 #!/usr/bin/perl
  2 # https://theweeklychallenge.org/blog/perl-weekly-challenge-219/#TASK2
  3 #
  4 # Task 2: Travel Expenditure
  5 # ==========================
  6 #
  7 # You are given two list, @costs and @days.
  8 #
  9 # The list @costs contains the cost of three different types of travel cards you can buy.
 10 #
 11 # For example @costs = (5, 30, 90)
 12 #
 13 # Index 0 element represent the cost of  1 day  travel card.
 14 # Index 1 element represent the cost of  7 days travel card.
 15 # Index 2 element represent the cost of 30 days travel card.
 16 #
 17 # The list @days contains the day number you want to travel in the year.
 18 #
 19 # For example: @days = (1, 3, 4, 5, 6)
 20 #
 21 # The above example means you want to travel on day 1, day 3, day 4, day 5 and day 6 of the year.
 22 #
 23 # Write a script to find the minimum travel cost.
 24 #
 25 # Example 1:
 26 #
 27 # Input: @costs = (2, 7, 25)
 28 #        @days  = (1, 5, 6, 7, 9, 15)
 29 # Output: 11
 30 #
 31 # On day 1, we buy a one day pass for 2 which would cover the day 1.
 32 # On day 5, we buy seven days pass for 7 which would cover days 5 - 9.
 33 # On day 15, we buy a one day pass for 2 which would cover the day 15.
 34 #
 35 # So the total cost is 2 + 7 + 2 => 11.
 36 #
 37 # Example 2:
 38 #
 39 # Input: @costs = (2, 7, 25)
 40 #        @days  = (1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31)
 41 # Output: 20
 42 #
 43 # On day 1, we buy a seven days pass for 7 which would cover days 1 - 7.
 44 # On day 10, we buy a seven days pass for 7 which would cover days 10 - 14.
 45 # On day 20, we buy a one day pass for 2 which would cover day 20.
 46 # On day 30, we buy a one day pass for 2 which would cover day 30.
 47 # On day 31, we buy a one day pass for 2 which would cover day 31.
 48 #
 49 # So the total cost is 7 + 7 + 2 + 2 + 2 => 20.
 50 #
 51 ############################################################
 52 ##
 53 ## discussion
 54 ##
 55 ############################################################
 56 #
 57 # First, we transform the @costs array into a hash that uses
 58 # the number of days as keys and the costs for those number
 59 # of days as the corresponding values. Then we call a recursive
 60 # function that tries to buy a x-day travel card for each
 61 # possible value of x, keep all not-covered days in a temporary
 62 # array and call itself recursively with the remaining days.
 63 # In the end, we keep the minimum possible value.
 64 
 65 use strict;
 66 use warnings;
 67 
 68 travel_expenditure( [2, 7, 25], [1, 5, 6, 7, 9, 15] );
 69 travel_expenditure( [2, 7, 25], [1, 2, 3, 5, 7, 10, 11, 12, 14, 20, 30, 31] );
 70 
 71 sub travel_expenditure {
 72    my ($costs, $days) = @_;
 73    print "Input: \@costs = (" . join(", ", @$costs) . ")\n";
 74    print "       \@days  = (" . join(", ", @$days) . ")\n";
 75    my $tc = {
 76       1 => $costs->[0],
 77       7 => $costs->[1],
 78       30 => $costs->[2],
 79    };
 80    print "Output: " . calculate( $tc, $days) . "\n";
 81 }
 82 
 83 sub calculate {
 84    my ($tc, $days) = @_;
 85    return 0 unless @$days;
 86    my $first = $days->[0];
 87    my $minimum;
 88    foreach my $tc_days ( keys %$tc ) {
 89       my $last = $first + $tc_days;
 90       my $cost = $tc->{$tc_days};
 91       my @tmp;
 92       foreach my $day (@$days) {
 93          push @tmp, $day if $day >= $last;
 94       }
 95       $cost += calculate($tc, \@tmp);
 96       $minimum //= $cost;
 97       $minimum = $cost if $cost < $minimum;
 98    }
 99    return $minimum;
100 }