# Searching for a pattern in a list of tuples

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)
return(left, index)
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


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)]

• Thanks alex. Yes, X will only ever be there at most once. This is much more concise that my original code! Lots to look at here.
– e h
Commented Nov 25, 2013 at 12:59
• The if/elif chain is really hard to follow. For quite a while I was convinced it would have included all preceding elements, rather than just uninterrupted sequences thereof. If this code is not a bottleneck I would consider making redundant tests for clarity. Or at least adding comments. :) Commented Nov 25, 2013 at 16:10

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

• Thanks. These are really good pointers. You have been very helpful.
– e h
Commented Nov 25, 2013 at 17:34

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').