Codility: An activity selection problem about scheduling two enemies to watch movies at a festival

Question

I don't remember the exact wording of the question, but it is clearly an activity selection problem, which is

[...] notable in that using a greedy algorithm to find a solution will always result in an optimal solution.

I put a rough description of the problem in the docstring, and present it together with my solution:

def solution(movies, K, L):
    """
    Given two integers K and L, and a list movies where the value at the ith index 
    represents the number of movies showing on the (i + 1)th day at the festival, returns 
    the maximum number of movies that can be watched in two non-overlapping periods of K and 
    L days, or -1 if no two such periods exist.
    """
    kl_days = [
        sum(movies[k_start:k_start + K] + movies[l_start:l_start + L])
        for k_start in range(len(movies) - K)
        for l_start in range(k_start + K, len(movies) - L + 1)
    ]
    lk_days = [
        sum(movies[k_start:k_start + K] + movies[l_start:l_start + L])
        for l_start in range(len(movies) - L)
        for k_start in range(l_start + L, len(movies) - K + 1)
    ]
    days = [-1] + kl_days + lk_days
    return max(days)

Is there a more elegant way to solve this?

P.S. The function name is fixed for grading purposes.

Answer 1

• Your code is probably around the best it can be performance wise. And so there's not much point splitting hairs finding anything better.

  However you should be able to find something that uses less memory. Something about \$O(L + K)\$ rather than \$O(M^2)\$

• I'd split finding indexes, and sums into two separate functions.

• Your code, to me, looks slightly wrong.

  range(l_start + L, len(movies) - K + 1)
  

  Should probably be:

  range(l_start + L, len(movies) - K)
  

• Finally I'd split your code into two more functions, one that performs the sum, and then one that performs the max.

And so I'd change your code to:

def _solution_indexes(movies, K, L):
    for k in range(movies - K):
        for l in range(k + K, movies - L):
            yield k, l

    for l in range(movies - L):
        for k in range(l + L, movies - K):
            yield k, l

def solution_(movies, K, L):
    for k, l in _solution_indexes(len(movies), K, L):
        yield sum(movies[k:k + K]) + sum(movies[l:l + L])

def solution(movies, K, L):
    return max(solution_(movies, K, L), default=-1)

Answer 2

Mixed Abstractions

It is harder than necessary for me to:

1. Understand the purpose of the program.
2. Understand how the program achieves the purpose.
3. Determine whether or not the program achieves the purpose.

Because the program mixes the mathematical abstractions of "two integers K and L" with the business logic abstractions of "movies", "days", "watching", and "festivals".

Remarks

• Pick one language or the other language (mathematics or business logic) or the other and describe the problem and solution (via code) only in terms of that language.

• Describing the problem and solution in terms of business logic is usually better because it will identify weaknesses in the implementation abstraction. For example: movies have tickets and tickets have prices and availability; festivals have transport and accommodations; and so on. Describing expansion/modification of the business model is more easily done in terms of the language of the business logic and a mathematical description is more likely to contain simplifying assumptions that don't apply later. See the boat rental example in Jackson's Principles of Program Design

• Describing the problem in terms of each language separately is also an option. The business logic language describes the design in terms of movies, days, and festivals. The mathematical logic describes the implementation details as a greedy approach to the activity selection problem.