Codegolf - Реконструкция Алфавита

  • Автор темы Rek1
  • Обновлено
  • 20, Oct 2024
  • #1

Вы историк, изучающий давно забытый язык. Вы только что обнаружили глиняную табличку, на которой, кажется, перечислены все известные слова языка в алфавитном порядке. Ваша задача — найти порядок этого алфавита, если он существует.

Задача

Имея упорядоченный список слов, попытайтесь вывести упорядоченный список символов такой, что:

  1. Каждый символ слов в списке слов появляется в списке символов ровно один раз.
  2. Указанный список слов сортируется «в алфавитном порядке» в соответствии со списком символов.

Если (и только если) ни один список символов не может удовлетворить этим требованиям, выведите значение false/fail по вашему выбору. В своем ответе вы должны указать выбранное вами значение.

Примечательно, что для данного списка слов возможно более одного алфавитного порядка; Если у нас есть слова Cod, Com и Dy, все, что можно предположить, это то, что C стоит перед D, а d стоит перед m. Буквы o и y занимают различные допустимые позиции в сгенерированном алфавите. Для большей ясности вот некоторые (но не все) допустимые результаты для этого списка слов:

 
 
 Input: GREG HOUSE ROCK AND ROLL
Output: [falsy]

Input: b5OtM bb5O MO Mtt 5
Output: [falsy]

Input: a aa aaa aaaaa aaaa
Output: [falsy]
 

Если существует несколько допустимых списков символов, ваш код должен вывести либо один действительный ответ или все действительные ответы, последовательно.

Правила

  • Ваш ввод представляет собой список слов, который можно ввести в любом разумном формате. Языкам только вывода разрешено включать этот список слов в свои исходные данные/программу без дополнительных затрат байтов.
  • Список слов будет содержать как минимум два слова, и никакие два слова не будут одинаковыми.
  • Любой буквенно-цифровой символ 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 may be included as a character in the wordlist.
  • Слова читаются слева направо и располагаются в алфавитном порядке сначала по самому левому символу, затем по следующему символу и т. д.
  • Два слова, начинающиеся с одной и той же подстроки, располагаются в алфавитном порядке только в том случае, если более короткое из двух слов стоит первым (например, «CAR» должно идти перед «CARP»).
  • Прописные и строчные буквы одного и того же символа считаются разными символами, т. е. алфавит чувствителен к регистру.
  • Вы можете вывести каждый алфавит в любом приемлемом формате, но каждый символ должен содержать каждый символ, присутствующий в списке слов, ровно один раз, и никаких других символов. (Это требование, конечно, не распространяется на ложные/неудачные выходы)

Примеры

Ваши правильные результаты могут не совпадать со всем этим, поскольку любой список слов может содержать более одного правильного алфавита. У некоторых может быть только один правильный ответ.

[A-Za-z0-9]

Примеры ложного вывода

Эти должен все они являются ложными выходными данными и могут использоваться в качестве тестовых примеров.

Input: Cod Com Dy Output: CDdmoy Output: CDdmyo Output: CDdomy Output: CoDdym Output: dmCDoy Output: dCmDoy Output: CdoymD Output: dyCoDm Output: yodmCD

Подсчет очков

Это значит, что выигрывает самый короткий код. :)

#код-гольф #код-гольф

Rek1


Рег
04 Apr, 2006

Тем
78

Постов
204

Баллов
614
  • 26, Oct 2024
  • #2

Виксал, 21 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 is.unsorted 

Попробуйте онлайн!

Выводит единственный возможный алфавит. Тайм-аут для входных данных с большими алфавитами, поскольку он проверяет все перестановки набора символов входных данных. Выход с ошибкой, если falsey.

14, если a-z wasn't falsey. Much shorter if base conversion wasn't so janky.

Объяснено (теоретически, если бы базовое преобразование не было таким трудным)

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)

Мне действительно пришлось использовать переменная-призрак и область видимости переменных на один раз.

 

LoveMU


Рег
16 Jul, 2012

Тем
68

Постов
181

Баллов
541
  • 26, Oct 2024
  • #3

Желе, 11 байт

Возвращает все допустимые алфавиты и пустой список как ложное значение.

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=''))])

Попробуйте онлайн!

¬â á æ@eUnX ||answer||

Древесный уголь, 92 76 байт

undefined

Попробуйте онлайн! Ссылка на подробную версию кода. Принимает входные данные в виде списка слов, заканчивающегося новой строкой (работает с пробелом в конце, но о конечном пробеле легко забыть) и выводит все упорядочения (сами упорядочения выводятся в порядке ASCII). Теперь еще медленнее для больших наборов символов. Объяснение:

˜ # 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)

Введите список слов.

ðý

Начните без обработки символов.

˜ÙœʒIkðýD{Q

Начните со списка из одного элемента с префиксом пробела — пустой строки.

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

Повторяйте до тех пор, пока не будут обработаны все отдельные символы.

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

Отметить, что этот символ был обработан.

⊞θι

Сгенерируйте все перестановки символов на данный момент.

W⌈⁻⪪⪫υω¹θ«

Отфильтруйте те перестановки, которые являются допустимыми порядками, удалив префикс пробела. Слова сравниваются путем дополнения их до одинаковой длины, а затем выполнения пользовательского преобразования базы с перестановкой с префиксом пробела.

 

Georgiahmd


Рег
09 Sep, 2011

Тем
70

Постов
185

Баллов
545
  • 26, Oct 2024
  • #4

05AB1E, 11 байты

≔ η

Порт @ovs's Jelly ответ, так что обязательно проголосуйте за него!

Ввод-вывод в виде списка списков символов. Выводит все возможные списки алфавитов.

Должно было быть 9 байты без ≔⟦⟧θ , but there is странная ошибка при сортировке после того, как мы только что проиндексировали..

Попробуйте онлайн или проверить большинство тестовых случаев (два из них удалены, поскольку истекло время ожидания).

Объяснение:

WS⊞υι ||answer||

Япт v2.0a0, 11 байты

Возврат WS⊞υι≔⟦⟧θ≔ ηW⌈⁻⪪⪫υω¹θ«⊞θι≔?⪪ηLθэκэκ⁺ξ⎇⁼νπιωη»EΦ⪪η⊕Lθ⬤υ⬤υ⁼‹μξ‹⍘◨λLνι⍘◨νLλιΦιμ for inputs without a solution.

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?

Попробуйте это

 

Warhangel


Рег
08 Dec, 2003

Тем
66

Постов
192

Баллов
542
  • 26, Oct 2024
  • #6

Р + gtools, 162 байта

∑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

Попробуйте онлайн!

Перебирает все перестановки (рассчитанные пакетом gtools, так как у меня не хватило духу сделать это самому) используемого алфавита и проверяет, дает ли сортировка по нему желаемый результат. Это делается путем перевода символов в a aa aaa aaaaa aaaa and using built-in ∑UṖ'→эµ←:₃[nL|β];?⁼;h .

Ничего не возвращает как ложное.

 

Vovanhill


Рег
23 Jul, 2009

Тем
67

Постов
178

Баллов
563
Тем
403,760
Комментарии
400,028
Опыт
2,418,908

Интересно