Este es un problema autorreferencial

49

Fórmula autorreferencial de Tupper (copiada de Wikipedia)

La fórmula autorreferencial de Tupper es una fórmula definida por Jeff Tupper que, cuando se representa en dos dimensiones en una ubicación muy específica en el plano, se puede "programar" para reproducir visualmente la fórmula en sí. Se utiliza en varios cursos de matemática y ciencias de la computación como un ejercicio de fórmulas gráficas.

Fórmula autorreferencial de Tupper

¿Dónde suelo está la función del piso?

Sea kel siguiente número de 543 dígitos: 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719

Si uno gráficas El conjunto de puntos (x, y)en 0 <= x < 106y k <= y < k + 17que satisface la desigualdad dada anteriormente, las miradas gráfico resultante de este tipo (nota que los ejes en esta parcela se han invertido, de lo contrario la imagen se revele boca abajo):

Resultado de la fórmula autorreferencial de Tupper

¿Y qué?

Lo interesante de esta fórmula es que se puede usar para graficar cualquier imagen posible de 106x17 en blanco y negro. Ahora, buscar en realidad sería extremadamente tedioso, por lo que hay una manera de averiguar el valor k donde aparece su imagen. El proceso es bastante simple:

  1. Comience desde el píxel inferior de la primera columna de su imagen.
  2. Si el píxel es blanco, se agregará un 0 al valor k. Si es negro, agregue un 1.
  3. Mueva hacia arriba la columna, repitiendo el paso 2.
  4. Una vez al final de la columna, pase a la siguiente columna y comience desde abajo, siguiendo el mismo proceso.
  5. Después de analizar cada píxel, convierta esta cadena binaria a decimal y multiplique por 17 para obtener el valor k.

¿Cual es mi trabajo?

Su trabajo es crear un programa que pueda tomar cualquier imagen de 106x17 y generar su valor k correspondiente. Puede hacer los siguientes supuestos:

  1. Todas las imágenes serán exactamente 106x17
  2. Todas las imágenes solo contendrán píxeles negros (# 000000) o blancos (#FFFFFF), nada en el medio.

También hay algunas reglas:

  1. La salida es simplemente el valor k. Debe estar en la base adecuada, pero puede estar en cualquier formato.
  2. Las imágenes deben leerse desde PNG o PPM.
  3. No hay lagunas estándar.

Imágenes de prueba

[ Nintendo] debería producir ~ 1.4946x10 542

[ Un gran número] debería producir ~ 7.2355x10 159

[ 2 ^ 1801 * 17] debería producir 2 1801 * 17

[ 2 ^ 1802 - 1 * 17] debería producir (2 1802 -1) * 17

Echa un vistazo a este Gist para las soluciones exactas.

Este es el , por lo que gana el menor número de bytes.


Enlaces Útiles

Wikipedia

Wolfram Mathworld

Kade
fuente
¿Puedo tomar un PPM?
Maltysen
EDITAR: Sí, se permite el formato PPM. Cuando se me ocurrió el programa, pretendía que se utilizaran PNG, pero permitir que PPM permitiera la participación de más idiomas de golf.
Kade
3
Mientras leía esta pregunta, antes de llegar a la parte "Cuál es mi trabajo", estaba seguro de que veré la palabra en quinealguna parte.
Jacob
No voy a pretender ser un programador que puede hacer este tipo de cosas, sino que simplemente presentaré una pregunta inocente y sincera: Sí, pero ¿se puede hacer a la inversa? Es decir, ¿alimentar en la solución y ver el * .png generado como resultado?
@NotAsSharpAsYouGuys: si tiene una aritmética de precisión arbitraria, es trivial, solo tiene que verificar el resultado de esa fórmula para cada píxel y generar la imagen resultante.
Matteo Italia

Respuestas:

12

CJam, 16

l,l~q:~f*/W%ze_b

Con muchas gracias a Dennis. Pruébalo en línea

En caso de que tenga problemas con la URL, esta es la entrada que probé:

P1
106 17
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000011111100000000000000000000000
0000000000000000000000000000000000000000000000000000000000000111111000
0000011111100110000000000000000000000000000000000000000000000000000000
0000000000000000000000000110011111100000100111100001000000000000001100
0110000000000000000000000000000000000000000000000000000000001000011110
0100010011111100001000000000000100101001110000000000000000000000000000
0011000000000000000000000100001111110010010110000110001000000000000100
0110010010000000011000000000000000000100100000000000000000000100011000
0110101111000000111111000000000001000110010011111100100100111001111100
0111001011110000000000000011111100000011111111000000110111000000000001
0000100111100000110000110001100000101000001100001000000000000011101100
0000111110110000001000010000000000010010000100100110011001100100100110
0100110010011001000000000000100001000000110110011000011000010000000000
0100110001001001100110011000001001100100110010011001000000000000100001
1000011001100111111111001100000000000100110001001001100110011001111001
1001001100100110010000000000001100111111111001101111111111111100000000
0001001010010010011001100101000110011001100000110000100000000000001111
1111111111010111001001001110000000000000110001101101100110011000111001
1001100111110011110000000000000001110010010011100010001001000100000000
0000000000000000000000000000000000000000000000000000000000000000000000
1000100100010000100000000001000000000000000000000000000000000000000000
0000000000000000000000000000000000001000000000010000010000000010000000
0000000000000000000000000000000000000000000000000000000000000000000000
0001000000001000000011111111000000000000000000000000000000000000000000
0000000000000000000000000000000000000000111111110000

Usé el formato que GIMP generó al exportar como ASCII pbm, con el comentario eliminado.

Explicación:

l,    read the first line ("P1" magic number) and get its length (2)
l~    read and evaluate the second line (106 17)
q     read the rest of the input (actual pixels)
:~    evaluate each character ('0' -> 0, '1' -> 1, newline -> nothing)
f*    multiply each number by 17
/     split into rows of length 106
W%    reverse the order of the rows
z     transpose
e_    flatten (effectively, concatenate the lines)
      now we have all the pixels in the desired order, as 0 and 17
b     convert from base 2 "digits" to a number
aditsu
fuente
Lo tengo en la URL para ti.
mbomb007
@ mbomb007 gracias, no estoy seguro de qué salió mal.
aditsu
Si no tiene que lidiar con los comentarios, l;l~\qN-/W%zs:~2b*debería funcionar igual de bien.
Dennis
@Dennis OMG, hay varios niveles de brillo allí :) ¿Quieres publicarlo tú mismo?
aditsu
No creo que una respuesta por separado sea lo suficientemente diferente de la suya.
Dennis
17

Pyth - 21 bytes

Simple de hacer con la iconversión de base de pyth . Toma la entrada como PBMnombre de archivo y lee usando el 'comando. Tuve que usar !Mpara negar negros y blancos. Todo lo demás se explica por sí mismo.

*J17i!MsC_cJrstt.z7 2

Pruébalo aquí en línea . (El intérprete web no puede leer archivos, por lo que se modifica y toma el archivo como entrada).

Maltysen
fuente
6060
No creo que nada en Pyth se explique por sí mismo. : /
Alex A.
3
Ningún idioma que conozca puede vencer a este. Pero, de nuevo, ninguno de los idiomas que conozco son "hechos para jugar al golf".
Mahesh
No se puede abrir el enlace, el camino es demasiado largo, dang (Safari 8.1)
Kametrixom
Tu imagen de ejemplo parece incorrecta. ¿Querías usar P2 en lugar de P3?
aditsu
Oh, espera, ni siquiera es P2, parece P1 pero está invertido
aditsu
9

Python 2: 133 110 bytes

Un primer intento en python usando PIL:

from PIL.Image import*
j=open(input()).load()
a=k=0
while a<1802:k=(j[a/17,16-a%17][0]<1)+k*2;a+=1
print k*17

Gracias a los comentarios útiles a continuación

joc
fuente
2
como solo usa una vez Image.open (input ()). load y no se ve como si lo estuviera modificando, ¿no sería mejor usarlo como está, en lugar de usar una var j? sería algo asífrom PIL import Image k=0 for a in range(1802):y=a%17;x=a/17;k=(0 if Image.open(input()).load()[x,16-y][0]else 1)+k*2 print k*17
Katenkyo
3
Continuando con el punto de @Katenkyo, también puede simplemente conectarse a/17y ubicarse a%17en los lugares apropiados, y puede abusar del hecho de que 1 es verdadero y 0 es falso. Aquí está el resultado de estos cambios, bajará a 111 bytes :)
Kade
@Kateyenko, lamentablemente input()se llama en cada iteración del bucle con esa modificación. Sin embargo, editando con otros consejos, gracias.
joc
1
(...<1) --> 0**...¿tal vez?
Sp3000
7

C #, 199

¡Esto fue divertido! No hay nada de malo en recargar un mapa de bits 106 * 17 veces, ¿verdad? Lo hice como una función para guardar algunos bytes, no estoy seguro si eso es legal.

BigInteger s(string i){return (Enumerable.Range(0,106).SelectMany(x=>Enumerable.Range(0,17).Select(y=>new BigInteger(new Bitmap(i).GetPixel(x,y).B==0?1:0)).Reverse()).Aggregate((x,y)=>(x<<1)+y)*17);}

i es el nombre del archivo de entrada.

Además, como una sola expresión, solo porque es una expresión, con iprovisto o subbed (167 bytes)

(Enumerable.Range(0,106).SelectMany(x=>Enumerable.Range(0,17).Select(y=>new BigInteger(new Bitmap(i).GetPixel(x,y).B==0?1:0)).Reverse()).Aggregate((x,y)=>(x<<1)+y)*17)
DLeh
fuente
1
La pregunta dice "su trabajo es crear un programa ..."
Sean Latham
1

Mathematica 69 Bytes

17*FromDigits[1-Flatten[Reverse/@Transpose[ImageData@Binarize@#]],2]&

Binarize @ se puede omitir si la imagen tiene formato monocromo.

Esta función reproducirá la imagen:

   ArrayPlot[Table[Boole[1/2<Floor[Mod[Floor[y/17]2^(-17Floor[x]-Mod[Abs[y],17]),2]]],{y,1+#,17+#},{x,106,1,-1}]]&
Kelly Lowder
fuente