Imprima un valor específico en esta matriz binaria generada

14

Supongamos que definimos una matriz infinita M, en N^2 -> {0, 1}(donde Ncomienza en 1lugar de 0) de esta manera:

  • M(1, 1)= 0.

  • Para cada x > 1, M(x, 1)= 1si xes primo, y de lo 0contrario.

  • Para cada y > 1, M(1, y)= el ytérmino th en el Thue-Morse sequence.

  • Por cada x, y > 1, M(x, y)= M(x, y-1) + M(x-1, y) mod 2.

La 16x16sección superior izquierda de esta matriz se ve (con xser filas y ycolumnas):

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 xy ycomo entrada, en cualquier forma que elija, y devolverá M(x, y), que será 0o 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 8192x8192cuadro superior izquierdo en un período de tiempo razonable.

El programa que evalúa correctamente la mayor cantidad de entradas en el 8192 x 8192cuadro superior izquierdo será el ganador, con un código más corto que actúa como un desempate.

Joe Z.
fuente
Probablemente voy a actualizar el caso de prueba a algo un poco más elegante en un momento, así que espere hasta que vuelva a editar la pregunta.
Joe Z.
@mbuettner Sí, lo hace.
Joe Z.
1
No veo cómo necesitamos una nueva etiqueta para "precisión". Esto es solo un [desafío de código]. Primero ejecute nuevas ideas de género de desafío a través del meta (hay una cosa que aprendimos de [code-trolling]).
Pomo de la puerta
^ Notado. Quitaré esa etiqueta.
Joe Z.
1
@TheDoctor No es muy raro. La respuesta aceptada cambia con el tiempo.
Joe Z.

Respuestas:

9

J - 42 38 char

Bastante rápido, 100% preciso y dentro de las limitaciones de memoria.

([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:

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:

(                                 )&<:  NB. decrement each of x and y
     &(                        )        NB. apply the following function...
   +                                    NB. ... (x-1)+(y-1) times...
                                0:      NB. ... starting with a zero:
    2             ~:/\                  NB.   pairwise XOR on the argument
                      ,(p:>:)&#         NB.   append prime bit (is 1+length prime?)
       ~:/@#:@#@],                      NB.   prepend TM bit (XOR of binary)
 [{                                     NB. take the x-th bit (at index x-1)

El uso de este verbo es x m ypara M (x, y) como se especifica en la pregunta, ¿dónde mestá el verbo?

   5 ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<: 8
0
   m =: ([{+2&(~:/@#:@#@],~:/\,(p:>:)&#)0:)&<:
   1+i.16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   m/~ 1+i.16
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

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 8192todavía funciona en menos de 0.07 sy alrededor de 100 KiB en mi modesta computadora portátil.

Algoritmo de tiburón
fuente
6

Mathematica - 100% de precisión, 223 193 189 bytes

f=(r=Array[0&,Max@##];For[s=2,s<=#+#2,++s,For[i=Max[1,s-#2],i<=Min[s-1,#],++i,j=s-i;r[[j]]=Which[i==1,PrimeQ@j,j==1,OddQ@Total@IntegerDigits[i-1,2],0<1,Xor@@r[[j-1;;j]]]]];If[r[[#2]],1,0])&

Aquí hay una versión legible:

f[x_,y_] := (
   r = Array[0 &, Max[x,y]];
   For[s = 2, s <= x + y, ++s,
    For[
     i = Max[1, s - y],
     i <= Min[s - 1, x],
     ++i,

     j = s - i;
     r[[j]] = Which[
       i == 1,
       PrimeQ@j,
       j == 1,
       OddQ@Total@IntegerDigits[i - 1, 2],
       0 < 1,
       r[[j - 1]]~Xor~r[[j]]
       ]
     ]
    ];
   If[r[[y]], 1, 0]
   );

Básicamente precalculo a lo largo de diagonales de constante x+y .

caracteristicas:

  • Es exacto.
  • Se ejecuta en O(x*y).
  • f[8192,8192]Toma alrededor de 400 segundos. Supongo que hay margen de mejora (tal vez RotateLeftpodrí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:

    MemoryConstrained[f[8192, 8192], 2^21]
    
Martin Ender
fuente
Bueno, parece que lo tienes. Sin embargo, haré los más difíciles en el futuro: P
Joe Z.
Hm, en uno de los cambios debo haber estropeado el rendimiento del tiempo de ejecución. El ciclo interno todavía se llama 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 es O(1)eso sería muy útil! :) (bueno, PrimeQy Total@IntegerDigitsno lo son, pero los he tenido allí desde el principio, y solo llamaron O(y)y las O(x)horas respectivamente)
Martin Ender
3

Matlab: 100% de precisión, 120 caracteres, tiempo de ejecución irrazonable

function z=M(x,y)
if y==1 z=(x>1)*isprime(x);elseif x==1 z=mod(sum(dec2bin(y-1)-48),2);else z=xor(M(x,y-1),M(x-1,y));end

Usar:

> M(4,4)
ans =
      0
> M(1, 9)
ans =
      1
intx13
fuente
1
Ahora aquí está la pregunta, ¿puedes ejecutar este programa y probarlo?
Joe Z.
Si no puedes correr M(8192, 8192), no puedo soportarlo.
Joe Z.
@JoeZ Es un código M, puede ejecutarlo en Matlab u Octave.
intx13
@JoeZ Calculará con precisión M (8192, 8192). El desafío no dijo nada sobre el tiempo para completar;)
intx13
1
@JoeZ bueno, parece que M (20,20) lleva más tiempo del que estoy dispuesto a esperar. Pero bueno, ¡es "exacto"! : P
intx13
2

Python, 192 caracteres

100% de precisión, calcula M (8192,8192) en ~ 10 segundos en mi máquina.

R=range
def M(X,Y):
 X+=1;c=[1]*X;r=[0]
 while len(r)<Y:r+=[i^1 for i in r]
 for i in R(2,X):
  if c[i]:
   for j in R(i+i,X,i):c[j]=0
  r[0]=c[i]
  for i in R(1,Y):r[i]^=r[i-1]
 return r[Y-1]
Aleksi Torhamo
fuente
0

Haskell - 261 bytes - 100% - 1MB - No creo que termine pronto

Toma alrededor de 10 segundos para m 16 16con -O2, pero como lo he escrito de todos modos, puedo mostrarlo a pesar de este problema:

m x y=if n x y then 1 else 0 where n x 1=b x;n 1 y=(a!!13)!!(y-1);n x y=(n x (y-1))`f`(n(x-1)y)
f True False=True
f False True=True
f _ _=False
a=[False]:map step a where step a=a++map not a
b x=x`elem`takeWhile(<=x)e
e=c [2..]where c(p:s)=p:c[x|x<-s,x`mod`p>0]

¿Quizás algún buen Haskeller puede optimizarlo?

m' x y = if m x y then 1 else 0
    where
        m x 1 = isPrime x
        m 1 y = morse' y
        m x y = (m x (y-1)) `xor` (m (x-1) y)

xor True False = True
xor False True = True
xor _ _ = False

morse' x = (morse !! 13) !! (x-1)
morse = [False] : map step morse where step a = a ++ map not a

isPrime x = x `elem` takeWhile (<=x) primes
primes :: [Integer]
primes = sieve [2..] where sieve (p:xs) = p : sieve [x|x <- xs, x `mod` p > 0]

main = putStrLn $ show $ m' 16 16
TimWolla
fuente
Creo que el algoritmo en sí es defectuoso. de todos modos, hay muchas cosas que puedes hacer para jugar golf. en su mayoría paréntesis adicionales, pero también f p|p=not|0<1=iddebería ser mejor. Además, intente usar morse = False : concat $ iterate [True] (\a -> a ++ map not a)para aumentar la pereza. Me pregunto cómo afectará el rendimiento.
orgulloso Haskeller
También, se puede jugar golf Truea 0<1y Falsea 0>1.
orgulloso Haskeller
0

Perl, 137

No para 'ganar' :-), pero como todavía no hay Perl aquí y el código se escribió de todos modos, aquí está.

sub f{($n,$m)=@_;@a=0;@a=(@a,map{0+!$_}@a)while@a<$n;for$k(2..$m){$p=0;O:{$k%$_?1:last O for 2..sqrt$k;$p=1}$p=$a[$_]^=$p for 1..$n-1}$p}

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:

sub f{
    ($n,$m)=@_;
    @a=0;                                  # @a will be current line.
    @a=(@a,map{0+!$_}@a)while@a<$n;        # Fill it with Thue-Morse sequence.
    for$k(2..$m){                          # Repeat until required line number.
        $p=0;                              # Find out if current line number 
        O:{                                # is a prime.
            $k%$_?1:last O for 2..sqrt$k;
            $p=1                           # Store result (0 or 1) in $p.
        }
        $p=$a[$_]^=$p for 1..$n-1          # XOR previous value in current position
    }                                      # with $p and store in $p.
    $p                                     # Return $p.
}
usuario2846289
fuente
0

Haskell, 223

g n=div(filter(>=n)(iterate(*2)1)!!0)2
1%1=0>1
1%n=not$1%(n-g n)
n%1=and[rem n x>0|x<-[2..n-1]]
a%b=g[0<1]where g s|foldr seq(0>1)s=0<1|n==a+b=s!!(b-1)|0<1=g$n%1:zipWith x s(tail s)++[1%n]where n=length s+1
x p|p=not|0<1=id

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 -O3y el |foldr seq(0>1)s=0<1guardia, 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 :-).

orgulloso Haskeller
fuente