# 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 }