# Method 1
def find(chain):
    last_character = chain[-1][-1]
    options = d[last_character] - set(chain)
    
    if not options:
        return chain
    else:
        return max( (find(chain+[i]) for i in options), key=len)            
    
 
start = time.clock()   

d = defaultdict(set)       
for word in pokemon:
    d[word[0]].add(word)

print max( (find([word]) for word in pokemon), key=len)

end = time.clock()
print end - start



# Method 2 try bottom down approach
def find2(chain):
    first_character = chain[0][0]
    options = d[first_character] -set(chain)
    
    if not options:
        return chain
    else:
        return max( (find2([i]+ chain) for i in options), key=len)
    
start = time.clock()
d = defaultdict(set)
for word in pokemon:
    d[word[-1]].add(word)
      
print max( (find2([word]) for word in pokemon), key=len)
end = time.clock()
print end - start 



# Method 3 - Using loop instead of generator expression
def find(chain):
    l=[]
    last_character = chain[-1][-1]
    options = d[last_character] - set(chain)
    
    if not options:
        return chain
    else:
        for i in options:
            l.append(find(chain+[i]))
        return max(l, key=len)
            
        #return [ find(chain+[i]) f=or i in options]        
        
pokemon = set(pokemon)

d = defaultdict(set)       
for word in pokemon:
    d[word[0]].add(word)

print max( [find([word]) for word in pokemon], key=len)





# Just try it out to have a better understanding how return plays an important role in recursion

def find(chain):
    last_character = chain[-1][-1]
    options = d[last_character] - set(chain)
    
    if not options:
        return chain
    else:
        for i in options:
            find(chain+[i])
    #to understand importance of return, here once we are in else block nothing is returned       
    
    
pokemon = set(pokemon)

d = defaultdict(set)       
for word in pokemon:
    d[word[0]].add(word)

print [find([word]) for word in pokemon]
ある子供向けゲームでは、特定のカテゴリーの単語から始める。参加者は順番に単語を言うが、その単語は前の単語の最後の文字で始まらなければならない。 一度言った単語を繰り返すことはできない。相手がそのカテゴリーの単語を出せなかった場合は、ゲームから脱落する。例えば、「動物」をカテゴリーとすると以下となる。

Child 1: dog 
Child 2: goldfish
Child 1: hippopotamus
Child 2: snake

pythonを用いて、ウィキペディアのポケモン一覧から抜粋した70の英語のポケモン名から、後続の名前が先行する名前の最後の文字で始まる、可能な限り数の多いポケモン名の並びを生成しなさい。ポケモンではない名前は繰り返さないです。

audino bagon baltoy banette bidoof braviary bronzor carracosta charmeleon
cresselia croagunk darmanitan deino emboar emolga exeggcute gabite
girafarig gulpin haxorus heatmor heatran ivysaur jellicent jumpluff kangaskhan
kricketune landorus ledyba loudred lumineon lunatone machamp magnezone mamoswine
nosepass petilil pidgeotto pikachu pinsir poliwrath poochyena porygon2
porygonz registeel relicanth remoraid rufflet sableye scolipede scrafty seaking
sealeo silcoon simisear snivy snorlax spoink starly tirtouga trapinch treecko
tyrogue vigoroth vulpix wailord wartortle whismur wingull yamask