Searching for a pattern in a list of tuples

Question

I have written some code to search a for a pattern in a list of tuples.

It works, but I am sure that it can be improved. Any feedback or ideas would be greatly appreciated.

The list of tuples I am searching in looks like this:

x = [('A', True), ('B', True), ('C', False), ('D', False), ('X', False), ('E', True), ('F', True), ('G', True)]

I want to find X and then also grab all the values in the tuple adjacent to X that have a value of true.

So the expected output would be:

X E F G

For:

y = [('X', True), ('1', True), ('2', True), ('3', True), ('4', False), ('5', True)]

The expected output would be:

X 1 2 3

For:

z = [('Dog', True), ('Cow', False), ('Shark', True), ('Cat', True), ('X', False)]

The expected output would be:

Shark Cat X

For:

z = [('C', True), ('X', False), ('D', True), ('C', False), ('S', True)]

The expected output would be:

C X D

This is my code:

test = [('A', False), ('B', False), ('C', True), ('D', True), 
     ('E', True), ('X', False), ('G', True), ('H', False)]

def find_x(x):
    for item in x:
        if item[0] == 'X':
            index = x.index(item)
            return(index)
    return(None)

def look_around(x, index):
    left = 0
    right = len(x)-1    
    found_left = False
    found_right = False

    #look left:
    if index != 0:
        for i in range(index, -1, -1):
            if x[i][1] == True:
                left = i
                found_left = True
            if x[i][1] == False and i != index:
                break

   #look right
    if index != len(x)-1:
        for i in range(index, len(x), +1):
            if x[i][1] == True:
                right = i
                found_right = True
            if x[i][1] == False and i != index:
                break 

    if found_left and found_right:
        return(left, right)
    elif found_left and not found_right:
        return(left, index)
    elif not found_left and found_right:
        return(index, right)
    else:
        return (index, index)

index_of_x = find_x(test)
if index_of_x != None:
    left, right = look_around(test, index_of_x)
    print "match:"
    for i in range (left, right+1, +1):
        print test[i][0], #comma prints everything on same line

Answer 1

If I understand correctly, your problem can be defined as:

• take the longest uninterrupted chain of True elements ending in X
• take X regardless of value
• take all True elements after X until the first False one

So the actual position of X is not relevant, we only need to know if we encountered it or not. Based on this, we can generate the result with only one pass through the input list. This works if at most one X element is present.

Bellow you can see my quick and dirty version of the implementation:

from itertools import count, izip
from collections import namedtuple
Elem = namedtuple('Elem', ['name', 'value'])

def valid_elements(elem_lst):
    valid_elem = []
    found_x = False

    for elem in elem_lst:
        if elem.name == 'X':
            found_x = True
            valid_elem.append(elem)
        elif elem.value:
            valid_elem.append(elem)
        elif found_x:
            break
        else:
            valid_elem = []

    if found_x:
        return valid_elem
    return []

z = [Elem('C', True), Elem('X', False), Elem('D', True), Elem('C', False), Elem('S', True)]
print [elem.name for elem in valid_elements(z)]

Answer 2

I do like alex's solution. That said, you can improve yours incrementally as well. Look for places you can collapse your code. For example let's examine your "look left" code:

#look left:
if index != 0:
    for i in range(index, -1, -1):
        if x[i][1] == True:
            left = i
            found_left = True
        if x[i][1] == False and i != index:
            break

You can leverage the behavior of range() to simplify things a lot here.

• You don't need to check at index, so start your range at index - 1 and skip the last if.
• Consider the behavior of range around the edge cases. Look at what range(1, -1, -1), range(0, -1, -1) and range(-1, -1, -1) return. You should quickly see that you don't need any special handling for starting at index == 0, so you can remove your outer if.
• Looking a bit more globally, if start with left set to index, you don't need found_left at all.
• Oh, and skip comparisons to True.

The result:

left = index
# ...

#look left:
for i in range(index - 1, -1, -1):
    if x[i][1]:
        left = i
    else:
        break

You can apply similar reasoning to cut down on the "look right" code as well, and finally always return left, right

Answer 3

My answer is an overkill but I think it's good to know that such tools exist. You can checkout Parser Combinators.

Some sample code with NLTK.

list_of_tokens = [('hi', 'True'), ('bye', 'Cow'), 
                  ('cartoons', 'True'), ('games', 'True'),
                  ('football', 'False')]

grammar_for_my_type = r"""
    MYCUSTOMTYPE:
    # One or more True followed by a False
    {<True>*<False>}
"""
parser = nltk.chunk.RegexpParser(grammar_for_my_type)
parse_tree = parser.parse(list_of_tokens)

From here you can easily extract all possible matches. In my case this would catch ('cartoons', 'True'), ('games', 'True'), ('football', 'False').