Die Wythoff-Matrix ist eine unendliche Matrix, die aus den Grundy-Zahlen jedes Quadrats auf einem Schachbrett in Wythoffs Spiel besteht .

Jeder Eintrag in dieser Matrix entspricht der kleinsten nichtnegativen Zahl, die nirgends über, links oder diagonal nordwestlich der Position des Eintrags erscheint.

Das obere linke 20-mal-20-Quadrat sieht folgendermaßen aus:

  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
  1  2  0  4  5  3  7  8  6 10 11  9 13 14 12 16 17 15 19 20
  2  0  1  5  3  4  8  6  7 11  9 10 14 12 13 17 15 16 20 18
  3  4  5  6  2  0  1  9 10 12  8  7 15 11 16 18 14 13 21 17
  4  5  3  2  7  6  9  0  1  8 13 12 11 16 15 10 19 18 17 14
  5  3  4  0  6  8 10  1  2  7 12 14  9 15 17 13 18 11 16 21
  6  7  8  1  9 10  3  4  5 13  0  2 16 17 18 12 20 14 15 11
  7  8  6  9  0  1  4  5  3 14 15 13 17  2 10 19 21 12 22 16
  8  6  7 10  1  2  5  3  4 15 16 17 18  0  9 14 12 19 23 24
  9 10 11 12  8  7 13 14 15 16 17  6 19  5  1  0  2  3  4 22
 10 11  9  8 13 12  0 15 16 17 14 18  7  6  2  3  1  4  5 23
 11  9 10  7 12 14  2 13 17  6 18 15  8 19 20 21  4  5  0  1
 12 13 14 15 11  9 16 17 18 19  7  8 10 20 21 22  6 23  3  5
 13 14 12 11 16 15 17  2  0  5  6 19 20  9  7  8 10 22 24  4
 14 12 13 16 15 17 18 10  9  1  2 20 21  7 11 23 22  8 25 26
 15 16 17 18 10 13 12 19 14  0  3 21 22  8 23 20  9 24  7 27
 16 17 15 14 19 18 20 21 12  2  1  4  6 10 22  9 13 25 11 28
 17 15 16 13 18 11 14 12 19  3  4  5 23 22  8 24 25 21 26 10
 18 19 20 21 17 16 15 22 23  4  5  0  3 24 25  7 11 26 12 13
 19 20 18 17 14 21 11 16 24 22 23  1  5  4 26 27 28 10 13 25

Derzeit ist kein effizienter Algorithmus zur Berechnung eines beliebigen Eintrags in der Wythoff-Matrix bekannt. Ihre Aufgabe bei diesem Problem besteht jedoch darin, eine heuristische Funktion zu entwerfen, die angibt, ob die Zahl an einer bestimmten Koordinate wythoff(x, y)gerade oder ungerade ist.

Ihr Programm darf nicht mehr als 64 KB (65.536 Byte) Quellcode enthalten oder mehr als 2 MB (2.097.152 Byte) Arbeitsspeicher verwenden.

Insbesondere für die Speichernutzung bedeutet dies, dass die maximale Größe des residenten Satzes Ihres Programms 2 MB nicht überschreiten darf als die maximale Größe des residenten Satzes eines leeren Programms in dieser Sprache. Im Fall einer interpretierten Sprache wäre dies die Speichernutzung des Interpreters / der virtuellen Maschine selbst, und im Fall einer kompilierten Sprache wäre es die Speichernutzung eines Programms, das die Hauptmethode ausführt und nichts tut.

Ihr Programm wird in der 10000 x 10000Matrix auf Zeilen- 20000 <= x <= 29999und Spaltenwerte in getestet 20000 <= y <= 29999.

Die Punktzahl Ihres Programms ist die Genauigkeitsrate (Anzahl der richtigen Vermutungen), die Ihr Programm erreicht, wobei kürzerer Code als Tiebreaker fungiert.

Python; Genauigkeit = 54.074.818; Größe = 65.526 Bytes

Frühere Ergebnisse: 50.227.165; 50,803,687; 50.953.001

#coding=utf-8
d=r'''<65,400 byte string>'''
def f(x,y):
 a=max(x,y)-20000;b=min(x,y)-20000;c=(a*(a+1)//2+b)%523200
 return(ord(d[c//8])>>(c%8))&1

Dieser Ansatz unterteilt alle eindeutigen Einträge der Matrix in 523.200 Gruppen und liest die beste Schätzung für die Gruppe (x, y) aus einer binären Zeichenfolge. Sie können den vollständigen Quellcode von Google Drive herunterladen .

Ich habe die Paritäten von @ PeterTaylor verwendet , um die Zeichenfolge zu generieren und die Genauigkeit zu berechnen.

CJam (Genauigkeit 50016828/100000000, 6 Byte)

{+1&!}

(Im ALGOL-Pseudocode für Nicht-CJammer :) return ((x + y) & 1) == 0.

Dies ist besser als alle anderen zwei Dutzend einfachen Heuristiken, die ich ausprobiert habe. Es ist sogar besser als jede Kombination mit den nächsten beiden besten.

Die Punktzahl setzt voraus, dass mein berechneter Abschnitt der Matrix korrekt ist. Unabhängige Überprüfung begrüßt. Ich hoste die berechneten Paritätsbits unter http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (8 MB Download, Auszüge aus 50 MB Textdatei: Da die Matrix symmetrisch zur Hauptdiagonale ist, habe ich nur jede eingeschlossen Linie beginnend mit der Hauptdiagonale, also müssen Sie versetzen, transponieren und bitweise ODER, um das volle Quadrat zu erhalten).

Der Code, mit dem ich ihn berechnet habe, ist Java. Die Definition wird recht einfach verwendet, jedoch mit einer festgelegten Datenstruktur, deren Lauflänge die Bereiche codiert, sodass schnell zum nächsten zulässigen Wert gesprungen werden kann. Eine weitere Optimierung wäre möglich, läuft jedoch auf meinem mäßig alten Desktop in etwa zwei Stunden und 1,5 GB Heap-Speicherplatz.

import java.util.*;

public class PPCG95604Analysis
{
    static final int N = 30000;

    public static void main(String[] args) {
        Indicator[] cols = new Indicator[N];
        Indicator[] diag = new Indicator[N];
        for (int i = 0; i < N; i++) {
            cols[i] = new Indicator();
            diag[i] = new Indicator();
        }

        int maxVal = 0;

        for (int y = 0; y < N; y++) {
            Indicator row = new Indicator(cols[y]);

            for (int x = y; x < N; x++) {
                Indicator col = cols[x];
                Indicator dia = diag[x - y];

                Indicator.Result rr = row.firstCandidate();
                Indicator.Result rc = col.firstCandidate();
                Indicator.Result rd = dia.firstCandidate();

                while (true) {
                    int max = Math.max(Math.max(rr.candidateValue(), rc.candidateValue()), rd.candidateValue());
                    if (rr.candidateValue() == max && rc.candidateValue() == max && rd.candidateValue() == max) break;

                    if (rr.candidateValue() != max) rr = rr.firstCandidateGreaterThan(max - 1);
                    if (rc.candidateValue() != max) rc = rc.firstCandidateGreaterThan(max - 1);
                    if (rd.candidateValue() != max) rd = rd.firstCandidateGreaterThan(max - 1);
                }

                if (y >= 20000 && x >= 20000) System.out.format("%d", rr.candidateValue() & 1);
                maxVal = Math.max(maxVal, rr.candidateValue());
                rr.markUsed();
                rc.markUsed();
                rd.markUsed();
            }
            if (y >= 20000) System.out.println();
        }
    }

    static class Indicator
    {
        private final int INFINITY = (short)0xffff;
        private final int MEMBOUND = 10000;

        private short[] runLengths = new short[MEMBOUND];

        public Indicator() { runLengths[1] = INFINITY; }

        public Indicator(Indicator clone) { System.arraycopy(clone.runLengths, 0, runLengths, 0, MEMBOUND); }

        public Result firstCandidate() {
            // We have a run of used values, followed by a run of unused ones.
            return new Result(1, 0xffff & runLengths[0], 0xffff & runLengths[0]);
        }

        class Result
        {
            private final int runIdx;
            private final int runStart;
            private final int candidateValue;

            Result(int runIdx, int runStart, int candidateValue) {
                this.runIdx = runIdx;
                this.runStart = runStart;
                this.candidateValue = candidateValue;
            }

            public int candidateValue() {
                return candidateValue;
            }

            public Result firstCandidateGreaterThan(int x) {
                if (x < candidateValue) throw new IndexOutOfBoundsException();

                int idx = runIdx;
                int start = runStart;
                while (true) {
                    int end = start + (0xffff & runLengths[idx]) - 1;
                    if (end > x) return new Result(idx, start, x + 1);

                    // Run of excluded
                    start += 0xffff & runLengths[idx];
                    idx++;
                    // Run of included
                    start += 0xffff & runLengths[idx];
                    idx++;

                    if (start > x) return new Result(idx, start, start);
                }
            }

            public void markUsed() {
                if (candidateValue == runStart) {
                    // Transfer one from the start of the run to the previous run
                    runLengths[runIdx - 1]++;
                    if (runLengths[runIdx] != INFINITY) runLengths[runIdx]--;
                    // May need to merge runs
                    if (runLengths[runIdx] == 0) {
                        runLengths[runIdx - 1] += runLengths[runIdx + 1];
                        for (int idx = runIdx; idx < MEMBOUND - 2; idx++) {
                            runLengths[idx] = runLengths[idx + 2];
                            if (runLengths[idx] == INFINITY) break;
                        }
                    }

                    return;
                }

                if (candidateValue == runStart + (0xffff & runLengths[runIdx]) - 1) {
                    // Transfer one from the end of the run to the following run.
                    if (runLengths[runIdx + 1] != INFINITY) runLengths[runIdx + 1]++;
                    if (runLengths[runIdx] != INFINITY) runLengths[runIdx]--;
                    // We never need to merge runs, because if we did we'd have hit the previous case instead
                    return;
                }

                // Need to split the run. From
                //   runIdx: a+1+b
                // to
                //   runIdx: a
                //   runIdx+1: 1
                //   runIdx+2: b
                //   runIdx+3: previous val at runIdx+1
                for (int idx = MEMBOUND - 1; idx > runIdx + 2; idx--) {
                    runLengths[idx] = runLengths[idx - 2];
                }
                runLengths[runIdx + 2] = runLengths[runIdx] == INFINITY ? INFINITY : (short)((0xffff & runLengths[runIdx]) + runStart - 1 - candidateValue);
                runLengths[runIdx + 1] = 1;
                runLengths[runIdx] = (short)(candidateValue - runStart);
            }
        }
    }
}

J, Genauigkeit = 50022668/10 ⁸ = 50,0227%, 4 Bytes

2|*.

Nimmt die Koordinaten als zwei Argumente, berechnet das LCM zwischen ihnen und nimmt es Modulo 2. A 0bedeutet, dass es gerade und a 1bedeutet, dass es ungerade ist.

Die Leistung basiert auf den von @ Peter Taylor bereitgestellten Paritätsbits .

Die PRNG-Version zuvor für 7 Bytes 2|?.@#.hatte eine Genauigkeit von 50010491/10 ⁸ .

Erläuterung

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2