Période d'itération la plus longue

10

Comme nous le savons, une quine est un programme qui génère son propre code source. Cependant, il est également possible d'écrire un programme qui génère un autre programme différent, qui génère à nouveau le premier programme. Par exemple, le programme Python 2

x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3

, lors de l'exécution, affichera le texte suivant:

print """x = '''x = {}
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3'''
print 'print '+'"'*3+x.format("'"*3+x+"'"*3)+'"'*3"""

Lorsqu'il est exécuté en tant que programme Python, cela affichera à nouveau le code d'origine. C'est ce qu'on appelle un quine itératif . Parce que vous devez l'exécuter deux fois pour récupérer le code d'origine, nous disons qu'il a la période 2 . Mais bien sûr, des périodes beaucoup plus élevées sont possibles.

Votre défi est d'écrire un quine itératif avec une période aussi longue que possible, en 100 octets ou moins , dans la langue de votre choix. (Notez que mon exemple ci-dessus ne correspond pas à cette spécification, car il fait 119 octets, y compris la nouvelle ligne de fin.)

Veuillez noter les règles et clarifications suivantes:

  • Les règles de quine habituelles s'appliquent, c'est-à-dire que votre programme ne peut pas utiliser les fonctionnalités de langage qui lui permettraient d'accéder directement à son propre code source.
  • Les sorties itérées doivent finalement revenir en boucle exactement à votre code d'origine, et vous devez inclure une démonstration ou une preuve qu'il le fera.
  • Vous devez également inclure une explication de la raison pour laquelle le cycle est aussi long que vous le dites. Cela n'a pas à être au niveau d'une preuve mathématique, mais cela devrait être convaincant pour quelqu'un qui connaît votre langue. (Cette règle est ici parce que je m'attends à ce que certaines des réponses impliquent de très, très grands nombres.)
  • C'est bien de dire quelque chose comme "au moins 1 000 000 d'itérations" plutôt que de donner le nombre exact, tant que vous pouvez prouver qu'il est au moins aussi long. Dans ce cas, votre score serait de 1 000 000. Sinon, votre score est la période de votre quine.
  • La limite de 100 octets ne s'applique qu'à votre programme initial - les programmes qu'il génère peuvent être plus longs, bien sûr, ils devront éventuellement revenir à 100 octets pour sortir votre code d'origine.
  • Vous pouvez supposer que votre machine a une RAM infinie et un temps d'exécution infini, mais vous ne pouvez pas supposer des types de données de précision illimités (tels que des entiers) si votre langue ne les a pas. Vous pouvez supposer qu'il n'y a pas de limite à la longueur d'entrée que votre analyseur peut gérer.
  • Le score le plus élevé l'emporte.

Veuillez noter: il existe un défi appelé Quit Whining; Commencez Quining qui implique également l'itération des quines. Cependant, en plus d'être basés sur le même concept, ce sont des types de défis complètement différents. L'autre est le golf de code, alors que celui-ci est (intentionnellement!) Vraiment un problème de castor occupé déguisé. Les techniques nécessaires pour produire une bonne réponse à cette question sont susceptibles d'être très différentes de ce qui est nécessaire pour répondre à l'autre question, et c'est très bien par conception.

code-challenge quine busy-beaver Nathaniel
la source
1
@LeakyNun Je ne sais pas si c'est vous ou un mod qui a supprimé votre réponse, mais peut-être que si j'explique ce qui n'allait pas, vous comprendrez pourquoi ce n'est pas un doublon. Cette question spécifie une limite de 100 octets sur la longueur de la source, donc vous ne pouvez pas réellement aller "aussi haut que vous le souhaitez" en utilisant cette méthode. C'est tout l'intérêt de cette question. Pour y répondre, ce que vous auriez à faire serait de publier la version la plus longue pouvant contenir 100 caractères et de dire quelle est sa période. Ce que vous avez publié serait une bonne première tentative, mais il est très peu probable qu'il soit gagnant.
Nathaniel
1
@Dave le défi consiste précisément à spécifier un grand nombre dans un petit nombre d'octets, oui. C'est tout le principe autour duquel il a été conçu. La question est, est-ce que 3 ^^^ 3 est le nombre le plus élevé que vous pouvez spécifier dans 100 octets dans votre langue, ou y en a-t-il un plus grand? C'est de cela qu'il s'agit. C'est le cœur du problème. C'est ce que je voulais voir les gens faire. C'est super, super frustrant de l'avoir fermé sur la base d'une ressemblance superficielle avec un défi qui n'a rien de cette structure.
Nathaniel
1
@Dave (deuxième commentaire) mais si vous êtes intelligent, vous n'avez pas du tout besoin d'être limité par la précision de la machine. Je m'attendrais à ce que les réponses concurrentielles aient une période beaucoup plus longue que 2 ^ (2 ^ 64).
Nathaniel
3
Alors préférez-vous qu'il soit fermé en tant que doublon de codegolf.stackexchange.com/q/18028/194 ?
Peter Taylor
1
@PeterTaylor, c'est un thème beaucoup plus proche, mais c'est toujours un défi très différent - imprimer un nombre est très différent de faire quelque chose un grand nombre de fois. Je préférerais bien sûr qu'il ne soit pas fermé du tout.
Nathaniel

Réponses:

10

PHP, période 2,100,000,000

Qui aurait pensé que c'était possible en PHP?! :-)

C'est en fait mon premier quine et il fait 99 octets de long:

<?$i=1;$i*=21e8>$i;printf($a='<?$i=%d;$i*=21e8>$i;printf($a=%c%s%c,++$i,39,$a,39);',++$i,39,$a,39);

Bien que PHP prenne en charge de plus grands nombres qu'en 2 * 10^8passant de integerà double, l'incrément ne fonctionne plus (conduit à une boucle infinie) et je n'ai pas trouvé d'autre solution qui rentre dans les 100 octets. Encore.

La preuve est assez simple, car elle ne fait que compter sur chaque itération jusqu'à ce qu'elle atteigne le point de réinitialisation à 2,1 milliards.

Crédits à Dave , qui a posté l'approche en pseudo-code dans les commentaires et à Bob Twells , dont j'ai copié le code pour une quine PHP minimale.

Programme de test (sloooooow):

<?php
$o = file_get_contents('quine.php');
for ($i = 0; $i < 22e8; $i++) {
    if ($i%2==0) exec('php q > p'); else exec('php p > q');
    $a = file_get_contents(($i%2==0) ? 'p' : 'q');
    echo "\r" . str_pad($i,6,' ') . ":\t$a";
    if ($a == $o) {
        die;
    }
}

Eh bien, au moins je suis le premier à répondre.

YetiCGN
la source
1
Note: c'est de l'ordre de ~ 10 ^ 9.322219295.
LegionMammal978
8

Mathematica, période E8.5678 # 3 E2.1923 # 4 ~ E6.2695 # 3 # 2

Print[ToString[#0, InputForm], "[", #1 - 1 /. 0 -> "Nest[#!,9,9^9^99!]", "]"] & [Nest[#!,9,9^9^99!]]

Notez que les scores sont décrits en notation Hyper-E . Les itérations remplacent la finale Nest[#!,9,9^9^99!]par les extensions décimales de Nest[#!,9,9^9^99!]- 1, Nest[#!,9,9^9^99!]- 2, Nest[#!,9,9^9^99!]- 3, ..., 3, 2, 1, et reviennent à Nest[#!,9,9^9^99!].

LegionMammal978
la source
les factorielles ne croissent-elles pas plus vite?
Maltysen
1
Je ne connais pas Mathematica, mais n'est-ce pas une violation des règles d'un quine - lire son propre code source? ToString[#0, InputForm]
daniero
donc, seulement 9 !!!! ne fonctionne pas? idk cuz je n'ai pas mon mathica rpi avec moi en ce moment.
Maltysen
@Maltysen Qui calcule la double factorielle de la double factorielle de neuf, ou (9 !!) !! ≈ 2.116870635 · 10¹²⁰²
LegionMammal978
@daniero Je veux dire, l'idée est similaire à une CJam standard {"_~"}_~, donc je suppose qu'elle devrait être valide ...
LegionMammal978
5

R, période aléatoire avec attente 2 ^ 19936-0.5

f=function(){
    options(scipen=50)
    body(f)[[4]]<<-sum(runif(623))
    0
    cat("f=")
    print(f)
}

Le générateur de nombres aléatoires par défaut de R a une période de 2 ^ 19937-1 et une équidistribution dans 623 dimensions consécutives. Ainsi, quelque part (mais une seule fois) dans sa période sera un vecteur de zéros de 623 mètres de long. Lorsque nous y arriverons (et sommes alignés avec le début de la séquence), la somme des 623 prochains nombres aléatoires U [0,1] sera nulle et nous reviendrons à notre programme d'origine.

Notez que le programme passera très probablement par le même état non nul plusieurs fois avant de revenir à zéro. Par exemple, la somme 311,5 est la plus probable, et il existe de nombreuses façons qui peuvent se produire, mais le RNG permet à la période de 0 d'être plus longue que la période de 311,5.

JDL
la source
Je ne sais pas quel score vous voulez attribuer à cette entrée: P
JDL
1
Selon les règles: "C'est bien de dire quelque chose comme" au moins 1 000 000 d'itérations "plutôt que de donner le nombre exact" Donc, à mon avis, c'est "au moins 1 itération" parce que si nous avons vraiment de la chance au premier essai ...;)
YetiCGN
Contrairement à de nombreuses échappatoires standard comme «Je pourrais générer une entrée aléatoire, la réponse est là», c'est une preuve vraiment nette que la réponse précise est inévitable et une très bonne estimation est donnée. Agréable!
Andreï Kostyrka
1
Une fois que le programme revient à son état de base, il aura alors une période non aléatoire d'exactement 2 ^ 19937-1.
JDL
La sortie de ceci ne correspond pas au programme réel (il manque un peu d'espace). De plus, l'état ne sera pas conservé entre les appels de programme, donc la période ne sera pas un nombre exact, ni cohérente
Jo King
1

JavaScript, période 9 007 199 254 700 000

Je ne gagnerai pas, mais c'était amusant de travailler avec JavaScript sur ce défi:

a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)

Suit le cycle suivant:

a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699999-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254699998-1||90071992547e5)
// etc...
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),3-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),2-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),1-1||90071992547e5)
a="a=%s;console.log(a,uneval(a),%.0f-1||90071992547e5)";console.log(a,uneval(a),9007199254700000-1||90071992547e5)
// and so on

Remarque: Vous pouvez le raccourcir de 18 octets, tout en ne supprimant que ~ 0,08% du score, comme ceci:

a="a=%s;console.log(a,uneval(a),%.0f-1||9e15)";console.log(a,uneval(a),1-1||9e15)
ETHproductions
la source
1

C, période 2,100,000,000

unsigned long long i;main(a){i=1;i*=21e8>i;printf(a="ungisned long long i;main(a){i=%d;i*=21e8>i;printf(a=%c%s%2$c,++i,34,a);}",++i,34,a);}

Basé sur la réponse PHP (évidemment). Mettra à jour avec explication quand j'ai le temps.

MD XF
la source
1

C (gcc) , 66 octets, période 2 ^ 64

f(s){printf(s="f(s){printf(s=%c%s%1$c,34,s,%lu+1L);}",34,s,0+1L);}

Essayez-le en ligne!

2 ^ 64 nombres sont disponibles dans un unsigned longentier. Par conséquent, une période de 2 ^ 64.

SS Anne
la source
1

Python 2

Période: 9↑((99↑↑(9↑((99↑↑(9↑((99↑↑(9↑↑5-1))↑9)-1))↑9)-1))↑9)+1

Merci à @Bubbler pour avoir augmenté la période de 9↑9↑(99↑↑12)+1 jusqu'à maintenant

b=0;s="print'b=%d;s=%r;exec s'%(-~b%eval('9**9'*eval('9**9'*eval('9**9'*9**9**9**9**9))),s)";exec s

Essayez-le en ligne!

Dans le code, les b=0modifications apportées à b=1then b=2et ainsi de suite jusqu'à ce qu'il atteigne b=decimal expansion of the periodpuis se réinitialise surb=0

Mukundan
la source
1
9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9**9est beaucoup plus élevé que 9**9**99**99**99**99**99**99**99**99**99**99**99**99. Cela dit, vous pourriez faire quelque chose comme eval('9**9'*eval('9**9'*eval('9**9'*9**9**9**9**9)))pour des nombres beaucoup plus élevés.
Bubbler
Que signifie peroid?
SS Anne
@SSAnne, il est écrit dans la notation de la flèche vers le haut de Knuth
Mukundan
1
@Mukundan Je pense que vous voulez dire période, mais je ne suis pas sûr. Je comprends ce qu'est la tétration.
SS Anne
@SSAnne désolé, c'était une faute de frappe, merci de l'avoir signalé
Mukundan
0

Gol> <> , 70 octets, période 325883196621297064957600206175719056476804879488288708188003274919860959534770101079512433396348062803055739640225395758790852315876868469390603793729639715908136196505908165227136154287969475839017544811926036808089596209081885772040898530121921794489026069641113281250

Autre sage connu comme vraiment grand (3.25E270)

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||lPffXfX=?1:1=Q$~$~|:1)lPffXfX(Q?:|r2ssH##

Ceci est en fait la version modifiée de la réponse que j'ai mise sur l'itérateur de 500 octets

":1=l8:*6+=S&Q~:'~'=Q~~'H#'||//if last is equal to 1 and length is 71, delete the delete char, if the last char is '~', delete and push 'H#', which will later return to 'H##', completing the cycle!
lPffXfX=?1:1=Q$~$~|          //if length is equal to 15^15^15, then start delete process(append ascii one)
:1)lPffXfX(Q?:|              //if the last character is not 1 (the delete checker), and length is less than 15^15^15, duplicate the last value and append
r2ssH##                      //push the " to the front and output the whole thing

J'espère avoir obtenu le bon score, et il n'y a pas de bugs. Il n'y a pas de véritable moyen de réellement calculer cette valeur, il est théorique. Mais l'homme, c'est un nombre énorme !!!

Essayez-le en ligne!

KrystosTheOverlord
la source