Este es un desafío de policías y ladrones . El hilo de los policías a este desafío está aquí
Una pregunta interesante para pensar es la siguiente:
Si tengo una secuencia de números, ¿cuántos de ellos debo proporcionar antes de que quede claro de qué secuencia estoy hablando?
Por ejemplo, si quiero hablar sobre los enteros positivos en orden a partir de , podría decir , pero ¿es realmente suficiente?1 , 2 , 3 , ...
Tengo una forma de responder a esta pregunta, y ser un jugador de código implica el golf de código. Ha proporcionado suficientes términos de una secuencia si el código más corto que produce esos términos produce todos los términos de la secuencia. Si pensamos en esto en términos de código de golf, esto significaría que ha proporcionado suficientes casos de prueba para que el código más corto que pasa los casos de prueba haga la tarea deseada.
Desafío
Este desafío es un desafío de policías y ladrones . En el cual los policías presentarán casos de prueba y los ladrones tendrán que encontrar una forma más corta de falsificar los casos de prueba que no sea la secuencia prevista. Los policías presentarán lo siguiente:
Una pieza de código que toma un entero positivo como entrada y produce un entero como salida. Este código puede ser cero o uno indexado, pero debe quedar claro cuál es la indexación. Este código definirá su secuencia.
Cualquier plataforma relevante o requisitos de idioma que puedan afectar a la salida, por ejemplo, el tamaño de longint.
Un número , junto con los primeros términos de la secuencia calculados por el código. Estos actuarán como "casos de prueba".n
Los ladrones encontrarán un programa en el mismo lenguaje que es más corto que el presentado y pasa todos los casos de prueba (produce la misma salida para las primeras entradas que el código del policía). El código del ladrón también debe diferir en la salida del programa del policía para un número mayor que .n
Puntuación
Los ladrones serán puntuados en la cantidad de grietas que encuentren, con más grietas mejorando. Una respuesta se puede descifrar nuevamente al encontrar una respuesta válida más corta que la grieta original. Si una respuesta se descifra por segunda vez, el punto se otorga a la segunda galleta en lugar de a la primera.
fuente
Respuestas:
cQuents , la respuesta de Stephen , 3 bytes
Pruébalo en línea!
Cómo funciona
Parece que las secuencias deberían ser idénticas, pero esto da
12345678910
porn = 10
mientras"::$
da1234567891
.fuente
JavaScript, la respuesta de fəˈnɛtɪk (17 bytes)
Bueno, fue fácil codificar para obtener una puntuación mucho más baja ... Difiere de la implementación de referencia para cualquier entrada , 0 indexada. Esto utiliza un truco de golf JS muy conocido: la indexación en una secuencia con un número entero que excede los límites de la misma devuelve un valor falso ( ), por lo que simplemente se puede forzar a un valor predeterminado mediante el uso de OR lógico ( ), en este caso , manejando el último término de la secuencia pero también los que siguen.x ≥ 6
undefined
||
22
Pruebas
Alternativamente, ¡ pruébelo en línea!
fuente
Haskell , la respuesta de Laikoni , 15 bytes
Pruébalo en línea!
Por lo general, señalaría algo como esto en un comentario, pero luego pensé que los policías y los ladrones son un poco más feroces.
Esta es solo la respuesta de BMO menos el caso especial para
b 42
. Debido a que el original de Laikoni pasa por punto flotante, no es necesario: solo encuentre un número lo suficientemente grande como para dar errores de redondeo en eso, pero no en laInteger
aritmética exacta . Por ejemplo:fuente
Python 2 , la respuesta de xnor , 43 bytes
Pruébalo en línea!
Créditos
Una gran parte del crédito por este crack debe ir a @ Mr.Xcoder, quien primero publicó un comentario sobre un posible ataque con este método, y a @PoonLevi, que encontró una solución de 44 bytes.
¿Cómo?
Teoría
En particular, para :a = 2
Entonces, existe algún número entero positivo tal que:k
Lo que lleva a:
2 p - 1 = 2 k p + 1 2 p - 1 ≡ 1
Esta última fórmula es de la que se deriva el código Python y ahora se mantiene para , a pesar de que no es relativamente primo consigo mismo.2p = 2 2
Ahora, para la parte más importante: lo contrario del pequeño teorema de Fermat no es cierto. Podemos tener para algún número compuesto . Dichos números se llaman pseudoprimos de Fermat para basar . Los pseudoprimos de Fermat a la base 2 también se conocen como números de Poulet .n aunn - 1≡ 1( modn ) norte un
El primer pseudoprimo de Fermat a base (o primer número de Poulet) es , para lo cual tenemos:n = 341 = 11 × 312 n = 341 = 11 × 31
2 341 - 1 ≡ 1
Esto significa que nuestro algoritmo va a devolver en lugar de la esperada 69 º primer .347341 347
Implementación
@PoonLevi encontró la siguiente solución de 44 bytes, que se basa directamente en :( 2 )
Al usar en1 21- 1 ≡ 0( mod1 )
<2
lugar de==1
, guardamos 1 byte pero introducimos en la secuencia, porque :2 1 - 1 ≡ 0Pruébalo en línea!
Al comenzar con , obtenemos los términos esperados en 1 porque hacemos una iteración menos:p = 2
Pruébalo en línea!
El último truco es usar en
n<1or
lugar den and
. Esto es igual de largo pero hace que la última iteración devuelva True en lugar de 0 , por lo tanto, agrega el desplazamiento que falta a cada término.fuente
Python 3 , crashoz , 45 bytes
Pruébalo en línea!
x*60-x**3*10+x**5/2-x**7/84
fuente
JavaScript (ES6), la respuesta de Arnauld (10 bytes)
Pruébalo en línea!
fuente
Haskell , la respuesta de Laikoni ,
2622 bytes-4 bytes al no usar infijo
div
, ¡gracias a Laikoni !Pruébalo en línea!
Explicación
ceiling(realToFrac n/2)
div(n+1)2
fuente
((n+1)`div`2)
->div(n+1)2
.> <> , respuesta de crashoz 203 bytes
Pruébalo en línea!
Iba a hacer algo inteligente con el hecho de que los números pares / impares anteriores
n=20
eran los mismos, excepto por un elemento repetido en el centro, pero era más fácil codificar cada elemento.La entrada es a través de la
-v
bandera. No imprime nada para elementos superiores a 34.fuente
Pascal (FPC) , la respuesta de AlexRacer , 80 bytes
Pruébalo en línea!
Esta parece una respuesta tardía, pero de todos modos gracias @AlexRacer por un buen rompecabezas.
fuente
JavaScript, la respuesta de fəˈnɛtɪk (12 bytes)
Pruebas
Alternativamente, ¡ pruébelo en línea!
fuente
JavaScript, la respuesta de fəˈnɛtɪk (17 bytes)
x=>Math.exp(x)|1
Pruebas
Alternativamente, ¡ pruébelo en línea!
fuente
Husk , descifrando 5 bytes de BMO con
32 bytes-1 gracias a BMO (
LdΣ
->LΣ
ya que, cuando se le da unTnum
,L
realiza la "representación de la longitud de la cadena")Pruébalo en línea!
LΣ
←d+16
fuente
L
yLd
son equivalentes ahorro que un byte;)L
anulación como "representación de longitud de cadena"Tnum
.> <> , Respuesta de Aiden F. Pierce , 36 bytes
Pruébalo en línea!
Otra solución con cada valor codificado por línea. Como la respuesta original también estaba en su mayoría codificada, no me siento demasiado culpable por esto.
fuente
JavaScript, la respuesta de fəˈnɛtɪk , 23 bytes
Pruébalo en línea!
¿Cómo?
La expresión se
`${73211e9}`
expande a la cadena"73211000000000"
, proporcionando una tabla de búsqueda de 14 valores que se restan de 14, lo que da la secuencia esperada.21 bytes
NaN
Pruébalo en línea!
fuente