Längster Tag des Jahres - hier ist etwas, um die zusätzliche Zeit zu verschwenden ...

Überblick

Beachten Sie, dass dies kein Beliebtheitswettbewerb und keine Herausforderung für die grafische Ausgabe ist. Sie müssen lediglich eine Zeichenfolge mit 65.536 Nullen und Einsen ausgeben. Das Stapel-Snippet unten in der Frage zeigt dies als 256 x 256-Schwarzweißbild an und berechnet Ihre offizielle Punktzahl. Anschließend können Sie das Bild speichern und zusammen mit Ihrem Code in Ihre Antwort hochladen (da die Zeichenfolgenausgabe nicht in eine Stapelaustauschantwort mit 30.000 Zeichen passt).

Wertung

Der Score eines Bildes ist die Summe der Scores seiner einzelnen Pixel. Der Wert eines einzelnen Pixel ist die Summe der Teilscores für jede der nicht-orthogonal , prime Abstand Pixel , die von sind entgegengesetzte Farbe zu dem Pixel erzielt wird. Der Unterpunkt für jedes derartige Pixel ist, 1/pwo pder Hauptabstand ist.

Im Zusammenhang mit dieser Frage haben die Begriffe die folgenden Definitionen:

• Nicht orthogonal: Ein Pixel ist nicht orthogonal zu dem zu bewertenden Pixel, wenn es sich nicht in derselben Zeile und nicht in derselben Spalte befindet.

• Primabstand: Ein Pixel befindet sich in einem Primabstand von dem zu bewertenden Pixel, wenn sie durch einen euklidischen Abstand getrennt sind, der genau eine Primzahl ist. Insbesondere ist Abstand der Mindestabstand, der toroidal gemessen wird - der obere linke Pixel ist ein Abstandsqrt(2)vom unteren rechten Pixel (alle 4 Kanten werden umbrochen).

• Gegenüberliegende Farbe: Ein Pixel hat eine andere Farbe als das Pixel, das bewertet wird, wenn seine Werte 1 ergeben. Das heißt, das erste ist 0 und das zweite ist 1, oder das erste ist 1 und das zweite ist 0.

Das Stapel-Snippet enthält Beispielcode, der zeigt, wie ein Bild bewertet wird, enthält jedoch keine Optimierungen oder einen effizienten Ansatz, sondern nur den korrekten Code, damit die endgültigen Bilder konsistent bewertet werden können.

Wenn irgendetwas im Code nicht korrekt ist, lass es mich entweder in den Kommentaren oder im Chat wissen .

JavaScript muss nicht unbedingt die beste Sprache sein, um diese besondere Herausforderung zu beantworten . Beachten Sie, dass der Snippet-Code bewusst keine Hinweise auf schnellere Ansätze gibt. Es werden nur Effizienzen eingeführt, die bereits in einer vorhandenen Antwort gezeigt wurden.

Visualisierung

Die zählenden Pixel

Für ein intuitives Gefühl für die Verteilung der Scoring-Pixel sind hier (in Lila) die nicht-orthogonalen Primzahl-Abstandspixel für Pixel (128, 128) eines 256 × 256-Bildes:

Ein zufälliges Bild

Dies ist das zufällig generierte Bild aus der Python 3-Beispielantwort. Es hat eine Punktzahl von 138.267,64 und gibt Ihnen etwas zu schlagen.

Eingang

Der Code erfordert keine Eingabe.

Ausgabe

Der Code sollte eine Zeichenfolge von 65.536 Nullen und Einsen ausgeben, die die Pixel eines 256 x 256-Schwarzweißbilds darstellen. Die Ziffern sollten eine fortlaufende Zeichenfolge ohne Trennzeichen sein. Möglicherweise ist das Kopieren und Einfügen einfacher, wenn Sie in eine Datei ausgeben. Dies liegt jedoch bei Ihnen.

Ihr Code kann auch andere Informationen ausgeben, die Sie nützlich finden, solange die Zeichenfolge kopiert und in das Stapel-Snippet eingefügt werden kann. Beispielsweise möchten Sie möglicherweise in regelmäßigen Abständen die beste bisherige Zeichenfolge in einer Datei und die beste bisherige Punktzahl in STDOUT ausgeben, sodass der Benutzer auswählen kann, wann die Suche gestoppt werden soll.

Stapel-Snippet

Wie von Sp3000 herausgestellt , benötigte das Snippet 10 Minuten, um eine Punktzahl zu berechnen, die selbst für eine absichtlich ineffiziente Referenzimplementierung etwas zu langsam ist. Ich habe in Sp3000 die vorgeschlagene Verbesserung der Vorberechnung der Pixel-Offsets für das Scoring bearbeitet, und es dauert jetzt einige Sekunden, um eine Punktzahl zu berechnen.

canvas = document.getElementById('canvas')
ctx = canvas.getContext('2d')
scoreArea = document.getElementById('scoreArea')
pastedData = document.getElementById('pastedData')
timeout = 0

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499]

primesSquared = []
for (i=0; i<primes.length; i++) {
    primesSquared.push(primes[i] * primes[i])
}

width = canvas.width
height = canvas.height
area = width * height

scoringFilter = calculateScoringFilter()

function calculateScore() {
    var percentage = Math.floor(currentIndex / 65536 * 10000) / 100
    scoreArea.value = 'Calculating:' + percentage + '%'
    for (var t=0; t<1000; t++) {
        if (currentIndex < 65536) {
            partialScore += pixelScore(currentIndex)
            currentIndex += 1
        } else {
            scoreArea.value = 'Score: ' + partialScore
            return
        }
    }
    
    timeout = setTimeout(calculateScore, 10)
}

function pixelScore(i) {
    var score = 0
    var x = i % width
    var y = Math.floor(i / width)
    var a, b, xd, yd, j, k, d, m
    for (k=0; k<scoringFilter.length; k++) {
        bundle = scoringFilter[k]
        m = bundle[0]
        a = m % width
        b = Math.floor(m / width)
        j = ((x+a) % width) + width * ((y+b) % height)
        d = bundle[1]
        score += Math.abs(pixels[i] - pixels[j]) / d
    }
    return score
}

function display(pixels) {
    for (var i=0; i<area; i++) {
        ctx.fillStyle = pixels[i] ? 'white' : 'black'
        ctx.fillRect(i % width, Math.floor(i / width), 1, 1)
    }
}

function stop() {
    clearTimeout(timeout)
    scoreArea.value = 'Calculation cancelled.'
}

function isPrimeSquared(n) {
    return primesSquared.indexOf(n) > -1
}

function applyToImage() {
    var potentialPixels = []
    var pastedString = pastedData.value
    if (pastedString.length !== 65536) {
        scoreArea.value = 'Incorrect length:' + pastedString.length
        return
    }
    var i, digit
    for (i=0; i<pastedString.length; i++) {
        digit = pastedString.substring(i, i + 1)
        if (digit === '0') {
            potentialPixels.push(0)
        } else if (digit === '1') {
            potentialPixels.push(1)
        } else {
            scoreArea.value = 'Invalid character ' + i + ':' + digit
            return
        }
    }
    pixels = potentialPixels
    display(pixels)
    scoreArea.value = 'Calculating score...'
    partialScore = 0
    currentIndex = 0
    
    timeout = setTimeout(calculateScore, 10)
}

function calculateScoringFilter() {
    var scoringFilter = []
    var i, x, y, xd, yd
    for (i=0; i<area; i++) {
        x = i % width
        y = Math.floor(i / width)
        xd = Math.min(x,(-x+width)%width)
        yd = Math.min(y,(-y+height)%height)
        dSquared = xd*xd + yd*yd
        if (xd && yd && isPrimeSquared(dSquared)) {
            d = Math.sqrt(dSquared)
            scoringFilter.push([i, d])
        }
    }
    return scoringFilter
}

<canvas id='canvas' width='256' height='256'></canvas>
<br>
<input id='scoreArea' rows='1' readonly></input>
<br>
<button onclick='applyToImage()'>Apply string to image</button>
<button onclick='stop()'>Stop</button>
<br>
<br>
Paste in string of 65,536 zeroes and ones here:
<br>
<input id='pastedData'></input>

Wenn Sie die Ausgabe oder den Code einer anderen Antwort als Ausgangspunkt für Ihren eigenen Code verwenden, denken Sie bitte daran, das Guthaben anzugeben und auf die entsprechende Antwort zu verweisen. Bei Antworten auf diese Frage muss weder die Beispielantwort noch der Code in der Frage angegeben werden.

Dank an Randall Munroe für den Begriff Nerd Sniping

CJam, Partitur 276496.9062958626

2,128*_(]128*

Es stellt sich als optimal heraus, weil: Es gibt keine nicht-orthogonalen Paare mit Abstand 2. Der Abstand muss also ungerade sein, und ebenso der Abstand zum Quadrat. Da p ² = x ² + y ^{2 ist} , muss eines von x und y (quadriert oder nicht) ungerade und das andere gerade sein. Diese Punkte haben in diesem Bild immer die entgegengesetzte Farbe.

Dies und sein Negativ sind auch die einzig optimalen Lösungen. In einer optimalen Lösung sollten keine nicht orthogonalen Hauptabstandspixel die gleiche Farbe haben. Es gibt diagonal benachbarte gegenüberliegende Pixel wie (3,4) und (4,3). Durch Füllen von Pixeln mit der entgegengesetzten Farbe usw. können wir eine Diagonale mit derselben Farbe erhalten. Ausgehend von jedem Pixel in der Diagonale können alle Antidiagonalen auf dieselbe Weise gefüllt werden. Beachten Sie, dass sie herumlaufen. Es ist jedoch immer noch optimal, wenn dies nicht der Fall ist.

Python 3, Punktzahl 138267.64

Dies ist eine minimale Antwort als Beispiel für das, was benötigt wird, und als etwas zu schlagen ...

Es enthält

• Der Name der Sprache.
• Die Punktzahl aus dem Stack-Snippet in der Frage.
• Das aus dem Stapel-Snippet gespeicherte Bild.
• Der Code, der zum Erzeugen der Zeichenfolge aus 65.536 Nullen und Einsen verwendet wird.

Ausgabe

Code

from random import random

output_string = ''
filename = '65536digits.txt'

for t in range(65536):
    digit = int(random() * 2)
    output_string += str(digit)

with open(filename, 'w') as output_file:
    output_file.write(output_string)

Dies ist nur ein Beispiel. Python ist möglicherweise nicht die beste Sprache für kompetitive Antworten auf diese besondere Herausforderung.