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 '14 at 21:25
    
@mbuettner Yes, it does. –  Joe Z. Mar 19 '14 at 21:27
1  
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 '14 at 21:31
    
^ Noted. I'll remove that tag. –  Joe Z. Mar 19 '14 at 21:34
1  
@TheDoctor It's not too uncommon. The accepted answer changes over time. –  Joe Z. Mar 19 '14 at 23:47

7 Answers 7

up vote 8 down vote accepted

J - 42 38 char

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

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

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

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

   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

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 to get the bit we want. However, 8192 m 8192 still runs in less than 0.07 s and about 100 KiB on my modest laptop.

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 '14 at 23:09
    
I don't mind changing accepted answers. I do that all the time. –  Joe Z. Mar 19 '14 at 23:15
1  
Alright, I'll wait a few days before accepting your answer again. –  Joe Z. Mar 19 '14 at 23:44
    
Hm, in one of the changes I must have screwed up the runtime performance. The inner loop is still called O(x*y) times, but the total execution time increases faster than that. I'm not quite sure what's happening. If some Mathematica Guru could enlighten me, which operation in the loop is not O(1) that would be very helpful! :) (well, PrimeQ and Total@IntegerDigits aren't, but I've had them in there from the beginning, and they only called O(y) and O(x) times respectively) –  Martin Büttner Mar 20 '14 at 0:01

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 '14 at 22:14
    
If you can't run M(8192, 8192), I can't take it. –  Joe Z. Mar 19 '14 at 22:17
    
@JoeZ It's M-code, you can run it in Matlab or Octave. –  intx13 Mar 19 '14 at 22:17
    
@JoeZ It will accurately compute M(8192, 8192). The challenge didn't say anything about time to complete ;) –  intx13 Mar 19 '14 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 '14 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
    
i think the algorithm itself is flawed. anyway, there are many things you can do to golf this. mostly extra parentheses , but also f p|p=not|0<1=id should be better. also, try using morse = False : concat $ iterate [True] (\a -> a ++ map not a) for increased laziness. I wonder how it will affect performance. –  proud haskeller Jan 1 at 22:15
    
also, you can golf True to 0<1 and False to 0>1. –  proud haskeller Jan 1 at 22:15

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

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

this has fast runtime (5.7 seconds with -O3). memory wasn't checked yet, though it should be linear.

this uses the diagonal algorithm seen here before.

as far as speed is concerned, the only things that matter are the diagonal algorithm, -O3 , and the |foldr seq(0>1)s=0<1 guard, which makes the list strict. everything else is implemented rather inefficiently - prime checking is done by checking all the lesser numbers for division, the Morse sequence's elements are recomputed constantly. but it is still fast enough :-).

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.