Longest chain of elements from list in Python

Question

I have a list of nations, and I want to have the longest path of nations where each country chosen must begin with the same letter that ended the previous element

nations = ['albania','andorra','austria','belarus','belgium','bosnia and herzegovina',
      'bulgaria','croatia','czech republic','denmark','estonia',  
      'finland','france','germany','greece','hungary',
      'iceland','ireland','italy','latvia','liechtenstein','lithuania','luxembourg',
      'macedonia','malta','moldova','monaco','montenegro','netherlands', 
      'norway','poland','portugal','romania','russia',  
      'san marino','serbia','slovakia','slovenia','spain','sweden', 'switzerland',
      'ukraine','united kingdom','vatican city'] 

chain('spain')
>>>['spain', 'netherlands', 'slovenia', 'andorra', 'austria', 'albania']

I tried this way, but it doesn't work

def chain(naz):
    initial = naz[-1]
    initials=[]
    res = set()
    res.add(naz)
    for i in nations:
        if i.startswith(initial):
            initials.append(i)
    for j in initials:
        nations.remove(j)
        res.add(j)
        chain(j)
    return res

Any suggestion?

Answer 1

I've also gone for recursive descent. Not sure if dynamic programming is a good fit for this as the list is modified as we go. Slightly more compact and doesn't need start removed from the list before calling chain. :-)

def chain(start, countries):
    remaining = list(countries)
    del remaining[remaining.index(start)]
    possibles = [x for x in remaining if x[:1] == start[-1:]]
    maxchain = []
    for c in possibles:
        l = chain(c, remaining)
        if len(l) > len(maxchain):
            maxchain = l
    return [start] + maxchain

Call like this. :-)

>>> chain('spain', nations)
['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria']