Dada uma lista de seqüências de caracteres, substitua cada sequência por uma de suas subseqüências não vazias, que não é uma subseqüência de nenhuma das outras seqüências da lista e o mais curta possível.
Exemplo
Dada a lista ["hello","hallo","hola"]
, "hello"
deve ser substituído por apenas "e"
como este substring não está contido no "hallo"
e "hola"
e é o mais curto possível. "hallo"
Pode ser substituído por um ou outro "ha"
ou "al"
e "hola"
por qualquer um dos "ho"
, "ol"
ou "la"
.
Regras
- Você pode assumir que as seqüências de caracteres não estarão vazias e conterão apenas caracteres alfabéticos do mesmo caso.
- Você pode assumir que existe uma substring para cada string da lista, ou seja, nenhuma string da lista será uma substring de qualquer uma das outras strings.
- A entrada e a saída podem estar em qualquer formato razoável.
- Isso é código-golfe , então tente usar o mínimo de bytes possível no idioma de sua escolha.
Casos de teste
Apenas uma saída possível é fornecida na maioria dos casos.
["ppcg"] -> ["p"] (or ["c"] or ["g"])
["hello","hallo","hola"] -> ["e","ha","ho"]
["abc","bca","bac"] -> ["ab","ca","ba"]
["abc","abd","dbc"] -> ["abc","bd","db"]
["lorem","ipsum","dolor","sit","amet"] -> ["re","p","d","si","a"]
["abc","acb","bac","bca","cab","cba"] -> ["abc","acb","bac","bca","cab","cba"]
Relacionado: Substring de identificação mais curta - idéia semelhante, mas regras mais envolvidas e formato complicado.
code-golf
string
code-golf
string
code-golf
array-manipulation
code-golf
quine
code-golf
array-manipulation
integer
matrix
classification
code-golf
quine
code-golf
string
matrix
conversion
code-golf
string
number
code-golf
string
code-golf
number
sequence
integer
code-golf
decision-problem
matrix
code-golf
string
code-golf
math
code-golf
math
array-manipulation
combinatorics
code-golf
random
code-golf
code-golf
alphabet
code-golf
python
c
code-golf
base-conversion
code-golf
string
counting
code-challenge
code-generation
fastest-code
code-golf
kolmogorov-complexity
matrix
code-golf
string
code-golf
array-manipulation
decision-problem
random
sudoku
code-golf
chess
code-golf
card-games
encode
code-golf
decision-problem
code-golf
code-golf
math
array-manipulation
matrix
Laikoni
fonte
fonte
""
(string vazia) a identificação exclusiva para o"ppcg"
caso único ?Respostas:
Geléia ,
129 bytesExperimente online! Ou veja a suíte de testes (leva ~ 35s)
fonte
Python 2 , 116 bytes
Experimente online!
fonte
Pitão , 12 bytes
Experimente aqui!
Como funciona
Basicamente, filtra as substrings de cada uma que ocorrem apenas em uma das strings da lista (ou seja, é exclusiva dessa string) e obtém a primeira.
fonte
Prolog (SWI) ,
175163 bytesExperimente online!
A maioria das coisas aqui deve ser bastante óbvia, mas:
Explicação
Assinaturas: (
+
= entrada,?
= opcional,-
= saída,:
= expressão)sub_string(+String, ?Before, ?Length, ?After, ?SubString)
string_length(+String, -Length)
member(?Elem, ?List)
between(+Low, +High, ?Value)
findall(+Template, :Goal, -Bag)
forall(:Cond, :Action)
\+ \+
é justonot not
(isto é, converte uma correspondência em booleano (neste caso, impede que ela combine ambos osp
sppcg
separadamente))fonte
APL (Dyalog) , 25 bytes
Obrigado ngn por salvar um byte
Experimente online!
fonte
J ,
30 2925 bytesExperimente online!
fonte
Gelatina , 10 bytes
Experimente online!
fonte
JavaScript (ES6), 93 bytes
Experimente online!
Quão?
Para cada string s de comprimento L na matriz de entrada a [] e começando com n = 0 , usamos a função recursiva g () para gerar todas as substrings u de s com:
Por exemplo, com s = "abc" e L = 3 :
Algumas substrings são geradas várias vezes, mas isso não importa. O importante é que todas as substrings de comprimento N tenham sido geradas antes de qualquer substring de comprimento N + 1 .
Paramos o processo assim que você não puder ser encontrado em nenhuma outra string S em [] , o que é garantido que acontece quando u == s no pior caso, conforme a regra de desafio nº 2:
Portanto, no exemplo acima, as etapas 7 e 8 nunca serão processadas.
fonte
PowerShell , 107 bytes
Experimente online!
Explicação
Para cada sequência fornecida (e designe toda a matriz
$a
):for
loop sobre cada comprimento de substring (baseado em 1) da string (atribuindo a própria string$s
e o comprimento a$g
)$i
):$i
, em seguida, para cada índice:$s
) na posição$_
(índice) e no comprimento$i
Where-Object
(?
) e retorne-a se:$a
) que não contém a cadeia atual$s
, não possui uma correspondência para a substring atual$_
De volta ao nível da sequência, temos todas as subseqüências dessa sequência que não foram encontradas nas outras. Portanto, pegue a primeira,
[0]
pois precisamos apenas de uma delas e continue com a próxima.fonte
C # (compilador interativo do Visual C #) , 149 bytes
Experimente online!
Menos golfe ...
fonte