Misalkan kita mendefinisikan matriks tak terbatas M, pada N^2 -> {0, 1}(di mana Ndimulai dari 1alih-alih 0) dengan cara ini:

• M(1, 1)= 0.

• Untuk setiap x > 1, M(x, 1)= 1jika xprima, dan 0sebaliknya.

• Untuk setiap y > 1, M(1, y)= yistilah ke dalam Thue-Morse sequence.

• Untuk setiap x, y > 1, M(x, y)= M(x, y-1) + M(x-1, y) mod 2.

Bagian kiri atas 16x16dari matriks ini terlihat (dengan xmenjadi baris dan ykolom):

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

Tugas Anda adalah membangun sebuah program yang akan mengevaluasi nilai entri sewenang-wenang dalam matriks ini seakurat mungkin.

Program Anda akan mengambil dua bilangan bulat xdan ysebagai input, dalam bentuk apa pun yang Anda pilih, dan kembali M(x, y), yang bisa berupa 0atau 1.

Kode Anda dapat ditulis dalam bahasa apa pun, tetapi tidak boleh melebihi 64 kilobyte (65.536 byte) dari ukuran kode sumber atau 2 MB (2.097.152 byte) dari total penggunaan memori. Program Anda harus mulai dengan memori kosong (mis. Itu tidak dapat memuat data dari tempat lain) dan berjalan secara independen untuk setiap input (artinya, ia mungkin tidak menyimpan data umum untuk beberapa kali dijalankan). Program Anda juga harus dapat mengevaluasi semua entri di kotak kiri atas 8192x8192dalam jumlah waktu yang wajar.

Program yang mengevaluasi entri terbanyak dengan benar di kotak kiri atas 8192 x 8192akan menjadi pemenang, dengan kode yang lebih pendek bertindak sebagai tie-breaker.

J - 42 38 char

Cukup cepat, 100% akurat, dan berada dalam batasan memori.

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

Strateginya adalah sebagai berikut: kami akan menghitung antidiagonal berturut-turut dari matriks ini, melakukan XOR berpasangan untuk bergerak bersama dan menambahkan Thue-Morse dan bit prima ke ujungnya. Kami kemudian menarik angka yang diperlukan dari antidiagonal ketika kami sampai di sana.

Penjelasan demi ledakan:

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

Penggunaan kata kerja ini adalah x m yuntuk M (x, y) sebagaimana ditentukan dalam pertanyaan, di mana mkata kerjanya.

   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

Untuk menghemat penekanan tombol, kami tidak mencoba memberi tahu apakah kami masih membutuhkan lebih banyak bit prima atau Thue-Morse, jadi kami menghitung seluruh antidiagonal untuk mendapatkan bit yang kami inginkan. Namun, 8192 m 8192masih berjalan dalam waktu kurang dari 0,07 dan sekitar 100 KiB pada laptop sederhana saya.

Mathematica - Akurasi 100%, 223 193 189 byte

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

Ini adalah versi yang dapat dibaca:

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

Saya pada dasarnya melakukan precompute diagonal konstan x+y.

Fitur:

• Itu akurat.
• Itu berjalan di O(x*y).
• f[8192,8192]membutuhkan sekitar 400 detik. Saya kira ada ruang untuk perbaikan (mungkin RotateLeftbisa menggantikan lingkaran dalam).

• Hanya menggunakan satu larik hingga max(x,y)hasil antara dalam memori. Jadi tidak ada keharusan untuk menggunakan lebih dari sekitar 32k (dengan asumsi bilangan bulat 32-bit) untuk algoritma itu sendiri (plus, apa pun yang digunakan Mathematica). Sebenarnya, Mathematica menggunakan 31M sendiri pada sistem saya, tetapi ini berfungsi tanpa masalah:

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

Matlab: Akurasi 100%, 120 karakter, waktu eksekusi yang tidak masuk akal

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

Menggunakan:

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

Python, 192 karakter

Akurasi 100%, menghitung M (8192.8192) dalam ~ 10 detik pada mesin saya.

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 byte - 100% - 1MB - Saya tidak berpikir ini akan berakhir dalam waktu dekat

Memakan waktu sekitar 10 detik untuk m 16 16dengan -O2, tapi seperti yang saya tulis itu pula aku bisa menunjukkannya meskipun masalah ini:

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]

Mungkin beberapa Haskeller yang baik dapat mengoptimalkannya?

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

Bukan untuk 'menang' :-), tetapi karena belum ada Perl di sini dan kode tetap ditulis, ini dia.

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}

Dibutuhkan beberapa detik jika dipanggil print f(8192,8192), menyimpan satu baris matriks dalam memori (array 8192 integer (skalar)), sekitar 3,5 Mb seluruh proses Perl. Saya mencoba melakukannya dengan string, bukan array (baik dengan regexps atau mengakses dengan substr), membutuhkan lebih sedikit memori dan dapat golf lebih lanjut, tetapi berjalan lebih lambat.

Bertakuk:

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

ini memiliki runtime cepat (5,7 detik dengan -O3). memori belum diperiksa, meskipun itu harus linier.

ini menggunakan algoritma diagonal yang terlihat di sini sebelumnya.

sejauh menyangkut kecepatan, satu-satunya hal yang penting adalah algoritma diagonal -O3,, dan |foldr seq(0>1)s=0<1penjaga, yang membuat daftar menjadi ketat. semuanya diimplementasikan dengan agak tidak efisien - pemeriksaan prima dilakukan dengan memeriksa semua angka yang lebih rendah untuk pembagian, elemen urutan Morse dihitung ulang secara konstan. tapi itu masih cukup cepat :-).