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\$
0

2 Answers 2

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\$
2
  • \$\begingroup\$ "cat dog tred xy yz zx" returns 4. Is that correct? Shouldn't it be 3? \$\endgroup\$
    – Chas Brown
    Jul 16, 2017 at 21:10
  • \$\begingroup\$ @ChasBrown xy yz zx xy is the longest chain, so 4. \$\endgroup\$
    – notjagan
    Jul 16, 2017 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\$
6
  • \$\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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 1:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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