Najdłuższy dzień w roku - oto coś do stracenia dodatkowego czasu ...

Przegląd

Pamiętaj, że nie jest to konkurs popularności, a nie graficzne wyzwanie wyjściowe - musisz jedynie wygenerować ciąg 65 536 zer i jedynek. Fragment kodu w dolnej części pytania wyświetli to jako czarno-biały obraz 256 na 256 i obliczy Twój oficjalny wynik. Następnie możesz zapisać obraz i przesłać go do swojej odpowiedzi wraz ze swoim kodem (ponieważ wynik łańcucha nie mieści się w 30 000-znakowej odpowiedzi Stack Exchange).

Punktacja

Wynik obrazu jest sumą wyników jego poszczególnych pikseli. Wynik danego piksela jest sumą podwyników dla każdego z non-prostopadłych , prime odległości pikseli, które są przeciwnego koloru na piksel jest punktowane. Wynik dla każdego takiego piksela to miejsce, w 1/pktórym pznajduje się główna odległość.

W kontekście tego pytania terminy mają następujące definicje:

• Nie-ortogonalny: piksel nie jest ortogonalny w stosunku do ocenianego piksela, jeśli nie znajduje się w tym samym rzędzie i nie znajduje się w tej samej kolumnie.

• Główna odległość: piksel znajduje się w największej odległości od punktowanego piksela, jeśli dzieli je odległość euklidesowa, która jest dokładnie liczbą pierwszą. W szczególności odległość to minimalna odległość mierzona toroidalnie - lewy górny piksel to odległośćsqrt(2)od prawego dolnego piksela (wszystkie 4 krawędzie zawinięcia).

• Kolor przeciwny: piksel ma kolor przeciwny do piksela ocenianego, jeśli ich wartości sumują się do 1. Oznacza to, że pierwszy to 0, a drugi to 1 lub pierwszy to 1, a drugi to 0.

Fragment kodu zawiera przykładowy kod pokazujący sposób oceniania obrazu, ale nie zawiera żadnych optymalizacji ani skutecznego podejścia, wystarczy poprawny kod, aby można było konsekwentnie oceniać końcowe obrazy.

Jeśli cokolwiek w kodzie jest nieprawidłowe, daj mi znać albo w komentarzach, albo na czacie .

JavaScript nie musi być najlepszym językiem do odbierania tego szczególne wyzwanie. Pamiętaj, że kod Snippet celowo nie daje wskazówek co do szybszych podejść. Będzie miał tylko wprowadzone wydajności, które zostały już wykazane w istniejącej odpowiedzi.

Wyobrażanie sobie

Punktowane piksele

Dla intuicyjnego wyczucia rozkładu pikseli punktowanych tutaj (na fioletowo) są nieortogonalne piksele o podstawowej odległości dla piksela (128, 128) obrazu 256 na 256:

Losowy obraz

Jest to losowo generowany obraz z przykładowej odpowiedzi w języku Python 3. Ma wynik 138 267,64 i daje ci coś do pokonania.

Wejście

Kod nie wymaga wprowadzania danych.

Wynik

Kod powinien generować ciąg 65 536 zer i jedynek, reprezentujących piksele czarno-białego obrazu 256 na 256. Cyfry powinny być ciągiem ciągłym, bez separatorów. Kopiowanie i wklejanie może być łatwiejsze, jeśli wyprowadzasz dane do pliku, ale to zależy od ciebie.

Twój kod może także wyświetlać inne informacje, które okażą się przydatne, o ile ciąg będzie można skopiować i wkleić do fragmentu kodu. Na przykład możesz chcieć wyprowadzać najlepszy ciąg znaków do pliku, a najlepszy jak dotąd wynik do STDOUT w regularnych odstępach czasu, pozwalając użytkownikowi wybrać, kiedy zatrzymać wyszukiwanie.

Fragment kodu

Jak wskazał Sp3000 , fragment kodu potrzebował 10 minut na obliczenie wyniku, który jest nieco zbyt wolny, nawet w przypadku celowo nieefektywnej implementacji referencyjnej. Zredagowałem w sugerowanej przez Sp3000 poprawie wstępnego obliczania przesunięć pikseli dla punktacji, a teraz obliczenie wyniku zajmuje kilka sekund.

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>

Jeśli wykorzystasz wynik lub kod innej odpowiedzi jako punkt wyjścia dla własnego kodu, pamiętaj o podaniu kredytu i linku do odpowiedzi uzupełniającej. Odpowiedzi na to pytanie nie muszą podawać przykładowej odpowiedzi ani kodu w pytaniu.

Podziękowania dla Randalla Munroe za termin Nerd Sniping

CJam, wynik 276496,9062958626

2,128*_(]128*

Okazuje się, że jest optymalny, ponieważ: Nie ma żadnych nieortogonalnych par o odległości 2. Zatem odległość musi być nieparzysta, podobnie jak odległość do kwadratu. Ponieważ p ² = x ² + y ² , jeden z xiy (kwadrat lub nie) musi być nieparzysty, a drugi musi być parzysty. Punkty te są zawsze w przeciwnych kolorach na tym obrazie.

To i jego minus są również jedynymi optymalnymi rozwiązaniami. W optymalnym rozwiązaniu żadne nieortogonalne piksele o pierwotnej odległości nie powinny mieć tego samego koloru. Są po przekątnej sąsiadujące przeciwległe piksele, takie jak (3,4) i (4,3). Wypełniając piksele przeciwnego przeciwnego koloru itp., Możemy uzyskać przekątną tego samego koloru. Zaczynając od każdego piksela po przekątnej, możemy wypełnić wszystkie anty-przekątne w ten sam sposób. Pamiętaj, że się owijają. Jednak nadal jest optymalne, jeśli nie.

Python 3, wynik 138267,64

To minimalna odpowiedź jako przykład tego, co jest wymagane i jako coś do pokonania ...

Obejmuje

• Nazwa języka
• Wynik z fragmentu stosu w pytaniu.
• Obraz zapisany z fragmentu stosu.
• Kod użyty do wygenerowania ciągu 65 536 zer i jedynek.

Wynik

Kod

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)

To tylko przykład. Python niekoniecznie jest najlepszym językiem dla konkurencyjnych odpowiedzi na to szczególne wyzwanie.