Załóżmy, że definiujemy macierz nieskończoną Mna N^2 -> {0, 1}(gdzie Nzaczyna się 1zamiast 0) w następujący sposób:

• M(1, 1)= 0.

• Dla każdego x > 1, M(x, 1)= 1jeśli xjest pierwsza, a 0inaczej.

• Dla każdego y > 1, M(1, y)= yth termin w Thue-Morse sequence.

• Dla każdego x, y > 1, M(x, y)= M(x, y-1) + M(x-1, y) mod 2.

16x16Wygląda górna lewa sekcja tej macierzy (z xwierszami i ykolumnami):

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

Twoim zadaniem jest zbudowanie programu, który oszacuje wartość dowolnego wpisu w tej macierzy tak dokładnie, jak to możliwe.

Twój program weźmie dwie liczby całkowite xi yjako dane wejściowe, w dowolnej formie, którą wybierzesz, i zwróci M(x, y), która będzie albo 0albo 1.

Kod może być napisany w dowolnym języku, ale nie może przekraczać 64 kilobajtów (65 536 bajtów) rozmiaru kodu źródłowego lub 2 MB (2097152 bajtów) całkowitego zużycia pamięci. Twój program musi uruchomić się z pustą pamięcią (tzn. Nie może załadować danych z innego miejsca) i działać niezależnie dla każdego wejścia (tzn. Nie może przechowywać wspólnych danych dla wielu uruchomień). Twój program musi także być w stanie ocenić wszystkie wpisy w lewym górnym rogu 8192x8192w rozsądnym czasie.

Zwycięzcą zostanie program, który poprawnie oceni najwięcej wpisów w lewym górnym 8192 x 8192kwadracie, a krótszy kod będzie działał jako rozstrzygający.

J - 42 38 znaków

Dość szybki, 100% dokładny i dobrze w granicach pamięci.

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

Strategia jest następująca: będziemy obliczać kolejne antydiagonale tej macierzy, wykonując parą XOR, aby się poruszać i dodając bieżące Thue-Morse'a i bity pierwsze na końcach. Kiedy tam dotrzemy, wyciągamy wymaganą cyfrę z antyiagonalnej.

Wyjaśnienie przez wybuch:

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

Użycie tego czasownika dotyczy x m yM (x, y), jak określono w pytaniu, gdzie mjest czasownik.

   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

Aby zapisać naciśnięcia klawiszy, nie staramy się stwierdzić, czy nadal potrzebujemy więcej bitów prime lub Thue-Morse, więc obliczamy cały antypoślizgowy, aby uzyskać żądany bit. Jednak 8192 m 8192nadal działa na mniej niż 0,07 si około 100 KiB na moim skromnym laptopie.

Mathematica - 100% dokładności, 223 193 189 bajtów

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

Oto czytelna wersja:

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

Zasadniczo obliczam wstępnie wzdłuż przekątnych stałej x+y .

Cechy:

• To jest dokładne.
• Wbiega O(x*y).
• f[8192,8192]zajmuje około 400 sekund. Przypuszczam, że jest miejsce na ulepszenia (być może RotateLeftmoże zastąpić wewnętrzną pętlę).

• W max(x,y)pamięci wykorzystuje tylko jedną tablicę wyników do pośrednich. Dlatego nie ma potrzeby używania więcej niż około 32k (przy założeniu 32-bitowych liczb całkowitych) dla samego algorytmu (plus, cokolwiek Mathematica używa). W rzeczywistości Mathematica sama używa 31M w moim systemie, ale działa to bez problemu:

  MemoryConstrained[f[8192, 8192], 2^21]
  

Matlab: 100% dokładności, 120 znaków, nieuzasadniony czas wykonania

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

Używać:

> M(4,4)
ans =
      0
> M(1, 9)
ans =
      1

Python, 192 znaki

100% dokładności, oblicza M (8192,8192) w ~ 10 sekund na mojej maszynie.

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]

Haskell - 261 bajtów - 100% - 1 MB - Nie sądzę, że wkrótce się skończy

Trwa około 10 sekund, m 16 16z -O2, ale jak pisałem to i tak mogę pokazać to pomimo tego problemu:

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]

Może jakiś dobry Haskeller jest w stanie go zoptymalizować?

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

Perl, 137

Nie po to, żeby „wygrać” :-), ale ponieważ nie ma tu jeszcze Perla i kod został napisany, oto jest.

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}

Wywołanie zajmuje kilka sekund print f(8192,8192), przechowuje pojedynczą linię macierzy w pamięci (tablica liczb całkowitych 8192 (skalarów)), około 3,5 Mb całego procesu Perla. Próbowałem to zrobić za pomocą łańcucha zamiast tablicy (albo z wyrażeniami regularnymi, albo z dostępem do podłoża), zajmuje mniej pamięci i można grać w golfa dalej, ale działa znacznie wolniej.

Zębaty:

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

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

ma to krótki czas działania (5,7 sekundy z -O3). pamięć nie została jeszcze sprawdzona, choć powinna być liniowa.

wykorzystuje to algorytm diagonalny widoczny tutaj wcześniej.

jeśli chodzi o prędkość, jedyne, co się liczy, to algorytm diagonalny -O3i |foldr seq(0>1)s=0<1osłona, która czyni listę ścisłą. wszystko inne jest implementowane raczej nieefektywnie - sprawdzanie liczby pierwotnej odbywa się poprzez sprawdzenie wszystkich mniejszych liczb do podziału, elementy sekwencji Morse'a są stale przeliczane. ale wciąż jest wystarczająco szybki :-).