minimum_tickets_cost.py

"""
Author : Alexander Pantyukhin
Date : November 1, 2022

Task:
Given a list of days when you need to travel. Each day is integer from 1 to 365.
You are able to use tickets for 1 day, 7 days and 30 days.
Each ticket has a cost.

Find the minimum cost you need to travel every day in the given list of days.

Implementation notes:
implementation Dynamic Programming up bottom approach.

Runtime complexity: O(n)

The implementation was tested on the
leetcode: https://leetcode.com/problems/minimum-cost-for-tickets/


Minimum Cost For Tickets
Dynamic Programming: up -> down.
"""

importfunctools


defmincost_tickets(days: list[int], costs: list[int]) ->int:
"""
 >>> mincost_tickets([1, 4, 6, 7, 8, 20], [2, 7, 15])
 11

 >>> mincost_tickets([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [2, 7, 15])
 17

 >>> mincost_tickets([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [2, 90, 150])
 24

 >>> mincost_tickets([2], [2, 90, 150])
 2

 >>> mincost_tickets([], [2, 90, 150])
 0

 >>> mincost_tickets('hello', [2, 90, 150])
 Traceback (most recent call last):
 ...
 ValueError: The parameter days should be a list of integers

 >>> mincost_tickets([], 'world')
 Traceback (most recent call last):
 ...
 ValueError: The parameter costs should be a list of three integers

 >>> mincost_tickets([0.25, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [2, 90, 150])
 Traceback (most recent call last):
 ...
 ValueError: The parameter days should be a list of integers

 >>> mincost_tickets([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [2, 0.9, 150])
 Traceback (most recent call last):
 ...
 ValueError: The parameter costs should be a list of three integers

 >>> mincost_tickets([-1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [2, 90, 150])
 Traceback (most recent call last):
 ...
 ValueError: All days elements should be greater than 0

 >>> mincost_tickets([2, 367], [2, 90, 150])
 Traceback (most recent call last):
 ...
 ValueError: All days elements should be less than 366

 >>> mincost_tickets([2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [])
 Traceback (most recent call last):
 ...
 ValueError: The parameter costs should be a list of three integers

 >>> mincost_tickets([], [])
 Traceback (most recent call last):
 ...
 ValueError: The parameter costs should be a list of three integers

 >>> mincost_tickets([2, 3, 4, 5, 6, 7, 8, 9, 10, 30, 31], [1, 2, 3, 4])
 Traceback (most recent call last):
 ...
 ValueError: The parameter costs should be a list of three integers
 """

# Validation
ifnotisinstance(days, list) ornotall(isinstance(day, int) fordayindays):
raiseValueError("The parameter days should be a list of integers")

iflen(costs) !=3ornotall(isinstance(cost, int) forcostincosts):
raiseValueError("The parameter costs should be a list of three integers")

iflen(days) ==0:
return0

ifmin(days) <=0:
raiseValueError("All days elements should be greater than 0")

ifmax(days) >=366:
raiseValueError("All days elements should be less than 366")

days_set=set(days)

@functools.cache
defdynamic_programming(index: int) ->int:
ifindex>365:
return0

ifindexnotindays_set:
returndynamic_programming(index+1)

returnmin(
costs[0] +dynamic_programming(index+1),
costs[1] +dynamic_programming(index+7),
costs[2] +dynamic_programming(index+30),
 )

returndynamic_programming(1)


if__name__=="__main__":
importdoctest

doctest.testmod()