CODEWITHSUNDEEP
pythondictionaryrecursionbinary-search-tree
Dan2783
Dan2783

Reputation: 53

Recursive function to build a string from dictionaries

I'm stuck in a problem with a recursive function.

hints = ['one','two','three', 'four']

firstCity = 'ROME'

dictionary = { 'ROMEone' : { 'PARIS' : {'hello'} , 'CAIRO': {'money'}, 'MOSCOW': {'racing'} },
           'CAIROtwo': { 'MILAN' : {'in'}},
           'PARIStwo': { 'BERLIN' : {'how'} , 'CANCUN' : {'im'} },
           'MOSCOWtwo': { 'AMSTERDAM' : {'cars'} },
           'BERLINthree': { 'AMSTERDAM' : {'are'} },
           'AMSTERDAMthree' : { 'MILAN' : {'are'} },
           'MILANthree' : { 'PARIS' : {'the'} },
           'CANCUNthree' : { 'LONDON' : {'john'}},
           'AMSTERDAMfour': { 'MILAN' : {'you'} },
           'MILANfour': { 'LONDON' : {'fast'} },
           'PARISfour': { 'CANCUN' : {'bank'} },
           'LONDONfour': { 'FLORENCE' : {'smith'}} }

The purpose of the function is to search in the dictionary starting from the "firstCity" and find all the possible phrases that can be extracted from the dictionary.

for each element of the dictionary there are 2 information : the destination (where to look after) and the word (to build the phrase we are looking for)

The result should be:

[ ["hello how are you" , "MILAN"],
  ["hello im john smith", 'FLORENCE"],
  ["money in the bank", "CANCUN"],
  ["racing cars are fast", "LONDON"] ]

so far I came up with this solution, but It doesn't work properly, may I ask for some suggestions to how to solve this? please!

def ex(dictionary, hints, firstCity, words = []):

    for key in dictionary:

        if key == (firstCity + hints[0]):

            for destination in dictionary[key]:

                firstCity = destination

                word = getValue(dictionary[key][destination])
                #getValue simply get the value from the set

                words.append(word)
                if hints[1:] == []:
                    return words
                ex(dictionary, hints[1:], firstCity,words)
    return words
    
def getValue(st):
for el in st:
    if len(st) == 1:
        return el

The results of the function with values will be:

['hello','how','are','you','are','fast','the','bank','im','john','smith','money','in','the','bank','racing','cars','are','fast','the','bank']

Upvotes: 1

Views: 77

Answers (1)

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion with a generator:

hints = ['one','two','three', 'four']
d = {'ROMEone': {'PARIS': {'hello'}, 'CAIRO': {'money'}, 'MOSCOW': {'racing'}}, 'CAIROtwo': {'MILAN': {'in'}}, 'PARIStwo': {'BERLIN': {'how'}, 'CANCUN': {'im'}}, 'MOSCOWtwo': {'AMSTERDAM': {'cars'}}, 'BERLINthree': {'AMSTERDAM': {'are'}}, 'AMSTERDAMthree': {'MILAN': {'are'}}, 'MILANthree': {'PARIS': {'the'}}, 'CANCUNthree': {'LONDON': {'john'}}, 'AMSTERDAMfour': {'MILAN': {'you'}}, 'MILANfour': {'LONDON': {'fast'}}, 'PARISfour': {'CANCUN': {'bank'}}, 'LONDONfour': {'FLORENCE': {'smith'}}}
def get_vals(s, c = [], t=[]):
   if (k:=next(filter(lambda x:x not in t, hints), None)):
      for a, [b] in d.get(f'{s}{k}', {}).items():
         yield from get_vals(a, c=c+[b], t=t+[k])
   else:
      yield c+[s]

print(list(get_vals('ROME')))

Output:

[['hello', 'how', 'are', 'you', 'MILAN'], 
 ['hello', 'im', 'john', 'smith', 'FLORENCE'], 
 ['money', 'in', 'the', 'bank', 'CANCUN'], 
 ['racing', 'cars', 'are', 'fast', 'LONDON']]

Upvotes: 2

Related Questions