17
\$\begingroup\$

Longest day of the year - here's something to waste the extra time...


Overview

Note this is not a popularity contest and not a graphical output challenge - you are only required to output a string of 65,536 zeroes and ones. The Stack Snippet at the bottom of the question will display this as a 256 by 256 black and white image and calculate your official score. You can then save the image and upload it to your answer alongside your code (since the string output will not fit in a 30,000 character Stack Exchange answer).


Scoring

The score of an image is the sum of the scores of its individual pixels. The score of an individual pixel is the sum of the subscores for each of the non-orthogonal, prime distance pixels that are of opposite colour to the pixel being scored. The subscore for each such pixel is 1/p where p is the prime distance.

In the context of this question, the terms have the following definitions:

  • Non-orthogonal: A pixel is non-orthogonal to the pixel being scored if it is not in the same row and is not in the same column.

  • Prime distance: A pixel is at a prime distance from the pixel being scored if they are separated by a Euclidean distance that is exactly a prime number. In particular, distance is the minimum distance measured toroidally - the top left pixel is a distance of sqrt(2) from the bottom right pixel (all 4 edges wrap).

  • Opposite colour: A pixel is of opposite colour to the pixel being scored if their values sum to 1. That is, the first is 0 and the second is 1, or the first is 1 and the second is 0.

The Stack Snippet includes example code that shows how to score an image, but does not include any optimisations or an efficient approach, just correct code so scoring of final images can be done consistently.

If anything in the code is not correct, please let me know either in the comments or in chat.

JavaScript may not necessarily be the best language for answering this particular challenge. Note that the Snippet code deliberately gives no clues as to faster approaches. It will only have efficiencies introduced that have already been demonstrated in an existing answer.


Visualisation

The scoring pixels

For an intuitive feel for the distribution of the scoring pixels, here (in purple) are the non-orthogonal prime distance pixels for pixel (128, 128) of a 256 by 256 image:

image of non-orthogonal prime distance distribution


A random image

This is the randomly generated image from the example Python 3 answer. It has a score of 138,267.64 and gives you something to beat.

randomly generated image


Input

The code does not require input.

Output

The code should output a string of 65,536 zeroes and ones, representing the pixels of a black and white 256 by 256 image. The digits should be a continuous string, with no separators. You may find copying and pasting easier if you output to a file, but this is up to you.

Your code may also output other information that you find useful, as long as the string can be copied and pasted into the Stack Snippet. For example, you may wish to output the best yet string to a file and the best yet score to STDOUT at regular intervals, allowing the user to choose when to stop the search.


Stack Snippet

As pointed out by Sp3000, the snippet was taking 10 minutes to calculate a score, which is a little too slow, even for a deliberately inefficient reference implementation. I've edited in Sp3000's suggested improvement of precomputing the pixel offsets for the scoring, and it now takes a few seconds to calculate a score.

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>


If you use the output or the code of another answer as the starting point for your own code, please remember to give credit and link to the supporting answer. Answers to this question do not need to credit the example answer or the code in the question.

Credit to Randall Munroe for the term Nerd Sniping

\$\endgroup\$
36
+150
\$\begingroup\$

CJam, score 276496.9062958626

2,128*_(]128*

It turns out to be optimal, because: There aren't any non-orthogonal pairs with distance 2. So the distance must be odd, and so is the distance squared. As p2=x2+y2, one of x and y (squared or not) must be odd, and the other must be even. Those points are always in the opposite color in this image.

This and its negative are also the only optimal solutions. In an optimal solution, no non-orthogonal, prime distance pixels should have the same color. There are diagonally adjacent opposite pixels like (3,4) and (4,3). By filling pixels of the opposite of opposite color, etc, we can get a diagonal with the same color. Starting from each pixel in the diagonal, we can get all the anti-diagonals filled in the same way. Note that they wrap around. It is still optimal if they don't, though.

\$\endgroup\$
  • 3
    \$\begingroup\$ I was hoping it would take longer for people to notice that... \$\endgroup\$ – trichoplax Jun 21 '15 at 16:28
  • 1
    \$\begingroup\$ It took me a long time to work out that there was an optimal solution when writing this question, so I thought it would be worth posting as a challenge. How did you see it so quickly? Was it just obvious or did you have a particular thought process? \$\endgroup\$ – trichoplax Jun 21 '15 at 16:43
  • 4
    \$\begingroup\$ P.S. I don't know what time you saw this question but an optimal solution 71 minutes after the question was posted is deserving of a bounty - I'll just have to wait 2 days before I can assign it... \$\endgroup\$ – trichoplax Jun 21 '15 at 16:45
  • \$\begingroup\$ @trichoplax From your first image, it seemed there are many points in the same diagonal. I was thinking of using wider stripes at the beginning. And then I opened Gimp to verify my idea. And to my surprise, I got a completely black image when I filled it with this pattern. \$\endgroup\$ – jimmy23013 Jun 21 '15 at 16:51
  • 8
    \$\begingroup\$ @trichoplax Given that you knew there was an optimal solution, I think you would have been better off revising the question to make it less solvable. Though jimmy23013 found it fast, it's always a matter of time until someone finds it, and then it's over. \$\endgroup\$ – xnor Jun 21 '15 at 20:24
1
\$\begingroup\$

Python 3, score 138267.64

This is a minimal answer as an example of what is required, and as something to beat...

It includes

  • The language name.
  • The score from the Stack Snippet in the question.
  • The image saved from the Stack Snippet.
  • The code used to produce the string of 65,536 zeroes and ones.

Output

randomly generated image

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)

This is just an example. Python may not necessarily be the best language for competitive answers to this particular challenge.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.