Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Suppose we define an infinite matrix M, on N^2 -> {0, 1} (where N starts from 1 instead of 0) in this manner:

  • M(1, 1) = 0.

  • For every x > 1, M(x, 1) = 1 if x is prime, and 0 otherwise.

  • For every y > 1, M(1, y) = the yth term in the Thue-Morse sequence.

  • For every x, y > 1, M(x, y) = M(x, y-1) + M(x-1, y) mod 2.

The top-left 16x16 section of this matrix looks like (with x being rows and y being columns):

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

Your task is to build a program that will evaluate the value of an arbitrary entry in this matrix as accurately as possible.

Your program will take two integers x and y as input, in any form you choose, and return M(x, y), which will be either 0 or 1.

Your code may be written in any language, but must not exceed 64 kilobytes (65,536 bytes) of source code size or 2 MB (2,097,152 bytes) of total memory usage. Your program must start with empty memory (i.e. it cannot load data from somewhere else) and run independently for each input (that is, it may not store common data for multiple runs). Your program must also be able to evaluate all the entries in the top-left 8192x8192 square in a reasonable amount of time.

The program that evaluates the most entries correctly in the top-left 8192 x 8192 square will be the winner, with shorter code acting as a tie-breaker.

share|improve this question
    
I'm probably going to update the testing case to something slightly more elegant in a moment, so hang on with the testing until I edit the question again. –  Joe Z. Mar 19 at 21:25
    
So your example output has x increasing downward and y increasing to the right? –  Martin Büttner Mar 19 at 21:26
    
@mbuettner Yes, it does. –  Joe Z. Mar 19 at 21:27
    
I fail to see how we need a new tag for "accuracy." This is just a [code-challenge]. Please run new challenge genre ideas through meta first (there's one thing we learned from [code-trolling]). –  Doorknob Mar 19 at 21:31
1  
@TheDoctor It's not too uncommon. The accepted answer changes over time. –  Joe Z. Mar 19 at 23:47

6 Answers 6

up vote 7 down vote accepted

J - 42 char

Pretty fast, 100% accurate, and well within the memory constraints.

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

The strategy is as follows: we will calculate successive antidiagonals of this matrix, performing a pairwise XOR to move along and adding the current Thue-Morse and prime bits to the ends. We then pull the required digit out of the antidiagonal when we get there.

Explanation by explosion:

(                                     )&<: NB. subtract 1 from each of x and y
       (                         ^:)       NB. execute the following procedure...
   ]`                               @+     NB. ... (x-1)+(y-1) times...
    `0:                                    NB. ... starting with a row of just 0
                 2&(~:/\)                  NB.   pairwise XOR on the previous row
                         ,1 p:1+#          NB.   append prime bit (is 1+length prime?)
        ~:/@#:@#,                          NB.   prepend TM bit (XOR of binary expansion)
 [{                                        NB. take the x-th element in the row

Usage of this verb is x m y for M(x, y) as specified in the question, where m is the verb.

   5 ([{]`0:(~:/@#:@#,2&(~:/\),1 p:1+#^:)@+)&<: 8
1
   m =: ([{]`0:(~:/@#:@#,2&(~:/\),1 p:1+#^:)@+)&<:  NB. naming for convenience
   1+i.16  NB. the integers from 1 to 16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
   m/~ 1+i.16  NB. make a table over 1..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

To save keystrokes we don't try to tell if we still need more prime or Thue-Morse bits, so we compute the entire antidiagonal of the matrix: that's a lot of wasted computation. However, 8192 m 8192 still runs in less than 0.15 s on my modest laptop, using approx. 100 KB.

share|improve this answer

Mathematica – 100% accuracy, 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])&

Here is a legible version:

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

I basically precompute along diagonals of constant x+y.

Features:

  • It's accurate.
  • It runs in O(x*y).
  • f[8192,8192] takes about 400 seconds. I suppose there is room for improvement (maybe RotateLeft could replace the inner loop).
  • It only uses one array of up to max(x,y) intermediate results in memory. So there is no necessity to use more than about 32k (assuming 32-bit integers) for the algorithm itself (plus, whatever Mathematica uses). In fact, Mathematica uses 31M by itself on my system, but this works without an issue:

    MemoryConstrained[f[8192, 8192], 2^21]
    
share|improve this answer
    
Well, looks like you got it. I'll be making harder ones in the future, though :P –  Joe Z. Mar 19 at 23:09
    
@JoeZ. I just golfed it down a bit. But there might be solutions using the same approach and less characters, so you might have to change the accepted answer at some point. ;) ... Also I think I can halve the memory requirement, because I wouldn't actually override any values before I have to use them (so I don't need fresh arrays). –  Martin Büttner Mar 19 at 23:14
    
I don't mind changing accepted answers. I do that all the time. –  Joe Z. Mar 19 at 23:15
    
@JoeZ. unaccepting my answer right now might get you more submissions though. It can be a little off-putting if the "winner" is already selected. Btw, I did change the code to use only a single array now. So there are exactly max(x,y) integers for intermediate results in memory (plus my 5 temporary variables). –  Martin Büttner Mar 19 at 23:38
1  
Alright, I'll wait a few days before accepting your answer again. –  Joe Z. Mar 19 at 23:44

Matlab: 100% accuracy, 120 characters, unreasonable execution time

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

To use:

> M(4,4)
ans =
      0
> M(1, 9)
ans =
      1
share|improve this answer
1  
Now here's the question, can you actually run this program and test it? –  Joe Z. Mar 19 at 22:14
    
If you can't run M(8192, 8192), I can't take it. –  Joe Z. Mar 19 at 22:17
    
@JoeZ It's M-code, you can run it in Matlab or Octave. –  intx13 Mar 19 at 22:17
    
@JoeZ It will accurately compute M(8192, 8192). The challenge didn't say anything about time to complete ;) –  intx13 Mar 19 at 22:18
1  
@JoeZ well it looks like M(20,20) takes longer than I'm willing to wait. But hey, it's "accurate"! :P –  intx13 Mar 19 at 22:21

Python, 192 characters

100% accuracy, calculates M(8192,8192) in ~10 seconds on my machine.

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]
share|improve this answer

Haskell - 261 bytes - 100% - 1MB - I don't think it is going to end anytime soon

Takes about 10 seconds for m 16 16 with -O2, but as I have written it anyway I can show it despite this problem:

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]

Maybe some good Haskeller is able to optimize it?

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
share|improve this answer

Perl, 137

Not to 'win' :-), but since there's no Perl here yet and code was written anyway, here it is.

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}

Takes several seconds if called print f(8192,8192), stores single line of matrix in memory (array of 8192 integers (scalars)), about 3.5 Mb whole Perl process. I tried to do it with string instead of array (either with regexps or accessing with substr), takes less memory and can be golfed further, but runs much slower.

Indented:

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.
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.