14
\$\begingroup\$

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 , shortest code wins. :)

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Can we output all possibilities in case of multiple ones? \$\endgroup\$
    – emanresu A
    Oct 20, 2021 at 2:54
  • \$\begingroup\$ @emanresuA the challenge does explicitly say no, but i am willing to defer to your expertise if you think itd make the challenge strictly Better \$\endgroup\$ Oct 20, 2021 at 2:56
  • \$\begingroup\$ for posterity: sandbox link here \$\endgroup\$ Oct 20, 2021 at 2:57
  • \$\begingroup\$ I'd allow both, but your choice \$\endgroup\$
    – emanresu A
    Oct 20, 2021 at 2:57
  • \$\begingroup\$ @emanresuA would "either just one or All valid possibilities" be a good restriction? dont want anyone being wishy washy, either find them all or just one \$\endgroup\$ Oct 20, 2021 at 2:58

7 Answers 7

5
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Dammit, you ninja'd me and outgolfed me by 3 bytes. Nice (ab)use of β! \$\endgroup\$
    – emanresu A
    Oct 20, 2021 at 3:08
  • \$\begingroup\$ @emanresuA I figured you were in the process of writing an answer given your clarification question lol. \$\endgroup\$
    – lyxal
    Oct 20, 2021 at 3:11
  • 1
    \$\begingroup\$ Maybe I'm doing something wrong, but your TIO link gives division by 0 errors.. Try it online with one of the test cases or try it online with the example. \$\endgroup\$ Oct 20, 2021 at 7:27
  • 1
    \$\begingroup\$ Can't you save two bytes by outputting all possible results / removing the trailing ;h? \$\endgroup\$ Oct 20, 2021 at 9:05
  • \$\begingroup\$ @KevinCruijssen for some reason, without it, it doesn't actually output all possible alphabets \$\endgroup\$
    – lyxal
    Oct 20, 2021 at 10:26
4
\$\begingroup\$

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?
\$\endgroup\$
4
\$\begingroup\$

Charcoal, 92 76 bytes

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

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:

WS⊞υι

Input the list of words.

≔⟦⟧θ

Start with no characters processed.

≔ η

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

W⌈⁻⪪⪫υω¹θ«

Repeat until all distinct characters have been processed.

⊞θι

Mark this character has having been processed.

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

Generate all permutations of the characters so far.

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

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.

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ My attempt was much longer because I didn't think of using character lists, but I still ran into the same bug. This seems to happen without loops as well: TIO \$\endgroup\$
    – ovs
    Oct 20, 2021 at 9:09
  • \$\begingroup\$ @ovs Ah, that's much cleaner reproduction code. I'll add it to the 05AB1E bug report I just did. Pretty annoying bug.. \$\endgroup\$ Oct 20, 2021 at 9:11
  • 1
    \$\begingroup\$ @ovs It seems to sort based on the string it indexed into by the looks of it: TIO. \$\endgroup\$ Oct 20, 2021 at 9:21
3
\$\begingroup\$

Japt v2.0a0, 11 bytes

Returns undefined for inputs without a solution.

¬â á æ@eUnX

Try it

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • 2
    \$\begingroup\$ in TIO, the 147 172 120 04 07 test case outputs 1470, which is distinctly missing a 2 \$\endgroup\$ Oct 20, 2021 at 12:53
  • 1
    \$\begingroup\$ @thejonymyster Should be fixed, by +1 byte. \$\endgroup\$
    – tsh
    Oct 21, 2021 at 0:21
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.