Programme qui se permute pour encoder une chaîne (quine-variant)

16

Écrivez un programme qui imprime la ligne de 80 caractères suivante:

Ce programme de codegolf.stackexchange.com se permute pour encoder une chaîne.

accepte ensuite une ligne d'entrée, puis imprime son code source avec ses points de code éventuellement réorganisés (aucun ajouté et aucun supprimé). Lorsque ce code est exécuté, la même chose doit se produire, sauf que la ligne imprimée serait la ligne d'entrée la plus récente.

Le regex de style Perl ^[A-Za-z0-9. ]{80}$correspondra à n'importe quelle ligne d'entrée. Vous ne pouvez faire aucune hypothèse supplémentaire.

Le score d'une soumission est le nombre de points de code dans son code source moins 94 . Plus c'est bas, mieux c'est.

Le code ne doit rien faire qui serait inacceptable dans une quine ( par exemple la lecture d'un fichier). En particulier, toute soumission avec un score négatif doit tricher d'une manière ou d'une autre, comme 93! est inférieur à 64 80 .

Ajouté le 21/04/2014: Le code source complet de votre programme doit être bien formé dans l'encodage des caractères sous lequel vous comptez les points de code. Par exemple, vous ne pouvez pas utiliser 80 octets consécutifs dans la plage d'octets de fin UTF-8 (80..BF) et compter chacun comme un seul caractère de remplacement U + FFFD (ou pire, comme pas un point de code du tout).

De plus, si l'encodage permet plusieurs façons de coder un point de code ( par exemple SCSU ), votre programme, ainsi que tous les programmes qu'il génère directement ou indirectement, ne doivent utiliser qu'un seul d'entre eux (ou au moins tous doivent être traités de manière équivalente dans tout le code ).

Veuillez vous lever
la source
Après avoir relu votre question, je ne sais pas si ma réponse fait exactement ce que vous aviez en tête. Le transfert de la nouvelle chaîne vers le programme est-il correct ou doit-il lancer une invite interactive?
Dennis
@Dennis: Ce n'est pas pourquoi votre réponse n'est pas acceptable. Il lit plutôt l'entrée avant d' imprimer "Ce programme à partir de [...]".
PleaseStand
C'est ce que je voulais dire, je ne l'ai pas bien exprimé. L'interpréteur GolfScript lit tout ce qui lui est acheminé avant de commencer à exécuter le script. La seule façon d'éviter cela est de lancer une invite, ce qui rend la tuyauterie impossible.
Dennis
Salut, j'essaye ceci en JavaScript. Il semble impossible de faire une quine sans lire le texte entre les balises <script>? Quel est le but de permuter le code source? Vous dites «éventuellement réorganisé»; cela signifie-t-il permuter seulement si nécessaire?
bacchusbeale

Réponses:

5

GolfScript, 231 162 131

'1àâ4ÿaVo5GùpZBtiXOürsóNîMmWåKHc09JdñúêyzíECäYïhDU ãáIFõ6é8òRìjTv23ønuðLwxfSkôbëAelqý.çèPQ
öûg7'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~

Comment ça fonctionne

Nous commençons par choisir 94 caractères différents qui seront permutés pour encoder une chaîne. 94 caractères fonctionneraient, mais nous choisissons ce qui suit à des fins de golf:

\n .0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
àáâãäåçèéêëìíîïðñòóôõöøùúûüýÿ

Appelons le tableau de ces caractères «&».

La ligne d'entrée contiendra toujours 81 caractères (y compris le LF). Tous ces caractères sont présents dans les 65 premiers caractères de «&». C'est la seule raison de choisir des caractères dans les 128 octets supérieurs.

Nous remplaçons chaque caractère de la chaîne par son index dans «&», donc LF devient 0, l'espace devient 1, etc.

Nous considérons les 81 nombres obtenus comme les chiffres d'un seul nombre de base 65. Appelons ce numéro «N».

Maintenant, nous énumérons toutes les permutations possibles de «&» et récupérons la permutation correspondant au nombre ci-dessus. Ceci est réalisé de la manière suivante:

  1. Définissez c = 1et A = [].
  2. Préparez N % cà A.
  3. Définissez N = N / cet c = c + 1.
  4. Si c < 95, revenez à 2.
  5. Définissez i = 0et s = "".
  6. Récupérez le caractère &[A[i]], ajoutez-le à «s» et supprimez-le de «&».
  7. Set i = i + 1.
  8. Si i < 94retournez à 6.

Supposons que nous ayons des blocs de code «E» et «D» qui codent et décodent une chaîne comme expliqué ci-dessus.

Maintenant, nous avons besoin d'un wrapper pour ces blocs de code qui est conforme aux exigences de la question:

'encoded string'{\.$[{}/]:&; D puts '"#{`head -1`}"'~ E "'".@+\+\'.~'}.~

Cela fait ce qui suit:

  • {…}.~définit un bloc, le duplique et exécute la deuxième copie. La première copie restera sur la pile.

  • \.$ échange la chaîne codée avec le bloc et crée une copie de la chaîne codée, avec des caractères triés.

  • [{}/]:&; convertit la chaîne ci-dessus en un tableau, l'enregistre dans «&» et la supprime.

  • D puts décode la chaîne encodée et imprime le résultat.

  • '"#{`head -1`}"'~lit une ligne d'entrée en s'exécutant head -1dans le shell.

  • E "'".@+\+ encode la chaîne et ajoute et ajoute une seule citation.

  • \'.~'échange la chaîne codée et le bloc et ajoute la chaîne '.~'.

  • Une fois le bloc exécuté, GolfScript imprime le contenu de la pile (chaîne codée, bloc '.~') et quitte.

"E" peut être défini comme suit:

{&?}%        # Replace each character by its index in “&”.
);           # Remove the last integer from the array, since it corresponds to the LF.
65base       # Convert the array to an integer “N” by considering it a base 65 number.
[            #
  94,        # For each integer “c” in 0 … 93:
  {          #
    )        # Increment “c”.
    1$1$%    # Push “N % c”.
    @@/      # Rotate “N % c” below “N” and “c” and divide the first by the latter.
  }/;        # Discard “N”.
]            # Collect the results of “N % c” in an array “A”.
-1%          # Reverse “A”.
&\           # Push “&” and swap it with “A”.
[            #
  {          # For each “j” in “A”:
    1$=.[]+  # Push “&[j] [&[j]]”.
    @^       # Rotate “&” on top of “[&[j]]” and take their symmetric difference.
  }/         #
]            # Collect the charcters into an array.

«D» peut être défini comme suit:

0&           # Push 0 (initial value of the accumulator “A”) and “&”.
@            # Rotate the encoded string on top of “&”.
{            # For each character “c” of the encoded string:
    @2$,*    # Rotate “A” on top of the stack and multiply it by the length of “&”.
    2$2$?+   # Get the index of “c” in “&” and add it to “A”.
    @@^      # Rotate “A” below “&” and “c” and take their symmetric difference.
}/;          # Discard “&”.
65base       # Convert “A” into the array of its digits in base 65.
{&=}%        # Replace each digit by the corresponding character in “&”.
''+          # Convert the resulting array into a string.

Golf final:

  • Remplacez \.$[{}/]:&;0&@par 0@.$[{}/]:&\pour enregistrer deux caractères.

  • Définissez la fonction {;65base}:bpour enregistrer un caractère.

  • Supprimez tous les espaces sauf le LF de fin et le LF dans la chaîne.

Exemple

$ # Create GolfScript file using base64 to avoid encoding issues.
$ base64 > permute.gs -d <<< JzHg4jT/YVZvNUf5cFpCdGlYT/xyc/NO7k1tV+VLSGMwOUpk8frqeXrtRUPkWe9oRFUg4+FJRvU26TjyUuxqVHYyM/hudfBMd3hmU2v0YutBZWxx/S7n6FBRCvb7ZzcnezBALiRbe30vXTomXHtAMiQsKjIkMiQ/K0BAXn0vezs2NWJhc2V9OmJ+eyY9fSUnJytwdXRzJyIje2BoZWFkIC0xYH0iJ357Jj99JSliWzk0LHspMSQxJCVAQC99LztdLTElJlxbezEkPS5AXn0vXSInIi5AK1wrXCcufid9Ln4K
$
$ # Set locale to en_US (or any other where one character is one byte).
$ LANG=en_US
$
$ # Go back and forth between two different strings.
$ # Second and sixth line are user input, not output from the script.
$
$ golfscript permute.gs | tee >(tail -n+2 > tmp.gs) && golfscript tmp.gs && rm tmp.gs
This program from codegolf.stackexchange.com permutes itself to encode a string.
Permuting source code code points to encode a string is a certain quine variant.
'18äJoS3sgV9qdçëxm0ÿKMNe5íPî.Htn2ciâIuøbRZéð4AwB7áìUüöôWõèûfñåLàóDrhQlO6
pTaýzòkùYCyFêïãG júEvX'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~
Permuting source code code points to encode a string is a certain quine variant.
This program from codegolf.stackexchange.com permutes itself to encode a string.
'1àâ4ÿaVo5GùpZBtiXOürsóNîMmWåKHc09JdñúêyzíECäYïhDU ãáIFõ6é8òRìjTv23ønuðLwxfSkôbëAelqý.çèPQ
öûg7'{0@.$[{}/]:&\{@2$,*2$2$?+@@^}/{;65base}:b~{&=}%''+puts'"#{`head -1`}"'~{&?}%)b[94,{)1$1$%@@/}/;]-1%&\[{1$=.@^}/]"'".@+\+\'.~'}.~
$
$ # Sort all characters from the original source code and hash them.
$ fold -1 permute.gs | sort | md5sum
b5d978c81df5354fcda8662cf89a9784  -
$
$ # Sort all characters from the second output (modified source code) and hash them.
$ golfscript permute.gs | tail -n+2 | fold -1 | sort | md5sum
Permuting source code code points to encode a string is a certain quine variant.
b5d978c81df5354fcda8662cf89a9784  -
$
$ # The hashes match, so the characters of the modified source code are a permutation
$ # of the character of the original one.
Dennis
la source
224 moins 94 est 130.
mbomb007
Pourriez-vous élaborer?
Dennis
1

Perl, 1428 1099

Celui-ci contient 1193 caractères ASCII (dont 960 chiffres binaires permutés). 1193 - 94 = 1099

$s='010011100001100010101100111111101001101011101000100000101011011010100110111111011111101011101000100110111111011100101000011101011110100000101000100101011111111110101100101101011010011100100100011110110001011100100001011010100111100000011110111110011100101000100110111111101001011110101011100110101110101101011110101100111111100010101101101100011110100101011111111111101101101000111111011110100111011100101000011101011110111111011010111111101100101101101011100010100111100000111110';$_=q{$i=join'',A..Z,a..z,0..9,'. ';print map({substr$i,oct'0b'.$_,1}$s=~/.{6}/g),$/;chop($s=<>);$s=join'',map{sprintf"%06b",index$i,$_}$s=~/./g;$t=join'',map{$_ x(480-(()=$s=~/$_/g))}0,1;print"\$s='$s';\$_=q{$_};eval#$t"};eval#000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Mon premier design

Avant de prendre une suggestion de Dennis pour passer au binaire, mon programme permutait les chiffres octaux.

Mon premier design encode chaque chaîne en 160 chiffres octaux, avec 2 chiffres par caractère. Cet encodage a 100 8 = 64 caractères différents. Le système octal a 8 chiffres différents. Le programme doit avoir 160 copies de chaque chiffre, donc il permute 8 × 160 = 1280 chiffres.

Je garde 160 chiffres $set les 1120 autres chiffres $t. Je commence avec un programme qui n'est pas une quine, mais imprime uniquement les affectations vers $set $tpour la prochaine exécution. Ça y est:

$s = '2341425477515350405332467737535046773450353640504537765455323444366134413247403676345046775136534656553654774255543645377755507736473450353677327754555342474076';
$t = '0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222223333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777';

# $i = character map of 64 characters, such that:
#  substr($i, $_, 1) is the character at index $_
#  index($i, $_) is the index of character $_
$i = join '', 'A'..'Z', 'a'..'z', '0'..'9', '. ';

# Decode $s from octal, print.
#  1. ($s =~ /../g) splits $s into a list of pairs of octal digits.
#  2. map() takes each $_ from this list.
#  3. oct() converts $_ from an octal string to a number.
#  4. substr() on $i converts number to character.
#  5. print() outputs the characters from map() and a final "\n".
print map({ substr $i, oct, 1 } $s =~ /../g), "\n";

# Read new $s, encode to octal.
#  1. ($s = <>) reads a line.
#  2. chop($s) removes the last character of $s, the "\n".
#  3. ($s =~ /./g) splits $s into characters.
#  4. map() encodes each character $_ as a pair of octal digits.
#  5. join() concatenates the pairs from map().
chop($s = <>);
$s = join '', map { sprintf "%02o", index $i, $_ } $s =~ /./g;

# Make new $t.
#  1. map() takes each $_ from 0 to 7.
#  2. $_ x (160 - (() = $s =~ /$_/g)) makes a string where $_ repeats
#     160 times, minus the number of times that $_ appears in $s.
#  3. join() concatentates the strings from map().
$t = join '', map { $_ x (160 - (() = $s =~ /$_/g)) } 0..7;

# Print the new assignments for $s and $t.  This is not yet a quine,
# because it does not print the rest of the program.
print "\$s = '$s';\n\$t = '$t';\n";

(() = $s =~ /$_/g))est une affectation à une liste vide de variables. Je prends cette astuce dans le didacticiel de contexte de PerlMonks . Il force le contexte de liste sur l'opérateur de correspondance =~. Dans un contexte scalaire, la correspondance serait vraie ou fausse, et j'aurais besoin d'une boucle comme $i++ while ($s =~ /$_/g)pour compter les correspondances. Dans un contexte de liste, $s =~ /$_/gest une liste de correspondances. J'ai placé cette liste dans le contexte scalaire d'une soustraction, donc Perl compte les éléments de la liste.

Pour faire une quine, je reprends le formulaire $_=q{print"\$_=q{$_};eval"};evaldes quines Perl de Rosetta Code . Celui-ci affecte une chaîne q{...}à $_puis appelle eval, afin que je puisse avoir mon code dans une chaîne et l'exécuter également. Mon programme devient une quine lorsque j'encapsule ma troisième à la dernière ligne dans $_=q{et };eval, et change ma dernière printen print "\$s = '$s';\n\$t = '$t';\n\$_=q{$_};eval".

Enfin, je joue à mon programme en remplaçant la première affectation $tpar un commentaire et en supprimant les caractères supplémentaires.

Cela a 1522 caractères ASCII (dont 1280 chiffres octaux permutés).
1522 - 94 = 1428

$s='2341425477515350405332467737535046773450353640504537765455323444366134413247403676345046775136534656553654774255543645377755507736473450353677327754555342474076';#0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222223333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777
$_=q{$i=join'','A'..'Z','a'..'z','0'..'9','. ';print map({substr$i,oct,1}$s=~/../g),"\n";chop($s=<>);$s=join'',map{sprintf"%02o",index$i,$_}$s=~/./g;$t=join'',map{$_ x(160-(()=$s=~/$_/g))}0..7;print"\$s='$s';#$t\n\$_=q{$_};eval"};eval

Le passage au binaire

Dans les commentaires, Dennis a remarqué que 960 chiffres binaires permutés seraient inférieurs à 1280 chiffres octaux. J'ai donc représenté graphiquement le nombre de chiffres permutés pour chaque base de 2 à 16.

Maxima 5.29.1 http://maxima.sourceforge.net
using Lisp ECL 13.5.1
...
(%i36) n : floor(x);
(%o36)                             floor(x)
...
(%i41) plot2d(n * ceiling(log(64) / log(n)) * 80, [x, 2, 16],
              [xlabel, "base"], [ylabel, "number of permuted digits"]);
(%o41) 

graphique avec base sur l'axe des x, nombre de chiffres permutés sur l'axe des y

Bien que la base 8 soit un minimum local, les bases 2 et 3 et 4 sont égales pour la meilleure base, à 960 chiffres permutés. Pour le golf de code, la base 2 est la meilleure car Perl a des conversions pour la base 2.

Le remplacement de 1280 chiffres octaux par 960 chiffres binaires enregistre 320 caractères.

Passer d'un code octal à un code binaire coûte 8 caractères:

  • Modification octdes oct'0b'.$_coûts 7.
  • Modification /../gdes /.{6}/gcoûts 2.
  • Changer "%02o"pour "% 06b" `coûte 0.
  • Modification 160des 480coûts 0.
  • Passer 0..7en 0,1sauvegardes 1.

J'ai appris quelques conseils de golf Perl . Ils sauvent 14 caractères:

  • Changer 'A'..'Z','a'..'z','0'..'9'en A..Z,a..z,0..9utilisant des mots nus et des nombres nus, enregistre 12 caractères.
  • Changer "\n"pour $/enregistrer 2 caractères.

J'enregistre 3 caractères en déplaçant le #$tcommentaire à la fin du fichier. Cela supprime la nouvelle ligne qui termine le commentaire et un littéral \ndans la quine.

Ces modifications permettent d'économiser un total de 329 caractères et de réduire mon score de 1428 à 1099.

kernigh
la source
1
L'utilisation de chiffres binaires au lieu d'octaux nécessiterait «seulement» 960 caractères permutables.
Dennis
@Dennis Merci pour le conseil! J'ai fait le passage au binaire (sauvegarde de 312 caractères). Pendant que j'étais ici, j'ai joué au golf avec 17 autres personnages.
kernigh