Gibt einen bestimmten Wert in dieser generierten binären Matrix aus

14

Angenommen , wir eine unendliche Matrix definieren M, auf N^2 -> {0, 1}(wobei Nbeginnt ab , 1statt 0) in dieser Art und Weise:

  • M(1, 1)= 0.

  • Für jeden x > 1, M(x, 1)= 1wenn xist Primzahl und 0sonst.

  • Für jeden y > 1, M(1, y)= der yth Begriff in der Thue-Morse sequence.

  • Für jeden x, y > 1, M(x, y)= M(x, y-1) + M(x-1, y) mod 2.

Der obere linke 16x16Abschnitt dieser Matrix sieht wie folgt aus (wobei xes sich um Zeilen und ySpalten handelt):

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

Ihre Aufgabe ist es, ein Programm zu erstellen, das den Wert eines beliebigen Eintrags in dieser Matrix so genau wie möglich auswertet.

Ihr Programm nimmt zwei ganze Zahlen xund ygibt sie in einer beliebigen Form als Eingabe ein und gibt sie zurück M(x, y), entweder 0oder 1.

Ihr Code kann in einer beliebigen Sprache geschrieben sein, darf jedoch 64 Kilobyte (65.536 Bytes) Quellcodegröße oder 2 MB (2.097.152 Bytes) Gesamtspeicherauslastung nicht überschreiten. Ihr Programm muss mit leerem Speicher beginnen (dh es kann keine Daten von einer anderen Stelle laden) und muss für jede Eingabe unabhängig ausgeführt werden (d. H., Es darf keine gemeinsamen Daten für mehrere Durchläufe speichern). Ihr Programm muss außerdem in der Lage sein, alle Einträge im oberen linken 8192x8192Quadrat in angemessener Zeit auszuwerten .

Das Programm, das die meisten Einträge im oberen linken 8192 x 8192Quadrat richtig auswertet, wird der Gewinner sein, wobei ein kürzerer Code als Auslöser fungiert.

Joe Z.
quelle
Wahrscheinlich werde ich den Testfall in Kürze auf etwas eleganteres aktualisieren. Machen Sie also mit dem Testen weiter, bis ich die Frage erneut bearbeite.
Joe Z.
@mbuettner Ja, das tut es.
Joe Z.
1
Ich verstehe nicht, wie wir ein neues Tag für "Genauigkeit" brauchen. Dies ist nur eine [Code-Herausforderung]. Bitte führen Sie zuerst neue Challenge-Genre-Ideen über Meta aus (eines haben wir aus [Code-Trolling] gelernt).
Türklinke
^ Zur Kenntnis genommen. Ich werde diesen Tag entfernen.
Joe Z.
1
@TheDoctor Es ist nicht allzu ungewöhnlich. Die akzeptierte Antwort ändert sich im Laufe der Zeit.
Joe Z.

Antworten:

9

J - 42 38 char

Ziemlich schnell, 100% genau und innerhalb der Speicherbeschränkungen.

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

Die Strategie ist wie folgt: Wir werden aufeinanderfolgende Antidiagonalen dieser Matrix berechnen, ein paarweises XOR ausführen, um sich entlang zu bewegen, und die aktuellen Thue-Morse- und Prim-Bits an den Enden addieren. Wir ziehen dann die gewünschte Ziffer aus der Antidiagonale, wenn wir dort ankommen.

Erklärung durch 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)

Die Verwendung dieses Verbs gilt x m yfür M (x, y) wie in der Frage angegeben. Wo mist das 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

Um Tastatureingaben zu sparen, versuchen wir nicht festzustellen, ob wir noch mehr Prim- oder Thue-Morse-Bits benötigen. Wir berechnen daher die gesamte Antidiagonale, um das gewünschte Bit zu erhalten. Läuft allerdings 8192 m 8192noch in weniger als 0,07 s und ca. 100 KiB auf meinem bescheidenen Laptop.

algorithmshark
quelle
6

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

Hier ist eine lesbare 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]
   );

Ich berechne im Grunde entlang von Diagonalen der Konstanten vor x+y.

Eigenschaften:

  • Es ist genau.
  • Es läuft in O(x*y).
  • f[8192,8192]dauert etwa 400 Sekunden. Ich nehme an, es gibt Raum für Verbesserungen ( RotateLeftkönnte vielleicht die innere Schleife ersetzen).
  • Es wird nur ein Array mit bis zu max(x,y)Zwischenergebnissen im Speicher verwendet. Es ist also nicht erforderlich, mehr als 32 KB (unter der Annahme von 32-Bit-Ganzzahlen) für den Algorithmus selbst zu verwenden (und unabhängig davon, was Mathematica verwendet). Tatsächlich verwendet Mathematica 31M für sich auf meinem System, dies funktioniert jedoch problemlos:

    MemoryConstrained[f[8192, 8192], 2^21]
    
Martin Ender
quelle
Sieht so aus, als hättest du es verstanden. In Zukunft werde ich es allerdings schwieriger machen: P
Joe Z.
Hm, bei einer der Änderungen muss ich die Laufzeitleistung vermasselt haben. Die innere Schleife heißt immer noch O(x*y)times, aber die Gesamtausführungszeit erhöht sich schneller. Ich bin mir nicht ganz sicher, was passiert. Wenn mich ein Mathematica-Guru aufklären könnte, welche Operation in der Schleife nicht O(1)hilfreich ist , wäre das sehr hilfreich! :) (nun, PrimeQund Total@IntegerDigitsnicht, aber ich habe sie von Anfang O(y)O(x)
Martin Ender
3

Matlab: 100% Genauigkeit, 120 Zeichen, unzumutbare Ausführungszeit

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

Benutzen:

> M(4,4)
ans =
      0
> M(1, 9)
ans =
      1
intx13
quelle
1
Hier ist die Frage, können Sie dieses Programm tatsächlich ausführen und testen?
Joe Z.
Wenn du nicht rennen kannst, kann M(8192, 8192)ich es nicht ertragen.
Joe Z.
@JoeZ Es ist M-Code, den Sie in Matlab oder Octave ausführen können.
Intx13
@ JoeZ Es wird genau berechnet M (8192, 8192). Die Herausforderung sagte nichts über die Zeit zu vervollständigen;)
intx13
1
@ JoeZ Nun, es sieht so aus, als würde M (20,20) länger dauern, als ich bereit bin zu warten. Aber hey, es ist "genau"! : P
intx13
2

Python, 192 Zeichen

100% Genauigkeit, berechnet M (8192,8192) in ~ 10 Sekunden auf meiner Maschine.

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
quelle
0

Haskell - 261 Bytes - 100% - 1 MB - Ich glaube nicht, dass es bald enden wird

Dauert ungefähr 10 Sekunden für m 16 16mit -O2, aber wie ich es trotzdem geschrieben habe, kann ich es trotz dieses Problems zeigen:

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]

Vielleicht kann ein guter Haskeller es optimieren?

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
quelle
Ich denke, der Algorithmus selbst ist fehlerhaft. Trotzdem gibt es viele Dinge, die Sie tun können, um Golf zu spielen. meist extra runde Klammern, sollte aber auch f p|p=not|0<1=idbesser sein. Versuchen Sie auch, morse = False : concat $ iterate [True] (\a -> a ++ map not a)für erhöhte Faulheit zu verwenden. Ich frage mich, wie sich das auf die Leistung auswirkt.
stolzer Haskeller
Sie können auch Truenach 0<1und Falsenach Golf spielen 0>1.
stolzer Haskeller
0

Perl, 137

Nicht um zu 'gewinnen' :-), aber da es hier noch kein Perl gibt und Code trotzdem geschrieben wurde, ist es hier.

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}

Dauert beim Aufruf einige Sekunden print f(8192,8192) und speichert eine einzelne Zeile der Matrix im Speicher (Array mit 8192 Ganzzahlen (Skalaren)). Der gesamte Perl-Prozess ist ungefähr 3,5 MB groß. Ich habe versucht, es mit String anstelle von Array zu machen (entweder mit Regexps oder Zugriff mit Substr), nimmt weniger Speicher in Anspruch und kann weiter golfen werden, läuft aber viel langsamer.

Eingerückt:

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
quelle
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

Dies hat eine schnelle Laufzeit (5,7 Sekunden mit -O3 ). Speicher wurde noch nicht überprüft, sollte aber linear sein.

Dies verwendet den hier zuvor gezeigten Diagonalalgorithmus.

Was die Geschwindigkeit betrifft, sind nur der Diagonal-Algorithmus -O3und der |foldr seq(0>1)s=0<1Guard von Bedeutung, der die Liste streng macht. alles andere ist eher ineffizient implementiert - die Prüfung der Primzahlen erfolgt durch Prüfung aller kleineren Zahlen auf Division, die Elemente der Morsefolge werden ständig neu berechnet. aber es ist trotzdem schnell genug :-).

stolzer haskeller
quelle