Program that permutes itself to encode a string (quine-variant)

Question

Write a program that prints the following 80-character line:

This program from codegolf.stackexchange.com permutes itself to encode a string.

then accepts one line of input, then prints its source code with its code points possibly reordered (none added and none deleted). When that code is executed, the same has to happen, except the printed line would be the most recent line of input.

The Perl-style regex ^[A-Za-z0-9. ]{80}$ will match any line of input. You cannot make any additional assumption.

A submission's score is the number of code points in its source code less 94. Lower is better.

The code must not do anything that would be unacceptable in a quine (e.g. file reading). In particular, any submission with a negative score must be cheating somehow, as 93! is less than 64⁸⁰.

Added 2014-04-21: Your program's entire source code must be well-formed in the character encoding under which you count code points. For example, you cannot use 80 consecutive bytes in the UTF-8 trailing byte range (80..BF) and count each as a single U+FFFD REPLACEMENT CHARACTER (or worse, as not a code point at all).

Additionally, if the encoding allows multiple ways to encode a code point (e.g. SCSU), your program, as well as all programs it directly or indirectly generates, must only use one of them (or at least all must be treated equivalently throughout the code).

Answer 1

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$=.@^}/]"'".@+\+\'.~'}.~

How it works

We start by choosing 94 different characters that will get permuted to encode a string. Any 94 characters would work, but we choose the following for golfing purposes:

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

Let's call the array of these characters “&”.

The line of input will always contain 81 characters (including the LF). All of those characters are present in the first 65 characters of “&”. This is the sole reason for choosing characters in the upper 128 bytes.

We replace each character of the string by its index in “&”, so LF becomes 0, space becomes 1, etc.

We consider the 81 obtained numbers the digits of a single base 65 number. Let's call this number “N”.

Now, we enumerate all possible permutations of “&” and retrieve the permutation corresponding to the number from above. This is achieved in the following manner:

1. Set c = 1 and A = [].
2. Prepend N % c to A.
3. Set N = N / c and c = c + 1.
4. If c < 95, go back to 2.
5. Set i = 0 and s = "".
6. Retrieve the charcter &[A[i]], append it to “s” and remove it from “&”.
7. Set i = i + 1.
8. If i < 94 go back to 6.

Suppose we have code blocks “E” and “D” that encode and decode a string as explained above.

Now, we need a wrapper for those code blocks that complies with the requirements of the question:

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

This does the following:

• {…}.~ defines a block, duplicates it and executes the second copy. The first copy will remain on the stack.

• \.$ swaps the encoded string with the block and creates a copy of the encoded string, with sorted characters.

• [{}/]:&; converts the string from above into an array, saves it in “&” and discards it.

• D puts decodes the encoded string and prints the result.

• '"#{`head -1`}"'~ reads one line of input by executing head -1 in the shell.

• E "'".@+\+ encodes the string and prepends and appends a single quote.

• \'.~' swaps the encoded string and the block and appends the string '.~'.

• After the block has been executed, GolfScript prints the contents of the stack (encoded string, block, '.~') and exits.

“E” can be defined as follows:

{&?}%        # 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” can be defined as follows:

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.

Final golfing:

• Replace \.$[{}/]:&;0&@ with 0@.$[{}/]:&\ to save two characters.

• Define the function {;65base}:b to save one character.

• Remove all whitespace except the trailing LF and the LF in the string.

Example

$ # 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.

Answer 2

Perl, 1428 1099

This has 1193 ASCII characters (including 960 permuted binary digits). 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

My first design

Before I took a suggestion from Dennis to switch to binary, my program permuted octal digits.

My first design encodes each string in 160 octal digits, with 2 digits per character. This encoding has 100₈=64 different characters. The octal system has 8 different digits. The program must have 160 copies of each digit, so it permutes 8×160=1280 digits.

I keep 160 digits in $s and the other 1120 digits in $t. I start with a program that is not a quine, but only prints the assignments to $s and $t for the next run. This is it:

$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)) is an assignment to an empty list of variables. I take this trick from the context tutorial at PerlMonks. It forces list context on the match operator =~. In scalar context, the match would be true or false, and I would need a loop like $i++ while ($s =~ /$_/g) to count the matches. In list context, $s =~ /$_/g is a list of matches. I put this list in the scalar context of a subtraction, so Perl counts the list elements.

To make a quine, I take the form $_=q{print"\$_=q{$_};eval"};eval from the Perl quines at Rosetta Code. This one assigns a string q{...} to $_ and then calls eval, so I can have my code in a string and also run it. My program becomes a quine when I wrap my third to last lines in $_=q{ and };eval, and change my last print to print "\$s = '$s';\n\$t = '$t';\n\$_=q{$_};eval".

Finally, I golf my program by changing the first assignment to $t to a comment, and by removing extra characters.

This has 1522 ASCII characters (including 1280 permuted octal digits).
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

The switch to binary

In the comments, Dennis noticed that 960 permuted binary digits would be fewer than 1280 octal digits. So I graphed the number of permuted digits for each base from 2 to 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) 

Though base 8 is a local minimum, bases 2 and 3 and 4 tie for best base, at 960 permuted digits. For code golf, base 2 is best because Perl has conversions for base 2.

Replacing 1280 octal digits with 960 binary digits saves 320 characters.

Switching code from octal to binary costs 8 characters:

• Change oct to oct'0b'.$_ costs 7.
• Change /../g to /.{6}/g costs 2.
• Change "%02o" to "%06b"` costs 0.
• Change 160 to 480 costs 0.
• Change 0..7 to 0,1 saves 1.

I learned some Perl golf tips. They save 14 characters:

• Change 'A'..'Z','a'..'z','0'..'9' to A..Z,a..z,0..9, using barewords and bare numbers, saves 12 characters.
• Change "\n" to $/ saves 2 characters.

I save 3 characters by moving the #$t comment to the end of the file. This removes the newline that ends the comment, and a literal \n in the quine.

These changes save a total of 329 characters, and reduce my score from 1428 to 1099.