optimal_transport_tickets.py

def solution(arr):
    """
    Take a list of days and return optimal solution for transport fees where
    Tickets are: day (2), weekly (7) and monthly (25) tickets
    And month is bounded to 30 days, first day is 1
    :param arr: list of days
    :type arr: list
    :return: transport month fees
    :type: int
    """
    result = []
    # try to find optimal week
    optimal_week = 7
    while True:
        if optimal_week > 3:
            i = 0
            while (i + optimal_week) < len(arr)+1:
                if len([d for d in arr[i:i+optimal_week] if d < arr[i]+7]) == optimal_week:
                    # found an optimal week, add a weekly ticket
                    result.append(7)
                    # remove days from array
                    arr = arr[:i] + arr[i+optimal_week:]
                    # keep going from i, no need to move index
                else:
                    # slide of a day
                    i += 1
            optimal_week -= 1
        else:
            # the last days are not optimal
            result.append(len(arr) * 2)
            break

    return sum(result) if sum(result) < 25 else 25

assert solution([1, 2, 3, 6, 7, 29, 30]) == 11
assert solution([1, 2, 4, 5, 21, 29, 30]) == 13
assert solution([1, 2, 3, 4, 5, 6, 7, 29, 30]) == 11
assert solution([1, 2, 7, 8, 9, 10, 11, 12, 13]) == 11
assert solution([1, 2, 3, 18, 19, 20, 28, 29, 30]) == 18
assert solution([1, 2, 3, 4, 18, 19, 20, 21, 28, 29, 30]) == 20
assert solution([1, 2, 3, 4, 18, 19, 20, 21, 27, 28, 29, 30]) == 21