Dada a entrada de uma lista de palavras e suas abreviações, produza o padrão pelo qual as abreviações podem ser formadas.

Vamos dar o exemplo de entrada de

potato ptao
puzzle pzze

como um exemplo (ou seja, a abreviação de potatoé ptaoe a abreviação de puzzleé pzze).

Considere todas as maneiras possíveis para obter ptaoa partir potato. Uma maneira possível é usar a primeira, terceira, quarta e sexta letras, às quais iremos nos referir 1346. Mas desde te oaparecer várias vezes na palavra, existem várias outras maneiras possíveis para gerar ptaoa partir de potato: 1546, 1342e 1542.

Da mesma forma, nota que pzzepode ser gerado a partir puzzlede qualquer um 1336, 1346, 1436, 1446. O único padrão que essas duas abreviações têm em comum é 1346; portanto, essa deve ser a saída para esta entrada. Se vários padrões possíveis forem possíveis, você poderá gerar um, alguns ou todos eles (pelo menos um).

Você pode assumir que:

• As palavras e abreviações de entrada contêm apenas letras minúsculas.

• Há pelo menos um par de palavras / abreviações na entrada.

• É possível que toda abreviação seja formada a partir da palavra correspondente.

• Sempre haverá pelo menos um padrão que forma todas as abreviações.

• O comprimento máximo de cada palavra é de 9 caracteres.

A entrada pode ser aceita como uma das seguintes opções:

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

• matriz / lista unidimensional plana [word, abbr, word, abbr, ...]

• sequência única, delimitada por qualquer caractere que não seja uma letra minúscula "word abbr word abbr"

• hash / array associativo / etc. {word => abbr, word => abbr, ...}

Em qualquer uma dessas opções de entrada, você também pode trocar a ordem das palavras / abbr (descreva completamente o formato de entrada em sua postagem).

A saída pode ser fornecida como um número único, uma string delimitada por não-dígitos ou uma matriz / lista / tupla / etc. de números.

Como isso é código-golfe , o código mais curto em bytes será vencedor.

Casos de teste (lembre-se de que você só precisa gerar 1 ou mais resultados se vários padrões funcionarem):

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

Pitão, 19 bytes

[email protected]

Experimente aqui!

Leva uma lista no seguinte formato:

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

Solução alternativa de 17 bytes que gera o resultado como lista de índices baseados em zero, agrupados em uma lista de 1 elemento:

[email protected]

Explicação

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

Primeiro, mapeamos todos os caracteres da abreviação para uma lista dos índices de todas as ocorrências na palavra que produz

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

Então transpomos essa lista que nos dá

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

Portanto, os índices de cada caractere de cada abreviação estão juntos em uma lista.

Então, apenas precisamos encontrar um índice comum em todas as listas que produza:

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

Esta é a saída da minha solução alternativa de 17 bytes acima. Isso então é transformado [1,3,4,6].

Repartição do código

[email protected] # Q = entrada

m entrada de mapa Q # com d
        m ed # mapeie cada abreviação com k
            mbhd # mapeia a palavra para a lista de caracteres
         mxk # mapeia cada caracter de abreviação para uma lista de índices
      .T # Transpose
    Fd # Dobre todos os elementos
   @ # e filtro na presença
 hh # Pegue o primeiro elemento do resultado e aumente-o

MATL , 29 bytes

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

A entrada é uma matriz 2D no seguinte formato:

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

Experimente online! ( o código vinculado inclui algumas modificações devido a alterações no idioma desde que esta resposta foi publicada )

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

O código exigia alguns truques envolvidos (e demorados!) Para

• Impedir que a orientação dos vetores produzidos por find( f) seja alterada dependendo do formato da entrada. Estas são as instruções X:wX:: força ambas as saídas a serem vetores de coluna.
• Contrarie o comportamento padrão "trabalhar ao longo da primeira dimensão não singleton" da função min( X>). Estas são as instruções tv: concat uma cópia de si mesma para garantir pelo menos duas linhas);

Perl, 46 45 42 bytes

Inclui +1 para -p

Dê entrada como palavras seqüenciais no STDIN, por exemplo

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Encerre o STDIN com ^Dou^Z que for necessário em seu sistema

abbrev.pl:

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

Explicação

Considere esta entrada (layout conceitual, não a maneira real de entrada para este programa):

potatoes     ptao
puzzle       pzze

O programa constrói cadeias representando as colunas verticais das cadeias completas indexadas em um ID de coluna

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

etc. Também faz o mesmo para as abreviações, mas usando um ID diferente

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

As palavras são implicitamente processadas uma a uma usando a -popção As seqüências de caracteres das colunas são construídas usando concatenações repetidas enquanto cada palavra é usada s#.# ...code.. #eg, portanto, cada coluna precisa de um ID repetível. Uso menos o número da coluna seguido pelo número da linha módulo 2. O número da coluna pode ser construído usando o --$_que começa como a palavra atual que, devido ao uso de only, a-zé garantida para avaliar como 0 em um contexto numérico. Então eu entendo -1, -2, -3, .... Eu realmente gostaria de usar 1, 2, 3, ..., mas o uso $_++ativaria o incremento de string mágica perl em vez de um contador numérico normal. Eu e não alguma outra variável porque qualquer outra variável que eu teria que inicializar para zero em cada loop que leva muitos bytes. não quero usar$_

O número da linha módulo 2 é para garantir que os IDs da palavra completa e os IDs da abreviação não colidam. Observe que eu não posso usar a palavra completa e a abreviação em uma sequência para ter um número de coluna passando sobre a sequência combinada porque as palavras completas nem todas têm o mesmo comprimento, para que as colunas das palavras abreviadas não se alinhem. Também não consigo colocar a palavra abreviada em primeiro lugar (todas elas têm o mesmo comprimento) porque preciso que o número da primeira coluna das palavras completas seja 1.

Abuso o espaço de nome global perl através de uma referência não estrita para construir as seqüências de caracteres da coluna como:

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

Em seguida, mapeio cada string de coluna para o primeiro número de coluna em que a string já aparece (o mapeamento já indicado acima) abusando novamente do espaço de nomes global perl (mas observe que os nomes não podem entrar em conflito para que as globais não interfiram entre si):

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

Eu tenho que negar $_porque, como expliquei acima, conto as colunas como -1, -2, -3, .... A ||=garantir que apenas a primeira aparição de uma determinada coluna recebe um novo número da coluna, caso contrário, o número da coluna anterior é preservada e retornado como valor. Isso acontecerá em particular para cada palavra abreviada, pois a especificação garante que exista uma coluna nas palavras completas que aparecerão anteriormente. Portanto, na última palavra abreviada, cada letra será substituída pelo número da coluna na palavra completa que corresponde à coluna para todas as palavras abreviadas. Portanto, o resultado da última substituição é o resultado final desejado. Portanto, imprima se e somente se estivermos no final da entrada:

$_ x=eof

A atribuição do índice da coluna também criará entradas para colunas incompletas porque a coluna ainda não foi completamente construída ou algumas palavras são mais curtas e não atingem o comprimento total da coluna. Isso não é um problema, pois é garantido que as colunas necessárias em cada palavra abreviada possuem uma coluna correspondente às palavras completas, com o comprimento máximo possível (o número de pares vistos no momento), para que essas entradas extras nunca causem correspondências falsas.

Haskell, 74 bytes

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

O formato de entrada é uma lista de pares de strings, por exemplo:

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

Como funciona: mapM(o mesmo que sequence . map) primeiro transforma todos os pares (w,a)em uma lista de índices das letras da abreviação ( ' ':corrige o índice com base em 0 nativo de Haskell para 1 com base em 1), por exemplo, ("potato", "ptao") -> [[1],[3,5],[4],[2,6]]e depois em uma lista de todas as combinações em que o elemento na posição ié extraído da isub-lista, por exemplo [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersectencontra a interseção de todas essas 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))

Aceita entrada como uma matriz de palavras e uma matriz de abreviações. Retorna uma matriz de índices baseados em 1 (que me custa 2 bytes de erro). No caso de várias soluções, os índices mais altos são retornados.

Python 3, 210 bytes

Não é uma resposta impressionante, alcançando os melhores resultados aqui, mas esta é realmente uma das mais loucas listas de compreensão que já fiz com Python. A abordagem é bastante direta.

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

A função espera entrada sempre como uma matriz 2D de cadeia de caracteres como: [[word, abbr],...] e retorna uma lista de números inteiros.

Ps: Uma explicação detalhada em breve

Ps2: Mais sugestões de golfe são bem-vindas!