9
\$\begingroup\$

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.)

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "cat dog tred xy yz zx" returns 4. Is that correct? Shouldn't it be 3? \$\endgroup\$ – Chas Brown Jul 16 '17 at 21:10
  • \$\begingroup\$ @ChasBrown xy yz zx xy is the longest chain, so 4. \$\endgroup\$ – notjagan Jul 16 '17 at 21:14
1
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ The last one took like 19s on my computer on TIO. btw, the reason you use Lambdabot is to avoid writing import statements, right? \$\endgroup\$ – geokavel Jul 31 '17 at 0:46
  • \$\begingroup\$ Yes, I do. But I stopped doing that since nobody else was doing this, not sure about it. Why? \$\endgroup\$ – ბიმო Jul 31 '17 at 1:11
  • \$\begingroup\$ I'm trying to figure out who won. Typically, you include import statements in byte count. But, if you found environment that doesn't require imports, then it's ok. \$\endgroup\$ – geokavel Jul 31 '17 at 1:16
  • \$\begingroup\$ Oh, I wouldn't accept an answer anyway. If you want to, then I'll change my answer because @notjagan's answer is better than mine. \$\endgroup\$ – ბიმო Jul 31 '17 at 1:27
  • 1
    \$\begingroup\$ I mean this is code golf, so you're in first place. Anyway, you're answer fits your name. But I'll leave it open at your request. \$\endgroup\$ – geokavel Jul 31 '17 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.