Python Programming Challenge – Intervals of Consecutive Characters

Here’s a fun Python programming challenge:

Write a function which takes a string as input and returns a list of tuples containing the start and end position of the intervals containing each character.

This algorithm is closely related to run-length encoding, which is a form of data compression. Here’s the function stub along with a few assertions to make the task clear:

def find_intervals(data):
    pass


data = 'A'
assert find_intervals(data) == [(0, 0, 'A')]
data = 'BBABBA'
assert find_intervals(data) == [(0, 1, 'B'), (2, 2, 'A'), (3, 4, 'B'), (5, 5, 'A')]
data = 'ABBAABBAA'
assert find_intervals(data) == [(0, 0, 'A'), (1, 2, 'B'), (3, 4, 'A'), (5, 6, 'B'), (7, 8, 'A')]
data = ''
assert find_intervals(data) is None

The key to this algorithm is comparing each character with the one next to it. This can be done by either “looking forward” of “looking backwards” (think i + 1 or i - 1 if i is your loop variable). This kind of logic comes up in several common algorithms covered on Computer Science courses, such as Insertion sort and Bubble Sort.

if you are not familiar with assert in Python, it’s a very handy way to set up some very basic tests. If the condition after the assert keyword is correct, nothing will be displayed, but if not, you will get an AssertionError when you run the code. Obviously with just pass in the function definition all the assertions will fail.

One potential difficulty with this kind of algorithm, and something you might want to give some thought to in advance, is exactly what the range of iteration should be.

Python Intervals Challenge Solution.

Here is one possible solution to the consecutive intervals challenge:

def find_intervals(data):
    if len(data) < 1:
        return
    intervals = []
    current_char = data[0]
    start_of_interval = 0
    for i in range(len(data) - 1):
        if data[i + 1] != current_char:
            intervals.append((start_of_interval, i, current_char))
            start_of_interval = i + 1
            current_char = data[i + 1]
    intervals.append((start_of_interval, len(data) - 1, current_char))

    return intervals


data = 'A'
assert find_intervals(data) == [(0, 0, 'A')]
data = 'BBABBA'
assert find_intervals(data) == [(0, 1, 'B'), (2, 2, 'A'), (3, 4, 'B'), (5, 5, 'A')]
data = 'ABBAABBAA'
assert find_intervals(data) == [(0, 0, 'A'), (1, 2, 'B'), (3, 4, 'A'), (5, 6, 'B'), (7, 8, 'A')]
data = ''
assert find_intervals(data) is None 

Refinement to Python Consecutive Intervals Challenge Solution

The given solution works, but you may notice there is some repetition of code as the last interval is treated separately. With just a small adjustment this issue can be addressed and a more compact and elegant solution can be written. Have a think about how you might do this and try to refine your own solution before looking at mine.

def find_intervals2(data):
    if len(data) < 1:
        return

    data = data + "!"
    intervals = []
    current_char = data[0]
    start_of_interval = 0
    for i in range(len(data) - 1):
        if data[i + 1] != current_char:
            intervals.append((start_of_interval, i, current_char))
            start_of_interval = i + 1
            current_char = data[i + 1]

    return intervals


data = 'A'
assert find_intervals2(data) == [(0, 0, 'A')]
data = 'BBABBA'
assert find_intervals2(data) == [(0, 1, 'B'), (2, 2, 'A'), (3, 4, 'B'), (5, 5, 'A')]
data = 'ABBAABBAA'
assert find_intervals2(data) == [(0, 0, 'A'), (1, 2, 'B'), (3, 4, 'A'), (5, 6, 'B'), (7, 8, 'A')]
data = ''
assert find_intervals2(data) is None

What we did here was to add a “dummy” character to enable us to iterate fully over the string. What do you think of this solution? In this particular example we didn’t save a huge amount of code. However, if there were more program statements in the repeated code, the benefits of the second approach might be more significant. It is certainly a useful and interesting exercise to come with alternative approaches to solving the same problem.

I hope you enjoyed this Python programming challenge. To keep up to date with news and offers, why not sign up to our newsletter if you haven’t already?

Happy computing!

Sharing is caring!