Adjuntar 1009 píxeles

24

La salida es una forma que encierra 1009 píxeles.

  • La forma debe tomar la forma de un solo bucle cerrado, no intersectado.

La entrada es un entero positivo distinto de cero.

  • Cada entrada debe producir una salida única, es decir, cada salida debe ser única de las generadas usando una entrada más baja.

La victoria se decide por el límite de entrada más grande:

  • El límite de entrada de su envío se considera 1 menos que la entrada más baja que proporciona una salida no única o no válida.
  • Por ejemplo, si se produce una salida válida y única para una entrada de 1, 2 o 3 pero no 4, su límite de entrada es 3.

Hay un límite de 1009 bytes en el código fuente. Si hay un empate, la entrada con la menor cantidad de bytes gana.


Restricciones y aclaraciones:

  • El tamaño máximo de una forma es de 109 por 109 píxeles. El tamaño incluye la línea utilizada para dibujar la forma.
  • Una línea es de ancho constante.
  • El espacio cerrado debe estar completamente cerrado por la línea; no puede usar el límite del archivo de imagen.
  • Los 1009 píxeles incluidos se refieren solo al espacio cerrado. No incluye la línea.
  • La salida es una imagen.
  • No hay más restricciones gráficas, por ejemplo, en color, grosor de línea, etc.
  • La singularidad de una salida se refiere solo al espacio cerrado. Los cambios en la línea u otros cambios gráficos son irrelevantes si el espacio cerrado no es único.
  • Una traducción de forma no es única. Las rotaciones, los reflejos y cualquier otra transformación cuentan como únicos.
  • La salida debe ser reproducible: la misma entrada siempre dará la misma salida
  • No es necesario que haya una relación entre salidas, consecutivas o de otro tipo.
  • Fuera del 'límite de entrada' de un envío no hay salida definida.
  • No se permite ninguna otra entrada o recuperación de datos externos.
  • Una línea debe ser continua, es decir, los píxeles deben tocarse (tocar una esquina cuenta).
  • Un píxel es la unidad más pequeña de 'dibujo' utilizada por su método de dibujo, y no necesariamente se corresponde con un píxel de la pantalla.

Ejemplos:

  • Aquí hay un ejemplo de una forma válida:

    ingrese la descripción de la imagen aquí

  • Las siguientes formas no son válidas:

    inválido1 inválido2 inválido3

EDITAR: toque de línea:

  • El espacio cerrado debe ser continuo, que se define como píxeles que se tocan. Tocar esquinas cuenta.
  • Una línea no puede encerrar ningún espacio en su lado exterior. Esta imagen publicada por @Sparr ilustra este punto: solo la primera forma en cada fila es válida:

    conmovedor

  • Los lados exteriores de una línea pueden tocarse, pero no de una manera que encierre el espacio.

  • Las líneas táctiles pueden no solaparse; por ejemplo, dos líneas gruesas de 1 píxel que se tocan tendrían un grosor combinado de 2 px, nunca 1 px.
jsh
fuente
¿Qué pasa con las rotaciones de la misma forma? ¿Son distintos?
Martin Ender
Si le doy un mordisco al costado de la forma, ¿está bien tener una línea frontal (negra) de un píxel de ancho? ¿O tiene que tener 3 píxeles de ancho para que la línea entrante y saliente no se toque? ¿o está bien tener 2 píxeles de ancho, de modo que la línea entrante y saliente se toque, pero no se superponga?
Level River St
Algunas preguntas más: 1. ¿Puede el borde de la imagen 109x109 actuar como un límite de la forma? 2. Si el grosor de la línea depende de mí, ¿puedo decir que son 200 píxeles, de modo que la forma sea solo píxeles blancos en una imagen negra? 3. ¿Está conectada la forma si sus píxeles solo se tocan en una esquina? 4. No soy un gran admirador del límite de personajes. Muchos idiomas pueden usar 3/4 de eso solo para configurar las especificaciones de salida exactas.
Martin Ender
2
Pregunta, ¿cómo obtuviste 1009?
Claudiu
1
¿Cuál de estas formas son válidas y sin agujeros? i.imgur.com/FSV0nHz.png
Sparr

Respuestas:

25

Python + Pycairo, 2 100 formas

Comencemos con lo obvio.

Animación 1

from cairo import *
from sys import argv

n = int(argv[1]) - 1

s = ImageSurface(FORMAT_ARGB32, 109, 109); c = Context(s)
c.set_antialias(ANTIALIAS_NONE); c.set_line_width(1); c.translate(54, 54)
def pixel(x, y): c.rectangle(x, y, 1, 1); c.fill()

W, H, R = 100, 10, 9
X1, Y1 = -W / 2 - 1, -H / 2 - 1
X2, Y2 = X1 + W + 1, Y1 + H + 1

pixel(X2 - 1, Y1)
c.move_to(X1, Y1 + 1); c.line_to(X1, Y2 + 1)
c.move_to(X2 + 1, Y1); c.line_to(X2 + 1, Y1 + R + 1);
c.move_to(X2, Y1 + R + 1); c.line_to(X2, Y2 + 1)
c.stroke()

for i in xrange(W):
    offset = (n >> i) & 1
    for y in Y1, Y2: pixel(X1 + i, y + offset)

s.write_to_png("o.png")

Toma el número en la línea de comando y escribe o.png.

Ana
fuente
Muy agradable. Idea simple, bien ejecutada. No será el puntaje ganador, pero establece un buen listón para futuras entradas.
Sparr
... * 2, comoRotations [...] count as unique.
edc65
@ edc65: En realidad * 4, ya que no es simétrico.
justhalf
19

BBC Basic, puntaje 10 ^ 288 (menos 1 si no se cuenta cero)

Descargue interepreter en http://sourceforge.net/projects/napoleonbrandy/ (no es mi intérprete básico habitual de la BBC, ese no es compatible con cadenas lo suficientemente largas).

Para codificar mucha información, necesita una gran cantidad de perímetro. Eso significa una forma delgada. Comienzo con una barra vertical de 49 píxeles a la izquierda y le agrego diez tentáculos de 96 píxeles. Cada tentáculo puede codificar 96 bits de manera similar a la solución de @ ell, un total de 960 bits.

Como BBC Basic no puede manejar números tan grandes, se ingresa un número de hasta 288 dígitos decimales como una cadena, y cada conjunto de 3 dígitos decimales se convierte en un número binario de 10 bits. Cada bit se usa para mover uno de los tentáculos un píxel hacia arriba si es un 1(pero no si es un 0.) El programa puede manejar hasta 288/3 = 96 conjuntos de 3 dígitos

    1MODE1:VDU19,0,7;0;19,15,0;0;               :REM select an appropriate screen mode and change to black drawing on white background
   10INPUT a$
   20a$=STRING$(288-LEN(a$)," ")+a$             :REM pad input up to 288 characters with leading spaces
   50RECTANGLE0,0,8,200                         :REM draw a rectangle at the left, enclosing 49 pixels
   60FOR n=0 TO 95
   70  b=VAL(MID$(a$,n*3+1,3))                  :REM extract 3 characters from a$ and convert to number
   80  FOR m=0 TO 9                             :REM plot the ten tentacles
   90    PLOT71,n*4+8,m*20+8+(b/2^m AND 1)*4    :REM plot (absolute coordinates) a background colour pixel for tentacle m at horizontal distance n
  100    POINT BY 0,-4                          :REM offsetting vertically by 1 pixel according to the relevant bit of b
  110    POINT BY 4,4
  120    POINT BY -4,4                          :REM then plot foreground colour pixels (relative coordinates) above, below and to the right.
  130  NEXT
  140NEXT

Salida

Una salida típica para un número de 288 dígitos. Tenga en cuenta que 999 es 1111100111 en binario. Puedes ver cómo los conjuntos de 9 dígitos hacen que los tentáculos se ondulen.

ingrese la descripción de la imagen aquí

Tecnicismos

A. La respuesta al punto 3 de Martin "¿está conectada la forma si su píxel se toca solo a lo largo de una esquina?" fue "sí", así que entiendo que mi respuesta cumple. Sin embargo, si alterna (por ejemplo) 999 y 000 en cada fila, se verá muy ocupado.

B. Si vemos esto como un rectángulo con mordidas sacadas del costado, puedes ver que permití tres píxeles entre cada par de tentáculos adyacentes, para asegurar que la línea negra alrededor del exterior nunca se toque. No hay una regla específica sobre esto (espero que mi razón para preguntar sea más clara a la luz de mi respuesta). Si se permite que la línea se toque en el EXTERIOR de la forma, podría mover los tentáculos juntos y usar menos píxeles para la barra vertical (y así hacer que los tentáculos sean un poco más largos). Sin embargo, sería muy confuso determinar a simple vista si un píxel estaba dentro o fuera de la forma, por lo que creo que mi interpretación de que el exterior de la línea negra nunca debería tocarse en sí es lo mejor.

C. BBC basic en este modo de pantalla trata un cuadrado de 2x2 píxeles de pantalla como un solo píxel. Lo dejé como está, porque ayuda a ver si la forma no es demasiado pequeña. Cada uno de estos píxeles básicos de la BBC se considera como una caja de unidades lógicas 4x4. Desde el principio, los desarrolladores de BBC basic tuvieron la previsión de darse cuenta de que un día las resoluciones de pantalla aumentarían, por lo que hicieron que la resolución lógica fuera más alta que la resolución física.

Level River St
fuente
R: La respuesta sigue siendo "sí", aunque ahora veo que es un poco extraño. B. Ahora veo tu punto y he hecho una edición para aclarar, perdón por la confusión.
jsh
C: Eso no es un problema. Un píxel ahora se define como la unidad de dibujo más pequeña utilizada.
jsh
6

Mathematica, 496 bytes, Puntuación: large-ish (> 1157)

El límite inferior que tengo allí es ridículamente bajo, pero aún no he encontrado una mejor manera que la fuerza bruta para verificar.

SeedRandom@Input[];
g = 0 &~Array~{109, 109};
g[[2, 2]] = 1;
h = {{2, 2}};
For[n = 1, n < 1009,
  c = RandomChoice@h;
  d = RandomChoice[m = {{1, 0}, {0, 1}}];
  If[FreeQ[e = c + d, 1 | 109] && 
    Count[g[[2 ;; e[[1]], 2 ;; e[[2]]]], 0, 2] == 1,
   ++n;
   h~AppendTo~e;
   g[[## & @@ e]] = 1
   ];
  ];
(
    c = #;
    If[e = c + #; g[[## & @@ e]] < 1,
       g[[## & @@ e]] = 2
       ] & /@ Join @@ {m, -m}) & /@ h;
ArrayPlot[g, ImageSize -> 109, PixelConstrained -> True, 
 Frame -> 0 > 1]

Todavía no he jugado golf, porque no había necesidad de hacerlo. Lo haré una vez que alguien demuestre que en realidad están empatando conmigo.

Básicamente, el algoritmo está haciendo un relleno de inundación desde la esquina superior izquierda de la imagen de 109x109 (desplazado por un píxel para permitir la línea) y cuando he inundado 1009 celdas, me detengo y marco el borde. Dijiste que los colores dependen de nosotros, por lo que el fondo es blanco, la línea es negra y el interior es gris (si es necesario, puedo quitar el gris para un puñado de caracteres).

El relleno de inundación es bastante limitado, pero eso asegura que no tenga que preocuparme por los agujeros. Relajar estas restricciones probablemente aumentará dramáticamente mi puntaje (aún desconocido).

Trataré de poner algunos límites inferiores en la puntuación ahora.

Martin Ender
fuente
¿Puede proporcionar un archivo CDF para que pueda probar esto?
jsh
1
@jsh Prueba esto
Martin Ender
Creo que todas las soluciones que dependen de números aleatorios requerirán una fuerza bruta para validar. No estoy seguro de si está haciendo una verificación de píxel por píxel, pero podría intentar guardar cada salida en un mapa de bits monocromático (tamaño de archivo pequeño) y comparar los hashes. Me imagino que es tan rápido como lo harás para las comparaciones de imágenes.
stokastic
@stokastic Actualmente estoy construyendo un hash muy ingenuo (suma de todas las coordenadas de píxeles), y luego estoy revisando los contenedores colisionantes en detalle. El problema es que, no importa cuán sofisticado sea el enfoque que utilizo para la verificación de colisiones, el método de generación es tan lento que ni siquiera podré resolver más de unas pocas semillas de 10k o 100k en un tiempo razonable. Sin embargo, creo que hay varias formas de acelerar considerablemente el algoritmo, por lo que podría analizarlo en algún momento.
Martin Ender
@ MartinBüttner Probablemente ya lo haya probado (o Mathica no lo admite), pero un hash de archivo directo podría ser más rápido. Solo una sugerencia si no lo has intentado.
estocástico
1

Python 2, Puntuación> 10 ^ 395

Es extremadamente lento, y en realidad no he logrado obtener ningún resultado que no sea n = 0, pero si quieres probarlo más bajo SIZE (el número de píxeles) y BOUNDla longitud lateral máxima del cuadrado delimitador, debería poder para obtener muchos resultados Fue muy difícil tratar de calcular cuántos produciría; Estoy bastante seguro de que el límite inferior que doy es exacto, pero sospecho que el recuento real es significativamente mayor, y puedo tratar de mejorarlo más adelante.

import sys
import pygame
sys.setrecursionlimit(1100)

def low(s):
    return min(sum(e[1] for e in s[:i+1]) for i in range(len(s)))
def high(s):
    return max(sum(e[1] for e in s[:i+1])+s[i][0] for i in range(len(s)))

BOUND = 109
SIZE = 1009

def gen(n,t=0):
    if n <= (BOUND-t)*BOUND:
        for i in range(1,min(n,BOUND)):
            for r in gen(n-i,t+1):
                a,b=r[0]
                for x in range(max(1-a,high(r)-low(r)-BOUND),i):
                    yield [(i,0),(a,x)]+r[1:]
        yield [(n,0)]

def create(n):
    g=gen(SIZE)
    for i in range(n+1):shape=g.next()
    s=pygame.Surface((BOUND+2,BOUND+2))
    l=low(shape);x=0
    for y,(t,o) in enumerate(shape):
        x+=o;pygame.draw.line(s,(255,255,255),(x-l+1,y+1),(x-l+t,y+1))
    out=[]
    for x in range(BOUND+2):
        for y in range(BOUND+2):
            if all((0,0,0)==s.get_at((x+dx,y+dy))for dx,dy in[(-1,0),(1,0),(0,-1),(0,1)]if 0<=x+dx<BOUND+2 and 0<=y+dy<BOUND+2):
                out.append((x,y))
    for x,y in out:
        s.set_at((x,y),(255,255,255))
    pygame.image.save(s,"image.png")
KSab
fuente
2
¿Puedes dar la imagen n=0? ¿Y también puedes explicar cómo logras 10 ^ 395?
justhalf