Imprima un valor específico en la matriz de Wythoff módulo 2

11

La matriz de Wythoff es una matriz infinita que consiste en los números Grundy de cada cuadrado en un tablero de ajedrez en el juego de Wythoff .

Cada entrada en esta matriz es igual al número no negativo más pequeño que no aparece en ninguna parte arriba, a la izquierda o en diagonal al noroeste de la posición de la entrada.

El cuadrado superior izquierdo de 20 por 20 se ve así:

  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

Actualmente no se conoce un algoritmo eficiente para calcular una entrada arbitraria en la matriz de Wythoff. Sin embargo, su tarea en este problema es tratar de diseñar una función heurística que indique si el número en una coordenada específica wythoff(x, y)es par o impar.

Su programa no puede contener más de 64 KB (65,536 bytes) de código fuente, o usar más de 2 MB (2,097,152 bytes) de memoria de trabajo.

En particular para el uso de memoria, esto significa que el tamaño máximo de conjunto residente de su programa no puede exceder los 2 MB más que el tamaño máximo de conjunto residente de un programa vacío en ese idioma. En el caso de un lenguaje interpretado, sería el uso de la memoria del propio intérprete / máquina virtual, y en el caso de un lenguaje compilado, sería el uso de la memoria de un programa que ejecuta el método principal y no hace nada.

Su programa será probado en la 10000 x 10000matriz para valores de fila en 20000 <= x <= 29999y valores de columna en 20000 <= y <= 29999.

El puntaje de su programa es la tasa de precisión (número de conjeturas correctas) que logra su programa, con un código más corto que actúa como un desempate.

code-challenge classification test-battery binary-matrix Joe Z.
fuente
3
01.Res un 05AB1E que genera verdadero o falso al azar. Deje que 0 sea verdadero y 1 falso, teóricamente mi programa será correcto ~ 50% del tiempo. ¿Es esta una entrada válida?
Magic Octopus Urn
@carusocomputing En realidad, olvidé mencionar que las soluciones aleatorias no están permitidas: su programa debe producir la misma salida para la misma entrada cada vez, aunque sospecho que la función de palabra implica eso.
Joe Z.
Si corrijo la semilla de mi prng en cada llamada, producirá la misma salida para una entrada idéntica, y sé lo que quieres decir, pero es probable que tengas que redactarlo más específicamente de alguna manera.
millas
Obtengo algo muy diferente cuando busco Wythoff Matrix
Linus
@Linus ¿Sería mejor "Wythoff's Game Matrix"? Yo también vi esa página.
Joe Z.

Respuestas:

6

Pitón; precisión = 54,074,818; tamaño = 65,526 bytes

Puntajes anteriores: 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

Este enfoque divide todas las entradas únicas de la matriz en 523,200 grupos y lee la mejor estimación para el grupo (x, y) de una cadena binaria. Puede descargar el código fuente completo de Google Drive .

He usado las paridades de @ PeterTaylor para generar la cadena y calcular la precisión.

Dennis
fuente
Probé muchos enfoques diferentes y más interesantes, pero al final, un simple código duro los superó a todos ...
Dennis
La codificación rígida también es un enfoque válido: podría convertirse, por ejemplo, en qué esquema de codificación rígida arroja el mejor resultado.
Joe Z.
No digo lo contrario, pero dado que la distribución de las paridades es obviamente no aleatoria, esperaba superar este enfoque. Hasta ahora, todos mis intentos han fallado sin embargo.
Dennis
No, está bien. Simplemente significa que este problema es demasiado difícil de hacer correctamente. He estado haciendo muchos más problemas de este estilo, excepto unidimensional. Todos están en la caja de arena si quieres verlos.
Joe Z.
4

CJam (precisión 50016828/100000000, 6 bytes)

{+1&!}

(En pseudocódigo de estilo ALGOL para no CJammers:) return ((x + y) & 1) == 0.

Esto funciona mejor que cualquiera de las otras dos docenas de heurísticas simples que he probado. Es incluso mejor que cualquier combinación con los siguientes dos mejores.

La puntuación supone que mi sección calculada de la matriz es correcta. Verificación independiente bienvenida. Estoy alojando los bits de paridad calculados en http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (descarga de 8 MB, extractos en un archivo de texto de 50 MB: dado que la matriz es simétrica respecto a la diagonal principal, solo he incluido cada uno línea a partir de la diagonal principal, por lo que debe desplazar, transponer y bit a bit O para obtener el cuadrado completo).

El código que solía calcular es Java. Utiliza la definición de manera bastante directa, pero con una estructura de datos establecida que la longitud de ejecución codifica los rangos para que sea rápido saltar al siguiente valor permitido. Sería posible una mayor optimización, pero se ejecuta en mi escritorio moderadamente antiguo en aproximadamente dos horas y 1.5 GB de espacio de almacenamiento dinámico.

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
fuente
3

J, precisión = 50022668/10 8 = 50.0227%, 4 bytes

2|*.

Toma las coordenadas como dos argumentos, calcula el MCM entre ellas y toma el módulo 2. A 0significa que es par y a 1significa que es impar.

El rendimiento se basa en los bits de paridad proporcionados por @ Peter Taylor .

La versión PRNG anterior para 7 bytes, 2|?.@#.tenía una precisión de 50010491/10 8 .

Explicación

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
millas
fuente
1
La paridad del LCM es la paridad del AND bit a bit. ¿Eso te ahorra un byte? Lo fascinante es que obviamente es una mala heurística (da 1solo el 25% del tiempo, cuando la proporción correcta es casi exactamente el 50%), y sin embargo, es mejor que muchas que no son tan obviamente malas.
Peter Taylor
Gracias, pero desafortunadamente bitwise Y en J es literalmente AND.
millas
@PeterTaylor Ese tipo de descubrimiento heurístico sorprendente es de lo que se supone que se trata este tipo de desafíos.
Joe Z.