태그 보관물: primes

primes

프라임 얼간이 저격 패턴 currentIndex

일년 중 가장 긴 날-여기 여분의 시간을 낭비하는 것이 있습니다 …


개요

이것은 인기 경연 대회가 아니며 그래픽 출력 문제가 아닙니다. 65,536 개의 0과 1의 문자열 만 출력하면됩니다. 질문 하단의 스택 스 니펫은 이것을 256 x 256 흑백 이미지로 표시하고 공식 점수를 계산합니다. 그런 다음 이미지를 저장하고 코드와 함께 답변에 업로드 할 수 있습니다 (문자열 출력이 30,000 자의 스택 교환 답변에 맞지 않기 때문에).


채점

이미지의 점수는 개별 픽셀의 점수의 합계입니다. 개별 픽셀의 점수는 각 영역 점수의 합 비 직교 , 프라임 거리 의 픽셀 만 반대 색상 획득되는 화소. 이러한 각 화소에 대한 부분 점수는 1/p여기서 p프라임 거리이다.

이 질문의 맥락에서 용어는 다음과 같은 정의를 갖습니다.

  • 비 직교 : 픽셀이 같은 행에 있지 않고 같은 열에 있지 않으면 픽셀이 스코어링되는 픽셀과 직교하지 않습니다.

  • 프라임 거리 : 픽셀이 정확하게 소수 인유클리드 거리로 분리 된 경우 픽셀은 스코어링되는 픽셀과 프라임 거리에 있습니다. 특히, 거리는 환상적으로 측정 된 최소 거리입니다. 왼쪽 위 픽셀은sqrt(2)오른쪽 아래픽셀과의 거리입니다(모든 4 개의 가장자리 랩).

  • 반대 색상 : 픽셀의 값이 1 인 경우 스코어링되는 픽셀과 반대 색상입니다. 즉, 첫 번째는 0이고 두 번째는 1이거나 첫 번째는 1이고 두 번째는 0입니다.

스택 스 니펫에는 이미지의 점수를 매기는 방법을 보여주는 예제 코드가 포함되어 있지만 최적화 또는 효율적인 접근 방법은 포함되어 있지 않으며 코드 만 수정하면 최종 이미지의 점수를 일관되게 수행 할 수 있습니다.

코드의 내용이 정확하지 않은 경우 의견이나 채팅으로 알려주십시오 .

JavaScript 가이 특정 도전 에 대답 하기위한 최상의 언어 일 필요는 없습니다 . Snippet 코드는 의도적으로 더 빠른 접근 방식에 대한 단서를 제공하지 않습니다. 기존 답변에서 이미 입증 된 효율성 만 소개 할 것입니다.


심상

스코어링 픽셀

스코어링 픽셀의 분포에 대한 직관적 인 느낌을주기 위해, 여기 (보라색)는 256 x 256 이미지의 픽셀 (128, 128)에 대한 비 직교 주요 거리 픽셀입니다.

비 직교 주요 거리 분포 이미지


임의의 이미지

이 예제는 Python 3 답변 예제에서 임의로 생성 된 이미지입니다. 그것은 138,267.64의 점수를 가지고 있으며 당신에게 이길 수 있습니다.


입력

코드는 입력이 필요하지 않습니다.

산출

이 코드는 흑백 256 x 256 이미지의 픽셀을 나타내는 65,536 개의 0과 1의 문자열을 출력해야합니다. 숫자는 구분 기호가없는 연속 문자열이어야합니다. 파일로 출력하면 복사 및 붙여 넣기가 더 쉬울 수 있지만 이는 사용자에게 달려 있습니다.

문자열을 복사하여 스택 스 니펫에 붙여 넣을 수 있으면 코드에서 유용한 다른 정보를 출력 할 수도 있습니다. 예를 들어, 가장 좋은 문자열을 파일에 출력하고 가장 좋은 스코어를 정기적으로 STDOUT에 출력하여 사용자가 검색을 중지 할시기를 선택할 수 있습니다.


스택 스 니펫

Sp3000 에서 지적했듯이 스 니펫은 점수를 계산하는 데 10 분이 걸렸으며 , 의도적으로 비효율적 인 참조 구현의 경우에도 너무 느립니다. Sp3000에서 스코어링을위한 픽셀 오프셋 사전 계산의 개선 제안을 편집했으며 이제 스코어를 계산하는 데 몇 초가 걸립니다.

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>

자신의 코드의 시작점으로 출력 또는 다른 답변의 코드를 사용하는 경우 지원 답변에 대한 크레딧과 링크를 제공해야합니다. 이 질문에 대한 답변은 예제 답변이나 질문의 ​​코드를 가리지 않아도됩니다.

Nerd Sniping 이라는 용어로 Randall Munroe의 크레딧



답변

CJam, 276496.9062958626 점

2,128*_(]128*

거리가 2 인 직교가 아닌 쌍이 ​​없기 때문에 거리가 홀수 여야하며 거리도 제곱입니다. p 2 = x 2 + y 2 이므로 x와 y (제곱 여부) 중 하나는 홀수 여야하고 다른 하나는 짝수 여야합니다. 이러한 점은이 이미지에서 항상 반대 색상입니다.

이것과 그것의 부정적인 것만이 유일한 최적의 솔루션입니다. 최적의 솔루션에서 직교하지 않은 기본 거리 픽셀의 색상은 동일하지 않아야합니다. (3,4) 및 (4,3)과 같이 대각선으로 인접한 반대 픽셀이 있습니다. 반대 색상 등의 픽셀을 채움으로써 같은 색상의 대각선을 얻을 수 있습니다. 대각선의 각 픽셀에서 시작하여 모든 대각 대각선을 같은 방식으로 채울 수 있습니다. 그것들은 둘러 싸여 있습니다. 그래도 그래도 최적입니다.


답변

Python 3, 138267.64 점

이것은 필요한 것의 예와 이길만한 최소한의 대답입니다 …

그것은 포함

  • 언어 이름.
  • 질문의 스택 스 니펫 점수입니다.
  • 이미지가 스택 스 니펫에서 저장되었습니다.
  • 이 코드는 65,536 개의 0과 1의 문자열을 생성하는 데 사용됩니다.

산출

암호

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)

이것은 단지 예일뿐입니다. 파이썬이 반드시이 특정 도전에 대한 경쟁적인 답변에 가장 적합한 언어는 아닙니다.


답변