Esta pergunta é baseada em uma pergunta que fiz no idioma espanhol . Sim, solicitei um algoritmo no idioma espanhol. :)
Na Espanha, as matrículas atuais têm esse padrão:
1234 XYZ
onde XYZ são três consoantes retiradas do conjunto completo de consoantes espanholas (exceto a 'Ñ', eu acho).
Às vezes, quando viajamos com minha esposa, costumamos jogar um jogo. Quando vemos uma placa de carro, pegamos suas três consoantes e tentamos formar uma palavra que contenha essas três consoantes, aparecendo na mesma ordem que na placa de carro. Exemplos (em espanhol):
BCD
BoCaDo (valid)
CaBezaDa (not valid)
FTL
FaTaL (valid)
FLeTar (not valid)
FTR
FleTaR (valid, wins)
caFeTeRa (valid, loses)
O vencedor é aquele que usa o menor número de caracteres, como você pode ver no último exemplo.
O desafio
Escreva o programa ou a função mais curta que receba uma lista de palavras e um conjunto de três consoantes e encontre a palavra mais curta na lista que contém as três consoantes na mesma ordem. Para os propósitos deste jogo, o caso não importa.
- A entrada para a lista de palavras (primeiro parâmetro) será uma matriz do seu
string
tipo de idioma . O segundo parâmetro (as três consoantes) será outrostring
. Se for melhor para o seu idioma, considere ostring
com as três consoantes o último item de toda a lista de parâmetros. A saída será outrastring
. - As palavras na lista de palavras não serão inventadas ou serão infinitas; elas aparecerão em qualquer dicionário padrão. Se você precisar de um limite, suponha que nenhuma palavra na lista de palavras tenha mais de 50 caracteres.
- Se houver várias palavras com o mesmo comprimento que possam ser a resposta válida, você poderá retornar qualquer uma delas. Apenas certifique-se de retornar apenas uma palavra ou uma sequência vazia, se nenhuma palavra corresponder ao padrão de três consoantes.
- Você pode repetir consoantes no grupo, portanto, entradas válidas para as três consoantes são ambos
FLR
eGGG
. - As consoantes espanholas são exatamente as mesmas do inglês, com a adição do "Ñ". As vogais são as mesmas com a adição das vogais estressadas: "áéíóúü". Não haverá outro tipo de marca como "-" ou "'".
- Você pode supor que o caso será sempre o mesmo na lista de palavras e nas três consoantes.
Se você quiser testar seu algoritmo com uma coleção real de palavras em espanhol, poderá baixar um arquivo (15,9 MB) do Dropbox com mais de um milhão de palavras.
Casos de teste
Input: 'psr', {'hola' 'repasar' 'pasarais' 'de' 'caída' 'pequeñísimo' 'agüeros'}
Output: 'repasar'
Input: 'dsd', {'dedos' 'deseado' 'desde' 'sedado'}
Output: 'desde'
Input: 'hst', {'hastío' 'chest'}
Output: 'chest'
Este é o código-golfe , então o programa mais curto que me ajuda a vencer sempre a minha esposa vence! :)
Respostas:
05AB1E ,
108 bytesEconomizou 2 bytes graças a Leo
Experimente online!
Explicação
Eu teria usado
head
no final salvando um byte, mas isso geraria uma lista vazia se não houver uma correspondência.fonte
3ù #keep only those of length 3
por que você precisa disso?MATL ,
3029 bytesExperimente online!
Explicação
fonte
PHP , 111 bytes
Experimente online!
fonte
You can suppose the case will always be the same in both the word list and the three consonants.
- não há necessidade do modificador regex. Você já tentou emwordwrap
vez dejoin(str_split())
?Geléia ,
12 1110 bytesUm programa completo que aceita uma lista de listas de caracteres minúsculos (as palavras) e uma lista de caracteres minúsculos (as letras) e imprime a primeira das palavras mais curtas que contêm uma sub-sequência igual às letras (ou nada, se não existir) )
Experimente online!
Quão?
fonte
Pitão -
2221191211 bytes-1 Obrigado a Maltysen.
Toma 2 linhas como entrada. 1ª é a sequência de 3 letras (minúscula) e a 2ª é uma lista minúscula de palavras.
Experimente aqui
Explicação:
Solução antiga de 19 bytes:
fonte
Brachylog v2, 11 bytes
Experimente online!
Envio de função. (O link TIO possui um argumento de linha de comando para executar uma função como se fosse um programa completo.)
Explicação
Apenas uma tradução direta da especificação novamente…
Na verdade, você pode quase responder com
h⊆.&t∋
- trocar a ordem de avaliação significa que o Brachylog escolherá a resposta mais curta por padrão (como a primeira restrição que ele vê é a⊆
que tem o "menor" conveniente como um tiebreak padrão) - mas, nesse caso, a Brachylog Infelizmente, o algoritmo de avaliação entraria em um loop infinito se a resposta não fosse realmente encontrada. Portanto, quase metade da resposta é dedicada a lidar com o caso de não haver uma resposta apropriada. Mesmo assim, alᵒ
substituição de desempate (que é tecnicamente uma espécie, fazendo uso de∋
O tiebreak padrão dos elementos preferenciais mais perto do início da lista) é de apenas dois bytes; os outros três vêm da necessidade de gerar uma string vazia especificamente quando a saída não é encontrada, em oposição ao valor sentinela padrão "sem soluções" de Brachylog (porque a final.
seria implícita se não fosse necessário segui-la∨
).Curiosamente, há um recurso que foi implementado anteriormente no Brachylog que salvaria um byte aqui. Em um ponto, você pode extrair elementos do argumento de entrada usando
?₁
,?₂
etc. sintaxe; isso permitiria reorganizar o programa paratlᵒ∋.⊇?₁∨Ẹ
, que é de apenas 10 bytes. Infelizmente, a implementação usada realmente não funcionou (e causou a interrupção de muitos programas em funcionamento), por isso foi revertida. Você pode pensar no programa como sendo "conceitualmente" 10 bytes de comprimento.fonte
Haskell
12912574 bytesCRÉDITO para @nimi
fonte
map
e ofilter
com uma lista de compreensão. Como você já tem oData.List
escopo, pode usarsortOn length
e escolher a cabeça para encontrar o elemento com comprimento mínimo. Por fim, criey
uma função infix. Tudo isso fazf
ek
supérfluo:l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0
.Data.Lists
, você pode usarargmin
em vez desortOn
e salvar o!!0
:l#w=argmin length[...]
.Data.Lists
tem muitas funções agradáveisPerl, 53 bytes
Código de 48 bytes + 5 para
-paF
.Isso leva vantagem do fato de que as listas interpolados para o
m//
operador utilizar a$"
variável que muda a seqüência de entrada inicial a partirpsr
dep.*s.*r
que é então combinado para cada palavra adicional e é classificada emlength
.Experimente online!
fonte
<<<
operador acrescenta isso para mim na linha de comando!JavaScript (ES6),
777572 bytesPega as 3 consoantes
c
e a lista de palavrasl
na sintaxe de curry(c)(l)
. Ambas as entradas são esperadas no mesmo caso.Casos de teste
Mostrar snippet de código
fonte
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))
para 72, eu achoR, 101 bytes
Golfe pela primeira vez! Tenho certeza que isso pode ser condensado de alguma forma
Pega a string x e um vetor de caracteres y de possíveis entradas
Experimente online!
Edit: Minha versão era 135, obrigado Scrooble pelo -34!
fonte
Retina , 58 bytes
Experimente online! Leva as três consoantes em uma linha e depois a lista de palavras em todas as linhas subseqüentes. Explicação:
O
classifica a lista,¶.+
excluindo a primeira linha digitada#
numericamente$
pelo$.&
comprimento. Uma correspondência é então procurada por uma linha que inclua as três consoantes em ordem. Se existir uma linha adequada que a anterior, ou seja, a mais curta, essa linha se torna a saída, caso contrário, a saída está vazia. O?-s:
desativa temporariamente o efeito des`
modo que apenas uma linha é correspondida.fonte
Pip , 17 bytes
Adota a lista de palavras como argumentos de linha de comando e as consoantes de stdin. Experimente online!
Explicação
fonte
Java 8,
132126 bytes-6 bytes graças a @Nevay .
Explicação:
Experimente online.
fonte
s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}
Python, 77 bytes
Experimente online!
fonte
MATL ,
282726 bytesExperimente online!
x
- Pegue implicitamente a primeira entrada (string com três letras) e exclua-a. É copiada para a área de transferência G, nível 1 automaticamente (esta parte foi inspirada na resposta de @Luis Mendo )."
- Pegue implicitamente a segunda entrada (matriz de palavras das células), itere através dela.l
- Pressione 1 para ser usado mais tarde1G
- Pressione a primeira entrada (diga 'psr')@g
- Empurre a palavra atual como matriz3XN
-nchoosek
- Obtenha todas as combinações de 3 letras da palavraXm
- Veja se o código da placa 'psr' é uma dessas combinações. Retorna 0 para falso e 1 para verdadeiro./
- Dividindo o 1 (que pressionamos anteriormente) por esse resultado. Altera os 0s paraInf
s@gn
- Obter o tamanho da palavra atual*
- Multiplique o comprimento pelo resultado da divisão. Retorna o tamanho como está quando a palavra contém os 3 caracteres; caso contrário, retornaInf
v
- concatenar verticalmente esses resultados em uma única matriz]
- laço fechado&X<
- obtém o índice do valor mínimo dessa matriz, ou seja, o índice onde a palavra que contém as letras e com tamanho mínimo foi encontrada2G
- Pressione a segunda entrada novamentew
- Coloque o índice mínimo de volta no topo da pilha)
- Índice em array de palavras com o índice mínimo, retornando a palavra válida com tamanho mínimo(Saída implícita.)
Mais velho:
fonte