O jogo de placas da Espanha

26

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 stringtipo de idioma . O segundo parâmetro (as três consoantes) será outro string. Se for melhor para o seu idioma, considere o stringcom as três consoantes o último item de toda a lista de parâmetros. A saída será outra string.
  • 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 FLRe GGG.
  • 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 , então o programa mais curto que me ajuda a vencer sempre a minha esposa vence! :)

Charlie
fonte
Quanto tempo as palavras na lista de palavras são garantidas?
Neil
2
Em placas de carros reais, a letra Q também não é permitida; e W é, embora não seja uma carta espanhola adequada
Luis Mendo
2
Podemos assumir as palavras da lista e as três letras serão todas em um único caso?
Jonathan Allan
1
@LuisMendo W é uma carta em espanhol desde 1969 .
walen
1
@walen É por isso que eu disse "bom" :-) Ela existe em espanhol, mas é se sente estrangeira
Luis Mendo

Respostas:

7

05AB1E , 10 8 bytes

Economizou 2 bytes graças a Leo

ʒæså}éR`

Experimente online!

Explicação

ʒ         # filter list, keep only members for which the following is true
  så      # input is in the
 æ        # powerset of the current word
    }     # end filter
     é    # sort by length
      R   # reverse
       `  # push separately (shortest on top)

Eu teria usado headno final salvando um byte, mas isso geraria uma lista vazia se não houver uma correspondência.

Emigna
fonte
3
3ù #keep only those of length 3por que você precisa disso?
Leo
1
@ Leo: Eu não, isso foi bobagem da minha parte. Obrigado :)
Emigna
6

MATL , 30 29 bytes

xtog!s2$S"1G!'.*'Yc!@gwXXn?@.

Experimente online!

Explicação

x         % Implicitly take first input (string with three letters). Delete.
          % Gets copied into clipboard G, level 1
t         % Implicitly take second input (cell array of strings defining the
          % words). Duplicate
o         % Convert to numeric array of code points. This gives a matrix where
          % each string is on a row, right-padded with zeros
g         % Convert to logical: nonzeros become 1
!s        % Sum of each row. This gives the length of each word
2$S       % Two-input sort: this sorts the array of strings according to their
          % lengths in increasing order
"         % For each word in the sorted array
  1G      %   Push first input, say 'xyz'
  !       %   Transpose into a column vector of chars
  '.*'Yc  %   Concatenate this string on each row
  !       %   Transpose. This gives a char array which, when linearized in
          %   column-major order, corresponds to 'x.*y.*z.*'
  @g      %   Push corrent word
  w       %   Swap
  XX      %   Regexp matching. Gives a cell array with substrings that match
          %   the pattern 'x.*y.*z.*'
  n       %   Number of matchings
  ?       %   If non-zero
    @     %     Push cell array with current word, to be displayed as output
    .     %     Break loop
          %   Implicit end (if)
          % Implicit end (for)
          % Implicitly display stack
Luis Mendo
fonte
6

PHP , 111 bytes

$y=array_map(str_split,preg_grep("#".chunk_split($_GET[1],1,".*")."#",$_GET[0]));sort($y);echo join($y[0]??[]);

Experimente online!

Jörg Hülsermann
fonte
2
A chapa de matrícula deve ser uma sequência, não uma matriz. Mas você não precisa do modificador.
Titus
@Titus fixed !!
Jörg Hülsermann
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 em wordwrapvez de join(str_split())?
Titus
@Titus good idea
Jörg Hülsermann
5

Geléia ,  12 11  10 bytes

ŒPċðÐfLÞḣ1

Um 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?

ŒPċðÐfLÞḣ1 - Main link: words; characters
   ðÐf     - filter keep words for which this is truthy:
ŒP         -   the power-set (all sub-sequences of the word in question)
  ċ        -   count (how many times the list of characters appears)
           - ...note 0 is falsey while 1, 2, 3, ... are truthy
       Þ   - sort by:
      L    -  length
        ḣ1 - head to index 1 (would use Ḣ but it yields 0 for empty lists)
           - implicit print (smashes together the list of lists (of length 1))
Jonathan Allan
fonte
1
Se entendi sua explicação corretamente, isso iria recusar uma palavra como "borracho" para uma seqüência de consoantes de "BRC", porque "BRC" não é uma substring de "brrc"
Leo
@Leo ah, sim boa captura Eu acho que seria um fracasso ...
Jonathan Allan
@ Leo - bem, é fixo (verifica-se que "existe" para todo o conjunto de potências de cada palavra), mas pode não estar totalmente pronto ...
Jonathan Allan
5

Pitão - 22 21 19 12 11 bytes

h+f/yTQlDEk

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

h+f/yTQlDEk
       lDE   # Sort word list by length
  f          # Filter elements T of the word list...
    yT       # by taking the powerset...
   /  Q      # and checking whether the 3-letter string Q is an element of that.
 +        k  # Add empty string to the list (in case no results found)
h            # And take the first result (the shortest)

Solução antiga de 19 bytes:

h+olNf/-T"aeiou"QEk                       
Maria
fonte
@JonathanAllan: Fixed! Obrigado por apontar isso.
Maria
1
@ JonathanAllan: Parece que ele editou a pergunta para esclarecer que ela deve retornar uma string vazia nesse caso. Eu editei minha resposta de acordo.
Maria
1
Temos uma espécie-by operador meta em D, então u pode substituir OLN com lD
Maltysen
5

Brachylog v2, 11 bytes

tlᵒ∋.&h⊆.∨Ẹ

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…

tlᵒ∋.&h⊆.∨Ẹ
t            The last element of {standard input}
   ∋.        contains the return value as an element
     &       and
      h      the first element of {standard input}
       ⊆.    is a subsequence of the return value
         ∨   alternate behaviour if no solution is found:
          Ẹ  return empty string
  ᵒ          tiebreak override: favour answers that have a low
 l           length

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, a lᵒsubstituição de desempate (que é tecnicamente uma espécie, fazendo uso deO 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 para tlᵒ∋.⊇?₁∨Ẹ, 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.

ais523
fonte
4

Haskell 129 125 74 bytes

import Data.List
l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0

CRÉDITO para @nimi

Davide Spataro
fonte
1
Você pode substituir o mais à direita mape o filtercom uma lista de compreensão. Como você já tem o Data.Listescopo, pode usar sortOn lengthe escolher a cabeça para encontrar o elemento com comprimento mínimo. Por fim, crie yuma função infix. Tudo isso faz fe ksupérfluo: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0.
N
você está certo! Eu apenas comecei a jogar golfe! Obrigado!
Davide Spataro
1
Um mais: se você mudar a importação Data.Lists, você pode usar argminem vez de sortOne salvar o !!0: l#w=argmin length[...]. Data.Liststem muitas funções agradáveis
nimi
3

Perl, 53 bytes

Código de 48 bytes + 5 para -paF.

$"=".*";($_)=sort{$a=~y///c-length$b}grep/@F/,<>

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 partir psrde p.*s.*rque é então combinado para cada palavra adicional e é classificada em length.

Experimente online!

Dom Hastings
fonte
Se eu inserir "adsd" na sua lista, seu programa não conseguirá encontrá-lo. O primeiro caractere a ser encontrado não precisa ser o primeiro da palavra.
Charlie
@CarlosAlejo A entrada precisa de uma nova linha à direita, funciona ok: Experimente online! . Isso me pegou desprevenido, pois o <<<operador acrescenta isso para mim na linha de comando!
Dom Hastings
3

JavaScript (ES6), 77 75 72 bytes

Pega as 3 consoantes ce a lista de palavras lna sintaxe de curry (c)(l). Ambas as entradas são esperadas no mesmo caso.

c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

Casos de teste

Arnauld
fonte
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))para 72, eu acho
LarsW
@LarsW De fato, obrigado! No entanto, escolhi outra abordagem para cumprir a nova regra: ou uma sequência vazia, se nenhuma palavra corresponder ao padrão de três consoantes .
precisa
3

R, 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

w=pryr::f((b=y[sapply(gsub(paste('[^',x,']'),'',y),function(l)regexpr(x,l))>0])[which.min(nchar(b))])

Experimente online!

Edit: Minha versão era 135, obrigado Scrooble pelo -34!

Punintended
fonte
1
Bem-vindo ao PPCG! Parece um trecho em que a entrada está em variáveis ​​codificadas. As respostas precisam ser programas completos ou funções que podem ser chamadas. Você pode dar uma olhada nessas (ou outras respostas R) para possíveis métodos de E / S.
Martin Ender
2

Retina , 58 bytes

O#$^`¶.+
$.&
s`^((.)(.)(.).*¶(?-s:(.*\2.*\3.*\4.*)))?.*
$5

Experimente online! Leva as três consoantes em uma linha e depois a lista de palavras em todas as linhas subseqüentes. Explicação: Oclassifica 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 de s`modo que apenas uma linha é correspondida.

Neil
fonte
1
Não consigo decidir se são três umbigos ou três seios.
Charlie
@CarlosAlejo Você está pensando em Eccentrica Gallumbits por acaso?
Neil
Eu estava pensando no estrangeiro de Total Recall, mas Eccentrica poderia ser também uma opção ... :)
Charlie
2
@CarlosAlejo Aparentemente, Mary é uma homenagem à Eccentrica Gallumbits.
Neil
1

Pip , 17 bytes

@:qJ`.*`N_FI#_SKg

Adota a lista de palavras como argumentos de linha de comando e as consoantes de stdin. Experimente online!

Explicação

                   g is list of cmdline args (implicit)
              SKg  Sort g using this key function:
            #_      Length of each item (puts shortest words first)
          FI       Filter on this function:
  q                 Line of input
   J`.*`            joined on regex .* (turns "psr" into `p.*s.*r`)
        N_          Count regex matches in item (keeps only words that match)
@:                 Get first element of result (using : meta-operator to lower precedence)
                   If the list is empty, this will give nil, which results in empty output
DLosc
fonte
1

Java 8, 132 126 bytes

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;}

-6 bytes graças a @Nevay .

Explicação:

Experimente online.

s->a->{              // Method with two String-array parameters and String return-type
  String r="";       //  Result-String, starting empty
  for(String x:a)    //  Loop over the words
    r=(x.length()<r.length()
                     //   If a word is smaller than the current `r`,
      |r.isEmpty())  //   or `r` is still empty
      &x.matches(r.format(".*%s.*%s.*%s.*",s))?
                     //   And if the word is valid
       x             //    Change `r` to the current word
      :              //   Else:
       r;            //    Leave `r` the same
  return r;}         //  Return the result
Kevin Cruijssen
fonte
1
126 bytes: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;}
Nevay
0

Python, 77 bytes

import re
lambda s,a:min([x for x in a if re.search('.*'.join(s),x)],key=len)

Experimente online!

Uriel
fonte
0

MATL , 28 27 26 bytes

x"l1G@g3XNXm/@gn*v]&X<2Gw)

Experimente 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 tarde

1G - Pressione a primeira entrada (diga 'psr')

@g - Empurre a palavra atual como matriz

3XN- nchoosek- Obtenha todas as combinações de 3 letras da palavra

Xm- 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 para Infs

@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 encontrada

2G - Pressione a segunda entrada novamente

w - 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:

x"@g1Gy3XNXm1w/wn*v]&X<2Gw)

x"@g1Gy3XNXm1w/wn*v]2Gw2$S1)
sundar - Restabelecer Monica
fonte