Peter Norvig
Dec 2018
Updated Jun 2020

# Portmantout Words A [***portmanteau***](https://en.wikipedia.org/wiki/Portmanteau) is a word that squishes together two words, like *math* + *athlete* = *mathlete*. Inspired by [**Darius Bacon**](http://wry.me/), I covered this as a programming exercise in my 2012 [**Udacity course**](https://www.udacity.com/course/design-of-computer-programs--cs212). In 2018 I was re-inspired by [**Tom Murphy VII**](http://tom7.org/), who added a new twist: [***portmantout words***](http://www.cs.cmu.edu/~tom7/portmantout/) (*tout* from the French for *all*), which are defined as: > A **portmantout** of a set of words $W$ is a string $S$ such that: * Every word in $W$ is a **substring** of $S$. (Although a word may appear more than once in $S$.) * The words **overlap**: the start of every word (except the first) is equal to or before the end of another word. * **Nothing else** is in $S$: every letter in $S$ comes from the overlapping words. This notebook attempts to find a portmantout that is as short as possible, while covering a set $W$ of over 100,000 words. My program discovered: - **preferendumdums**: a political commentary
portmanteau of {prefer, referendum, dumdums} - **impromptutankhamenability**: a willingness to see the Egyptian exhibit on the spur of the moment
portmanteau of {impromptu, tutankhamen, amenability} - **dashikimonogrammarianarchy**: chaos when a linguist enscribes African/Japanese garb
portmanteau of {dashiki, kimono, monogram, grammarian, anarchy} - **allegestionstage**: a brutal theatre review
portmanteau of {alleges, egestions, onstage} - **skymanipulablearsplittinglers**: a nerve-damaging aviator
portmanteau of {skyman, manipulable, blears, earsplitting, tinglers} - **edinburgherselflesslylyricize**: a Scottish music review
portmanteau of {edinburgh, burghers, herself, selflessly, slyly, lyricize} - **fortyphonshore**: a dire weather report
portmanteau of {forty, typhons, onshore} # Problem-Solving Strategy Although I haven't proved it, my intuition is that finding a shortest $S$ is an NP-hard problem, and with 100,000 words to cover, it is unlikely that I can find an optimal solution in a reasonable amount of time. A common approach to NP-hard problems is a **greedy algorithm**: make the locally best choice at each step, in the hope that the steps will fit together into a solution that is not too far from the globally shortest solution. Thus, my approach will be to build up a **path**, starting with one word, and then adding **steps** to the end of the evolving path, one at a time. Each step consists of a word from *W* that overlaps the end of the previous word by at least one letter. I will choose the step that seems to be the best choice at the time (the one with the **lowest cost**), and will never undo a step, even if the path seems to get stuck later on. I distinguish two types of steps: - **Unused word step**: using a word for the first time. (Once we use them all, we're done.) - **Bridging word step**: if no remaining unused words overlap the previous word, we need to do something to get back on track to consuming unused words. I call that something a **bridge**: a step that **repeats** a previously-used word and has an ending that matches the start of some unused word. Repeating a word may add letters to the final length of $S$, and it doesn't get us closer to the requirement of using all the words, but it is sometimes necessary. Sometimes two words are required to build a bridge, but never more than two (at least with the 100,000 word set we will be dealing with). There's actually a third type of word, but it doesn't need a corresponding type of step: a **subword** is a word that is a substring of another word. If, say, `ajar` is in $W$, then we know we have to place it in some step along the path. But if `jar` is also in $W$, we don't need a separate step for it—whenever we place `ajar`, we have automatically placed `jar`. The program can save computation time save time by initializing the set of **unused words** to be just the **nonsubwords** in $W$. (We are still free to use a subword as a **bridging word** if needed.) (*English trivia:* I use the clumsy term "nonsubwords" rather than "superwords", because there are a small number of words, like "cozy" and "pugs" and "july," that are not subwords and also not superwords.) If we're going to be **greedy**, we need to know what we're being greedy about. I will always choose a step that minimizes the **number of excess letters** that the step adds. To be precise: I arbitrarily assume a baseline model in which all the words are concatenated with no repeated words and no overlap between them. (That's not a valid solution, but it is useful as a benchmark.) So if I add an unused word, and overlap it with the previous word by three letters, that is an excess of -3 (a negative excess is a positive thing): I've saved three letters over just concatenating the unused word. For a bridging word, the excess is the number of letters that do not overlap either the previous word or the next word. **Examples:** In each row of the table below, `'ajar'` is the previous word, but each row makes different assumptions about what unused words remain, and thus we get different choices for the step to take. The table shows the overlapping letters between the previous word and the step, and in the case of bridges, it shows the next unused word that the step is bridging to. In the final column we give the excess letters (if any) and excess score. |Previous|Step(s)|Overlap|Bridge to|Type of Step|Excess| |--------|----|----|---|---|---| | ajar|jarring|jar||unused word |-3 | | ajar|arbitrary|ar||unused word |-2| | ajar|argot|ar|goths|one-step bridge |0| | ajar|arrow|ar|owlets| one-step bridge|"r" 1| | ajar|rani+iraq|r|quizzed| two-step bridge|"anira" 5 | Let's go over the example steps one row at a time: - **jarring**: Here we assume `jarring` is an unused word, and it overlaps by 3 letters, giving it an excess cost of -3, which is the best possible (an overlap of 4 would mean `ajar` is a subword, and we already agreed to eliminate subwords). - **arbitrary**: an unused word that overlaps by 2 letters, so it would only be chosen if there were no unused words with 3-letter overlap. - **argot**: From here on down, we assume there are no unused words that overlap, which means that `argot` is a best-possible bridge, because it completely overlaps the `ar` in `ajar` and the `got` in an unused word, `goths`. - **arrow**: overlaps the `ar` in `ajar` and the `ow` in an unused word, `owlets`, but that leaves one excess letter, `r`, for an excess cost of 1. - **rani + iraq**: Suppose `quizzed` is the only remaining unused word. There is no single word that bridges from any suffix of `ajar` to any prefix of `quizzed`. But I have arranged to build two-word bridges for every combination of one letter on the left and one letter on the right (unless there was already a shorter one-word bridge for that combination). The bridge from `'r'` to `'q'` is `rani` followed by `iraq`, which has an excess score of 5 due to the letters `anira` not overlapping anything. We see that unused word steps always have a negative excess cost (that's good) while bridge steps always have a zero or positive excess cost; thus an unused word step is always better than a bridge step (according to this metric). # Data Type Implementation Here I describe how to implement the main data types in Python: - **Wordset**: a subclass of `set`, denoting a set of words. - **Word**: a Python `str` (as are subparts of words, like suffixes or individual letters). - **Step**: a namedtuple of an overlap and a word; the step adding `jarring` to `ajar` would be `Step(3, 'jarring')`. The first step in a path should have an overlap of 0; all others should have a positive integer overlap. - **Path**: a Python `list` of steps. - **Bridge**: a namedtuple of an excess cost followed by a list of steps, e.g. `Bridge(1, [Step(2, 'arrow')])`. (*Python trivia:* I implemented `Wordset` as a subclass of `set` so that I can add attributes (such as `W.subwords`) to it later. You can do that with a user-defined subclass, but not with a builtin class.)