Imprimir um valor específico no módulo 2 da matriz Wythoff

11

A matriz Wythoff é uma matriz infinita que consiste nos números Grundy de cada quadrado em um tabuleiro de xadrez no jogo de Wythoff .

Cada entrada nessa matriz é igual ao menor número não negativo que não aparece em nenhum lugar acima, à esquerda ou na diagonal a noroeste da posição da entrada.

O quadrado de 20 por 20 no canto superior esquerdo é assim:

  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

Atualmente, não existe um algoritmo eficiente conhecido para calcular uma entrada arbitrária na matriz Wythoff. No entanto, sua tarefa neste problema é tentar projetar uma função heurística que diga se o número em uma coordenada específica wythoff(x, y)é par ou ímpar.

Seu programa não pode conter mais de 64 KB (65.536 bytes) de código-fonte ou usar mais de 2 MB (2.097.152 bytes) de memória de trabalho.

Especialmente para uso de memória, isso significa que o tamanho máximo do conjunto de residentes do seu programa não pode exceder 2 MB a mais que o tamanho máximo do conjunto de residentes de um programa vazio nesse idioma. No caso de uma linguagem interpretada, seria o uso de memória do próprio intérprete / máquina virtual e, no caso de uma linguagem compilada, seria o uso de memória de um programa que executa o método principal e não faz nada.

Seu programa será testado na 10000 x 10000matriz para valores de linha 20000 <= x <= 29999e valores de coluna em 20000 <= y <= 29999.

A pontuação do seu programa é a taxa de precisão (número de suposições corretas) que o seu programa alcança, com um código mais curto atuando como desempate.

code-challenge classification test-battery binary-matrix Joe Z.
fonte
3
01.Ré um 05AB1E que gera verdadeiro ou falso aleatoriamente. Seja 0 verdadeiro e 1 falso, meu programa teoricamente estará correto ~ 50% das vezes. Esta entrada é válida?
Magic Octopus Urn
@carusocomputing Na verdade, eu esqueci de mencionar que soluções aleatórias não são permitidas - seu programa deve produzir a mesma saída para a mesma entrada todas as vezes, embora eu suspeite que a palavra função implique isso.
Joe Z.
Se eu fixar a semente do meu prng em cada chamada, ela produzirá a mesma saída para entrada idêntica, e eu sei o que você quer dizer, mas você provavelmente terá que defini-la de maneira mais específica.
miles
Recebo algo muito diferente quando procuro Wythoff Matrix
Linus
@Linus "Matriz de jogo de Wythoff" seria melhor? Eu também vi essa página.
Joe Z.

Respostas:

6

Pitão; precisão = 54.074.818; tamanho = 65.526 bytes

Pontuações 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

Essa abordagem divide todas as entradas exclusivas da matriz em 523.200 grupos e lê a melhor estimativa para o grupo (x, y) a partir de uma sequência binária. Você pode baixar o código fonte completo do Google Drive .

Eu usei as paridades de @ PeterTaylor para gerar a string e calcular a precisão.

Dennis
fonte
Eu tentei muitos diferentes, abordagens mais interessantes, mas no final, um hardcode simples superaram todos eles ...
Dennis
A codificação física também é uma abordagem válida - ela pode se transformar, por exemplo, em qual esquema de codificação codificada retorna o melhor resultado.
Joe Z.
Sem dizer o contrário, mas como a distribuição das paridades é obviamente não aleatória, eu esperava destacar essa abordagem. Até agora, todas as minhas tentativas falharam.
Dennis
Não, está tudo bem. Significa apenas que esse problema é muito difícil de resolver corretamente. Eu tenho causado muitos problemas desse estilo, exceto unidimensional. Eles estão todos na caixa de areia, se você quiser vê-los.
Joe Z.
4

CJam (precisão 50016828/100000000, 6 bytes)

{+1&!}

(No pseudocódigo no estilo ALGOL para não-CJammers:) return ((x + y) & 1) == 0.

Isso tem um desempenho melhor do que qualquer uma das outras duas dúzias de heurísticas simples que eu tentei. É ainda melhor do que qualquer combinação com os próximos dois melhores.

A pontuação assume que minha seção calculada da matriz está correta. Verificação independente bem-vinda. Estou hospedando os bits de paridade calculados em http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (download de 8 MB, extrai para um arquivo de texto de 50 MB: como a matriz é simétrica em relação à diagonal principal, incluí apenas cada linha começando na diagonal principal, para compensar, transpor e OR bit a bit para obter o quadrado inteiro).

O código que eu usei para calcular é Java. Ele usa a definição de maneira bastante direta, mas com uma estrutura de dados definida que codifica os intervalos de execução para que seja rápido pular para o próximo valor permitido. Uma otimização adicional seria possível, mas ela é executada no meu desktop moderadamente antigo em cerca de duas horas e 1,5 GB de espaço de heap.

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

J, precisão = 50022668/10 8 = 50,0227%, 4 bytes

2|*.

Pega as coordenadas como dois argumentos, calcula o LCM entre elas e o pega no módulo 2. A 0significa que é par e a 1que é ímpar.

O desempenho é baseado nos bits de paridade fornecidos por @ Peter Taylor .

A versão PRNG anterior, por 7 bytes, 2|?.@#.tinha uma precisão de 50010491/10 8 .

Explicação

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
milhas
fonte
1
A paridade do LCM é a paridade do AND bit a bit. Isso economiza um byte? O fascinante é que, obviamente, é uma heurística ruim (fornece 1apenas 25% do tempo, quando a proporção correta é quase exatamente 50%), e ainda assim é melhor do que muitas que não são obviamente tão ruins.
Peter Taylor
Obrigado, mas infelizmente AND em J é literalmente AND.
miles
@ PeterTaylor Esse tipo de descoberta heurística surpreendente é o que desafios como esse devem ter.
Joe Z.