<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A tiny regex challenge solved without another regex
This notebook presents a small challenge a friend of mine asked me (in Python).
I'll write Python code valid for versions $\geq$ 3.6, and to show of I use the typing module to have type hints.
Step1:  Introduction
Step2:  The solution I came up with
Let's write a simple function that will read this list of intervals, and compress the ones that are not disjoint.
For instance, when reading [(0, 3), (2, 5)], the second interval is not disjoint from the first one, so both can be compressed to (0, 5), which is disjoint from the next one (7, 10).
Let's test (in constant time wrt $n$ number of intervals) if two consecutive intervals are disjoint or not
Step3:  Let's compute the union of two consecutive intervals, if they are not disjoint
Step4:  And now we are reading to compress the list of intervals (in linear time)
Step5:  Example
Step6:  So now we can write the requested function
Step7:  Other examples
<ASSISTANT_TASK:>
Python Code:
import sys
print(sys.version)
from typing import List, Tuple
Position = int
Interval = Tuple[Position, Position]
Explanation: A tiny regex challenge solved without another regex
This notebook presents a small challenge a friend of mine asked me (in Python).
I'll write Python code valid for versions $\geq$ 3.6, and to show of I use the typing module to have type hints.
End of explanation
import re
def bad_events(pattern: str, string: str) -> List[Interval]:
    # m.span(1) = (m.start(1), m.end(1))
    return [m.span(1) for m in re.finditer(f"(?=({pattern}))", string)]
pat = "aca"
strng = "acacavcacabacacbbacacazdbacaca"
# Do you know if there is a regex trick to obtain
# [(0, 5), (7, 10), (11, 14), (17, 22), (25, 30)]
# instead of
bad_events(pat, strng)
# [(0, 3), (2, 5), (7, 10), (11, 14), (17, 20), (19, 22), (25, 28), (27, 30)]
# ?
Explanation: Introduction: the problem a friend of mine asked me
End of explanation
def are_not_disjoint(interval1: Interval, interval2: Interval) -> bool:
    x1, y1 = interval1
    assert x1 <= y1, f"Error: interval = {intervals1} is not a valid interval."
    x2, y2 = interval2
    assert x2 <= y2, f"Error: interval = {intervals2} is not a valid interval."
    if x1 <= x2 <= y1 <= y2:   # interval1 finishes in interval2
        return True
    elif x2 <= x1 <= y2 <= y1: # interval2 finishes in interval1
        return True
    elif x1 <= x2 <= y2 <= y1: # interval2 is included in interval1
        return True
    elif x2 <= x1 <= y1 <= y2: # interval1 is included in interval2
        return True
    return False
assert are_not_disjoint((0, 3), (2, 5))  # True
assert not are_not_disjoint((0, 5), (7, 10))  # False
Explanation: The solution I came up with
Let's write a simple function that will read this list of intervals, and compress the ones that are not disjoint.
For instance, when reading [(0, 3), (2, 5)], the second interval is not disjoint from the first one, so both can be compressed to (0, 5), which is disjoint from the next one (7, 10).
Let's test (in constant time wrt $n$ number of intervals) if two consecutive intervals are disjoint or not:
End of explanation
def union_intervals(interval1: Interval, interval2: Interval) -> bool:
    x1, y1 = interval1
    assert x1 <= y1, f"Error: interval = {intervals1} is not a valid interval."
    x2, y2 = interval2
    assert x2 <= y2, f"Error: interval = {intervals2} is not a valid interval."
    return (min(x1, x2), max(y1, y2))
union_intervals((0, 3), (2, 5))
Explanation: Let's compute the union of two consecutive intervals, if they are not disjoint: (again in constant time)
End of explanation
def compress_intervals(intervals: List[Interval]) -> List[Interval]:
    intervals_after_compression: List[Interval] = []
    n = len(intervals)
    assert n > 0
    current_interval = intervals[0]   # eg (0, 3)
    i = 1
    # as long as we can read another interval in the list
    while i < n:  # ==> O(n) as the inside of the loop is O(1)
        next_interval = intervals[i]  # eg (2, 5)
        if are_not_disjoint(current_interval, next_interval):
            # eg (0, 3) and (2, 5) -> (0, 5)
            current_interval = union_intervals(current_interval, next_interval)
        else:
            # eg (0, 5) and (7, 10) -> (0, 5) is added,
            intervals_after_compression.append(current_interval)
            # and current_interval = next_interval = (7, 10)
            current_interval = next_interval
        i += 1
    # we add the last current interval if it was not yet added
    if current_interval not in intervals_after_compression:
        intervals_after_compression.append(current_interval)
    return intervals_after_compression
Explanation: And now we are reading to compress the list of intervals (in linear time):
End of explanation
# Do you know if there is a regex trick to obtain
# [(0, 5), (7, 10), (11, 14), (17, 22), (25, 30)]
# instead of
intervals = bad_events(pat, strng)
print(intervals)
# [(0, 3), (2, 5), (7, 10), (11, 14), (17, 20), (19, 22), (25, 28), (27, 30)]
# ?
compress_intervals(intervals)
Explanation: Example:
End of explanation
def bad_events_compressed(pat: str, strng: str) -> List[Interval]:
    intervals1 = bad_events(pat, strng)
    intervals2 = compress_intervals(intervals1)
    return intervals2
def test(pat: str, strng: str) -> None:
    print(f"For pattern {pat} and string {strng}, the bad events uncompressed are:\n{bad_events(pat, strng)}\nand the bad events compressed are:\n{bad_events_compressed(pat, strng)}")
test(pat, strng)
Explanation: So now we can write the requested function:
End of explanation
test("acab", "acabacabacabacacavcacabacacbbacacazdbacacaacacavcacabacacbbacacazdbacacaacabacab")
test("merci", "mercimerciderienmercimerki")
Explanation: Other examples
End of explanation
<END_TASK>