Drucken Sie einen bestimmten Wert in die Wythoff-Matrix Modulo 2

11

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.

Joe Z.
quelle
3
01.Rist ein 05AB1E, der zufällig wahr oder falsch ausgibt. Sei 0 wahr und 1 falsch, mein Programm wird theoretisch ~ 50% der Zeit korrekt sein. Ist das ein gültiger Eintrag?
Magic Octopus Urn
@carusocomputing Eigentlich vergessen, die ich zu erwähnen , dass randomisierte Lösungen sind nicht erlaubt - Ihr Programm sollte jedes Mal die gleiche Leistung für den gleichen Eingang erzeugen , obwohl ich vermute , dass das Wort Funktion das impliziert.
Joe Z.
Wenn ich bei jedem Aufruf den Startwert meines Prng festlege, wird dieselbe Ausgabe für identische Eingaben erzeugt, und ich weiß, was Sie meinen, aber Sie müssen ihn wahrscheinlich irgendwie genauer formulieren.
Meilen
Ich bekomme etwas ganz anderes, wenn ich nach Wythoff Matrix
Linus
@Linus Wäre "Wythoffs Spielmatrix" besser? Ich habe diese Seite auch gesehen.
Joe Z.

Antworten:

6

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.

Dennis
quelle
Ich habe viele verschiedene, interessantere Ansätze ausprobiert, aber am Ende hat ein einfacher Hardcode alle übertroffen ...
Dennis
Hardcodierung ist auch ein gültiger Ansatz - es kann sich beispielsweise herausstellen, welches Hardcodierungsschema das beste Ergebnis liefert.
Joe Z.
Nicht anders zu sagen, aber da die Verteilung der Paritäten offensichtlich nicht zufällig ist, hatte ich gehofft, diesen Ansatz zu übertreffen. Bisher sind jedoch alle meine Versuche gescheitert.
Dennis
Nein, es ist in Ordnung. Es bedeutet nur, dass dieses Problem zu schwer zu lösen ist. Ich habe ein paar weitere Probleme mit diesem Stil gemacht, außer eindimensional. Sie sind alle im Sandkasten, wenn Sie sie überprüfen möchten.
Joe Z.
4

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);
            }
        }
    }
}
Peter Taylor
quelle
3

J, Genauigkeit = 50022668/10 8 = 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 8 .

Erläuterung

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
Meilen
quelle
1
Die Parität des LCM ist die Parität des bitweisen UND. Spart Ihnen das ein Byte? Das Faszinierende ist, dass es so offensichtlich eine schlechte Heuristik ist (es gibt 1nur 25% der Zeit, wenn der richtige Anteil fast genau 50% beträgt), und dennoch ist es besser als viele, die nicht so offensichtlich schlecht sind.
Peter Taylor
Danke, aber leider ist bitweise UND in J buchstäblich AND.
Meilen
@PeterTaylor Diese Art von überraschender heuristischer Entdeckung ist es, worum es bei Herausforderungen wie dieser gehen soll.
Joe Z.