Вывести определенное значение в матрицу Витхоффа по модулю 2

11

Матрица Витоффа - это бесконечная матрица, состоящая из чисел Гранди каждого квадрата на шахматной доске в игре Витоффа .

Каждая запись в этой матрице равна наименьшему неотрицательному числу, которое не появляется нигде выше, слева или по диагонали к северо-западу от позиции записи.

Верхний левый квадрат 20 на 20 выглядит так:

  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

В настоящее время не существует известного эффективного алгоритма для вычисления произвольной записи в матрице Витоффа. Однако ваша задача в этой задаче состоит в том, чтобы попытаться создать эвристическую функцию, которая сообщит, является ли число по определенной координате wythoff(x, y)четным или нечетным.

Ваша программа может содержать не более 64 КБ (65 536 байт) исходного кода или использовать более 2 МБ (2 097 152 байт) рабочей памяти.

В частности, для использования памяти это означает, что максимальный размер резидентного набора вашей программы не может превышать на 2 МБ больше, чем максимальный размер резидентного набора пустой программы на этом языке. В случае интерпретируемого языка это будет использование памяти интерпретатором / самой виртуальной машиной, а в случае скомпилированного языка это будет использование памяти программой, которая выполняет метод main и ничего не делает.

Ваша программа будет проверена на 10000 x 10000матрице для значений строк в 20000 <= x <= 29999и значений столбцов в 20000 <= y <= 29999.

Оценка вашей программы - это показатель точности (количество правильных предположений), достигнутый вашей программой, с более коротким кодом, действующим в качестве тай-брейка.

code-challenge classification test-battery binary-matrix Джо З.
источник
3
01.Rявляется 05AB1E, который выводит true или false случайным образом. Пусть 0 будет истинно, а 1 - ложно, моя программа теоретически будет правильной ~ 50% времени. Это действительная запись?
Волшебная Урна Осьминога
@carusocomputing На самом деле, я забыл упомянуть, что рандомизированные решения недопустимы - ваша программа должна каждый раз выдавать один и тот же вывод для одного и того же ввода, хотя я подозреваю, что слово function подразумевает это.
Джо З.
Если я фиксирую начальное значение моего prng при каждом вызове, он будет выдавать один и тот же вывод для идентичных входных данных, и я знаю, что вы имеете в виду, но вам, вероятно, придется как-то конкретнее это произнести.
миль
Я получаю что-то совсем другое, когда я ищу Wythoff Matrix
Линус
@Linus «Матрица игры Уайтоффа» будет лучше? Я тоже видел эту страницу.
Джо З.

Ответы:

6

Python; точность = 54,074,818; размер = 65 526 байт

Предыдущие оценки: 50 227 165; 50803687; 50953001

#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

Этот подход делит все уникальные записи матрицы на 523 200 групп и считывает наилучшее предположение для группы (x, y) из двоичной строки. Вы можете скачать полный исходный код с Google Drive .

Я использовал четности @ PeterTaylor, чтобы сгенерировать строку и вычислить точность.

Деннис
источник
Я перепробовал много разных, более интересных подходов, но в итоге простой жесткий код превзошел их всех ...
Деннис
Жесткое кодирование также является допустимым подходом - оно может превратиться, скажем, в схему жесткого кодирования, которая дает лучший результат.
Джо З.
Не говоря об обратном, но поскольку распределение паритетов совершенно очевидно неслучайно, я надеялся опередить этот подход. Пока что все мои попытки провалились.
Деннис
Нет, все нормально Это просто означает, что эту проблему слишком сложно решить правильно. Я делал кучу проблем с этим стилем, кроме одномерных. Они все в песочнице, если вы хотите проверить их.
Джо З.
4

CJam (точность 50016828/100000000, 6 байтов)

{+1&!}

(В псевдокоде в стиле ALGOL для не-CJammers:) return ((x + y) & 1) == 0.

Это работает лучше, чем любая из двух других дюжин простых эвристик, которые я пробовал. Это даже лучше, чем любая комбинация со следующими двумя лучшими.

Оценка предполагает, что мой вычисленный раздел матрицы является правильным. Независимая проверка приветствуется. Я размещаю рассчитанные биты четности по адресу http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (загрузка 8 МБ, извлечение в текстовый файл 50 МБ: поскольку матрица симметрична относительно главной диагонали, я включил только каждую линия начинается с главной диагонали, поэтому вы должны сместить, транспонировать и поразрядно ИЛИ, чтобы получить полный квадрат).

Код, который я использовал для вычисления, это Java. Он использует определение довольно просто, но с заданной структурой данных, длина длины которой кодирует диапазоны, чтобы можно было быстро перейти к следующему разрешенному значению. Дальнейшая оптимизация возможна, но она запускается на моем умеренно старом рабочем столе примерно через два часа и 1,5 ГБ кучи.

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);
            }
        }
    }
}
Питер Тейлор
источник
3

J, точность = 50022668/10 8 = 50,0227%, 4 байта

2|*.

Принимает координаты в качестве двух аргументов, вычисляет LCM между ними и принимает их по модулю 2. 0Средство, которое является четным, и 1средство, которое является нечетным.

Производительность основана на битах четности, предоставленных @ Peter Taylor .

Версия PRNG, ранее для 7 байтов, 2|?.@#.имела точность 50010491/10 8 .

объяснение

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
миль
источник
1
Четность LCM - это четность побитового AND. Это спасет вас байт? Захватывающая вещь заключается в том, что это, очевидно, плохая эвристика (это дает 1всего 25% времени, когда правильная пропорция почти точно равна 50%), и все же это лучше, чем у многих, которые не так уж и плохи.
Питер Тейлор
Спасибо, но, к сожалению, поразрядно И в J буквально AND.
миль
@PeterTaylor Такого рода удивительное эвристическое открытие - вот о чем должны быть такие вызовы, как этот.
Джо З.