The cheapest way to the square

I'm always amazed at how far technology has come. If you told me twenty years ago, I'd be completing this challenge 41,000 feet in the air on a device that is $300 (about US$200), I'd totally laugh at you :)

Unfortunately the budget airline I'm flying with (Air Asia X) doesn't offer WiFi, otherwise I could also push this 41,000 feet in the air too.

Weekly Challenge 219

Challenge, My solution

Task 1: Sorted Squares

Task

You are given a list of numbers.

Write a script to square each number in the list and return the sorted list, increasing order.

My solution

This is straight forward, so doesn't need much explanation. I take the input, square each number, sort the list, and finally print the list.

Examples

$ ./ch-1.py -2 -1 0 3 4
0, 1, 4, 9, 16

$ ./ch-1.py 5 -4 -1 3 6
1, 9, 16, 25, 36

Task 2: Travel Expenditure

Task

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.

My solution

For this task, it's back to using a recursive function. For the input, I take assume the first three values are the cost for a 1 day, 7 day and 30 day pass, and use the rest of the numbers for the days list.

I start by defining the passes dict (hash in Perl), where the key is the days the pass is valid for, and the value is the cost of the pass. I also create the travel_on list (array in Perl) representing the days that I want to travel. This list is sorted numerically.

I then call the buy_pass function with the passes dict and travel_on list. If the later is empty, I don't need to buy any more passes, so return 0. I loop through each item in the passes dict. I know that the days the pass doesn't cover is the first day (i.e. travel_on[0]) plus the days of the pass. I call the function again with the remaining days. I also track the minimum spend, and this is record and sent upstream of the function.

Examples

$ ./ch-2.py 2 7 25 1 5 6 7 9 15
11

$ ./ch-2.py 2 7 25 1 2 3 5 7 10 11 12 14 20 30 31
20