Print a specific value in the Wythoff matrix modulo 2
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.
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);
}
}
}
}
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