Alphabet Reconstruction

Question

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.

The Task

Given an ordered list of words, try to output an ordered list of characters such that:

1. Every character of the words in the word list appears exactly once in the character list.
2. 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.

Rules

• 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)

Examples

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]

Scoring

This is code-golf, shortest code wins. :)

Answer 1

Vyxal, 21 bytes

∑UṖ'→?µ←:₃[nL|β];?⁼;h

Try it Online!

Outputs a single possible alphabet. Times out for inputs with larger alphabets because it checks all permutations of the character set of the input. Exits with an error if falsey.

14 if a aa aaa aaaaa aaaa wasn't falsey. Much shorter if base conversion wasn't so janky.

Explained (in theory if base conversion wasn't so janky)

∑UṖ'→?µ←ðpβ;?⁼;h
∑U                # Get all unique characters of the input
  Ṗ               # and then all permutations of that.
   '              # From that, keep only items (n) where
    →?µ←ðp;       #    the input sorted by conversion to bijective base n with a space prepended to make everything non-zero
            ?⁼   #    equals the original input (⁼ is non-vectorising equals)
              ;h # and get the first from that

I actually got to use the ghost variable and variable scoping for once.

Answer 2

Jelly, 11 bytes

Returns all valid alphabets and the empty list as a falsy value.

FQŒ!iⱮⱮṢƑ¥Ƈ

Try it online!

F            -- flatten the word list into a single string
 Q           -- get the unique characters
  Œ!         -- get all permutations of those characters
          Ƈ  -- keep the permutation that return a truthy value for:
         ¥   --   group the last two links into dyad
             --   which is called with the permutation on the left and the word list on the right
    iⱮⱮ      --   for each character of each word get its index in the permutation
       ṢƑ    --   is the resulting list invariant under sorting?

Answer 3

Charcoal, 92 76 bytes

ＷＳ⊞υι≔⟦⟧θ≔ ηＷ⌈⁻⪪⪫υω¹θ«⊞θι≔⭆⪪ηＬθ⭆κ⭆κ⁺ξ⎇⁼νπιωη»ＥΦ⪪η⊕Ｌθ⬤υ⬤υ⁼‹μξ‹⍘◨λＬνι⍘◨νＬλιΦιμ

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of words (space-terminated works, but it's easy to forget the trailing space) and outputs all orderings (the orderings themselves are output in ASCII order). Even slower now for larger character sets. Explanation:

ＷＳ⊞υι

Input the list of words.

≔⟦⟧θ

Start with no characters processed.

≔ η

Start with a space-prefixed list of one element, the empty string.

Ｗ⌈⁻⪪⪫υω¹θ«

Repeat until all distinct characters have been processed.

⊞θι

Mark this character has having been processed.

≔⭆⪪ηＬθ⭆κ⭆κ⁺ξ⎇⁼νπιωη

Generate all permutations of the characters so far.

»ＥΦ⪪η⊕Ｌθ⬤υ⬤υ⁼‹μξ‹⍘◨λＬνι⍘◨νＬλιΦιμ

Filter those permutations which are valid orderings, removing the space prefix. Words are compared by padding them to the same length, then performing custom base conversion with the space-prefixed permutation.

Answer 4

05AB1E, 11 bytes

˜ÙœʒIkðýD{Q

Port of @ovs's Jelly answer, so make sure to upvote him!

I/O as a list of character-lists. Outputs all possible alphabet-lists.

Should have been 9 bytes without the ðý, but there is a weird bug when sorting after we've just indexed apparently..

Try it online or verify most test cases (two of them are removed because they time out).

Explanation:

˜          # Flatten the (implicit) input-list of character-lists
 Ù         # Uniquify this list of characters
  œ        # Get all its permutations
   ʒ       # Filter this list of lists by:
    Ik     #  Get the index of each character of the input-list of lists
      ðý   #  (Bug workaround: join each inner list by spaces)
      D    #  Duplicate the list
       {   #  Sort the copy
        Q  #  And check if it's still the same
           # (after which the resulting list of character-lists is output implicitly)

Answer 5

Japt v2.0a0, 11 bytes

Returns undefined for inputs without a solution.

¬â á æ@eUnX

Try it

Answer 6

JavaScript (Node.js), 146 bytes

a=>(g=s=>s[0]?g(s.filter(c=>a.some(w=>s.includes((r=/(.*)(.?).*,\1(.)/.exec([p,p=w]))[2])&&r[3]==c,p='')||!(q+=c))):q)([...new Set(a.join(q=''))])

Try it online!

Answer 7

R + gtools, 162 bytes

function(w,a=unique(unlist(strsplit(w,""))),l=length(a))for(x in apply(gtools::permutations(l,l,a),1,Reduce,f=paste0))if(!is.unsorted(chartr(x,"a-z",w)))return(x)

Try it online!

Iterates through all permutations (calculated by gtools package as I didn't have the heart to do it myself) of used alphabet and checks whether sorting by it gives desired result. This is done by translating the characters to a-z and using built-in is.unsorted.

Returns nothing as falsy.