Background
Three years ago, this guy Tom Murphy got it into his head to extend the idea of a portmanteau to all words in a language and called this a portmantout (portmanteau plus tout [French for all]). Defining English as a list of 108,709 words, he managed to find a sequence of 611,820 letters with the following two properties:
- Every English word is contained in the string.
- Some neighborhood containing any two adjacent letters in the string is an English word.
Here's a link to a page on which this portmantout can be found (along with a video explanation).
A portmantout
The first of the two properties of a portmantout is easy to understand. The second may require some explanation.
Basically, words must overlap. "golfcode" will never appear in a portmantout of English, as there is no word there that contains the "fc". However, you might find "codegolf" in a portmantout, for "ego" bridges the gap (and all other pairs of letters are in either "code" or "golf").
Your task:
Write a program or function that takes a list of strings and returns any portmantout of the list.
This Python 3 code will verify a portmantout.
Test cases
All lists are unordered; that is,
{"code", "ego", "golf"} -> "codegolf"
{"more", "elm", "maniac"} -> "morelmaniac" or "morelmorelmaniac" or "morelmorelmorelmaniac" or...
Would a morelmaniac be some sort of mycologist?
{"ab", "bc", "cd", "de", "ef", "fg", "gh", "hi", "ij", "jk", "kl", "lm", "mn", "no", "op", "pq", "qr", "rs", "st", "tu", "uv", "vw", "wx", "xy", "yz", "za"} -> "abcdefghijklmnopqrstuvwxyza" or "rstuvwxyzabcdefghijklmnopqrstuvwxyzabcdef" or any 27+ letters in order
And why not? The massive one on Murphy's site, if your code executes within reasonable time.
Rules
- Your code must halt.
- You need not return the same portmantout with each execution.
- You may assume all strings consist of only lowercase letters
a
throughz
. - If no portmantout is possible, your program may do anything. Ex:
{"most", "short", "lists"}
- Standard rules for I/O and loopholes apply.
This is code-golf, so the shortest solution (in bytes) in each language wins! Happy golfing!
{"sic", "bar", "rabbits", "cradle"} -> "barabbitsicradle"
{"mauve", "elated", "cast", "electric", "tame"} -> "mauvelectricastamelated"
(more test cases) \$\endgroup\$ – sundar Jun 7 '18 at 0:19