C'est un problème auto-référentiel

49

Formule auto-référentielle de Tupper (copie de Wikipedia)

La formule auto-référentielle de Tupper est une formule définie par Jeff Tupper qui, lorsqu'elle est représentée graphiquement en deux dimensions à un endroit très spécifique du plan, peut être "programmée" pour reproduire visuellement la formule elle-même. Il est utilisé dans divers cours de mathématiques et d'informatique comme exercice de représentation graphique de formules.

Formule autoréférentielle de Tupper

sol est la fonction de sol.

Soit kle numéro à 543 chiffres suivant: 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719

Si un graphique l'ensemble des points (x, y)dans 0 <= x < 106et k <= y < k + 17satisfaisant à l'inégalité donnée ci - dessus, l'aspect graphique résultant comme celui - ci (note que les axes dans ce complot ont été inversés, sinon l'image ressorte à l' envers):

Résultat de la formule autoréférentielle de Tupper

Et alors?

Ce qui est intéressant à propos de cette formule est qu’elle peut être utilisée pour représenter graphiquement toute image possible en noir et blanc au format 106x17. Effectivement, effectuer une recherche serait extrêmement fastidieux. Il existe donc un moyen de déterminer la valeur k où votre image apparaît. Le processus est assez simple:

  1. Commencez par le pixel en bas de la première colonne de votre image.
  2. Si le pixel est blanc, un 0 sera ajouté à la valeur-k. S'il est noir, ajoutez un 1.
  3. Montez la colonne en répétant l'étape 2.
  4. Une fois à la fin de la colonne, passez à la colonne suivante et partez du bas en suivant le même processus.
  5. Une fois chaque pixel analysé, convertissez cette chaîne binaire en décimal et multipliez-la par 17 pour obtenir la valeur k.

Quel est mon travail

Votre travail consiste à créer un programme qui peut prendre n'importe quelle image 106x17 et générer sa valeur k correspondante. Vous pouvez faire les hypothèses suivantes:

  1. Toutes les images seront exactement 106x17
  2. Toutes les images ne contiendront que des pixels noirs (# 000000) ou blancs (#FFFFFF), rien entre les deux.

Il y a aussi quelques règles:

  1. La sortie est simplement la valeur k. Il doit être dans la base appropriée, mais peut être dans n’importe quel format.
  2. Les images doivent être lues à partir d’un fichier PNG ou PPM.
  3. Aucune échappatoire standard.

Images d'essai

[ Nintendo] devrait produire ~ 1.4946x10 542

[ Un grand nombre] devrait produire ~ 7.2355x10 159

[ 2 ^ 1801 * 17] devrait produire 2 1801 * 17

[ 2 ^ 1802 - 1 * 17] devrait produire (2 1802 -1) * 17

Découvrez ce Gist pour les solutions exactes.

C'est le , donc le moins d'octets gagne.


Liens utiles

Wikipédia

Wolfram Mathworld

Kade
la source
Puis-je prendre un PPM?
Maltysen
EDIT: Oui, le format PPM est autorisé. Lorsque je suis venu avec le programme, je voulais utiliser les PNG, mais autoriser le PPM devrait permettre à plus de langues de golf de participer.
Kade
3
En lisant cette question, avant d’arriver à la partie "Quel est mon travail", j’étais convaincue que je verrais le mot quinequelque part.
Jacob
Je ne prétends pas être un programmeur capable de faire ce genre de choses, je vais simplement présenter une question innocente et sérieuse: oui, mais cela peut-il être inversé? C'est-à-dire nourrir la solution et voir le * .png généré comme résultat?
@NotAsSharpAsYouGuys: si vous avez une arithmétique de précision arbitraire, c'est trivial, il vous suffit de vérifier le résultat de cette formule pour chaque pixel et de générer l'image résultante.
Matteo Italia

Réponses:

12

CJam, 16 ans

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

Merci à Dennis. Essayez-le en ligne

Si vous rencontrez des problèmes avec l'URL, voici l'entrée que j'ai testée:

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

J'ai utilisé le format généré par GIMP lors de l'exportation au format ASCII, avec le commentaire supprimé.

Explication:

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
la source
Je l'ai dans l'URL pour vous.
mbomb007
@ mbomb007 merci, je ne sais pas ce qui ne va pas.
Aditsu
Si vous n'avez pas à traiter de commentaires, cela l;l~\qN-/W%zs:~2b*devrait également fonctionner.
Dennis
@ Dennis OMG, il y a plusieurs niveaux de brillance :) voulez-vous le poster par vous-même?
Aditsu
Je ne pense pas qu'une réponse séparée serait suffisamment différente de la vôtre.
Dennis
17

Pyth - 21 octets

Simple à faire avec la iconversion de base de pyth . Prend l'entrée comme PBMnom de fichier et lit à l'aide de la 'commande. Je devais utiliser !Mpour nier les Noirs et les Blancs. Tout le reste est explicite.

*J17i!MsC_cJrstt.z7 2

Essayez-le ici en ligne . (L'interprète Web ne peut pas lire les fichiers, il est donc modifié et prend le fichier en entrée).

Maltysen
la source
60
Je ne pense pas que rien dans Pyth soit explicite. : /
Alex A.
3
Aucune langue que je connais ne peut battre celle-ci. Mais là encore, aucune des langues que je connais n'est "faite pour le golf".
Mahesh
Impossible d'ouvrir le lien, le chemin est trop long, dang (Safari 8.1)
Posté le
Votre exemple d'image semble faux. Vouliez-vous utiliser P2 plutôt que P3?
Aditsu
Oh, attendez, ce n'est même pas P2, il ressemble à P1 mais inversé
aditsu
9

Python 2: 133 110 octets

Une première tentative en python avec 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

Merci aux commentateurs utiles ci-dessous

joc
la source
2
comme vous n'utilisez qu'une fois Image.open (input ()). load et que vous ne le modifiez pas, ne serait-il pas préférable de l'utiliser tel quel, au lieu d'utiliser un var j? ce serait quelque chose comme çafrom 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
En continuant sur le point @ Katenkyo, vous pouvez également simplement vous connecter a/17et a%17aux emplacements appropriés, et vous pouvez abuser du fait que 1 est la vérité et 0 est la falsie. Voici le résultat de ces changements, vous serez ramené à 111 octets :)
Kade
@Kateyenko, est malheureusement input()appelé à chaque itération de la boucle avec cette modification. Édition avec d’autres astuces cependant, merci.
joc
1
(...<1) --> 0**...peut être?
Sp3000
7

C #, 199

C'était amusant! Il n'y a rien de mal à recharger un bitmap 106 * 17 fois, non? Je l'ai fait comme une fonction pour sauvegarder des octets, pas sûr que ce soit légal.

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 est le nom du fichier d'entrée.

En outre, en tant qu’expression unique, simplement parce qu’il s’agit d’une seule expression, avec iou fourni (167 octets)

(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
la source
1
La question dit "votre travail est de créer un programme ..."
Sean Latham le
1

Mathematica 69 octets

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

Binarize @ peut être omis si l’image est au format monochrome.

Cette fonction reproduira l'image:

   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
la source