What other word sequence is hidden in this word sequence?

woodsman, ageing, rainbow, mental, lowdown, playback

Show answer

This is the word sequence we were looking for

manage, ingrain, bowmen, tallow, downplay, backwoods

You get this sequence by splitting each word into two parts.

The colors indicate how the words in the top sequence can be split into two parts, creating the new word sequence at the bottom by merging two parts of the same color together. Note that we have also repeated the first word in the top sequence at the back of the sequence for illustrative purposes.

You then get the hidden words by merging the second part of a word with the first part of the next word. The last hidden word is obtained by merging the second part of the last word with the first part of the first word.

Assignment

A compilation is a word that is composed of two parts, each consisting of one or more letters. The two parts of a compilation can be distinguished from each other because one part is written in uppercase letters and the other part in lowercase letters: woodsMAN or WOODSman.

We can recombine a sequence of compilations into a new sequence of words: the first word is composed of the second part of the first compilation and the first part of the second compilation, the second word is composed of the second part of the second compilation and the first part of the third compilation, … and the last word is composed of the second part of the last compilation and the first part of the first compilation.

We say that compilation $$c$$ is followed by compilation $$d$$ — or that $$d$$ is a successor of $$c$$ — if the first part of $$d$$ is the same as the second part of $$c$$. In comparing parts, no distinction is made between uppercase and lowercase letters.

If we also denote the words that arise from recombining a sequence of compilations as compilations of the parts of which they are composed, we see a sequence of successors emerging. For example, if we recompile this sequence of compilations

WOODSman, AGEing, RAINbow, MENtal, LOWdown, PLAYback

into this new sequence of compilations

manAGE, ingRAIN, bowMEN, talLOW, downPLAY, backWOODS

then we see that WOODSman is followed by manAGE, manAGE by AGEing, AGEing by ingRAIN, ... and that PLAYback is followed by backWOODS.

Your task:

Write a function divide that takes a compilation $$c$$ (str) and returns a tuple with the two parts (str) of compilation $$c$$.
Write a function recombine that takes a sequence $$\mathcal{C}$$ (list or tuple) of compilations (str) and returns the list of words (str) that result from recombining the compilations in $$\mathcal{C}$$.
Write a function successors that takes a compilation $$c$$ (str) and a sequence $$\mathcal{C}$$ (list or tuple) of compilations (str). The function must return a list with all successors of $$c$$ in $$\mathcal{C}$$, where the successors keep their order from $$\mathcal{C}$$.
Write a function intertwine that takes a sequence $$\mathcal{C}$$ (list or tuple) of compilations (str). The function must return a tuple with two lists (list) in which all compilations from $$\mathcal{C}$$ are distributed as follows. The compilation from $$\mathcal{C}$$ that comes first in alphabetic order (without making a distinction between uppercase and lowercase letters) goes into the first list. Then the unique successor in $$\mathcal{C}$$ of the previous compilation (starting with the compilation that comes first in alphabetic order) is placed at the end of the other list. This procedure continues until all compilations in $$\mathcal{C}$$ have been placed in one of the two lists. If a compilation has no unique successor in $$\mathcal{C}$$ when performing this procedure, an AssertionError must be raised with the message invalid sequence.

Example

        >>> divide('WOODSman')
('WOODS', 'man')
>>> divide('billION')
('bill', 'ION')

>>> recombine(['WOODSman', 'AGEing', 'RAINbow', 'MENtal', 'LOWdown', 'PLAYback'])
['manAGE', 'ingRAIN', 'bowMEN', 'talLOW', 'downPLAY', 'backWOODS']
>>> recombine(('billION', 'isingLASS', 'oedEMA', 'nationWIDE', 'screenPLAY'))
['IONising', 'LASSoed', 'EMAnation', 'WIDEscreen', 'PLAYbill']

>>> successors('WOODSman', ['backWOODS', 'manAGE', 'LOWdown', 'ingRAIN', 'AGEing', 'talLOW', 'MENtal', 'bowMEN', 'RAINbow', 'downPLAY', 'PLAYback', 'WOODSman'])
['manAGE']
>>> successors('boardWALK', ('nationWIDE', 'PLAYbill', 'EMAnation', 'IONising', 'isingLASS', 'WIDEscreen', 'oedEMA', 'billION', 'LASSoed', 'screenPLAY'))
[]
>>> successors('rocketMAN', ['manGROVE', 'roMANTIC', 'MANUscript', 'MANkind', 'HUman', 'MANtra', 'KLEPTOmania'])
['manGROVE', 'MANkind', 'MANtra']

>>> intertwine(['backWOODS', 'manAGE', 'LOWdown', 'ingRAIN', 'AGEing', 'talLOW', 'MENtal', 'bowMEN', 'RAINbow', 'downPLAY', 'PLAYback', 'WOODSman'])
(['AGEing', 'RAINbow', 'MENtal', 'LOWdown', 'PLAYback', 'WOODSman'], ['ingRAIN', 'bowMEN', 'talLOW', 'downPLAY', 'backWOODS', 'manAGE'])
>>> intertwine(('nationWIDE', 'PLAYbill', 'EMAnation', 'IONising', 'isingLASS', 'WIDEscreen', 'oedEMA', 'billION', 'LASSoed', 'screenPLAY'))
(['billION', 'isingLASS', 'oedEMA', 'nationWIDE', 'screenPLAY'], ['IONising', 'LASSoed', 'EMAnation', 'WIDEscreen', 'PLAYbill'])