Cetak nilai tertentu dalam modulo 2 matriks Wythoff

11

Matriks Wythoff adalah matriks tak terbatas yang terdiri dari angka Grundy dari setiap kotak di papan catur dalam permainan Wythoff .

Setiap entri dalam matriks ini sama dengan angka nonnegatif terkecil yang tidak muncul di mana pun di atas, ke kiri, atau diagonal barat laut dari posisi entri.

Kotak 20-kali-20 atas-kiri terlihat seperti ini:

  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

Saat ini tidak ada algoritma efisien yang dikenal untuk menghitung entri sewenang-wenang dalam matriks Wythoff. Namun, tugas Anda dalam masalah ini adalah mencoba merancang fungsi heuristik yang akan memberi tahu apakah angka pada koordinat tertentu wythoff(x, y)genap atau ganjil.

Program Anda mungkin tidak mengandung lebih dari 64 KB (65.536 byte) kode sumber, atau menggunakan lebih dari 2 MB (2.097.152 byte) memori kerja.

Khususnya untuk penggunaan memori, ini berarti bahwa ukuran set residen maksimum dari program Anda tidak boleh melebihi 2 MB lebih dari ukuran set residen maksimum dari sebuah program kosong dalam bahasa itu. Dalam kasus bahasa yang ditafsirkan, itu akan menjadi penggunaan memori interpreter / mesin virtual itu sendiri, dan dalam kasus bahasa yang dikompilasi, itu akan menjadi penggunaan memori dari suatu program yang mengeksekusi metode utama dan tidak melakukan apa-apa.

Program Anda akan diuji pada 10000 x 10000matriks untuk nilai baris 20000 <= x <= 29999dan nilai kolom dalam 20000 <= y <= 29999.

Nilai program Anda adalah tingkat akurasi (jumlah tebakan yang benar) yang dicapai oleh program Anda, dengan kode yang lebih pendek bertindak sebagai tiebreak.

code-challenge classification test-battery binary-matrix Joe Z.
sumber
3
01.Radalah 05AB1E yang menghasilkan benar atau salah secara acak. Biarkan 0 benar dan 1 salah, program saya secara teoritis akan benar ~ 50% dari waktu. Apakah ini entri yang valid?
Magic Octopus Mm
@carusocomputing Sebenarnya, saya lupa menyebutkan bahwa solusi acak tidak diperbolehkan - program Anda harus menghasilkan output yang sama untuk input yang sama setiap kali, walaupun saya curiga bahwa fungsi kata menyiratkan hal itu.
Joe Z.
Jika saya memperbaiki benih prng saya pada setiap panggilan, itu akan menghasilkan output yang sama untuk input yang identik, dan saya tahu apa yang Anda maksudkan tetapi Anda mungkin harus mengatakannya secara lebih spesifik.
mil
Saya mendapatkan sesuatu yang sangat berbeda ketika saya mencari Wythoff Matrix
Linus
@Linus Akankah "Wythoff's Game Matrix" lebih baik? Saya melihat halaman itu juga.
Joe Z.

Jawaban:

6

Python; akurasi = 54.074.818; ukuran = 65.526 byte

Skor sebelumnya: 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

Pendekatan ini membagi semua entri unik dari matriks menjadi 523.200 grup dan membaca tebakan terbaik untuk grup (x, y) dari string biner. Anda dapat mengunduh kode sumber lengkap dari Google Drive .

Saya telah menggunakan paritas @ PeterTaylor untuk menghasilkan string dan untuk menghitung akurasinya.

Dennis
sumber
Saya mencoba banyak pendekatan berbeda, lebih menarik, tetapi pada akhirnya, hardcode sederhana mengungguli mereka semua ...
Dennis
Hardcoding juga merupakan pendekatan yang valid - mungkin berubah menjadi, katakanlah, skema hardcoding mana yang memberikan hasil terbaik.
Joe Z.
Tidak mengatakan sebaliknya, tetapi karena distribusi paritas sangat jelas non-acak, saya berharap untuk mengungguli pendekatan ini. Sejauh ini, semua upaya saya gagal.
Dennis
Tidak apa-apa. Ini hanya berarti bahwa masalah ini terlalu sulit untuk dilakukan dengan benar. Saya telah membuat banyak masalah dengan gaya ini kecuali satu dimensi. Semuanya ada di kotak pasir jika Anda ingin memeriksanya.
Joe Z.
4

CJam (akurasi 50016828/100000000, 6 byte)

{+1&!}

(Dalam pseudocode gaya ALGOL untuk non-CJammers:) return ((x + y) & 1) == 0.

Ini berkinerja lebih baik daripada dua lusin heuristik sederhana lainnya yang pernah saya coba. Ini bahkan lebih baik daripada kombinasi apa pun dengan dua yang terbaik berikutnya.

Skor tersebut mengasumsikan bahwa bagian matriks yang saya hitung benar. Verifikasi independen disambut. Saya hosting bit paritas yang dihitung di http://cheddarmonk.org/codegolf/PPCG95604-parity.bz2 (unduhan 8MB, ekstrak ke file teks 50MB: karena matriksnya simetris tentang diagonal utama, saya hanya menyertakan masing-masing garis mulai dari diagonal utama, sehingga Anda harus mengimbangi, mengubah posisi, dan bitwise ATAU untuk mendapatkan kuadrat penuh).

Kode yang saya gunakan untuk menghitungnya adalah Java. Ini menggunakan definisi cukup mudah, tetapi dengan struktur data yang panjang run-encode rentang sehingga cepat untuk melompat ke nilai berikutnya yang diizinkan. Optimalisasi lebih lanjut mungkin dilakukan, tetapi berjalan pada desktop saya yang sudah cukup lama dalam waktu sekitar dua jam dan ruang penyimpanan 1,5GB.

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

J, akurasi = 50022668/10 8 = 50.0227%, 4 byte

2|*.

Mengambil koordinat sebagai dua argumen, menghitung LCM di antara mereka dan membawanya modulo 2. A 0berarti genap dan 1berarti aneh.

Kinerja didasarkan pada bit paritas yang disediakan oleh @ Peter Taylor .

Versi PRNG sebelum selama 7 byte, 2|?.@#.memiliki akurasi 50010491/10 8 .

Penjelasan

2|*.  Input: x on LHS, y on RHS
  *.  LCM(x, y)
2|    Modulo 2
mil
sumber
1
Paritas LCM adalah paritas dari bitwise AND. Apakah itu menghemat satu byte? Hal yang menarik adalah bahwa itu jelas heuristik yang buruk (itu memberikan 1hanya 25% dari waktu, ketika proporsi yang benar hampir persis 50%), namun itu lebih baik daripada banyak yang tidak begitu jelas buruk.
Peter Taylor
Terima kasih, tapi sayangnya bitwise AND dalam J secara harfiah AND.
mil
@PeterTaylor Penemuan heuristik yang mengejutkan semacam itulah yang seharusnya menjadi tantangan seperti ini.
Joe Z.