5
\$\begingroup\$

A program is "conveniently palindromic" if

it is equal to the string derived when its reverse has all its parentheses (()), brackets ([]), and braces ({}) flipped. No other characters are special and require flipping. (<> are sometimes paired but often not so they are left out.)

copied from this challenge.

Write a conveniently palindromic program that prints its own source.

You must be able to prove that it is impossible to remove one or more byte from the program so that the resulting program, when executed in the same language:

  • prints the original source, or
  • prints the new modified source

Note that the resulting program won't necessarily be a convenient palindrome. It also means that you cannot use comments or equivalent structures.

Rules

  • Program must be longer than one character
  • Reading you own source code (from the file or any other resource) is forbidden.
  • Your program must be a proper quine.
\$\endgroup\$
  • 1
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Dec 15 '16 at 17:27
  • \$\begingroup\$ Is it OK to submit a proper quine from which characters can be deleted to make an improper quine? \$\endgroup\$ – user62131 Dec 15 '16 at 18:11
  • \$\begingroup\$ @ais523 Yes, you can. \$\endgroup\$ – noɥʇʎԀʎzɐɹƆ Dec 15 '16 at 21:06
  • \$\begingroup\$ Is it OK if the program exits via crashing after it's produced the appropriate quine output? Or does it have to exit the "normal way"? \$\endgroup\$ – user62131 Dec 26 '16 at 4:52
  • 1
    \$\begingroup\$ This would be a pretty hard challenge for most non-esoteric/non-golfing languages; moreover, it would be impossible to verify programs over, say, 40 bytes, which is 2^40 = 1e+12 subsets. I suppose you could remove some of the trivial subsets, but still.... \$\endgroup\$ – Calconym Dec 28 '16 at 23:06
6
\$\begingroup\$

Jelly, 17 bytes

ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð

Try it online!

Verfication

A string of length 17 has only 217 = 131,072 subsequences, so this can be done by brute force.

$ # Generate all 131,072 subsequences of the source code.
$ jelly eun '“ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð”ṾḊṖŒPY' > subsequences
$ wc -l subsequences
131072 subsequences
$ cat verify.py
import jelly

# Discard extraneous output to STDOUT (just a bunch of 0's and [0]'s).

jelly.print = lambda _, end: None

for line in open('subsequences').readlines():
        line = line.strip()
        try:
                output = jelly.stringify(jelly.jelly_eval(line, []))
        except:
                output = ''
        if output == line or output == 'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð':
                print(repr(line))

$ time python3 verify.py
'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð'

real    0m9.678s
user    0m9.653s
sys     0m0.028s

How it works

ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð  Main link. No arguments. Implicit left argument: 0

       ø           Make the chain to the right niladic.
        “øḄŒṚṖṾṛð  Yield the string 'øḄŒṚṖṾṛð'.
ð                  Make the chain to the right and up to ø dyadic.
                   The main link is now a monadic 2,0-chain, so the dyadic chain
                   is called with the implicit left argument 0 and right argument
                   'øḄŒṚṖṾṛð'.
 ṛ                 Yield the right argument, i.e., 'øḄŒṚṖṾṛð'.
  Ṿ                Uneval; yield the string representation of the right argument,
                   i.e., '“øḄŒṚṖṾṛð”'.
   Ṗ               Pop; remove the last character, yielding '“øḄŒṚṖṾṛð'.
    Ṛ              Reverse, yielding 'ðṛṾṖṚŒḄø“'.
     ŒḄ            Bounce, yielding 'ðṛṾṖṚŒḄø“øḄŒṚṖṾṛð'.
                   (implicit) Print the last return value.
\$\endgroup\$
4
\$\begingroup\$

7, 12 bytes

The program is in binary. Here's an xxd dump:

00000000: 47b6 1818 b647 47b6 1818 b647            G....GG....G

This is rather more readable in the alternative octal notation (which isn't a valid answer to the question because changing the encoding changes the boundaries between bits):

2173303006133107217330300613310

Try it online!

Here's how the octal encoding of one half of the program corresponds to the packed encoding. (The other half is identical, except that it doesn't have a trailing 7 command because trailing 1 bits are treated like trailing whitespace, and ignored.) This is the form in which I actually worked on the problem, because trying to ensure that a program makes sense when viewed as three-bit chunks, but is palindromic when viewed as eight-bit chunks, is really unintuitive.

 2  1  7  3  3  0  3  0  0  6  1  3  3  1  0  7
...'''...'''...'''...'''...'''...'''...'''...'''
010001111011011000011000000110001011011001000111
........''''''''........''''''''........''''''''
   47      b6      18      18      b6      47

Like most golfed 7 quines, this program consists of two halves, each of which prints the other. Each half is originally passive on the stack, but an active copy is made and executed when the program runs out of commands to run, in reverse order from right to left. Here's how the active copy works (I'm using the escaped representation here because the unescaped representation contains some commands that don't have names, and thus are hard to talk about):

2          Copy the top of the stack
173303006  Push "330300" onto the stack
13         Pop the top of the stack
3          Output the copy of the top of the stack, and discard the original
10         Append nothing to the top of stack

In other words, each half of the program prints itself (because it's still at the top of the stack; the original wasn't removed when the copy was made), and then throws itself away. So this is effectively just the standard 7 quine 23723 written in a particularly verbose way, to make it palindromic at the byte level.

There's quite a lot of junk code here that doesn't do anything useful, and it could easily be deleted if deletions were at the command level. (As a result, I suspect this can be golfed substantially smaller, but I can't see how.) This might seem to violate the specification; however, the problem defines comment-freedom via deletion at the byte level (which makes about as little sense for 7 as requiring the program to be a palindrome at the byte level does), and doing that will typically throw off the boundaries between commands, making the program quite different. The rest of this post, therefore, talks about how I ensured that no deletions could lead to a proper quine.

Verification

I used the following Perl program to find all 7 quines, and all 7 programs printing the original program, that could be produced via deleting from the existing code (plus the original code itself, as it was easier to disregard that by hand than to write code to ignore it):

use 5.010;
use IPC::Run qw/run timeout/;
undef $/;
$| = 1;

my %seen = ();
my $original = <>;
sub check_program {
    my $unprocessed = shift;
    my $processed = shift;
    if ($unprocessed eq '') {
        my ($out, $err);
        $seen{$processed} and return;
        $seen{$processed}++;
        my $binary = unpack "B*", $processed;
        $binary =~ s/1+$//;
        $binary .= 1 while (length $binary) % 3;
        my $program = "";
        $program .= oct "0b$&" while $binary =~ s/^...//;
        print "$program          \r";
        my $ok = "t";
        eval {
            $ok = run [$^X, '7.pl'], '<', \$processed, '>', \$out, '2>', \$err, timeout(1);
            $ok = $ok ? "x" : "e";
        };
        if ($out eq $processed || $out eq $original) {
            $out eq $original and $ok .= "o";
            print "$program $ok\n";
        }
    } else {
        $unprocessed =~ s/^.//;
        check_program($unprocessed, $&.$processed);
        check_program($unprocessed, $processed);
    }
}

check_program($original, "");

The program produces quite a bit of output, because there are a number of 7 quines that can be produced like this. However, none are proper quines. They fall into three groups, listed here in octal to make it easier to verify that they aren't proper quines:

Programs which print themselves plus 21, but crash before it can be output

2161403021733030061
2161403055414030555
2161403055414030
2161403055443430555
2161403055443430
2161403055443507061
2161403055533030555
2161403055533030
21614030555
21614030

These programs each consist of the escaped representation of a single stack element that starts 721614030. (Where did the initial 7 come from? Each program starts with two empty elements on the stack, which is equivalent to two implicit 7s.) When it gets unescaped at runtime, its behaviour breaks down like this:

7216    Append "21" to the top of stack
14      Push two empty stack elements beneath the top of stack
0       Escape the top of stack, then append it to the element beneath
3       Output the top of stack, delete the second stack element
0       Crash due to insufficient stack

Now, when producing the first output in 7, you have to specify an output format. If the output is in need of escaping, that automatically escapes it and prepends a 7, and the first character output (in this case a 7) selects the format; most 7 quines rely on this. These programs, however, do the escaping manually, meaning that there's no implicitly prepended 7. Rather, the 7 at the start of the escaped representation (72161403021, etc.) ends up selecting the format, so it doesn't get escaped explicitly. In other words, the program prints itself plus an appended 21, then crashes.

The problem, of course, is that we're using packed, not octal, representation, so 21 is only six bits long, i.e. not a byte. As such, it can't (with programs of the lengths shown here) be output immediately, because more bits are needed to determine which byte to output. The 21 would be padded up to a full byte with 1 bits if the program exited normally, but it never gets a chance; it crashes before anything more can be output. When the crash occurs, the interpreter just exits immediately, and never gets the chance to print the incomplete byte.

Of course, this is an improper quine because all the output that's actually produced was produced via literally printing the corresponding characters of the original program.

Programs that print themself literally

Programs that crash:

2173303006133107061
217330300613310721614030555
217330300613310721614030

Programs that exit normally:

2173303006133030555
2173303006133030
2173303006133107061333
217330300613310
21733030061333
21733030554434300613310
2173303055443430061333
21733030555330300613310
2173303055533030061333

These all follow the same basic principle as the original program, but only have one stack element (either because the 7 that would normally separate stack elements got deleted, or because it's matched by a 6 later in the program, combining the element into one large element). The stack element prints itself literally first, for the same reason that the two elements in the original program each print the other, and then runs some random commands that don't produce output. Because the entire program is basically just a literal that prints itself, this doesn't count as a proper quine

The null quine

Yes, the null program is a quine in 7, and yes, you can produce it via deleting from the original program. This clearly isn't a proper quine, though.

\$\endgroup\$
2
+50
\$\begingroup\$

RProgN, 3 Bytes.

1
1

Good luck out golfing this one.

This is a valid quine, as each 1 prints the opposite 1, which can be proven by the code

1
2

which prints

2
1

As for removing characters, 11 prints 11, although is not a valid quine, as it's a constant. The other options, 1_ and _1 (where _ is a newline) are also not valid, as they are only constants, and they are missing the white space.

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Where are the newlines in the input? I believe 1\n1 prints 1\n1\n, thus isn't a quine; and although 1\n1\n is a quine, it isn't palindromic. \$\endgroup\$ – user62131 Dec 28 '16 at 1:33
  • 3
    \$\begingroup\$ Actually, 1\n1 now does, and has for a while, printed 1\n1, due to uh, 'popular demand'. \$\endgroup\$ – ATaco Dec 28 '16 at 1:34
  • \$\begingroup\$ Much like how 11 was not a valid Quine, neither is just a single 1, which the OP confirmed was valid in the comments \$\endgroup\$ – ATaco Jan 5 '17 at 2:43
1
\$\begingroup\$

Befunge-98, 55 or 57 bytes

<#0289+*00#p>$$$>:#,_652**,@,**256_,#:>$$$>p#00*+9820#<

Try it online!

This solution is dependent on the behaviour of wraparound strings. Most Befunge-98 implementations will push a space onto the stack whenever a string wraps across the edge of the playfield, while the FBBI interpreter (which is what is used by TIO) will not. If you want to test this on other interpreters, you'll most likely need to include an additional $ (drop) command to get rid of that extra space:

<#0289+*00#p>$$$$>:#,_652**,@,**256_,#:>$$$$>p#00*+9820#<

In theory it should be possible to make a more portable solution that would work on all interpreters (possibly even Befunge-93), but that would require a good deal more code.

Proof of validity

While there are characters in the code that aren't actually executed, they are all used in the construction of the output, and removing any of those characters will result in output that neither matches the original source or the modified source. This is because the output string is built up in reverse, and it is thus imperative that the source be palindromic for the output to match. If you can remove a character and still have it work, you'll just have created a better solution.

Explanation

<                  Reverse the direction of execution, wrapping to the end of the line.
           0#<     Jump over the zero.
      *+982        Push 34 (a double quote character) onto the stack. 
    00             Push two zeros - the coordinates of the first character in the source.
 >p#               Turn around and 'put' the double quote into the source at 0,0.
    00*+982        In reverse, this just pushes some numbers that will be ignored.
           0       This zero will serve as the string terminator though.
            #<     Jump over the left arrow so we can wrap around back to the start.

"#0289+*00...      At this point the first character has been updated to a quote, so 
                     we're now going to switch to string mode and push the entire source
                     onto the stack in reverse order. When the end of the line is reached, 
                     the string will wrap around to the start and terminate when it
                     encounters the quote again.

#0289+*00#p        Again we've got a sequence pushing values that we don't actually want.
           >$$$    This time we need to get rid of them, with a few drop operations.

>:#,_              A standard output routine, writing out the source from the stack.
     652**,        The last '<' character has to be output manually though.
           @       Then finally we can exit.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.