Traffic speed limit check for intervals

Question

Given 2 lists of tuples limits and speeds, both have the format of [(speed1, time1), (speed2, time2)]. My goal is to write a function to check whether the there is a period of time that the speed exceeds the limit (Return True if exceeds). For example, Given limits = [(50,100), (30, 20)], speeds = [(30, 80), (10, 30), (40, 10)], return True.

The example inputs imply that during the first 100 miles, the speed limit is 50. In the 101-120 mile, speed limit is 30. Since in the speeds list, the last 10 miles have speed 40 > 30, so we return True.

We can assume the inputs are valid, so the limits and speeds list always start and end at the same time.

Can I have some pointers on the correctness and how the code can be refactored?

def speed_check(limits, speeds):
  i, j = 0, 0
  prev_limit_range, prev_speed_range = 0, 0
  while j < len(speeds) and i < len(limits):
    if limits[i][0] < speeds[j][0]:
      return True
    if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
      prev_limit_range += limits[i][1]
      i += 1
    elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
      prev_speed_range += speeds[j][1]
      j += 1
    else:
      prev_limit_range += limits[i][1]
      prev_speed_range += speeds[j][1]
      i += 1
      j += 1

  return False

assert speed([(30, 15), (55, 20)], [(30, 15), (55, 20)]) == False
assert speed([(30, 15), (55, 20)], [(30, 14), (65, 20)]) == True

Answer 1

First, let's look at your answer with comments:

def speed_check(limits, speeds):
  # Explicit assignment of temporary variables
  i, j = 0, 0
  prev_limit_range, prev_speed_range = 0, 0
  # Assumption that speeds and limits will not change during iteration
  while j < len(speeds) and i < len(limits):
    # Multiple if statements make it so that we can't just swap lines of
    # code without breaking things.
    if limits[i][0] < speeds[j][0]: # speed > limit would be more readable
      return True
    # Operator precedence does not jump to the eye. Use parenthesis
    if limits[i][1] + prev_limit_range < speeds[j][1] + prev_speed_range:
      prev_limit_range += limits[i][1]
      i += 1
    elif limits[i][1] + prev_limit_range > speeds[j][1] + prev_speed_range:
      prev_speed_range += speeds[j][1]
      j += 1
    else:
    # Manual incrementation of local variables. 
      prev_limit_range += limits[i][1]
      prev_speed_range += speeds[j][1]
      i += 1
      j += 1

  return False

Python-wise there are multiple parts of your implementation that could be tackled differently. Let's see what we could do.

If you think about this problem graphically, drawing an x-axis for distance and a y-axis for speed, then all you want is to check whether the curve for actual speed ever crosses the curve for speed limits.

You could break down your problem into subparts:

def get_graph(speedlist):
    """Generate a list of tuples into a flatten list as in:
    [(1,2), (3, 4)] -> [1, 1, 3, 3, 3, 3]       
    """
    return [item for x in [y[1]*[y[0]] for y in speedlist] for item in x]

def check_exceeds(speeds, limits):
    speed_graph = get_graph(speeds)
    limits_graph = get_graph(limits)
    return any([x > y for x, y in zip(speed_graph, limits_graph)])

This approach avoids three issues I see in your implementation: excess of if-statements, explicit indexing, and explicit iteration. Why are these issues? Well, it's easy to make mistakes when indexing and manually iterating, and it's easy to forget possible branches when using if/else clauses. Python offers a lot of tooling so that you don't have to do everything yourself, and it's considered good practice to leverage that tooling to make your code both more readable and safe.

For your assertions, there is also no need to compare to True nor False, in case your function is defined in such a way that it returns a boolean:

assert check_exceeds([(30, 15), (55, 20)], [(30, 15), (55, 20)])
assert not check_exceeds([(30, 15), (55, 20)], [(30, 14), (65, 20)])

(quick answer as I was answering the post in StackOverflow before it migrated)

Answer 2

Your code seems to be working fine on the test cases (one the function name is fixed), let's see how it can be improved.

Style

There is an official standard Python style guide called PEP 8. This is highly recommended reading. It gives guidelines to help writing code that is both readable and consistent. The Python community tries to follow these guidelines, more or less strictly (a key aspect of PEP 8 is that it provides guidelines and not strict rules to follow blindly).

Among other things, it advised to

Use 4 spaces per indentation level.

Logic simplification

The comparisons seems complicated but it is actually fairly simple: you compare 2 values and consider 3 situations: they are equal or the first number is smaller or the first number is bigger. To avoid repeating (and computing) the different numbers, you could compute the difference once.

    diff = (limits[i][1] + prev_limit_range) - (speeds[j][1] + prev_speed_range)
    if diff < 0:
        prev_limit_range += limits[i][1]
        i += 1
    elif diff > 0:
        prev_speed_range += speeds[j][1]
        j += 1
    else:
        prev_limit_range += limits[i][1]
        prev_speed_range += speeds[j][1]
        i += 1
        j += 1

By re-organising the terms, we have:

diff = limits[i][1] - speeds[j][1] + prev_limit_range - prev_speed_range

and it appears that only the different between prev_limit_range and prev_speed_range is relevant: we could use a single variable for it.

prev_diff = 0
while j < len(speeds) and i < len(limits):
    if limits[i][0] < speeds[j][0]:
        return True
    diff = limits[i][1] - speeds[j][1] + prev_diff
    if diff < 0:
        prev_diff += limits[i][1]
        i += 1
    elif diff > 0:
        prev_diff += -speeds[j][1]
        j += 1
    else:
        prev_diff += limits[i][1] - speeds[j][1]
        i += 1
        j += 1

But then, prev_diff += limits[i][1] - speeds[j][1] corresponds to prev_diff = prev_diff + limits[i][1] - speeds[j][1] = diff = 0.

Also, storing the relevant data in variable, things get a bit cleaner.

    lim, speed = limits[i][1], speeds[j][1]
    diff = speed - lim
    if diff > prev_diff:
        prev_diff += lim
        i += 1
    elif diff < prev_diff:
        prev_diff += -speed
        j += 1
    else:
        prev_diff = 0
        i += 1
        j += 1

Iterator

Instead of dealing with indices explicitly, you could use iterators and just decide which iterator you "advance" on (I am not 100% convinced it makes things better in your case but it is always a good technique to know):

def speed_check(limits, speeds):
    prev_diff = 0
    speed_iter, limit_iter = iter(speeds), iter(limits)
    try:
        speed_val = next(speed_iter)
        limit_val = next(limit_iter)
        while limit_val[0] >= speed_val[0]:
            diff = speed_val[1] - limit_val[1]
            if diff > prev_diff:
                prev_diff += limit_val[1]
                limit_val = next(limit_iter)
            elif diff < prev_diff:
                prev_diff += -speed_val[1]
                speed_val = next(speed_iter)
            else:
                prev_diff = 0
                limit_val = next(limit_iter)
                speed_val = next(speed_iter)
        return True
    except StopIteration:  # no more values
        return False