A Quine Puzzle • Hacker News Board

Re: A Quine Puzzle

#31

Post by wgreenberg » Tue, Jul 21, 2015, 8:22 PM UTC

matchu wrote: post #20

Does there exist a solution that doesn't rely on undefined repeat behavior? I finally gave in and looked at the answers, but it looks like they all use `repeat M N>M`, or `repeat M N>currentOutputSize`. I kinda assumed that the interpreter was just there for convenience, and that its implementation of undefined behavior was irrelevant. But is the interpreter's implementation critical to the solution? (Then again, I'm…

Although I may be mistaken, LZ77 defines the repeat behavior to do exactly that: https://en.wikipedia.org/wiki/LZ77_and_LZ78#Example

Re: A Quine Puzzle

#32

Post by Yen » Tue, Jul 21, 2015, 9:18 PM UTC

personjerry wrote: post #15

Yen wrote: post #14

Earlier quoted context omitted.

Maybe it copy-pasted wrong, but this doesn't look like a solution to me. The output is shorter than the input, and contains commands in a different order.

I just tried it again, and then copy pasted from the output to the input; it still works. Did you select the full string and decode with base64?

hmm. Just tried it again, and it worked now. Nice job getting one that doesn't start with repeat!

Re: A Quine Puzzle

#33

Post by spacehome » Tue, Jul 21, 2015, 9:20 PM UTC

AaronFriel wrote: post #17

cHJpbnQgMQpwcmludCAxCnByaW50IDEKcHJpbnQgMQpwcmludCAxCnByaW50IDEKcmVwZWF0IDMg MgpwcmludCAyCnJlcGVhdCAzIDIKcHJpbnQgMgpyZXBlYXQgMyAyCgo= Wasn't terribly difficult, though not the shortest. What's the code golf answer?

I wrote an program to exhaustively search (in an intelligent way so that it terminates before the universe does). The minimal to do it without depending on undefined repeat behavior is 10 statements (and there's only one of this length). It's posted by JoshTriplett.

Re: A Quine Puzzle

#34

Post by spacehome » Tue, Jul 21, 2015, 10:13 PM UTC

mattdodge wrote: post #13

daveloyall wrote: post #2

Spoiler: cmVwZWF0IDMgMgpwcmludCAyCnJlcGVhdCAzIDIKcHJpbnQgMgpyZXBlYXQgMyAyCg==

This is the shortest one of the solutions so far. Wonder if it's the shortest possible? (Other than empty = empty)

Yes. It is the unique shortest possible solution if you allow for a repeat at the beginning. OTOH if you disallow starting with a REPEAT, the shortest is length 10.

Re: A Quine Puzzle

#35

Post by [deleted] » Tue, Jul 21, 2015, 10:28 PM UTC

[deleted]

Re: A Quine Puzzle

#36

Post by spacehome » Tue, Jul 21, 2015, 10:33 PM UTC

I made an Objective-C command-line tool that exhaustively searches for solutions.

http://pastebin.com/H2nZ9Fxz

It found JoshTriplett's 10-line solution and shows that it's minimal if you don't allow undefined REPEAT behavior, and it found daveloyall's 5-line solution and shows that it's minimal of you do allow undefined REPEAT behavior.