Matryca Wythoffa jest nieskończoną matrycą składającą się z liczb Grundy każdego kwadratu na szachownicy w grze Wythoffa .

Każdy wpis w tej macierzy jest równy najmniejszej nieujemnej liczbie, która nie pojawia się nigdzie powyżej, po lewej stronie lub po przekątnej na północny zachód od pozycji wejścia.

Lewy górny kwadrat 20 na 20 wygląda następująco:

  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

Obecnie nie ma znanego wydajnego algorytmu obliczania dowolnego wpisu w macierzy Wythoffa. Jednak Twoim zadaniem w tym problemie jest próba zaprojektowania funkcji heurystycznej, która powie, czy liczba przy określonej współrzędnej wythoff(x, y)jest parzysta czy nieparzysta.

Twój program nie może zawierać więcej niż 64 KB (65 536 bajtów) kodu źródłowego lub używać więcej niż 2 MB (2 097 152 bajtów) pamięci roboczej.

W szczególności w przypadku użycia pamięci oznacza to, że maksymalny rozmiar zestawu rezydentnego twojego programu nie może przekraczać 2 MB więcej niż maksymalny rozmiar zestawu rezydentnego pustego programu w tym języku. W przypadku języka interpretowanego byłoby to użycie pamięci przez interpreter / maszynę wirtualną, aw przypadku języka skompilowanego byłoby użycie pamięci przez program, który wykonuje główną metodę i nic nie robi.

Twój program zostanie przetestowany na 10000 x 10000macierzy pod kątem wartości wierszy 20000 <= x <= 29999i wartości kolumn w 20000 <= y <= 29999.

Wynik twojego programu to wskaźnik dokładności (liczba poprawnych domysłów) osiągnięty przez twój program, przy czym krótszy kod działa jak remis.

Pyton; dokładność = 54,074,818; rozmiar = 65 526 bajtów

Poprzednie wyniki: 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

Takie podejście dzieli wszystkie unikalne wpisy macierzy na 523 200 grup i odczytuje najlepsze przypuszczenie dla grupy (x, y) z ciągu binarnego. Możesz pobrać pełny kod źródłowy z Dysku Google .

Użyłem @ parytetów PeterTaylor za wygenerować ciąg i obliczyć dokładność.

CJam (dokładność 50016828/100000000, 6 bajtów)

{+1&!}

(W pseudokodzie w stylu ALGOL dla nie-CJammerów:) return ((x + y) & 1) == 0.

Działa to lepiej niż jakikolwiek z pozostałych dwudziestu prostych heurystyk, których próbowałem. To nawet lepsze niż jakakolwiek kombinacja z następnymi dwoma najlepszymi.

Wynik zakłada, że ​​mój obliczony przekrój macierzy jest poprawny. Z zadowoleniem przyjęto niezależną weryfikację. Hostuję obliczone bity parzystości na stronie http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (pobieranie 8 MB, wypakowanie do pliku tekstowego 50 MB: ponieważ macierz jest symetryczna względem głównej przekątnej, zawarłem tylko każdą linia zaczynająca się od głównej przekątnej, więc musisz przesunąć, transponować lub bitowo LUB uzyskać pełny kwadrat).

Kod, którego użyłem do obliczenia, to Java. Używa definicji dość prosto, ale z ustaloną strukturą danych, której długość koduje zakresy, dzięki czemu można szybko przejść do następnej dozwolonej wartości. Dalsza optymalizacja byłaby możliwa, ale działa na moim umiarkowanie starym komputerze za około dwie godziny i 1,5 GB miejsca na stosie.

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, dokładność = 50022668/10 ⁸ = 50,0227%, 4 bajty

2|*.

Bierze współrzędne jako dwa argumenty, oblicza LCM między nimi i przyjmuje to modulo 2. A 0oznacza, że ​​jest parzyste i a1 oznacza, że ​​jest nieparzyste.

Wydajność oparta jest na bitach parzystości dostarczonych przez @ Peter Taylor .

Poprzednia wersja PRNG dla 7 bajtów 2|?.@#.miała dokładność 50010491/10 ⁸ .

Wyjaśnienie

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