Word Chain Reloaded

Question

This is a variant of Play the word chain and Building a long chain of words .

---

The input is a non-empty list of unique words at least 2 chars long made of characters in [a-z]. You need to output the length of the longest possible chain, where each subsequent word starts with the last letter of the previous word. You can start with any word on the list.

Another twist is that you are allowed to repeat any single word on the list. However, you can not repeat any two-word block. For example, cat->tac->cat is allowed, but cat->tac->cat->tac is not, because you repeated a two-word block (cat->tac). Also, you can not use the same word twice in a row (e.g. eye->eye).

Examples:

• cat dog tree egg => 3 (cat->tree->egg)
• new men ten whim => 5 (ten->new->whim->men->new)
• truth fret heart his => 5 (fret->truth->heart->truth->his)
• we were stew early yew easy => 9 (stew->were->early->yew->were->easy->yew->we->easy)
• tac cat tac cot tac can => 6 (tac->cat->tac->cot->tac->can)

(Let me know if I made a mistake on any of these examples or if you come up with more.)

Answer 1

Python 3, 150 149 145 bytes

def f(d):
 a=[[w]for w in d]
 while a:b=a[0];a=[f+[l,y]for*f,l in a for y in{*d}-{b for a,b in zip(f,f[1:])if a==l}if l[-1]==y[0]]
 return len(b)

Try it online!

The idea for constructing successively longer paths (or in this case trails) until none longer could be created was directly inspired by grc's answer on the Play the word chain question.

Answer 2

Haskell, 131 141 bytes

Basically the brute force approach.. The idea is to generate all possible domino pieces, permute them, check if it's a valid combo and maximize the whole thing. The time complexity is ridiculous, the 4th test case already takes ~4s on my PC and on the TIO it doesn't seem to work!

import Data.List
p w=2+maximum[length$takeWhile(\(x,y)->x!!1==y!!0)$zip p$tail p|p<-permutations[[a,b]|(a,b)<-(,)<$>w<*>w,a/=b,last a==b!!0]]

Try it online!

Ungolfed

p w = maximum
  [ 2 + length c | p <- permutations [ [a,b] | (a,b) <- (,)<$>w<*>w
                                             , a /= b
                                             , last a == head b
                                     ]
                 , c <- [ takeWhile (\(x,y) -> x!!1 == y!!0) $ zip p (tail p) ]
  ]

Edit: Changed from Lambdabot to bare Haskell but saved a few bytes by golfing it, such that it's still less than 145 bytes :)