Dada una entrada de una lista de palabras y sus abreviaturas, genera el patrón mediante el cual se pueden formar las abreviaturas.

Tomemos el ejemplo de entrada de

potato ptao
puzzle pzze

como ejemplo (es decir, la abreviatura de potatois ptaoy la abreviatura de puzzleis pzze).

Considere todas las formas posibles de obtener ptaode potato. Una forma posible es tomar las letras primera, tercera, cuarta y sexta, a las que nos referiremos como 1346. Pero desde ty oaparecer varias veces en la palabra, hay varias otras maneras posibles de generar ptaoa partir de potato: 1546, 1342y 1542.

Del mismo modo, cabe destacar que pzzese pueden generar a partir puzzlede cualquiera de 1336, 1346, 1436, 1446. El único patrón que estas dos abreviaturas tienen en común es 1346; por lo tanto, esa debe ser la salida para esta entrada. Si son posibles varios patrones posibles, puede generar alguno, algunos o todos (al menos uno).

Puede suponer que:

• Las palabras y abreviaturas de entrada contienen solo letras minúsculas.

• Hay al menos un par de palabra / abreviatura en la entrada.

• Es posible que cada abreviatura se forme a partir de su palabra correspondiente.

• Siempre habrá al menos un patrón que forme cada abreviatura.

• La longitud máxima de cada palabra es de 9 caracteres.

La entrada puede tomarse como cualquiera de los siguientes:

• Matriz bidimensional / lista / matriz de tuplas / etc. [[word, abbr], [word, abbr], ...]

• lista / matriz plana de 1 dimensión [word, abbr, word, abbr, ...]

• cadena única, delimitada por cualquier carácter único que no sea una letra minúscula "word abbr word abbr"

• hash / matriz asociativa / etc. {word => abbr, word => abbr, ...}

En cualquiera de estas opciones de entrada, también se le permite intercambiar el orden de word / abbr (describa completamente el formato de entrada en su publicación).

La salida se puede dar como un solo número, una cadena delimitada por no dígitos, o una matriz / lista / tupla / etc. de números

Como se trata de código golf , el código más corto en bytes ganará.

Casos de prueba (recuerde que solo necesita generar ≥1 resultados si funcionan varios patrones):

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 bytes

[email protected]

Pruébalo aquí!

Toma una lista en el siguiente formato:

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

Solución alternativa de 17 bytes que genera el resultado como una lista de índices basados ​​en cero que se envuelven en una lista de 1 elemento:

[email protected]

Explicación

Ejemplo: [["potato", "ptao"],["puzzle", "pzze"]]

Primero mapeamos cada carácter en la abreviatura a una lista de los índices de todas las ocurrencias en la palabra que produce

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

Luego transponemos esta lista que nos da

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

Entonces, los índices de cada carácter de cada abreviatura están juntos en una lista.

Luego solo tenemos que encontrar un índice común en todas esas listas que produzca:

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

Este es el resultado de mi solución alternativa de 17 bytes anterior. Esto luego se transforma en [1,3,4,6].

Desglose de código

[email protected] # Q = input

m Q # entrada de mapa con d
        m ed # mapea cada abreviatura con k
            mbhd # palabra del mapa a la lista de caracteres
         mxk # asigna cada carácter de abreviatura a una lista de índices
      .T # Transponer
    Fd # Doblar cada elemento
   @ # y filtrar en presencia
 hh # Tome el primer elemento del resultado und e increméntelo

MATL , 29 bytes

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

La entrada es una matriz 2D en el siguiente formato:

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

Pruébalo en línea! ( el código vinculado incluye algunas modificaciones debido a cambios en el idioma desde que se publicó esta respuesta )

!       % 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

El código requería algunos trucos involucrados (¡y largos!) Para

• Evite que la orientación de los vectores producidos por find( f) cambie dependiendo de la forma de entrada. Estas son declaraciones X:wX:: obligan a ambas salidas a ser vectores de columna.
• Contrarresta el comportamiento predeterminado de "trabajar a lo largo de la primera dimensión no singleton" de la función min( X>). Estas son declaraciones tv: concat una copia de sí mismo para asegurar al menos dos filas);

Perl, 46 45 42 bytes

Incluye +1 para -p

Dar entrada como palabras secuenciales en STDIN, p. Ej.

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Termine STDIN con ^Do ^Zlo que sea necesario en su sistema

abbrev.pl:

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

Explicación

Considere esta entrada (diseño conceptual, no la forma real de entrada para este programa):

potatoes     ptao
puzzle       pzze

El programa crea cadenas que representan las columnas verticales de las cadenas completas indexadas en un ID de columna

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

etc. También hace lo mismo para las abreviaturas, pero usando una identificación diferente

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

Las palabras se procesan implícitamente una por una utilizando la -popción Las cadenas de columnas se construyen usando concatenaciones repetidas mientras se usa cada palabra s#.# ...code.. #eg, por lo que cada columna necesita una identificación repetible. Utilizo menos el número de columna seguido del número de línea módulo 2. El número de columna se puede construir usando el --$_que comienza como la palabra actual que, debido al uso de solo, a-zse garantiza que se evalúe como 0 en un contexto numérico. Entonces lo entiendo -1, -2, -3, .... Realmente me hubiera gustado usar 1, 2, 3, ..., pero usando y no alguna otra variable porque cualquier otra variable que tendría que inicializar a cero en cada ciclo que toma demasiados bytes.$_++ activaría el incremento de cadena mágica perl en lugar de un contador numérico normal. Yo no quiero usar$_

El número de línea del módulo 2 es asegurarse de que los identificadores de la palabra completa y los identificadores de la abreviatura no entren en conflicto. Tenga en cuenta que no puedo usar la palabra completa y la abreviatura en una cadena para tener un número de columna sobre la cadena combinada porque las palabras completas no tienen la misma longitud, por lo que las columnas de palabras abreviadas no se alinearían. Tampoco puedo poner primero la palabra abreviada (todas tienen la misma longitud) porque necesito que el recuento de la primera columna de las palabras completas sea 1.

Abuso del espacio de nombre global de Perl a través de una referencia no estricta para construir las cadenas de columna como:

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

A continuación, asigno cada cadena de columna al primer número de columna en el que aparece la cadena (la asignación ya se indicó anteriormente) al volver a abusar del espacio de nombres global de Perl (pero tenga en cuenta que los nombres no pueden entrar en conflicto para que los globales no interfieran entre sí):

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

Tengo que negar $_porque, como expliqué anteriormente, cuento las columnas como -1, -2, -3, .... El ||=asegurarse de que sólo la primera aparición de una columna dada consigue un nuevo número de la columna, de lo contrario el número de columna anterior se conserva y devuelve como valor. Esto sucederá en particular para cada palabra abreviada ya que la especificación garantiza que hay una columna en las palabras completas que aparecerán de antemano. Entonces, en la última palabra abreviada, cada letra se reemplazará por el número de columna en la palabra completa que corresponde con la columna para todas las palabras abreviadas. Entonces, el resultado de la última sustitución es el resultado final que se desea. Entonces imprima si y solo si estamos al final de la entrada:

$_ x=eof

La asignación del índice de columna también creará entradas para columnas incompletas porque la columna aún no está completamente construida o algunas palabras son más cortas y no alcanzan la longitud total de la columna. Esto no es un problema ya que las columnas necesarias en cada palabra abreviada tienen garantizada una columna correspondiente de las palabras completas que tiene la longitud máxima posible (el número de pares vistos actualmente) por lo que estas entradas adicionales nunca causan coincidencias falsas.

Haskell, 74 bytes

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

El formato de entrada es una lista de pares de cadenas, por ejemplo:

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

Cómo funciona: mapM(igual que sequence . map) primero convierte cada par (w,a)en una lista de listas de índices de las letras en la abreviatura ( ' ':fija el índice nativo de Haskell basado en 0 a 1), por ejemplo, ("potato", "ptao") -> [[1],[3,5],[4],[2,6]]y luego en una lista de todas sus combinaciones donde el elemento en la posición ise extrae de la isublista, por ejemplo [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersectencuentra la intersección de todas esas listas de listas.

ES6, 92 bytes

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

Acepta entradas como un conjunto de palabras y un conjunto de abreviaturas. Devuelve una matriz de índices basados ​​en 1 (que me cuesta 2 bytes maldita sea). En el caso de múltiples soluciones, se devuelven los índices más altos.

Python 3, 210 bytes

No es una respuesta impresionante ver los mejores puntajes aquí, pero esta es realmente una de las listas de comprensión más locas que he hecho con Python. El enfoque es bastante sencillo.

 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]]

La función espera una entrada siempre como una matriz 2D de cadena como: [[word, abbr],...]y devuelve una lista de enteros.

Ps: una explicación detallada próximamente

Ps2: más sugerencias de golf son bienvenidas!