El juego de placas de España

26

Esta pregunta se basa en una pregunta que hice en español . Sí, pedí un algoritmo en español. :)

En España, las placas actuales tienen este patrón:

1234 XYZ

donde XYZ son tres consonantes tomadas del conjunto completo de consonantes españolas (excepto el 'Ñ', creo).

A veces, cuando viajo con mi esposa, solemos jugar un juego. Cuando vemos una placa de matrícula, tomamos sus tres consonantes e intentamos formar una palabra que contenga esas tres consonantes, que aparecen en el mismo orden que en la placa de matrícula. Ejemplos (en español):

BCD
    BoCaDo (valid)
    CaBezaDa (not valid)
FTL
    FaTaL (valid)
    FLeTar (not valid)
FTR
    FleTaR (valid, wins)
    caFeTeRa (valid, loses)

El ganador es el que usa la menor cantidad de caracteres, como puede ver en el último ejemplo.

El reto

Escriba el programa o función más corta que reciba una lista de palabras y un conjunto de tres consonantes y encuentre la palabra más corta en la lista que contenga las tres consonantes en el mismo orden. Para los propósitos de este juego, el caso no importa.

  • La entrada para la lista de palabras (primer parámetro) será una matriz de su stringtipo de idioma . El segundo parámetro (las tres consonantes) será otro string. Si es mejor para su idioma, considere stringel último elemento de la lista completa de parámetros con las tres consonantes. La salida será otra string.
  • Las palabras en la lista de palabras no serán inventadas o palabras infinitas, serán palabras que aparecen en cualquier diccionario estándar. Si necesita un límite, suponga que ninguna palabra en la lista de palabras tendrá más de 50 caracteres.
  • Si hay varias palabras con la misma longitud que podrían ser la respuesta válida, puede devolver cualquiera de ellas. Solo asegúrese de devolver una sola palabra o una cadena vacía si ninguna palabra coincide con el patrón de tres consonantes.
  • Puede repetir consonantes en el grupo, por lo que las entradas válidas para las tres consonantes son ambas FLRy GGG.
  • Las consonantes españolas son exactamente las mismas que las inglesas, con la adición de "Ñ". Las vocales son las mismas con la adición de las vocales acentuadas: "áéíóúü". No habrá otro tipo de marcas como "-" o "'".
  • Puede suponer que el caso siempre será el mismo tanto en la lista de palabras como en las tres consonantes.

Si desea probar su algoritmo con una colección real de palabras en español, puede descargar un archivo (15.9 MB) de Dropbox con más de un millón de palabras.

Casos de prueba

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 es el , ¡así que el programa más corto que me ayude a vencer a mi esposa siempre gana! :)

Charlie
fuente
¿Cuánto duran las palabras en la lista de palabras?
Neil
2
En las matrículas reales, la letra Q tampoco está permitida; y W es, aunque no es una carta española apropiada
Luis Mendo
2
¿Podemos asumir las palabras en la lista y las tres letras serán todas en un caso?
Jonathan Allan
1
@LuisMendo W ha sido una carta en español desde 1969 .
walen
1
@walen Por eso dije "correcto" :-) Existe en español, pero se siente extranjero
Luis Mendo

Respuestas:

7

05AB1E , 10 8 bytes

Guardado 2 bytes gracias a Leo

ʒæså}éR`

Pruébalo en línea!

Explicación

ʒ         # 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)

Hubiera utilizado headal final guardar un byte, pero eso generaría una lista vacía si no hay una coincidencia.

Emigna
fuente
3
3ù #keep only those of length 3¿Por qué necesitas esto?
Leo
1
@Leo: No, eso fue una tontería de mi parte. Gracias :)
Emigna
6

MATL , 30 29 bytes

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

Pruébalo en línea!

Explicación

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
fuente
6

PHP , 111 bytes

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

Pruébalo en línea!

Jörg Hülsermann
fuente
2
La matrícula debe ser una cadena, no una matriz. Pero no necesitas el modificador.
Titus
@Titus arreglado !!
Jörg Hülsermann
You can suppose the case will always be the same in both the word list and the three consonants.- No es necesario el modificador regex. ¿Has probado en wordwraplugar de join(str_split())?
Titus
@Titus buena idea
Jörg Hülsermann
5

Jalea ,  12 11  10 bytes

ŒPċðÐfLÞḣ1

Un programa completo que acepta una lista de listas de caracteres en minúscula (las palabras) y una lista de caracteres en minúscula (las letras) e imprime la primera de las palabras más cortas que contienen una subsecuencia igual a las letras (o nada si no existe) )

Pruébalo en línea!

¿Cómo?

Œ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
fuente
1
Si entiendo su explicación correctamente, esto rechazaría una palabra como "borracho" para una secuencia de consonantes de "brc", porque "brc" no es una subcadena de "brrc"
Leo
@Leo ah, sí, buena captura, creo que fallaría ...
Jonathan Allan
@Leo: bueno, está arreglado (los controles "existen en" para todo el conjunto de potencia de cada palabra), pero es posible que no se juegue completamente ...
Jonathan Allan
5

Pyth - 22 21 19 12 11 bytes

h+f/yTQlDEk

-1 Gracias a Maltysen.

Toma 2 líneas como entrada. El primero es la cadena de 3 letras (minúsculas), y el segundo es una lista de palabras en minúsculas.

Pruébalo aquí

Explicación:

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)

Antigua solución de 19 bytes:

h+olNf/-T"aeiou"QEk                       
Maria
fuente
@JonathanAllan: ¡Solucionado! Gracias por señalar eso.
Maria
1
@ JonathanAllan: Parece que editó la pregunta para aclarar que debería devolver una cadena vacía en ese caso. He editado mi respuesta en consecuencia.
Maria
1
Tenemos una clasificación por operador meta en D, así que se puede sustituir OLN con DA
Maltysen
5

Brachylog v2, 11 bytes

tlᵒ∋.&h⊆.∨Ẹ

Pruébalo en línea!

Presentación de funciones. (El enlace TIO tiene un argumento de línea de comandos para ejecutar una función como si fuera un programa completo).

Explicación

Solo una traducción directa de la especificación de nuevo ...

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

En realidad, casi puede responder con h⊆.&t∋: intercambiar el orden de evaluación significa que Brachylog elegirá la respuesta más corta de forma predeterminada (como la primera restricción que ve , que tiene el "más corto" más conveniente como un desempate predeterminado), pero en ese caso, Brachylog's lamentablemente, el algoritmo de evaluación entraría en un bucle infinito si la respuesta no se encuentra realmente Entonces, casi la mitad de la respuesta está dedicada a manejar el caso de que no haya una respuesta adecuada. Incluso entonces, la lᵒanulación del desempate (que técnicamente es una especie, haciendo uso deEl desempate predeterminado de elementos preferidos más cerca del comienzo de la lista) es de solo dos bytes; los otros tres provienen de la necesidad de generar una cadena vacía específicamente cuando no se encuentra la salida, a diferencia del valor de centinela "sin soluciones" predeterminado de Brachylog (porque el final .sería implícito si no tuviéramos que seguirlo ).

Curiosamente, hay una característica que se implementó previamente en Brachylog que habría guardado un byte aquí. En un momento dado, se puede extraer elementos de entrada utilizando el argumento ?₁, ?₂etc. sintaxis; eso le permitiría reorganizar el programa tlᵒ∋.⊇?₁∨Ẹ, que solo tiene 10 bytes. Desafortunadamente, la implementación que se usó en realidad no funcionó (y causó la interrupción de muchos programas que funcionaban), por lo que se revirtió. Sin embargo, puede pensar que el programa tiene una longitud "conceptual" de 10 bytes.

ais523
fuente
4

Haskell 129 129 125 74 bytes

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

CRÉDITO a @nimi

Davide Spataro
fuente
1
Puede reemplazar el más a la derecha mapy el filtercon una lista de comprensión. Como ya tiene Data.Listalcance, puede usar sortOn lengthy elegir la cabeza para encontrar el elemento con una longitud mínima. Finalmente, haga yuna función infija. Todo esto hace fy ksuperflua: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0.
nimi
¡tienes razón! ¡Acabo de empezar a jugar al golf! ¡Gracias!
Davide Spataro
1
Uno más: si se cambia a la importación Data.Lists, se puede utilizar argminen lugar de sortOny salvar al !!0: l#w=argmin length[...]. Data.Liststiene muchas funciones agradables
nimi
3

Perl, 53 bytes

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

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

Esto aprovecha el hecho de que las listas interpoladas en el m//operador utilizan la $"variable que cambia la cadena de entrada inicial psra la p.*s.*rque luego se compara para cada palabra adicional y se ordena length.

Pruébalo en línea!

Dom Hastings
fuente
Si inserto "adsd" en su lista, su programa no puede encontrarlo. El primer carácter que se encuentra no necesita ser el primero en la palabra.
Charlie
@CarlosAlejo La entrada necesita una nueva línea final, funciona bien entonces: ¡ Pruébelo en línea! . Sin embargo, eso me tomó por sorpresa, ya que el <<<operador agrega eso para mí en la línea de comando.
Dom Hastings
3

JavaScript (ES6), 77 75 72 bytes

Toma las 3 consonantes cy la lista de palabras len sintaxis curry (c)(l). Ambas entradas se esperan en el mismo caso.

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

Casos de prueba

Arnauld
fuente
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))para 72, creo
LarsW
@LarsW De hecho, gracias! Sin embargo, he elegido otro enfoque para cumplir con la nueva regla: o una cadena vacía si ninguna palabra coincide con el patrón de tres consonantes .
Arnauld
3

R, 101 bytes

Primera vez jugando al golf! Estoy seguro de que esto se puede condensar de alguna manera

Toma la cadena xy un vector de caracteres y de posibles entradas

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

Pruébalo en línea!

Editar: Mi versión era 135, ¡gracias Scrooble por el -34!

Castigado
fuente
1
Bienvenido a PPCG! Esto parece un fragmento donde la entrada está en variables codificadas. Las respuestas deben ser programas completos o funciones invocables. Puede echar un vistazo a esto (u otras respuestas R) para posibles métodos de E / S.
Martin Ender
2

Retina , 58 bytes

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

Pruébalo en línea! Toma las tres consonantes en una línea y luego la lista de palabras en todas las líneas posteriores. Explicación: Oordena la lista ¶.+excluyendo la primera línea #numéricamente $tecleada por $.&longitud. Luego se busca una coincidencia para una línea que incluye las tres consonantes en orden. Si existe una línea adecuada que la última, es decir, la más corta, dicha línea se convierte en la salida, de lo contrario la salida está vacía. El ?-s:temporalmente desactiva el efecto de s`modo que solo una línea coincida.

Neil
fuente
1
No puedo decidir si son tres ombligos o tres senos.
Charlie
@CarlosAlejo ¿Estás pensando en Eccentrica Gallumbits por casualidad?
Neil
Estaba pensando en el extraterrestre de Total Recall, pero Eccentrica también podría ser una opción ... :)
Charlie
2
@CarlosAlejo Aparentemente Mary es un homenaje a Eccentrica Gallumbits.
Neil
1

Pip , 17 bytes

@:qJ`.*`N_FI#_SKg

Toma la lista de palabras como argumentos de línea de comandos y las consonantes de stdin. Pruébalo en línea!

Explicación

                   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
fuente
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 gracias a @Nevay .

Explicación:

Pruébalo en línea.

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
fuente
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)

Pruébalo en línea!

Uriel
fuente
0

MATL , 28 27 26 bytes

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

Pruébalo en línea!

x- Implícitamente tome la primera entrada (cadena con tres letras) y elimínela. Se copia en el portapapeles G, nivel 1 automáticamente (esta parte se inspiró en la respuesta de @Luis Mendo ).

" - Implícitamente tome la segunda entrada (conjunto de palabras de la celda), repítala.

l - Presione 1 para usarlo más tarde

1G - Empuje la primera entrada (diga 'psr')

@g - Empuje la palabra actual como matriz

3XN- nchoosek- Obtenga todas las combinaciones de 3 letras de la palabra

Xm- Vea si el código de placa 'psr' es una de estas combinaciones. Devuelve 0 para falso y 1 para verdadero.

/- Dividiendo el 1 (que empujamos antes) por este resultado. Cambia los 0 a Infs

@gn - Obtener la longitud de la palabra actual

*- Multiplica la longitud por el resultado de la división. Devuelve la longitud tal como está cuando la palabra contiene los 3 caracteres; de lo contrario, devuelveInf

v - concatenar verticalmente estos resultados en una sola matriz

] - lazo cerrado

&X< - obtener el índice del valor mínimo de esa matriz, es decir, el índice donde se encontró la palabra que contiene las letras y con una longitud mínima

2G - Presione la segunda entrada nuevamente

w - Vuelva a colocar el índice mínimo en la parte superior de la pila

) - Indice en una matriz de palabras con el índice mínimo, devolviendo la palabra válida con una longitud mínima

(Salida implícita).


Más viejo:

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

x"@g1Gy3XNXm1w/wn*v]2Gw2$S1)
sundar - Restablecer a Monica
fuente