Une rotation d'une chaîne est effectuée en divisant une chaîne en deux morceaux et en inversant leur ordre, par exemple "world! Hello,"une rotation de "Hello, world!". Il est possible de créer des programmes qui peuvent être tournés pour former un programme différent, mais toujours valide. Considérez cet exemple en python:
print ")import sys; sys.stdout.write("
Il peut être tourné pour former
import sys; sys.stdout.write("print ")
Qui est lui-même un programme python valide.
Votre défi est d'écrire un programme qui génère une rotation de lui-même, qui lors de l'exécution produira le programme d'origine. Des points bonus pour toute entrée avec une durée de cycle supérieure à deux!
Il s'agit du code golf, le score exact sera: (longueur du code) / (durée du cycle - 1).
EDIT: Nous avons un gagnant (sauf si quelqu'un d'autre est capable de battre un score de 4)! Je serais toujours très intéressé de voir d'autres solutions, qu'elles soient prétendantes ou non.
la source
Réponses:
APL (158 caractères, score = 4)
J'utilise Dyalog APL ici. Le nombre de cycles peut être augmenté de un en ajoutant
0(0 suivi d'un espace) à la fin de l'expression et à la fin de la chaîne (avant'''). La durée du cycle est(# 0's) + 1et la longueur de l'expression est150 + 4*(cycle length)). En supposant que nous continuons d'ajouter des zéros pour toujours, le score estLimit[(150 + 4*n)/(n - 1), n -> Infinity] = 4, oùnest la durée du cycle.Voici un exemple avec une longueur de cycle = 6:
192 caractères, score = 2
Selon l'implémentation, un point d'échec pourrait être lorsque l'entier préfixé à la chaîne est trop grand. Théoriquement, cependant, nous pouvons ajouter un cycle en ajoutant deux caractères - un
1à la fin de la chaîne (avant''') et un1à la fin de la ligne entière.200 caractères, score = 1
Mon implémentation APL n'a pas d'entiers de précision illimitée par défaut, donc l'entier est converti en un flottant quand il devient trop grand, ce qui rend la sortie incorrecte. Donc celui-ci est le plus capricieux, mais théoriquement (soit à la main ou avec un interpréteur APL différent), il devrait avoir un score de 1. Ajoutez simplement un
1à la fin de l'expression, et vous obtenez un autre cycle.Aperçu (avec un quine plus court)
Je vais donner un aperçu de la première version, car je pense que c'est probablement la plus facile à comprendre. Avant d'aborder cette version, cependant, nous allons considérer un quine simple dans APL :
J'ai trouvé que l'une des meilleures façons de comprendre certaines expressions APL est de regarder la sortie tout au long de la cascade d'opérateurs / fonctions. Tous les opérateurs et fonctions dans APL sont associatifs à droite et ont la même priorité, voici donc, de droite à gauche:
'''1⌽22⍴11⍴''': Ceci est juste un littéral de chaîne (une liste de caractères).''est le moyen APL d’échapper aux guillemets simples. Sortie:'1⌽22⍴11⍴'.11⍴'''1⌽22⍴11⍴''': Ici, nous remodelons (⍴) la chaîne pour qu'elle soit de longueur11. Parce que la longueur de la chaîne est inférieure à 11, elle est répétée (c'est-à-dire5⍴'abc'qu'elle donnerait'abcab'). Sortie:'1⌽22⍴11⍴''. Nous avons donc maintenant deux guillemets à la fin - nous arrivons quelque part!22⍴11⍴'''1⌽22⍴11⍴''': De même, nous remodelons maintenant notre sortie précédente pour qu'elle soit de longueur22. Sortie:'1⌽22⍴11⍴'''1⌽22⍴11⍴''. Nous y sommes presque - nous avons juste besoin de déplacer la première citation unique à la fin.1⌽22⍴11⍴'''1⌽22⍴11⍴''': Ici, nous faisons pivoter (⌽) la liste des caractères de1. Cela déplace le premier caractère de la chaîne à la fin. Comme autre exemple,2⌽'abcdef'retourne'cdefab'. Sortie:1⌽22⍴11⍴'''1⌽22⍴11⍴'''.Le quine tournant
Ce court quine est la base principale de notre quine rotatif. Maintenant, avec cela à l'esprit, jetons un œil à notre quine:
{ ... }définit une fonction sans nom, c'est là que nous ferons le travail. Notez que les fonctions dans APL prennent un argument droit, noté par⍵, et un argument gauche facultatif, noté⍺(pensez infixe). Nous voulons alimenter cette fonction à la fois notre chaîne de quine et quelque chose pour nous aider à créer un nombre arbitraire de cycles. Pour nous faciliter la tâche (et pour quiconque souhaite ajouter des cycles), nous faisons de la chaîne quine l'argument de gauche. Le bon argument est donc l'endroit où nous mettons notre liste de cycles. 2 éléments ou plus séparés par un espace créent une liste, donc dans cet exemple, nous avons une liste à 2 éléments composée de a1et a0.Nous pouvons voir que la fonction ressemble à la quine d'avant. Nous avons le même
...⌽...⍴...⍴...formulaire que précédemment. C'est donc bien - nous comprenons au moins cela! Nous allons plonger plus profondément dans les ellipses, en commençant par tout ce qui suit le dernier⍴:⊃,/(~^/¨⍺=0)/⍺.⍺=0renvoie une liste, dans ce cas, avec la même forme que⍺, où chaque élément de⍺est remplacé par a1s'il est égal à0, et0sinon. Ceci est effectué récursivement; donc si nous avons une liste d'une liste d'une liste de caractères, les caractères individuels seront testés par rapport à 0, et vous récupérerez une liste d'une liste d'une liste de valeurs binaires.⍺compose uniquement de notre chaîne, nous récupérons une liste de 0. Sinon, notre argument de gauche est précédé de 0 (par exemple0 0 0 'quinestring'), il s'agit donc d'une liste composée de 0 et d'une autre liste, notre chaîne. Ensuite, notre sortie ressemble1 1 1 <sub-list of zeros>.^/¨⍺=0: Nous appliquons la fonction dérivée^/, qui réduit (/) à l'aide de la fonction logique AND (^), à chaque¨élément ( ) de⍺=0. C'est pour aplatir la sous-liste des zéros afin que nous puissions considérer la chaîne quine comme une valeur binaire. Considérant l'exemple précédent, la sortie serait1 1 1 0.~: Nous binaire PAS chacune des valeurs d'avant (par exemple, le retour0 0 0 1).(~^/¨⍺=0)/⍺: Pour chaque élément de⍺, nous répliquons (/) le nombre de fois donné par l'élément correspondant dans l'argument de gauche. Cela élimine tous les 0, ne nous laissant que notre chaîne de quine.⊃,/est une paperasse nécessaire pour s'assurer que nous récupérons une liste de caractères aplatie, en réduisant le résultat avec la fonction de concaténation (,). Si l'entrée est déjà une liste aplatie (c'est-à-dire que l'argument de gauche de notre fonction principale n'est que la chaîne), nous obtenons une liste à 1 élément contenant cette liste. Dans l'autre cas, lorsque nous avons une liste composée d'une sous-liste pour la chaîne, nous obtenons la même chose (une liste avec une sous-liste). Nous décompressons ensuite this (⊃), ne nous donnant que le premier élément de la liste (c'est-à-dire la sous-liste de caractères). Cela peut sembler inutile, mais sinon nous essaierions alors de remodeler une liste à 1 élément!Ensuite, nous regardons la longueur donnée pour le premier remodelage, entre parenthèses:
⍺,⍵: Nous concaténons le bon argument au premier argument⊃,/⍺,⍵: Comme avant - aplatissez la liste.+/0=⊃,/⍺,⍵: Additionnez le nombre de zéros dans la liste en réduisant (/) en utilisant l'addition (+).2×+/0=⊃,/⍺,⍵: Multipliez ce nombre par deux.z←2×+/0=⊃,/⍺,⍵: Assign (←) , le résultat à une variable,z. Pour récapituler,zc'est maintenant le double du nombre de zéros trouvés dans les arguments gauche et droit.77+z←2×+/0=⊃,/⍺,⍵: Nous ajoutons ensuite77, pour les caractères de la chaîne de quine, en ignorant tout après l'espace suivant1. Comme dans l'exemple de quine initial, nous ajoutons 1 à la longueur de la chaîne pour obtenir un autre guillemet simple.'{(((3+z)×^/⍵)-5+2×+/+/¨⍺=0)⌽(2×77+z)⍴(77+z←2×+/0=⊃,/⍺,⍵)⍴⊃,/(~^/¨⍺=0)/⍺}1 0 ''L'argument de la refonte qui suit est simple et reflète le quine court (2 fois la longueur de la première refonte). Notre production est maintenant:
Maintenant, pour la dernière étape, où nous calculons la rotation de la chaîne de sortie:
0(et un autre espace) se déplacent également au début, nous voulons le faire pivoter de 3 caractères supplémentaires.+/+/¨⍺=0: Additionnez le nombre de zéros dans l' argument de gauche . Le premier (à droite)+/¨additionne le nombre de chaque élément (c'est-à-dire une sous-liste ou simplement un entier), et le second+/nous donne la somme de cette liste résultante.5+2×+/+/¨⍺=0: Multipliez par deux (pour faire également pivoter les espaces) et ajoutez 5 (le résultat que nous avons trouvé auparavant).-pour gérer le cas lorsque nous atteignons la fin de notre cycle:(3+z)×^/⍵: ET tous les éléments du bon argument ensemble pour voir si nous avons atteint notre fin (1), et multipliez-le par3+z.Et nous avons terminé!
la source
⍴opérateur (?). Je pense que je vais devoir lire le tout encore quelques fois avant de le digérer complètement!GolfScript, 10046/9999 ≈ 1,0047 (score asymptotique 1)
OK, je vais essayer de battre l'entrée APL de DC avec ceci:
Le code ci-dessus n'est pas le quine réel - je pensais que publier un one-liner de 10 Ko ne serait pas une très bonne idée. Au lieu de cela, l'exécution du code ci-dessus produit le programme GolfScript de 10046 caractères réel, qui, lorsqu'il est répété comme spécifié dans la question, génère 9999 rotations de lui-même et, enfin, de nouveau.
La durée du cycle (et du programme) peut être ajustée en changeant la constante
9999. Par souci de concision et de commodité, je vais montrer à quoi ressemble la sortie itérée si la constante est réduite à9:Lorsque la constante
9999augmente, le rapport entre la durée du programme et la durée du cycle (moins un) tend à un. Je suis presque sûr que cette solution ne peut pas être battue, du moins pas asymptotiquement. ;-)Comment ça marche?
GolfScript est un langage assez simple pour écrire des quines, car pratiquement n'importe quel nombre littéral agit comme une quine: par exemple, le programme GolfScript génère
12345- vous l'avez deviné -12345. En outre, la concaténation de plusieurs quines produit généralement une quine. Ainsi, je pourrais utiliser un nombre simple comme11111...111la partie répétitive de mon quine cyclique.Cependant, pour que le quine fonctionne réellement, nous devons transporter et exécuter une "charge utile" non triviale. La quine GolfScript la plus simple à laquelle je puisse penser qui peut le faire est la suivante:
Mon plan était donc de préfixer un quine comme celui-ci avec une constante numérique répétitive et d'utiliser une charge utile qui coupe un chiffre du nombre et le déplace à la fin du programme. Si les détecte de programme qui y est en face de lui aucune constante numérique (auquel cas la valeur ci - dessous sur la pile sera une chaîne vide, en supposant qu'il n'y pas d' entrée), il sera à la place préfixer une constante numérique de longueur fixe devant lui-même.
Il y a cependant une ride supplémentaire - lors du "bouclage", la charge utile doit également supprimer la sortie du nombre après lui-même. Normalement, quand un programme GolfScript se termine, toutes les valeurs de la pile sont automatiquement imprimées, ce qui serait un problème ici.
Cependant, il s'avère qu'il existe un moyen (AFAIK) non documenté pour éviter cela: l'interpréteur appelle en fait la fonction prédéfinie
putspour faire l'impression, donc redéfinir cette fonction en tant que no-op supprime la sortie automatique. Bien sûr, cela signifie également que nous devons d'abordputsnous appeler pour imprimer la partie de la pile que nous voulons imprimer.Le code final semble assez compliqué (même pour GolfScript), mais au moins cela fonctionne. Je soupçonne qu'il y a peut-être des moyens intelligents auxquels je n'ai pas encore pensé de supprimer quelques caractères de la charge utile, mais pour cette version, je me concentrais principalement sur le score asymptotique.
la source
puts{}:puts, même si je pouvais voir un argument{print}:putsen raison du fait qu'une nouvelle ligne dans la sortie signifierait qu'elle n'est pas strictement cycliste.]puts{}:putsest nécessaire pour le bouclage de{STUFF}.~111111111à111111111{STUFF}.~, sinon le nombre de1s à la fin du programme ne cesse de croître. ({}Cependant, cela semble inutile; apparemment, l'interpréteur GolfScript permet l'affectation à partir d'une pile vide.)HTML, moins l'infini (presque)
-2
AA-dix
AAAAAAAAAAEt ainsi de suite ... Si quelqu'un dit qu'il triche, nous pouvons en discuter, mais j'ai trouvé un trou en question :)
Donc je suppose que tout le monde comprend que le code le fait, il n'a pas de boucles, donc la boucle la plus longue est
0et compte tenu de la longueur du programmen, le score estn / (0 - 1)ou-n, je peux écrire un programme qui a unngrand entier positif, mais il est inutile, car tout le monde le comprend.la source