Finding if a string exists in a nested tuple in Python

Question

What is the best (and fastest) way, in Python 2.7.x, to check if a string (or any other data type) exists in a nested tuple?

For example:

RECIPES = (
    ('apple', 'sugar', 'extreme_Force'),
    ('banana', 'syrup', 'magical_ends'),
    ('caramel', 'chocolate', 'pancake_MONSTER'),
    ('banana',('someAnother','banana'))
)

This tuples needs to be checked if banana appears in any of the nested tuple and return the location index, in this case 1,0.

Also, the tuples could be nested to any depth.

Answer 1

Recursive multi-location indexing:

import sys
from collections import Sequence,defaultdict

#making code python3-compatible
if sys.version_info[0] == 3:
    basestring = str

def buildLocator(tree):
    locator = defaultdict(list)
    def fillLocator(tree, locator,location):
        for index,item in enumerate(tree):            
            if isinstance(item,basestring):
                locator[item].append(location+(index,))
            elif isinstance(item,Sequence):
                fillLocator(item,locator, location+(index,))
    fillLocator(tree,locator,())
    return locator

RECIPES = (
    ('apple', 'sugar', 'extreme_Force'),
    ('banana', 'syrup', 'magical_ends'),
    ('caramel', 'chocolate', 'pancake_MONSTER'),
    ('banana',('someAnother','banana'))
)
locator = buildLocator(RECIPES)

print(locator['banana'])

prints

[(1, 0), (3, 0), (3, 1, 1)]