Учитывая ввод списка слов и их сокращений, выведите шаблон, по которому могут быть сформированы сокращения.

Давайте возьмем пример ввода

potato ptao
puzzle pzze

в качестве примера (то есть сокращение для potatois ptao, а сокращение для puzzleis pzze).

Рассмотрим все возможные способы получения ptaoот potato. Один из возможных способов - взять первую, третью, четвертую и шестую буквы, которые мы будем называть 1346. Но так как tи oпоявляться несколько раз в слове, есть несколько других возможных способов получения ptaoиз potato: 1546, 1342и 1542.

Кроме того , заметим , что pzzeмогут быть получены из puzzleс любым из 1336, 1346, 1436, 1446. Единственный образец, который объединяет эти две аббревиатуры 1346: следовательно, это должен быть выход для этого ввода. Если возможно несколько возможных шаблонов, вы можете вывести любой, некоторые или все из них (хотя бы один).

Вы можете предположить, что:

• Входные слова и сокращения содержат только строчные буквы.

• На входе есть хотя бы одна пара слово / аббревиатура.

• Каждое сокращение может быть сформировано из соответствующего слова.

• Всегда будет хотя бы один шаблон, который образует каждую аббревиатуру.

• Максимальная длина каждого слова составляет 9 символов.

В качестве входных данных можно использовать любое из следующего:

• 2-мерный массив / список / массив кортежей / и т. Д. [[word, abbr], [word, abbr], ...]

• плоский одномерный массив / список [word, abbr, word, abbr, ...]

• одна строка, разделенная любым отдельным символом, который не является строчной буквой "word abbr word abbr"

• хэш / ассоциативный массив / и т.д. {word => abbr, word => abbr, ...}

В любом из этих вариантов ввода вам также разрешено менять порядок слова / abbr (пожалуйста, полностью опишите формат ввода в вашем посте).

Вывод может быть задан как одно число, строка, разделенная нецифрами, или массив / list / tuple / etc. чисел.

Поскольку это код-гольф , победит самый короткий код в байтах.

Контрольные примеры (помните, что вам нужно выводить результаты ≥1 только в случае работы нескольких шаблонов):

In                                Out
--------------------------------------------------------
potato ptao puzzle pzze         | 1346
aabbcc abc fddeef def           | 246
prgrmming prgmg puzzles pzzlz   | 14353
aaaaa a bbbb b ccc c dd d e e   | 1
aaaaa a bbbb b ccc c            | 1, 2, 3
abcxyz zbcyax                   | 623514
abcxyz acbbacbcbacbbac          | 132213232132213
potato ptao                     | 1346, 1546, 1342, 1542
a aaaaa                         | 11111

Pyth, 19 байт

mhh@Fd.TmmxkmbhdedQ

Попробуй это здесь!

Принимает список в следующем формате:

[["word","abbr"],["word","abbr"],...]

Альтернативное 17-байтовое решение, которое выводит результат в виде списка нулевых индексов, которые заключены в 1-элементный список:

m@Fd.TmmxkmbhdedQ

объяснение

Пример: [["potato", "ptao"],["puzzle", "pzze"]]

Сначала мы сопоставляем каждый символ в сокращении со списком индексов всех вхождений в слове, которое дает

[[[0], [2, 4], [3], [1, 5]], [[0], [2, 3], [2, 3], [5]]]

Затем мы переносим этот список, который дает нам

[[[0], [0]], [[2, 4], [2, 3]], [[3], [2, 3]], [[1, 5], [5]]]

Таким образом, индексы каждого символа каждой аббревиатуры объединены в один список.

Тогда нам просто нужно найти один общий индекс во всех этих списках, который дает:

[[0], [2], [3], [5]]

Это вывод моего альтернативного 17-байтового решения выше. Это затем превращается в[1,3,4,6] .

Разбивка кода

mhh@Fd.TmmxkmbhdedQ # Q = ввод

m Q # карта ввода с помощью d
        m ed # отобразить каждую аббревиатуру с помощью k
            mbhd # сопоставить слово со списком символов
         mxk # сопоставляет каждую аббревиатуру char со списком индексов
      .T # Транспонировать
    Fd # Сложить каждый элемент
   @ # и фильтр по присутствию
 hh # Возьмите первый элемент результата и увеличьте его

MATL , 29 байт

!"@Y:!=2#fX:wX:h]N$v1XQtv4#X>

Ввод представляет собой двумерный массив в следующем формате:

{'potato' 'ptao'; 'puzzle' 'pzze'}

Попробуйте онлайн! ( связанный код включает некоторые модификации из-за изменений в языке с момента публикации этого ответа )

!       % take input. Transpose
"       % for each column
  @Y:   %   push column. Unpack the two strings and push them onto the stack
  !     %   transpose second string
  =     %   matrix with all pairwise matchings of characters in word and abbreviation
  2#f   %   find row and col indices of those matchings
  X:    %   transform into column vector
  wX:   %   swap, transform into column vector
  h     %   concat into a two-col matrix
]       % end for
N$v     % concatenate all matrices containing the indices
1       % push 1
XQ      % build matrix adding 1 for each (row,col) index
tv      % concat vertically with itself, so that it has at least two rows.
        % This forces the following function to work on each col.
4#X>    % arg max of each col: position that produces a match in all pairs.
        % If there are several maximizers in each col this gives the first

Код потребовал некоторых (и длительных!) Трюков, чтобы

• Не допускайте изменения ориентации векторов, создаваемых find( f), в зависимости от формы ввода. Это операторы X:wX:: заставить оба выхода быть векторами столбцов.
• Противодействовать поведению по умолчанию «работа вдоль первого не-одиночного измерения» функции min( X>). Это заявления tv: конкататируйте свою копию, чтобы обеспечить как минимум две строки);

Perl, 46 45 42 байта

Включает +1 для -p

Введите вводные слова в STDIN, например

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Завершите STDIN с помощью ^Dили ^Zили что-то, что необходимо в вашей системе

abbrev.pl:

s#.#${${--$_.$.%2}.=$&}||=-$_#eg;$_ x=eof

объяснение

Рассмотрим этот ввод (концептуальное расположение, а не реальный способ ввода для этой программы):

potatoes     ptao
puzzle       pzze

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

id1    pp     -> 1
id2    ou     -> 2
id3    tz     -> 3
id4    az     -> 4
...

и т.д. Он также делает то же самое для сокращений, но с использованием другого идентификатора

ID1    pp     -> 1
ID2    tz     -> 3
ID3    az     -> 4
ID4    oe     -> 6

Слова неявно обрабатываются одно за другим с помощью -pопции. Строки столбцов строятся с использованием повторяющихся конкатенаций, в то время как каждое слово проходит, используя s#.# ...code.. #eg, поэтому каждый столбец нуждается в повторяемом идентификаторе. Я использую минус номер столбца, за которым следует номер строки по модулю 2. Номер столбца может быть --$_создан с использованием которого начинается как текущее слово, которое благодаря использованию только a-zгарантированно оценивается как 0 в числовом контексте. Итак, я понял -1, -2, -3, .... Мне бы очень хотелось использовать 1, 2, 3, ..., но использование $_++вызовет приращение магической строки perl вместо обычного числового счетчика. Я делаю, хочу , чтобы использовать$_ а не какую-то другую переменную, потому что любую другую переменную, которую я должен был бы инициализировать нулем в каждом цикле, который занимает слишком много байтов.

Номер строки по модулю 2 должен гарантировать, что идентификаторы для полного слова и идентификаторы для сокращения не конфликтуют. Обратите внимание, что я не могу использовать полное слово и аббревиатуру в одной строке, чтобы номер столбца проходил через объединенную строку, потому что не все слова имеют одинаковую длину, поэтому столбцы сокращенных слов не будут выстраиваться. Я также не могу поставить сокращенное слово первым (все они имеют одинаковую длину), потому что мне нужно, чтобы в первом столбце полных слов было 1.

Я злоупотребляю глобальным пространством имен perl через нестрогую ссылку для конструирования строк столбцов:

${--$_.$.%2}.=$&

Затем я сопоставляю каждую строку столбца с номером первого столбца, в котором эта строка когда-либо появляется (отображение уже указано выше), снова злоупотребляя глобальным пространством имен perl (но обратите внимание, что имена не могут конфликтовать, чтобы глобальные переменные не мешали друг другу):

${${--$_.$.%2}.=$&} ||= -$_

Я должен отрицать, $_потому что, как я объяснил выше, я считаю столбцы как -1, -2, -3, .... ||=УБЕДИТЕСЬ только первое появление данной колонки получает новый номер столбца, в противном случае предыдущий номер столбца сохраняется и возвращается в качестве значения. Это будет происходить, в частности, для каждого сокращенного слова, поскольку спецификация гарантирует, что в полных словах есть столбец, который появится раньше. Таким образом, в самом последнем сокращенном слове каждая буква будет заменена номером столбца в полном слове, который соответствует столбцу для всех сокращенных слов. Таким образом, результатом самой последней замены является конечный результат, который требуется. Так что печатайте тогда и только тогда, когда мы находимся в конце ввода:

$_ x=eof

При присваивании индекса столбцу также создаются записи для неполных столбцов, поскольку столбец еще не сформирован полностью или некоторые слова короче и не достигают полной длины столбца. Это не проблема, так как столбцы, необходимые в каждом сокращенном слове, гарантированно будут иметь соответствующий столбец из полных слов, который имеет максимально возможную длину (количество видимых в данный момент пар), поэтому эти дополнительные записи никогда не приводят к ложным совпадениям.

Haskell, 74 байта

import Data.List
foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)

Формат ввода представляет собой список пар строк, например:

*Main > foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)  $ [("potato","ptao"),("puzzle","pzze")]
[[1,3,4,6]]

Как это работает: mapM(так же, как sequence . map) сначала превращает каждую пару (w,a)в список списков индексов букв в аббревиатуре ( ' ':исправляет родной индекс на основе 0 в Haskell к 1 на основе), например, ("potato", "ptao") -> [[1],[3,5],[4],[2,6]]а затем в список всех их комбинаций, где элемент в позиции iберется из iподсписка th, например [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersectнаходит пересечение всех таких списков списков.

ES6, 92 байта

(w,a)=>[...a[0]].map((_,i)=>[...w[0]].reduce((r,_,j)=>w.some((s,k)=>s[j]!=a[k][i])?r:++j,0))

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

Python 3, 210 байт

Не очень впечатляющий ответ, увидев здесь топ-очки, но это действительно одно из самых сумасшедших представлений о списках, которые я когда-либо делал с Python. Подход довольно прямой.

 def r(p):
    z=[[[1+t[0]for t in i[0]if l==t[1]]for l in i[1]]for i in[[list(enumerate(w[0])),w[1]]for w in p]]
    return[list(set.intersection(set(e),*[set(i[z[0].index(e)])for i in z[1:]]))[0]for e in z[0]]

Функция всегда ожидает ввода в виде строкового двумерного массива, например: [[word, abbr],...]и возвращает список целых чисел.

PS: подробное объяснение в ближайшее время

PS2: Дальнейшие предложения по игре в гольф приветствуются!