11
\$\begingroup\$

The Wythoff matrix is an infinite matrix consisting of the Grundy numbers of each square on a chessboard in Wythoff's game.

Each entry in this matrix is equal to the smallest nonnegative number that does not appear anywhere above, to the left, or diagonally northwest of the position of the entry.

The top-left 20-by-20 square looks like this:

  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

There is currently no known efficient algorithm for computing an arbitrary entry in the Wythoff matrix. However, your task in this problem is to try to design a heuristic function that will tell whether the number at a specific coordinate wythoff(x, y) is even or odd.

Your program may not contain more than 64 KB (65,536 bytes) of source code, or use more than 2 MB (2,097,152 bytes) of working memory.

In particular for memory usage, this means that the maximum resident set size of your program may not exceed 2 MB more than the maximum resident set size of an empty program in that language. In the case of an interpreted language, it would be the memory usage of the interpreter / virtual machine itself, and in the case of a compiled language, it would be the memory usage of a program that executes the main method and does nothing.

Your program will be tested on the 10000 x 10000 matrix for row values in 20000 <= x <= 29999 and column values in 20000 <= y <= 29999.

The score of your program is the accuracy rate (number of correct guesses) your program achieves, with shorter code acting as a tiebreaker.

\$\endgroup\$
  • 3
    \$\begingroup\$ 01.R is a 05AB1E that outputs true or false randomly. Let 0 be true and 1 be false, my program will theoretically be correct ~50% of the time. Is this a valid entry? \$\endgroup\$ – Magic Octopus Urn Oct 7 '16 at 17:41
  • \$\begingroup\$ @carusocomputing Actually, I forgot to mention that randomized solutions are not allowed — your program should produce the same output for the same input every time, although I suspect that the word function implies that. \$\endgroup\$ – Joe Z. Oct 7 '16 at 20:20
  • \$\begingroup\$ If I fix the seed of my prng on each call, it will produce the same output for identical input, and I know what you mean but you will probably have to word it more specifically somehow. \$\endgroup\$ – miles Oct 7 '16 at 20:57
  • \$\begingroup\$ I get something very different when I search for Wythoff Matrix \$\endgroup\$ – Linus Oct 8 '16 at 4:20
  • \$\begingroup\$ @Linus Would "Wythoff's Game Matrix" be better? I saw that page too. \$\endgroup\$ – Joe Z. Oct 8 '16 at 6:08
6
\$\begingroup\$

Python; accuracy = 54,074,818; size = 65,526 bytes

Previous scores: 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

This approach divides all unique entries of the matrix into 523,200 groups and reads the best guess for the group (x, y) from a binary string. You can download the full source code from Google Drive.

I've used @PeterTaylor's parities to generate the string and to compute the accuracy.

\$\endgroup\$
  • \$\begingroup\$ I tried many different, more interesting approaches, but in the end, a simple hardcode outscored all of them... \$\endgroup\$ – Dennis Oct 11 '16 at 3:10
  • \$\begingroup\$ Hardcoding is also a valid approach — it might turn into, say, which hardcoding scheme returns the best result. \$\endgroup\$ – Joe Z. Oct 13 '16 at 5:18
  • \$\begingroup\$ Not saying otherwise, but since the distribution of the parities is very obviously non-random, I was hoping to outscore this approach. So far, all my attempts have failed though. \$\endgroup\$ – Dennis Oct 13 '16 at 14:13
  • \$\begingroup\$ Nah, it's fine. It just means that this problem is too hard to do properly. I've been making a bunch more problems of this style except one-dimensional. They're all in the sandbox if you want to check them out. \$\endgroup\$ – Joe Z. Oct 13 '16 at 16:18
4
\$\begingroup\$

CJam (accuracy 50016828/100000000, 6 bytes)

{+1&!}

(In ALGOL-style pseudocode for non-CJammers: return ((x + y) & 1) == 0).

This performs better than any of the other two dozen simple heuristics I've tried. It's even better than any combination with the next two best ones.


The score assumes that my calculated section of the matrix is correct. Independent verification welcomed. I'm hosting the calculated parity bits at http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (8MB download, extracts to 50MB text file: since the matrix is symmetric about the main diagonal, I've only included each line starting from the main diagonal, so you have to offset, transpose, and bitwise OR to get the full square).

The code which I used to calculate it is Java. It uses the definition fairly straightforwardly, but with a set data structure which run-length encodes the ranges so that it's quick to skip to the next permitted value. Further optimisation would be possible, but it runs on my moderately old desktop in about two hours and 1.5GB of heap space.

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);
            }
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

J, accuracy = 50022668/108 = 50.0227%, 4 bytes

2|*.

Takes the coordinates as two arguments, computes the LCM between them and takes it modulo 2. A 0 means it is even and a 1 means it is odd.

The performance is based on the parity bits provided by @Peter Taylor.

The PRNG version before for 7 bytes, 2|?.@#. had an accuracy of 50010491/108.

Explanation

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
\$\endgroup\$
  • 1
    \$\begingroup\$ The parity of the LCM is the parity of the bitwise AND. Does that save you a byte? The fascinating thing is that it's so obviously a bad heuristic (it gives 1 a mere 25% of the time, when the correct proportion is almost exactly 50%), and yet it does better than many which aren't so obviously bad. \$\endgroup\$ – Peter Taylor Oct 9 '16 at 21:55
  • \$\begingroup\$ Thanks, but unfortunately bitwise AND in J is literally AND. \$\endgroup\$ – miles Oct 9 '16 at 22:11
  • \$\begingroup\$ @PeterTaylor That sort of surprising heuristic discovery is what challenges like this one are supposed to be all about. \$\endgroup\$ – Joe Z. Oct 10 '16 at 4:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.