You are a historian studying a long forgotten language. You have just discovered a clay tablet which seems to list all known words in the language, in alphabetical order. Your task is to find this alphabet's order, if it exists.
Given an ordered list of words, try to output an ordered list of characters such that:
- Every character of the words in the word list appears exactly once in the character list.
- The word list as given is sorted "alphabetically" according to the character list.
If (and only if) no character list is able to satisfy these requirements, output a falsy/fail value of your choice. You must specify in your answer the value you have chosen.
Notably, it is possible that more than one alphabet ordering is valid for a given list of words; If we have the words Cod, Com, and Dy, all that can be assumed is that C comes before D, and d comes before m. The letters o and y have various valid positions in the generated alphabet. For more clarity, here are some (but not all) valid outputs for that word list:
Input: Cod Com Dy Output: CDdmoy Output: CDdmyo Output: CDdomy Output: CoDdym Output: dmCDoy Output: dCmDoy Output: CdoymD Output: dyCoDm Output: yodmCD
If there are multiple valid character lists, your code must output either one valid answer or all valid answers, consistently.
- Your input is a list of words, which may be input in any reasonable format. Output only languages are allowed to include this word list in their initial data/program at no additional byte cost.
- The word list will contain at least two words, and no two words will be identical.
- Any alphanumeric character
[A-Za-z0-9]may be included as a character in the wordlist.
- Words are read from left to right, and are alphabetized first by leftmost character, then by the next character, etc.
- Two words which begin with the same substring are only alphabetized if the shorter of the two comes first (e.g. "CAR" must come before "CARP").
- Uppercase and lowercase forms of the same character are considered to be different characters, i.e. the alphabet is case sensitive.
- You may output each alphabet in any reasonable format, but each must contain every character present in the word list exactly once, and no other characters. (This requirement, of course, does not apply to falsy/fail outputs)
Your correct outputs may not match all these, as any given wordlist may have more than one proper alphabet. Some may only have one valid answer.
Input: bob cat chat dog hat hot guy Output: tuybcdaohg Input: A Aa AA Bb Ba Output: baAB Input: 147 172 120 04 07 Output: 14720
Falsy output examples
These should all be falsy outputs, and can be used as test cases.
Input: GREG HOUSE ROCK AND ROLL Output: [falsy] Input: b5OtM bb5O MO Mtt 5 Output: [falsy] Input: a aa aaa aaaaa aaaa Output: [falsy]
This is code-golf, shortest code wins. :)