2 Laser beams number of intersections in a mirror problem

I've got an algorithmic problem that I've not been able to solve. Would appreciate any help with this

The main problem:

Two laser beams, blue and red color, are shot into a mirror and bounces around. Find the number of intersections between them. Example:

red = [2, 7, 8, 15, 20]
blue = [3, 4, 5, 7, 10, 16, 21]

Should give me 7

red = [10, 20, 30]
blue = [1, 10, 20]

Should give me 3

My attempt and issue

I've been able to solve the second example by setting up pairs of start and end, and checking for each iteration. But this won't work for the first example, as there are 2 intersections between red = [2] and blue = [3]. I circled this part in the picture. Any suggestion on what I should do would be appreciated.

Code

def count_intersections(red, blue):
    intersections = 0

    # 0 as the starting point
    red_points = [0] + red
    blue_points = [0] + blue

    # Create intervals for red beam
    red_intervals = []
    for i in range(len(red_points) - 1):
        if i % 2 == 0:
            red_intervals.append((red_points[i], red_points[i + 1], "Top"))
        else:
            red_intervals.append((red_points[i], red_points[i + 1], "Bottom"))

    # Create intervals for blue beam
    blue_intervals = []
    for i in range(len(blue_points) - 1):
        if i % 2 == 0:
            blue_intervals.append((blue_points[i], blue_points[i + 1], "Top"))
        else:
            blue_intervals.append((blue_points[i], blue_points[i + 1], "Bottom"))


    # Check all red intervals against all blue intervals
    for r_start, r_end, r_start_pos in red_intervals:
        for b_start, b_end, b_start_pos in blue_intervals:

            # Check if the intervals overlap and the paths cross
            if (r_start <= b_start and r_end >= b_end) or (r_start >= b_start and r_end <= b_end):

                print("check intersects")
                print(r_start, r_end)
                print(b_start, b_end)
                print("next")

                intersections += 1

    return intersections


red = [2, 7, 8, 15, 20]
blue = [3, 4, 5, 7, 10, 16, 21]

# red = [10, 20, 30]
# blue = [1, 10, 20]
# [(0, 10), (10, 20), (20, 30)]
# [(0, 1), (1, 10), (10, 20)]
print(count_intersections(red, blue))

Thanks.

The applicable technique is called a sweep line algorithm.

Imagine a vertical line moving from left to right, and consider every "point of interest" at which you get new relevant information. You only need to process the situations at the points of interest, and there are relatively few of those.

For your problem, the points of interest are just the bounce points, because everything that happens between them is predictable.

To solve it, just check which laser is higher at every bounce point. Let cmp = 1 if red is higher than blue, cmp=-1 if blue is higher than red, or cmp=0 if they're the same. Then you just add 1 intersection to the count every time cmp transitions 1 -> 0, 1 -> -1, -1 -> 0 or -1 -> 1.

The code is super easy:

def count_intersections(red, blue):
    redh = 1 # red starts at the top
    blueh = 1 # blue starts at the top
    cmp = 0 # They are equal height
    intersections = 1 # That counts as an intersection

    redpos = 0
    bluepos = 0
    while redpos < len(red) and bluepos < len(blue):
        oldcmp = cmp
        if red[redpos] == blue[bluepos]:
            # simultaneous bounce
            redpos += 1
            bluepos += 1
            redh = -redh
            blueh = -blueh
            cmp = (redh - blueh) // 2
        elif red[redpos] < blue[bluepos]:
            # red bounce first
            redpos += 1
            redh = -redh
            cmp = redh
        else:
            # blue bounce first
            bluepos += 1
            blueh = -blueh
            cmp = -blueh
        if cmp != oldcmp and oldcmp != 0:
            intersections += 1
    return intersections

red = [2, 7, 8, 15, 20]
blue = [3, 4, 5, 7, 10, 16, 21]
print(count_intersections(red,blue)) # 7

red = [10, 20, 30]
blue = [1, 10, 20]
print(count_intersections(red,blue)) # 3