Movimientos individuales
El tablero es una cuadrícula cuadrada infinita de 2 dimensiones, como un tablero de ajedrez ilimitado. Una pieza con valor N (un N-mover ) puede moverse a cualquier cuadrado que esté a una distancia exactamente de la raíz cuadrada de N desde su cuadrado actual (distancia euclidiana medida de centro a centro).
Por ejemplo:
- Un 1-mover puede moverse a cualquier casilla que esté adyacente horizontal o verticalmente
- Un motor de 2 movimientos puede moverse a cualquier casilla que esté diagonalmente adyacente
- Un jugador de 5 movimientos se mueve como un caballero de ajedrez
Tenga en cuenta que no todos los N-motores pueden moverse. Un jugador de 3 movimientos nunca puede abandonar su casilla actual porque ninguna de las casillas del tablero está a una distancia exactamente de la raíz 3 de la casilla actual.
Movimientos múltiples
Si se les permite moverse repetidamente, algunas piezas pueden alcanzar cualquier casilla en el tablero. Por ejemplo, un motor 1 y un motor 5 pueden hacer esto. Un motor de 2 movimientos solo puede moverse en diagonal y solo puede alcanzar la mitad de los cuadrados. Una pieza que no puede moverse, como un 3-mover, no puede alcanzar ninguno de los cuadrados (el cuadrado inicial no se cuenta como "alcanzado" si no se produce ningún movimiento) .
Las imágenes muestran qué cuadrados se pueden alcanzar. Más detalles sobre el vuelo estacionario. Haga clic para ampliar la imagen.
- Los cuadrados accesibles en 1 o más movimientos están marcados en negro
- Los cuadrados accesibles en exactamente 1 movimiento se muestran con piezas rojas
(aparte del 3-mover, que no puede moverse)
¿Qué proporción del tablero puede alcanzar un determinado N-mover?
Entrada
- Un entero positivo N
Salida
- La proporción de la placa que puede alcanzar un N-mover
- Este es un número del 0 al 1 (ambos incluidos)
- Para este desafío, se permite la salida como fracción en términos más bajos, como 1/4,
Entonces, para la entrada 10
, ambas 1/2
y 0.5
son salidas aceptables. La salida como numerador y denominador separados también es aceptable, ya que incluye idiomas que no admiten flotantes ni fracciones. Por ejemplo, 1 2
o [1, 2]
.
Para las salidas enteras (0 y 1), cualquiera de los siguientes son formatos aceptables:
- Para 0:
0
,0.0
,0/1
,0 1
,[0, 1]
- para 1:
1
,1.0
,1/1
,1 1
,[1, 1]
Puntuación
Este es el código de golf. La puntuación es la longitud del código en bytes. Para cada idioma, gana el código más corto.
Casos de prueba
En el formato input : output as fraction : output as decimal
1 : 1 : 1
2 : 1/2 : 0.5
3 : 0 : 0
4 : 1/4 : 0.25
5 : 1 : 1
6 : 0 : 0
7 : 0 : 0
8 : 1/8 : 0.125
9 : 1/9 : 0.1111111111111111111111111111
10 : 1/2 : 0.5
13 : 1 : 1
16 : 1/16 : 0.0625
18 : 1/18 : 0.05555555555555555555555555556
20 : 1/4 : 0.25
25 : 1 : 1
26 : 1/2 : 0.5
64 : 1/64 : 0.015625
65 : 1 : 1
72 : 1/72 : 0.01388888888888888888888888889
73 : 1 : 1
74 : 1/2 : 0.5
80 : 1/16 : 0.0625
81 : 1/81 : 0.01234567901234567901234567901
82 : 1/2 : 0.5
144 : 1/144 : 0.006944444444444444444444444444
145 : 1 : 1
146 : 1/2 : 0.5
148 : 1/4 : 0.25
153 : 1/9 : 0.1111111111111111111111111111
160 : 1/32 : 0.03125
161 : 0 : 0
162 : 1/162 : 0.006172839506172839506172839506
163 : 0 : 0
164 : 1/4 : 0.25
241 : 1 : 1
242 : 1/242 : 0.004132231404958677685950413223
244 : 1/4 : 0.25
245 : 1/49 : 0.02040816326530612244897959184
260 : 1/4 : 0.25
261 : 1/9 : 0.1111111111111111111111111111
288 : 1/288 : 0.003472222222222222222222222222
290 : 1/2 : 0.5
292 : 1/4 : 0.25
293 : 1 : 1
324 : 1/324 : 0.003086419753086419753086419753
325 : 1 : 1
326 : 0 : 0
360 : 1/72 : 0.01388888888888888888888888889
361 : 1/361 : 0.002770083102493074792243767313
362 : 1/2 : 0.5
369 : 1/9 : 0.1111111111111111111111111111
370 : 1/2 : 0.5
449 : 1 : 1
450 : 1/18 : 0.05555555555555555555555555556
488 : 1/8 : 0.125
489 : 0 : 0
490 : 1/98 : 0.01020408163265306122448979592
520 : 1/8 : 0.125
521 : 1 : 1
522 : 1/18 : 0.05555555555555555555555555556
544 : 1/32 : 0.03125
548 : 1/4 : 0.25
549 : 1/9 : 0.1111111111111111111111111111
584 : 1/8 : 0.125
585 : 1/9 : 0.1111111111111111111111111111
586 : 1/2 : 0.5
592 : 1/16 : 0.0625
593 : 1 : 1
596 : 1/4 : 0.25
605 : 1/121 : 0.008264462809917355371900826446
610 : 1/2 : 0.5
611 : 0 : 0
612 : 1/36 : 0.02777777777777777777777777778
613 : 1 : 1
624 : 0 : 0
625 : 1 : 1
fuente
Respuestas:
JavaScript (Node.js) ,
144138125747370 bytesPruébalo en línea!
-4 byte gracias @Arnauld!
Enfoque original, 125 bytes
Pruébalo en línea!
Inspirado en el video Pi escondido en las principales regularidades de 3Blue1Brown.
Para cada factor primo en la factorización del número, calcule :pn f(pn)
Multiplica todos los valores de las funciones, ahí estamos.
Actualizar
Gracias al esfuerzo de los colaboradores de Math.SE, el algoritmo ahora está respaldado por una prueba
fuente
Mathematica, 80 bytes
Este código depende principalmente de un teorema matemático. La idea básica es que el código solicita la densidad de una red dada un conjunto generador.
Más precisamente, se nos da una colección de vectores, es decir, aquellos cuya longitud al cuadrado es N, y se nos pide que calculen la densidad del conjunto de posibles sumas de estos vectores, en comparación con todos los vectores enteros. La matemática en juego es que siempre podemos encontrar dos vectores (y sus opuestos) que "generan" (es decir, cuyas sumas son) el mismo conjunto que la colección original. LatticeReduce hace exactamente eso.
Si tiene solo dos vectores, puede imaginarse dibujando un paralelogramo idéntico centrado en cada punto alcanzable, pero cuyas longitudes de borde son los vectores dados, de modo que el plano esté completamente en mosaico por estos paralelogramos. (Imagine, por ejemplo, una red de formas de "diamante" para n = 2). El área de cada paralelogramo es el determinante de los dos vectores generadores. La proporción deseada del plano es el recíproco de esta área, ya que cada paralelogramo tiene solo un punto alcanzable.
El código es una implementación bastante sencilla: genera los vectores, usa LatticeReduce, toma el determinante, luego toma el recíproco. (Sin embargo, probablemente se pueda jugar mejor al golf)
fuente
d@n_:=Boole[#!={}]/Det@LatticeReduce@#&@Select[Range[-n,n]~Tuples~2,#.#==n&]
Limpias ,
189185172171 bytesPruébalo en línea!
Encuentra cada posición accesible en el
n
cuadrado de la longitud del lado arrinconado en el origen en el primer cuadrante, luego se dividen^2
para obtener la porción de todas las celdas alcanzables.Esto funciona porque:
n
cuadrado de longitud lateral, cada una arrinconada en un punto accesible desde el origen como si fuera el origen.++ +- -+ --
, lo que permite que el mosaico superpuesto se extienda a través de los otros tres cuadrantes mediante reflejo y rotación.fuente
Retina 0.8.2 ,
12682 bytesPruébalo en línea! El enlace incluye casos de prueba. Explicación:
Convierte a unario.
Divide repetidamente por factores primos de la forma
4k+1
.Si el resultado no es un cuadrado ni dos veces un cuadrado, entonces el resultado es cero.
Calcule el recíproco como una fracción decimal.
fuente
Regex (ECMAScript, fuera recíproco),
256163157948382 bytes-93 bytes gracias a Neil
-6 bytes gracias nuevamente a Neil
-63 bytes haciendo la división sin capturar el divisor
-11 bytes gracias a la división simultánea opcional de Grimy- byte de raíz cuadrada y
-1 byte moviendo la condición de finalización y la captura de valor de retorno en el bucle como una segunda alternativa, gracias a Grimy
Utiliza las mismas matemáticas que la respuesta de JavaScript de Shieru Asakoto .
La entrada está en unario. Dado que una expresión regular pura solo puede devolver como salida una subcadena de la entrada (es decir, un número natural menor o igual a la entrada), o "sin coincidencia", esta expresión regular devuelve el recíproco de la proporción de la placa que un N-mover puedo alcanzar. Como el recíproco de 0 es infinito, en ese caso devuelve "no match".
ADVERTENCIA DE SPOILER : Para la raíz cuadrada, esta expresión regular utiliza una variante del algoritmo de multiplicación generalizado, que no es obvio y podría ser un rompecabezas gratificante para resolver por su cuenta. Para obtener más información, consulte una explicación de esta forma del algoritmo en Buscar un número Rocco .
Esta expresión regular primero entra en un ciclo que identifica todos los factores primos tales que , y divide el número de entrada por cada uno tantas veces como sea posible. Sea el resultado final de esto. Entonces, indirectamente a prueba para ver si la factorización prima de (y por tanto también el número de entrada) incluye cualquier primos elevado a una potencia impar, mediante el ensayo para ver si o es un cuadrado perfecto. Si no, entonces sí incluyó una prima tan elevada a una potencia extraña, y la expresión regular devuelve "no coincidencia"; de lo contrario, devuelve .p p≡1 (mod 4) m m ≡3 (mod 4) m m/2 m m
(Ahora es un poco más complicado que eso. Debido a la optimización de golf en la versión recíproca-producto, que pone a prueba no sólo y por ser un cuadrado, pero también el resultado intermedio antes de la división de cada , si el la primera prueba falla. Esto no cambia el resultado final, porque si la primera prueba cuadrada perfecta falla, al menos una potencia impar de un primo todavía estará presente en el número en cada paso, y no puede ser un cuadrado.)m m/2 p ≡3 (mod 4)
^(?=((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5|((xx?)(\8*))(?=(\7*)\9+$)\7*$\10)+$)\1
Pruébalo en línea!
Pruébalo en línea! (solo los casos de prueba)
Expresiones regulares (ECMAScript + (? *), Recíproco de salida),
207138132bytesObsoleado haciendo división sin capturar el divisor (es decir, ahora es idéntico al anterior).
Regex (ECMAScript 2018, salida recíproca),
212140134bytesObsoleado haciendo división sin capturar el divisor (es decir, ahora es idéntico al anterior).
Regex (ECMAScript, salida de fracción), 80 bytes
En esta versión, el numerador se devuelve en
\10
(cero si no está configurado / NPCG) y el denominador en\7
.A diferencia de la versión de salida recíproca:
La gran desventaja de una especificación de salida como esta es que no está contenida en el programa en sí.
((?=(x+)(?!(\2+)(\2\3)+$)((\2{4})+$))\5)*((((x)x?)(\9*))(?=(\8*)\11+$)\8*$\12|x)
Pruébalo en línea!
Pruébalo en línea! (solo los casos de prueba)
fuente
(((xx?)(\9*))(?=(\8*)\10+$)\8*$\11)
para verificar si N o N / 2 es un cuadrado.Jalea ,
2524 bytesUn enlace monádico que usa la ruta del factor primo.
Pruébalo en línea!
¿Cómo?
Los 25 anteriores fueron:
Programa completo forzador bruto
; posiblementeun código más largoque la ruta del factor primo (podría intentarlo más tarde).Pruébalo en línea!
Comienza creando movimientos individuales como coordenadas y luego se mueve repetidamente desde todas las ubicaciones alcanzadas acumulando los resultados, tomando el módulo
n
de cada coordenada (para restringir a unn
porn
cuadrante) y manteniendo aquellos que son distintos hasta que se alcanza un punto fijo; entonces finalmente divide la cuenta porn^2
fuente
05AB1E ,
272625 bytesPuerto de la respuesta de JavaScript de @ShieruAsakoto , ¡así que asegúrese de votarlo también!
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
fuente
APL (Dyalog Extended) , 21 bytes
Este programa usa la ruta del factor primo. Estoy en deuda con Adám, dzaima, H.PWiz, J.Sallé y ngn. APL Orchard es un excelente lugar para aprender APL y siempre están dispuestos a ayudar
Pruébalo en línea!
Ungolfing
La parte 2 de este código es la misma que en la versión de Dyalog Unicode a continuación, por lo que en esta explicación, me centraré en
⍭*1≠4|⍭
APL (Dyalog Unicode) ,
41403635 bytes SBCSEste programa usa la ruta del factor primo. Aprendí algunos trucos mientras escribía esto y estoy profundamente en deuda con Adám, dzaima, H.PWiz, J.Sallé y ngn. El APL Orchard es un gran lugar para aprender APL y siempre están dispuestos a ayudar (o esta publicación nunca hubiera despegado :)
Editar: -1 byte de ngn. -2 bytes de Adám y -2 más de ngn. -1 byte de ngn.
Pruébalo en línea!
Ungolfing
Este es un programa en dos partes:
fuente