Check if list is valid sequence of chunks

Question

I want to check whether a list is a valid sequence of chunks, where each chunk begins with some value and ends with the next occurrence of the same value. For example, this is a valid sequence of three chunks:

lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
       \___________/  \_____/  \_______________________/

And this is one is invalid:

lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
       \___________/  \_____/  \_____ ... missing the 2 to end the chunk

I have a solution but it's bad. Do you see something better?

def is_valid(lst):
    while lst:
        start = lst.pop(0)
        if start not in lst:
            return False
        while lst[0] != start:
            lst.pop(0)
        lst.remove(start)
    return True

# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))

Answer 1

How about this, creating an iter from the list and searching forward on that iter until the next matching element is found. Note that this might fail is None can be an element of the list; then you should rather define and compare against a sentinel obj = object().

def is_valid(lst):
    it = iter(lst)
    for x in it:
        if next((y for y in it if y == x), None) is None:
            return False
    return True

---

Since we don't actually need the value returned by next, we can also just use any instead, at the same time solving the problem of the default element. Like next, any will consume the iterator just as far as the matching element, if any:

def is_valid(lst):
    it = iter(lst)
    for x in it:
        if not any(y == x for y in it):
            return False
    return True

This can be further shortened using all instead of the outer for loop:

def is_valid(lst):
    it = iter(lst)
    return all(any(y == x for y in it) for x in it)

And this can finally be reduced to the equally cryptic and intriguing:

def is_valid(lst):
    it = iter(lst)
    return all(x in it for x in it)

Each way, each element is visited exactly once, the original list is not changed, little to no extra space, and IMHO it's even somewhat easy to read and understand.

---

This never was about speed, but anyway: Here are some benchmarks of the different solutions (and some more variations), running the test cases from the question as well as two random lists of 1,000 integers, one valid and one invalid, 10,000 times, on Python 3.8.10:

# with long lists             # only short test lists
1.52 is_valid_index           0.22 is_valid_index
3.28 is_valid_next            0.30 is_valid_next
2.78 is_valid_for_for_else    0.13 is_valid_for_for_else
5.26 is_valid_for_any         0.32 is_valid_for_any
5.29 is_valid_all_any         0.38 is_valid_all_any
3.42 is_valid_all_any_if      0.36 is_valid_all_any_if
2.02 is_valid_all_in          0.18 is_valid_all_in
1.97 is_valid_all_in_if       0.17 is_valid_all_in_if
1.87 is_valid_for_in          0.11 is_valid_for_in

Of course, all are O(n). With the long 1000-element-lists, the solution using index is fastest, but the one with x in it is not too bad, either. The any solutions lag somewhat behind, but are about as fast (or slow) as next when using a generator with condition, but still slower than when using plain for loops. With only the short test-lists, it's a bit different: Here, the solutions using one iterator and for-for-else and for-in are fastest by quite some margin.

Answer 2

Here's my take on the problem. I've optimized for readability, not speed (while keeping it in O(n) of course):

def is_valid(sequence):
    iterator = iter(sequence)
    for element in iterator:
        for other in iterator:
            if element == other:
                break
        else:
            return False
    return True

Each iteration of the outer loop corresponds to a chunk. When we're out of elements here we ended the sequence at a chunk border, and we can return True. Otherwise, we loop through the iterator until we find a matching element. If we run out of elements (a for-loop that "naturally" terminates, without break, goes into its else) we return False.

---

And here's another one using itertools. I would not prefer it over the solution above, mostly because of the arcane use of next with a sentinel:

from itertools import dropwhile

def is_valid(iterable):
    iterator = iter(iterable)
    sentinel = object()
    for element in iterator:
        if next(dropwhile(lambda x: x != element, iterator), sentinel) is sentinel:
            return False
    return True

Answer 3

It seems like you want to make sure the last "chunk" is closed at the end of the list. This ought to do that:

def is_valid(lst):
  search = None
  paired = True
  for item in lst:
    if paired:
      search = item
      paired = False
    elif search == item:
      paired = True
  return paired

This is O(n), checks each element only one time, so you won't pay a cost for your start not in lst check that is expensive for long input lists.

Answer 4

Mutating the list with pop(0) is costly and not needed.

You could use index... this may be particularly fast when the chunks are large:

def is_valid(lst):
    i = 0
    n = len(list)
    while i < n:
        try:
            i = lst.index(lst[i], i + 1) + 1
        except:
            return False
    return True

Answer 5

Below is an alternate, recursive solution to the problem. Basically just checks if the next target is in the list, and skips to that index to check again. I am not an expert here, but wanted to try and contribute a different way to solve the question.

def is_valid(
    input_list: list, 
    target_index: int = 0):

    # If we have only one element remaining, or if an empty list is passed initially, there cannot be a pair.
    if len(input_list) <= 1:
        return False
    
    target = input_list[target_index]
    search_range = input_list[target_index + 1 :]

    # print(f"target index: {target_index}")
    # print(f"target: {target}")
    # print(f"search range: {search_range}")
    # print("-------------------------------")

    if target in search_range:

        found_target_sublist_index = search_range.index(target)

        # Plus 2: two indexes start at 0 -> off by two
        next_target_index = target_index + found_target_sublist_index + 2

        if next_target_index == len(input_list):
            return True

        return is_valid(input_list, next_target_index)
    else:
        return False


test_one = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
test_two = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
test_three = ['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']
test_four = ['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']

print(is_valid(test_one)) 
print(is_valid(test_two))
print(is_valid(test_three))
print(is_valid(test_four))

Answer 6

The question does not fully explain if we need a greedy solution or not.

Consider an example - [1, 2, 1, 1]

if we consider a greedy approach, the solution will find the first sequence as [1, 2, 1] and will be left with [1]. And hence, will return False.

But without a greedy approach, the solution will consider [1, 2, 1, 1] as a full sequence and will return True.

I ran the solution provided by you and it returns False, so I am assuming we need a greedy approach.

So, here is one possible solution:

def is_valid(lst):
    to_find = None
    
    for value in lst:
        if to_find is None:
            to_find = value
            continue
        
        if to_find is value:
            to_find = None

    return to_find is None
    
# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))

Answer 7

A short attempt at creating a solution for this:

def isValid(input):
   if len(input) == 0:
       return True
   firstChar = input.pop(0)
   if firstChar not in input:
       return False
   input = input[input.index(firstChar)+1:]
   isValid(input)

While I do not think this is the fastest method, I think it is an interesting enough method to include here. Additionally, this can be optimised a bit further by removing the lines:

if firstChar not in input:
    return False

And put the code in a try/except block, like so:

def isValid(input):
    if len(input) == 0:
        return True
    firstChar = input.pop(0)
    try:
        input = input[input.index(firstChar)+1:]
        isValid(input)
    except:
        return False

as this code would give a ValueError if the index doesnt exist

I haven't tested the exact speed difference at the moment, but I am certain it is not the fastest method, but it should be relatively decent speed-wise.