Imprimir um valor específico nesta matriz binária gerada

14

Suponha que definamos uma matriz infinita M, on N^2 -> {0, 1}(de onde Ncomeça em 1vez de 0) desta maneira:

  • M(1, 1)= 0.

  • Para todo x > 1, M(x, 1)= 1se xé primo e 0caso contrário.

  • Para todos y > 1, M(1, y)= o yth termo no Thue-Morse sequence.

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

A 16x16seção superior esquerda desta matriz se parece (com xlinhas e ycolunas):

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

Sua tarefa é criar um programa que avalie o valor de uma entrada arbitrária nessa matriz com a maior precisão possível.

Seu programa terá dois números inteiros xe, ycomo entrada, em qualquer forma que você escolher, e retornará M(x, y), que será um 0ou 1.

Seu código pode ser escrito em qualquer idioma, mas não deve exceder 64 kilobytes (65.536 bytes) de tamanho de código-fonte ou 2 MB (2.097.152 bytes) de uso total de memória. Seu programa deve iniciar com memória vazia (ou seja, não pode carregar dados de outro lugar) e executar independentemente para cada entrada (ou seja, pode não armazenar dados comuns para várias execuções). Seu programa também deve poder avaliar todas as entradas no 8192x8192quadrado superior esquerdo em um período de tempo razoável.

O programa que avaliar mais entradas corretamente no 8192 x 8192quadrado superior esquerdo será o vencedor, com um código mais curto atuando como desempate.

Joe Z.
fonte
Provavelmente vou atualizar o caso de teste para algo um pouco mais elegante em um momento, então continue com o teste até editar a pergunta novamente.
Joe Z.
@mbuettner Sim, é verdade.
Joe Z.
1
Não vejo como precisamos de uma nova tag para "precisão". Este é apenas um [desafio de código]. Por favor, execute novas idéias de gênero de desafio através da meta primeiro (há uma coisa que aprendemos com [trollagem de código]).
Maçaneta
^ Notável. Vou remover essa etiqueta.
Joe Z.
1
@TheDoctor Não é muito incomum. A resposta aceita muda com o tempo.
Joe Z.

Respostas:

9

J - 42 38 char

Muito rápido, 100% preciso e dentro das restrições de memória.

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

A estratégia é a seguinte: calcularemos antidiagonais sucessivos dessa matriz, executando um XOR em pares para avançar e adicionando os atuais bits Thue-Morse e primos às extremidades. Em seguida, puxamos o dígito necessário para fora do antidiagonal quando chegamos lá.

Explicação por explosão:

(                                 )&<:  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)

O uso desse verbo é x m ypara M (x, y), conforme especificado na pergunta, onde mestá o 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 salvar as teclas digitadas, não tentamos dizer se ainda precisamos de mais bits primos ou Thue-Morse, portanto calculamos todo o antidiagonal para obter o bit que queremos. No entanto, 8192 m 8192ainda é executado em menos de 0,07 se cerca de 100 KiB no meu laptop modesto.

algoritmshark
fonte
6

Mathematica - 100% de precisão, 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])&

Aqui está uma versão legível:

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]
   );

Basicamente pré-calculo ao longo de diagonais de constante x+y.

Recursos:

  • É preciso.
  • É executado O(x*y).
  • f[8192,8192]leva cerca de 400 segundos. Suponho que haja espaço para melhorias (talvez RotateLeftpossa substituir o loop interno).
  • Ele usa apenas uma matriz de até max(x,y)resultados intermediários na memória. Portanto, não há necessidade de usar mais do que cerca de 32k (assumindo números inteiros de 32 bits) para o próprio algoritmo (além disso, o que quer que o Mathematica use). De fato, o Mathematica usa o 31M por si só no meu sistema, mas isso funciona sem problemas:

    MemoryConstrained[f[8192, 8192], 2^21]
    
Martin Ender
fonte
Bem, parece que você entendeu. No entanto, vou fazer as mais difíceis: P
Joe Z.
Hum, em uma das mudanças eu devo ter estragado o desempenho do tempo de execução. O loop interno ainda é chamado de O(x*y)tempos, mas o tempo total de execução aumenta mais rápido que isso. Não tenho muita certeza do que está acontecendo. Se algum Mathematica Guru pudesse me esclarecer, qual operação no loop não O(1)seria muito útil! :) (bem, PrimeQe Total@IntegerDigitsnão o são, mas eu tive-los lá desde o início, e eles só chamada O(y)e O(x)vezes, respectivamente)
Martin Ender
3

Matlab: 100% de precisão, 120 caracteres, tempo de execução não razoável

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
fonte
1
Agora, aqui está a pergunta: você pode realmente executar este programa e testá-lo?
Joe Z.
Se você não pode correr M(8192, 8192), eu não aguento.
Joe Z.
@ JoeO É o código M, você pode executá-lo no Matlab ou no Octave.
Intx13
@JoeZ Ele calculará com precisão M (8192, 8192). O desafio não disse nada sobre a hora de concluir;) #
intx13
1
@JoeZ bem, parece que M (20,20) leva mais tempo do que estou disposto a esperar. Mas ei, é "preciso"! : P
intx13
2

Python, 192 caracteres

100% de precisão, calcula M (8192,8192) em ~ 10 segundos na minha 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
fonte
0

Haskell - 261 bytes - 100% - 1MB - Acho que não vai acabar tão cedo

Leva cerca de 10 segundos para m 16 16com -O2, mas como eu ter escrito isso de qualquer maneira eu posso mostrar que apesar 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]

Talvez algum bom Haskeller seja capaz de otimizá-lo?

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
fonte
Eu acho que o algoritmo em si é falho. de qualquer forma, há muitas coisas que você pode fazer para jogar isso. principalmente parênteses extras, mas também f p|p=not|0<1=iddeve ser melhor. Além disso, tente usar morse = False : concat $ iterate [True] (\a -> a ++ map not a)para aumentar a preguiça. Eu me pergunto como isso afetará o desempenho.
haskeller orgulhoso
Além disso, você pode golfe Truepara 0<1e Falsepara 0>1.
haskeller orgulhoso
0

Perl, 137

Não para 'vencer' :-), mas como ainda não há Perl aqui e o código foi escrito de qualquer maneira, aqui 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}

Leva alguns segundos, se chamado print f(8192,8192), armazena uma única linha de matriz na memória (matriz de 8192 números inteiros (escalares)), cerca de 3,5 Mb de processo Perl inteiro. Tentei fazê-lo com string em vez de array (com regexps ou acessando com substr), consome menos memória e pode ser jogado mais, mas corre muito mais devagar.

Recuado:

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.
}
user2846289
fonte
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

isso tem tempo de execução rápido (5,7 segundos com -O3). a memória ainda não foi verificada, embora deva ser linear.

isso usa o algoritmo diagonal visto aqui antes.

No que diz respeito à velocidade, as únicas coisas que importam são o algoritmo diagonal -O3, e o |foldr seq(0>1)s=0<1guarda, o que torna a lista rígida. tudo o mais é implementado de maneira ineficiente - a verificação primária é feita verificando todos os números menores de divisão, os elementos da sequência Morse são recalculados constantemente. mas ainda é rápido o suficiente :-).

orgulhoso haskeller
fonte