Una regla estándar de longitud n tiene marcas de distancia en las posiciones 0, 1, ..., n (en cualquiera de las unidades). Una regla escasa tiene un subconjunto de esas marcas. Una regla puede medir la distancia k si tiene marcas en las posiciones p y q con p - q = k .
El reto
Dado un número entero positivo n , genera el número mínimo de marcas requeridas en una regla dispersa de longitud n para que pueda medir todas las distancias 1, 2, ..., n .
Este es OEIS A046693 .
Como ejemplo, para la entrada 6, la salida es 4. A saber, una regla con marcas en 0, 1, 4, 6 funciona, como 1−0 = 1, 6−4 = 2, 4−1 = 3, 4−0 = 4, 6−1 = 5 y 6−0 = 6.
Reglas adicionales
- El algoritmo debe ser válido para n arbitrariamente grande . Sin embargo, es aceptable si el programa está limitado por restricciones de memoria, tiempo o tipo de datos.
- La entrada / salida se puede tomar / producir por cualquier medio razonable .
- Se permiten programas o funciones , en cualquier lenguaje de programación . Las lagunas estándar están prohibidas.
- El código más corto en bytes gana.
Casos de prueba
1 -> 2
2 -> 3
3 -> 3
4 -> 4
5 -> 4
6 -> 4
7 -> 5
8 -> 5
9 -> 5
10 -> 6
11 -> 6
12 -> 6
13 -> 6
14 -> 7
15 -> 7
16 -> 7
17 -> 7
18 -> 8
19 -> 8
20 -> 8
21 -> 8
22 -> 8
23 -> 8
24 -> 9
25 -> 9
26 -> 9
27 -> 9
28 -> 9
29 -> 9
30 -> 10
31 -> 10
32 -> 10
Respuestas:
Jalea , 14 bytes
Un enlace monádico que toma y devuelve enteros no negativos.
Pruébalo en línea! (primeros 15 valores aquí - no eficiente)
¿Cómo?
Encuentra todas las reglas que uno podría hacer usando las marcas 1 a n + 1 (el conjunto de potencia de [1, n + 1]) ordenadas por su recuento de marcas, y mantiene solo aquellas que crean distancias máximas medibles (la longitud de conjunto de diferencias entre todos los pares de marcas ordenadas), luego devuelve la longitud de la primera (es decir, [una de] la más corta [s]).
fuente
Wolfram Language (Mathematica) , 65 bytes
Pruébalo en línea!
fuente
Mathematica, 84 bytes
Pruébalo en línea!
fuente
Pyth , 14 bytes
Pruébalo aquí!
Pyth ,
2119 bytesPruébalo aquí!
Cómo funciona
Actualizaré esto después de jugar al golf.
¡Gracias a isaacg por guardar un byte para mi segundo enfoque e inspirarme a jugar golf a 3 bytes de mi enfoque actual!
fuente
S
es innecesario.Python 2 ,
129128126 bytesgracias a totalmente humano por -1 byte
Pruébalo en línea!
la salida es a través del código de salida
fuente
Casco ,
2018 bytes¡Gracias @ H.PWiz por -2 bytes!
Pruébalo en línea!
Explicación
fuente
oa-
es lo mismo que≠
≈
.Jalea , 17 bytes
Pruébalo en línea!
¡Salvado 1 byte gracias a Jonathan Allan !
fuente
ḢL
debería estar bien ..Pyth, 15 bytes
Banco de pruebas
Cómo funciona
fuente
Jalea , 17 bytes
Pruébalo en línea!
Tomó prestado un truco de la respuesta del Sr. Xcoder para -1.
-1 gracias a Jonathan Allan .
fuente
ḢL
debería estar bien ..Ruby , 98 bytes
Pruébalo en línea!
fuente