Todos los cuadrados que coinciden con una secuencia de comodines [cerrado]

9

Esto fue inspirado por parte de la competencia ARML 2016 Equipo Problema # 6.

Aquí está el desafío:

Te dan una "secuencia comodín", que es una secuencia de dígitos y otro carácter. Una cadena coincide con esta secuencia comodín mediante el siguiente pseudocódigo:

w = wildcard
s = string
# s matches w iff
for all 0 >= i > wildcard.length, w[i] == '?' or s[i] == w[i]

Dónde '?' es un personaje de tu elección.

En términos de expresiones regulares, solo imagínense el '?'ser '.'.

El desafío es encontrar todos los números cuadrados (el requisito es de hasta 1 millón) cuyas representaciones de cadenas decimales coinciden con esta secuencia comodín. El "carácter comodín" puede ser cualquier carácter ASCII de su elección, siempre que no sea un dígito, obviamente.

Por ejemplo, 4096partidos 4**6y 4*9*aunque 4114no coincide tampoco.

Entrada

La entrada se dará como una secuencia que coincida con la expresión regular [0-9?]+. Puede ser una cadena, una matriz de caracteres o una matriz de bytes de los caracteres en ASCII.

Salida

La salida será una lista / conjunto / conjunto de números delimitados por lo que desee que sean cuadrados perfectos y coincidan con la secuencia de comodines.

Ejemplos de entradas válidas:

1234567*90
1234567?90
1234567u90
['1', '2', '3', '4', '5', '6', '7', '*', '9', '0']
[49, 50, 51, 52, 53, 54, 55, 42, 57, 48]
[1, 2, 3, 4, 5, 6, 7, '*', 9, 0]

Ejemplos de salidas válidas:

[1, 4, 9]
1 4 9
1, 4, 9
1-4-9

etc.

Especificaciones

  • No puede usar los builtins para encontrar una lista de cuadrados en un cierto rango
  • Se aplican lagunas estándar
  • Debe poder manejar hasta 1 000 000 (1 millón)
  • Si se proporciona con la entrada 1******, es correcto imprimir [1000000]. También es correcto imprimir[1000000, 1002001, 1004004, 1006009, 1008016, 1010025, ...]
  • Las secuencias comodín nunca comenzarán con el carácter comodín; es decir, siempre coincidirán con cadenas de la misma longitud.

Casos de prueba

4**6  ->  [4096, 4356]
1**1  ->  [1521, 1681]
1**  ->  [100, 121, 144, 169, 196]
9****9  ->  [908209, 915849, 927369, 935089, 946729, 954529, 966289, 974169, 986049, 994009]
9*9***  ->  [919681, 929296]
1**0*  ->  [10000, 10201, 10404, 10609, 12100, 14400, 16900, 19600]
9***4  ->  [91204, 94864, 97344]

Victorioso

Envío más corto (válido) (en funcionamiento) antes del 14 de febrero, desempate por el ganador más temprano.

Hiperneutrino
fuente
1
Creo que un buen comienzo para aclarar esto sería especificar que ?será elegido por el respondedor.
FryAmTheEggman
2
¿Por qué es 25una respuesta válida para ***pero no para *2*?
Neil
3
Creo que esto sería más claro si los números nunca tuvieran ceros a la izquierda, por lo que solo coincidían las secuencias de su longitud.
xnor
@Neil Eso sería un problema con mi propia solución. Tomaré la sugerencia de xnor.
HyperNeutrino
¿Puede la entrada ser una matriz de enteros de un dígito y el carácter especial, como {4, "w", "w", 6}(o mejor aún {4, w, w, 6}), en lugar de una matriz de caracteres, como {"4", "w", "w", "6"}?
Greg Martin el

Respuestas:

0

05AB1E , 22 bytes

Probablemente hay mucho margen de mejora aquí.
Cualquier no dígito está bien como comodín.

3°LnvyS¹)ø€Æ0QPyg¹gQ&—

Pruébalo en línea!

Explicación por venir después de más golf.

Emigna
fuente
Esto parece funcionar para todas las entradas. Buen trabajo.
HyperNeutrino
1

Mathematica, 44 bytes

Print@@@IntegerDigits[Range@1*^3^2]~Cases~#&

La entrada es una lista de dígitos con un _(sin comillas) como comodín. p.ej{4, _, _, 6}

Explicación

Range@1*^3

Generar lista {1, 2, 3, ... , 1000}

... ^2

Encuadrelo. (lista de todos los cuadrados del 1 al 1,000,000)

IntegerDigits[ ... ]

Divide cada cuadrado en una lista de dígitos.

... ~Cases~#

Encuentra los que coinciden con el patrón especificado por la entrada.

Print@@@ ...

Imprimirlos.

JungHwan Min
fuente
Esto parece funcionar para todos los casos de prueba. Buen trabajo.
HyperNeutrino
1

Brachylog , 23 bytes

@e:{@$|,}a#0:{c.~^#I,}f

Pruébalo en línea!

Explicación

@e                        Split into a list of characters
  :{@$|,}a                Replace each digit char by the corresponding digit, and each things
                            that are ot digits into variables
          #0              All elements of the resulting list must be digits
            :{       }f   Output is the result of finding all...
              c.            ...concatenations of those digits which...
               .~^#I,       ...result in a number which is the square of an integer #I

Formato de entrada diferente, 13 bytes

Dependiendo de lo que considere válido como entrada, puede hacer esto:

#0:{c.~^#I,}f

Pruébalo en línea!

que es básicamente la segunda parte de la respuesta anterior, con una lista como entrada que contiene dígitos y variables donde están los comodines.

Sin embargo, no considero esto válido porque solo hay 26 nombres de variables en Brachylog (las letras mayúsculas), por lo que esto no funcionaría si tuviera más de 26 wilcards.

Fatalizar
fuente
Esto parece funcionar para todas las entradas. Buen trabajo. Sin embargo, consideraría que esto es de 24 bytes porque se requiere un argumento de 1 byte. Sin embargo, no estoy seguro de cómo funcionaría la puntuación para esto.
HyperNeutrino
1
@AlexL. El argumento solo está ahí para indicar el nombre de la variable de salida (puede usar otra letra mayúscula si lo desea). Esto es similar a las respuestas en Prolog / languages ​​con funciones donde se nombra el predicado / función pero en realidad no cuenta los bytes que usa cuando lo llama.
Fatalize
Bueno. No estoy seguro de si uno debería puntuarlo como 24 ya que el argumento es necesario (de lo contrario, solo regresa true.), pero no he usado idiomas que lo requieran antes. Trataré de encontrar alguna referencia para determinar cómo debo calificar esto, pero tendría sentido calificarlo como 23, así que lo mantendré así.
HyperNeutrino
1

Perl 6 , 30 26 bytes

¡Gracias a @ b2gills por -4 bytes!

{grep /^<$_>$/,map * **2,^1e4}

{grep /^<$_>$/,(^1e4)»²}

Utiliza el punto como carácter comodín, de modo que la entrada puede usarse como una expresión regular:

{                            }   # a lambda
                         ^1e4    # range from 0 to 9999
               map * **2,        # square each value
 grep /      /,                  # filter numbers that match this regex:
        <$_>                     #   lambda argument eval'ed as sub-regex
       ^    $                    #   anchor to beginning and end

Pruébalo en línea .

Una variante que acepte el asterisco como comodín (como sugiere una revisión previa de la descripción de la tarea) sería de 42 bytes:

{grep /^<{.trans("*"=>".")}>$/,(^1e4)»²}
smls
fuente
Reestablecí las reglas y puedes elegir cualquier carácter comodín. Estoy anotando esto como 38 bytes.
HyperNeutrino
¿Cómo usas esto? No sé nada de Perl.
HyperNeutrino
@AlexL .: Gracias, actualicé la respuesta (y también agregué una explicación). Es una lambda; puede llamarlo directamente (p { ... }("9*9***"). ej. ) o asignarlo a una variable / símbolo para su uso posterior. Tenga en cuenta que Perl 6 es un idioma separado de Perl, por lo que no funcionará con un intérprete de Perl.
sonríe el
Solía sudo apt-get install rakudotener un supuesto intérprete de Perl6 ... Cuando pongo perl6un comando en mi terminal, comienza lo que parece ser un intérprete de Perl6, pero no sé cómo usarlo. Sé que es una lambda, pero no sé cómo llamarlo.
HyperNeutrino
@AlexL .: agregué un enlace "Pruébelo en línea" que lo muestra como un script completo que puede ejecutar como perl6 foo.p6. También puedes probarlo en un shell oneliner, comoperl6 -e 'say {grep /^<$_>$/,map * **2,^1e4}( "9.9..." )'
smls
1

Ruby, 54 bytes

Función que toma un argumento de cadena. Pruébalo en línea.

->s{(0..1e3).map{|i|"#{i**2}"[/^#{s.tr ?*,?.}$/]}-[p]}
Tinta de valor
fuente
Puede guardar un byte usando i * i en lugar de i ** 2
GB
Esto no parece funcionar porque el segundo #está haciendo que el resto de la línea sea un comentario.
HyperNeutrino
@AlexL Oh, funciona bien. repl.it/FJCV
Value Ink el
ohhhh bien, simplemente no sabía cómo probar a Ruby. Mis disculpas. Esto parece funcionar para todas las entradas. ¡Buen trabajo!
HyperNeutrino
0

Lote, 109 bytes

@for /l %%i in (0,1,999)do @set/aj=%%i*%%i&call copy nul %%j%%.%%j%%$>nul
@for %%s in (%1.%1$)do @echo %%~ns

Usos ?como comodín. Funciona creando 1000 archivos. El nombre del archivo es el número cuadrado y la extensión del archivo es el número cuadrado con un $sufijo. Esto se debe a que la coincidencia de patrones de Batch cuenta los ?s finales como opcionales, por 1?lo que coincidirá con ambos 1y 16; $Por lo tanto, obliga a que la coincidencia sea exacta. Sin embargo, no queremos generar el $, por lo que solo mostramos el nombre del archivo sin extensión.

Neil
fuente
0

JavaScript (ES6), 68 66 bytes

EDITAR: Actualicé mi solución a continuación después de inspirarme con la respuesta de JungHwan Min . Ahora es compatible con ES6.

Toma entrada en el formato '1..4' donde .está el comodín.

En lugar de iterar a 1e6 y enraizamiento cuadrado, este itera a 1e3 y cuadrados.

p=>[...Array(1e3)].map((_,n)=>''+n*n).filter(n=>n.match(`^${p}$`))

JavaScript (ES7), 71 69 bytes

p=>[...Array(1e6).keys()].filter(n=>n**.5%1?0:(''+n).match(`^${p}$`))

Crea una matriz de números del 0 al 1e6 y luego la filtra por números que son cuadrados y coinciden con el patrón.

Es terriblemente lento porque siempre itera a 1e6.

George Reith
fuente
No creo que **esté funcionando, porque me está dando un "SyntaxError: expected expression, got '*'".
HyperNeutrino
@AlexL. Las reglas parecen haber cambiado. Las reglas anteriores sugerían que podía elegir el carácter comodín.
George Reith el
Solo necesita soportar hasta 1e6...
HyperNeutrino
Además, volví a cambiar las reglas; El problema no es con las reglas, es porque el **operador no existe, al menos no con mi sistema.
HyperNeutrino
@AlexL. Ah lo siento, pensé que te referías a la entrada **. Sí, es ES7. Actualizaré el título. Aquí hay una lista de los navegadores compatibles actualmente developer.mozilla.org/en/docs/Web/JavaScript/Reference/…
George Reith
0

Perl, 42 45 38 bytes

EDITAR: aclaración de Alex, podemos usar el punto como carácter comodín que elimina la operación y //.

perl -pe 's|.*|@{[grep/^$&$/,map$_*$_,1..1e3]}|'

EDITAR: solución que utiliza el asterisco como carácter comodín y espera la secuencia comodín en STDIN

perl -pe 'y/*/./;s|.*|@{[grep/^$&$/,map$_*$_,1..1e3]}|'

Sin duda, esto deja mucho margen de mejora, es bastante sencillo. La expresión comodín se espera como argumento de línea de comando, con el carácter comodín de punto (¿qué más?).

say"@{[grep/^$ARGV[0]$/,map$_*$_,1..1e3]}"
daniel
fuente
La pregunta especifica que los comodines se dan como asteriscos. ¿Una revisión anterior de la pregunta permitió elegir su propio carácter comodín?
sonríe el
1
@smls: la pregunta aún especifica elegir su propio comodín, aunque no se encuentra en la sección de reglas: el carácter utilizado como comodín no necesariamente debe ser un asterisco, puede ser cualquier carácter ASCII de su elección, siempre que no es un dígito, obviamente.
Emigna
Sí, me confundí con eso. Más adelante, dice claramente que el carácter comodín debe ser un asterisco. Supongo que la definición con la expresión regular es líder. Revisaré mi solución.
daniel
1
Hm realidad, la frase citada por @Emigna es bastante claro que podemos elegir nuestro propio carácter comodín, ¿verdad?
sonríe el
Para aclarar, el carácter comodín puede ser lo que quieras. Accidentalmente estropeé las reglas cuando reformulé la explicación.
HyperNeutrino
0

Python 3 - 98 97 bytes

import re;print(re.findall(r"\b"+input()+r"\b",("\n".join([str(x*x) for x in range(1,1001)]))))

Requiere una entrada como '4..6'.

Carra
fuente
Puede guardar 3 bytes usando import rey re.findall; la optimización con el en from...import *realidad no lo optimiza en este caso.
HyperNeutrino
Entrada proporcionada 1...., da 1 4 9y 16 25como respuestas válidas, lo que no es correcto. Por favor corrija su programa.
HyperNeutrino
Arregle el caso uniéndose a "\ n".
Carra
Esto no funciona para 1....... Regresa [], pero debería ceder [1000000]. Esto se puede solucionar a un costo de 0 bytes utilizando en range(0, 1001)lugar de range(0, 1000).
HyperNeutrino
Buen punto, acabo de comprobar todos los casos de prueba de la descripción :)
Carra
0

k - 28 caracteres

{s(&:)($:s:s*s:!1001)like x}

Se utiliza ?como carácter comodín. La likefunción se usa ?como comodín, y esta función hace una lista de los primeros 1001 cuadrados (para incluir 1M), los convierte a todos en cadenas y luego comprueba dónde coinciden con el patrón.

    {s(&:)($:s:s*s:!1001)like x} "1??"
100 121 144 169 196
C. Quilley
fuente
Estoy recibiendo este error para ello: type error {s(&:)($:s:s*s:!1001)like x} "1" at execution instance 2 of ":". ¿Podría proporcionar un enlace a un conjunto de pruebas en funcionamiento o ver si hay un problema?
HyperNeutrino
@AlexL. Funciona para mí en el modo k de kdb +
C. Quilley
Hmm Intentaré probarlo con diferentes intérpretes.
HyperNeutrino
0

bash + utilidades Unix, 33 bytes

dc<<<'0[2^pv1+lax]dsax'|grep ^$1$

Esto usa '.' como el carácter comodín.

El programa de CC imprime los números cuadrados en un bucle infinito:

0     Push 0 on the stack.

[     Start a macro (called a).

2^    Square the number at the top of the stack.

p     Print the number at the top of the stack, followed by a newline.

v     Replace the number at the top of the stack (a square number) with its square root.

1+    Increment the number at the top of the stack.

lax   Run the macro again (looping).

]     End of the macro.

dsax  Store the macro in register a and run it.

La salida de CC se canaliza a grep, que imprime solo los cuadrados que coinciden con el patrón requerido.

Esto funciona cuando lo ejecuto en un sistema Linux o OS X real (pero no funciona en TIO, probablemente porque el programa de CC intenta repetirse para siempre, y sospecho que TIO se queda sin espacio de pila para la recursión y / o tiene un problema con la tubería interminable).

Mitchell Spector
fuente
Estoy ejecutando esto con Linux Mint 17.3 Rosa, y no está terminando. Creo que el problema es con el dccomando interminable .
HyperNeutrino
Sospecho que en realidad es el búfer lo que está causando el problema. No tengo esa versión de Linux, pero podría intentar reemplazar el grep con grep --line-bufffer (para hacer que cada línea se imprima como grep). [Por supuesto, eso agrega una cantidad de bytes.]
Mitchell Spector
Agregué el argumento grep, pero no hace la diferencia. Traté de ponerlo --line-buffereda cada lado de la ^$1$, pero no funciona de ninguna manera.
HyperNeutrino
@ AlexL. Gracias por intentarlo. No sé si la diferencia está en el kernel o en la versión bash que estoy ejecutando. Lo hice funcionar en TIO forzando el final de la entrada de grep usando head, de la siguiente manera: dc <<< '0 [2 ^ pv1 + lax] dsax' | head -1 sed s/./0/g<<<$1| grep ^ $ 1 $ Esto usa la longitud de patrón para limitar los números que se prueban (los patrones de 4 caracteres verifican solo hasta 9999, etc.). Aquí hay un enlace TIO: tio.run/nexus/…
Mitchell Spector
Gracias por la corrección. No creo que la solución actual realmente funcione (aunque no tengo mucho conocimiento de bash), porque parece que necesita calcular todos los valores antes de introducir eso grep. Sin embargo, como actualmente no es la solución más corta, la mantendré en 33 bytes para la puntuación. Parece funcionar para todas las entradas, ¡así que buen trabajo!
HyperNeutrino