“Angry Professor” Python implementation

Posted on

Problem

Problem Statement

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Input Format

The first line of the input contains T, the number of test cases. Each test case contains two lines.
The first line of each test case contains two space-separated integers, N and K.
The next line contains N space-separated integers, a1,a2,,aNa1,a2,,aN, representing the arrival time of each student.

If the arrival time of a given student is a non-positive integer (ai0ai0), then the student enters before the class starts. If the arrival time of a given student is a positive integer (ai>0ai>0), the student enters after the class has started.

Output Format

For each testcase, print “YES” (without quotes) if the class gets cancelled and “NO” (without quotes) otherwise.

Constraints

111100T10,N1000,KN,ai100,where i[1,N]1T10,1N1000,1KN,100ai100,where i[1,N]

Note

If a student enters the class exactly when it starts (ai=0ai=0), the student is considered to have entered before the class has started.

Sample Input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

Sample Output

YES
NO

Solution

def is_on_time(a):
    return a <= 0

def class_cancelled(expected, arrival_times):
    actual = map(lambda x: 1 if is_on_time(x) else 0, arrival_times).count(1)
    return actual >= expected

def read_int():
    return int(raw_input())

def read_ints():
    return map(int, raw_input().strip().split())

if __name__ == '__main__':
    T = read_int()
    for _ in xrange(T):
        N, K = read_ints()
        A = read_ints()
        print "NO" if class_cancelled(K, A) else "YES"

Solution

def class_cancelled(expected, arrival_times):
    ....
    return actual >= expected

print "NO" if class_cancelled(K, A) else "YES"

class_cancelled is a misnomer. It in fact computes a class_not_cancelled condition: class should be cancelled when actual < expected. Also the problem asks to print “Yes” when the class gets cancelled. Funny how two wrongs make it right.

The roll call can be accomplished using sum(), which is the simplest way to count True values:

def on_time_attendees(arrival_times):
    return sum(t <= 0 for t in arrival_times)

As @vnp mentioned, class_cancelled() actually does the opposite of what its name suggests. Now that you have introduced that confusion, the best way out may be to eliminate that function entirely.

for test_case in xrange(read_int()):
    n, k = read_ints()
    print("YES" if on_time_attendees(read_ints()) < k else "NO")

Readability Counts

I challenge you to come back in a week and tell me what this code does:

def class_cancelled(expected, arrival_times):
    actual = map(lambda x: 1 if is_on_time(x) else 0, arrival_times).count(1)
    return actual >= expected

First of all, you could rewrite it without the lambda by doing:

actual = map(is_on_time, arrival_times).count(True)

but, while more terse, that doesn’t actually aid reability either. You could drop the count() by instead using filter():

actual = len(filter(is_on_time, arrival_times))

but that’s not really any better either.

Both are also inefficient. We’re constructing a new list based on arrival_times, and then iterating over it again to count the 1s or Trues instead of counting them as we go. We can use a generator expression for that:

def class_cancelled(expected, arrival_times):
    actual = sum(1 for t in arrival_times
                 if is_on_time(t))
    return actual >= expected

Or, even better:

def number_on_time(arrival_times):
    return sum(1 for t in arrival_times
               if t <= 0)

...
print "NO" if number_on_time(A) >= K else "YES"

I wouldn’t put the non-positive check in its own function. This is clear enough as it is.


If you want to refactor anything, I would add something like this to your toolkit:

def count_if(iterable, pred):
    return sum(1 for x in iterable if pred(x))

So that:

def number_on_time(arrival_times):
    return count_if(arrival_times, lambda t: t <= 0)

That is easily understood.

Leave a Reply

Your email address will not be published. Required fields are marked *