Supongamos que definimos una matriz infinita M
, en N^2 -> {0, 1}
(donde N
comienza en 1
lugar de 0
) de esta manera:
M(1, 1)
=0
.Para cada
x > 1
,M(x, 1)
=1
six
es primo, y de lo0
contrario.Para cada
y > 1
,M(1, y)
= ely
término th en elThue-Morse sequence
.Por cada
x, y > 1
,M(x, y)
=M(x, y-1) + M(x-1, y) mod 2
.
La 16x16
sección superior izquierda de esta matriz se ve (con x
ser filas y y
columnas):
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
1 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 1 0 0 0 0 1 0 0 1 0
0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1
1 0 1 1 0 0 1 0 1 0 1 1 1 1 0 1
0 0 1 0 0 0 1 1 0 0 1 0 1 0 0 1
1 1 0 0 0 0 1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 1
0 1 0 1 0 1 1 1 1 1 0 0 0 0 0 1
0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 0
1 0 1 1 1 0 0 1 1 0 1 0 1 0 1 1
0 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0
0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1
0 1 0 1 1 1 0 0 0 1 1 0 1 1 0 1
0 1 1 0 1 0 0 0 0 1 0 0 1 0 0 1
Su tarea es crear un programa que evalúe el valor de una entrada arbitraria en esta matriz con la mayor precisión posible.
Su programa tomará dos enteros x
y y
como entrada, en cualquier forma que elija, y devolverá M(x, y)
, que será 0
o 1
.
Su código puede estar escrito en cualquier idioma, pero no debe exceder los 64 kilobytes (65,536 bytes) de tamaño de código fuente o 2 MB (2,097,152 bytes) de uso total de memoria. Su programa debe comenzar con memoria vacía (es decir, no puede cargar datos desde otro lugar) y ejecutarse independientemente para cada entrada (es decir, puede que no almacene datos comunes para múltiples ejecuciones). Su programa también debe poder evaluar todas las entradas en el 8192x8192
cuadro superior izquierdo en un período de tiempo razonable.
El programa que evalúa correctamente la mayor cantidad de entradas en el 8192 x 8192
cuadro superior izquierdo será el ganador, con un código más corto que actúa como un desempate.
fuente
Respuestas:
J -
4238 charBastante rápido, 100% preciso y dentro de las limitaciones de memoria.
La estrategia es la siguiente: calcularemos sucesivas antidiagonales de esta matriz, realizando un XOR por pares para avanzar y agregando los bits Thue-Morse y primo actuales a los extremos. Luego sacamos el dígito requerido del antidiagonal cuando llegamos allí.
Explicación por explosión:
El uso de este verbo es
x m y
para M (x, y) como se especifica en la pregunta, ¿dóndem
está el verbo?Para guardar las pulsaciones de teclado, no intentamos saber si aún necesitamos más bits primos o Thue-Morse, por lo que calculamos todo el antidiagonal para obtener el bit que queremos. Sin embargo,
8192 m 8192
todavía funciona en menos de 0.07 sy alrededor de 100 KiB en mi modesta computadora portátil.fuente
Mathematica - 100% de precisión,
223193189 bytesAquí hay una versión legible:
Básicamente precalculo a lo largo de diagonales de constante
x+y
.caracteristicas:
O(x*y)
.f[8192,8192]
Toma alrededor de 400 segundos. Supongo que hay margen de mejora (tal vezRotateLeft
podría reemplazar el bucle interno).Solo usa una matriz de resultados hasta
max(x,y)
intermedios en la memoria. Por lo tanto, no hay necesidad de usar más de aproximadamente 32k (suponiendo enteros de 32 bits) para el algoritmo en sí mismo (además, lo que sea que use Mathematica). De hecho, Mathematica usa 31M por sí mismo en mi sistema, pero esto funciona sin problemas:fuente
O(x*y)
tiempos, pero el tiempo total de ejecución aumenta más rápido que eso. No estoy muy seguro de lo que está pasando. Si algún Mathematica Guru pudiera iluminarme, ¡qué operación en el ciclo no esO(1)
eso sería muy útil! :) (bueno,PrimeQ
yTotal@IntegerDigits
no lo son, pero los he tenido allí desde el principio, y solo llamaronO(y)
y lasO(x)
horas respectivamente)Matlab: 100% de precisión, 120 caracteres, tiempo de ejecución irrazonable
Usar:
fuente
M(8192, 8192)
, no puedo soportarlo.Python, 192 caracteres
100% de precisión, calcula M (8192,8192) en ~ 10 segundos en mi máquina.
fuente
Haskell - 261 bytes - 100% - 1MB - No creo que termine pronto
Toma alrededor de 10 segundos para
m 16 16
con-O2
, pero como lo he escrito de todos modos, puedo mostrarlo a pesar de este problema:¿Quizás algún buen Haskeller puede optimizarlo?
fuente
f p|p=not|0<1=id
debería ser mejor. Además, intente usarmorse = False : concat $ iterate [True] (\a -> a ++ map not a)
para aumentar la pereza. Me pregunto cómo afectará el rendimiento.True
a0<1
yFalse
a0>1
.Perl, 137
No para 'ganar' :-), pero como todavía no hay Perl aquí y el código se escribió de todos modos, aquí está.
Toma varios segundos si se llama
print f(8192,8192)
, almacena una sola línea de matriz en la memoria (matriz de enteros 8192 (escalares)), aproximadamente 3.5 Mb de proceso completo de Perl. Intenté hacerlo con una cadena en lugar de una matriz (ya sea con expresiones regulares o accediendo con substr), requiere menos memoria y se puede jugar más, pero corre mucho más lento.Sangrado:
fuente
Haskell, 223
esto tiene un tiempo de ejecución rápido (5,7 segundos con
-O3
). la memoria aún no se verificó, aunque debería ser lineal.esto usa el algoritmo diagonal visto aquí antes.
En lo que respecta a la velocidad, lo único que importa es el algoritmo diagonal
-O3
y el|foldr seq(0>1)s=0<1
guardia, lo que hace que la lista sea estricta. todo lo demás se implementa de manera bastante ineficiente: la verificación primaria se realiza al verificar todos los números menores para la división, los elementos de la secuencia Morse se recalculan constantemente. pero todavía es lo suficientemente rápido :-).fuente