5
\$\begingroup\$

https://mihaly.barasz.com/compressed-loop/game.html

You have a simple, line-oriented “compression” language. The language works as follows:

The document must start with the begin keyword and end with the end keyword. There are two possible commands, each identified with a single letter followed by one or two non-negative integer arguments. These are as follows:

  • Literal: l n — The n lines that follow this command are added to the output as is. The next command comes after that.

  • Repeat: r n k — The k lines of the output which start at the nth line from the current end of the output are repeated. Note, that if k > n, then some of the repeated lines will be the lines that were added by this command itself.

Your goal is to create a valid “compressed” document for which the output is identical to the input. Write the compressed document on the left, see the result on the right.

For example,

begin
l 3
foo
bar
baz
r 2 1
r 4 1
end

outputs

foo
bar
baz
bar
foo

What is the fewest number of instructions needed to realize a quine?

\$\endgroup\$

3 Answers 3

6
\$\begingroup\$

27 instructions

begin
l 3
begin
l 3
begin
l 3
l 3
begin
l 3
l 3
l 3
begin
l 3
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
doesn't
matter
r 2 2
end
r 2 2
end

Based on @programjames answer.

\$\endgroup\$
3
  • \$\begingroup\$ I brute-forced for solutions that only used l 3 3, l 3 4, and r x y where x and y ranged from 1 to 5, but my script ran out of memory. Its best solution so far was similar to this solution though. \$\endgroup\$
    – Neil
    Apr 10 at 4:59
  • \$\begingroup\$ ... because it had a stupid bug and was never going to terminate. Sigh... \$\endgroup\$
    – Neil
    Apr 10 at 6:45
  • \$\begingroup\$ Having finally fixed my code, it now finds this solution in 8 seconds. \$\endgroup\$
    – Neil
    Apr 11 at 5:31
4
\$\begingroup\$

24 instructions

begin
l 1
begin
l 1
l 1
l 4
begin
l 1
l 1
l 4
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
doesn't
matter
r 2 2
end
r 2 2
end

Based on the following answer. First 17 steps found in 1 minute by a Python script by a Python script checking most combinations of instructions using arguments ranging from 1 to 5 inclusive. Fortunately it happened to spot a partial solution that I was then able to complete.

26 instructions

begin
l 2
begin
l 2
l 3
begin
l 2
l 3
l 3
begin
l 2
l 3
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
r 4 4
l 4
doesn't
matter
r 2 2
end
r 2 2
end

Based on @gsitcia's answer. Found in 2.5 minutes by a Python script checking most combinations of instructions using arguments ranging from 2 to 5 inclusive. (The script isn't infallible but fortunately the wild cards in the output it did find can be filled in consistently.)

\$\endgroup\$
2
  • \$\begingroup\$ I've also brute-forced all programs ending in the same 7 instructions using parameters from 1 to 8 inclusive and this is still the optimal answer. \$\endgroup\$
    – Neil
    Apr 11 at 7:42
  • \$\begingroup\$ I've now brute-forced all programs of up to 24 instructions using parameters from 1 to (I think) 6 inclusive and this is still an optimal answer (my script stopped at the first answer). \$\endgroup\$
    – Neil
    Apr 15 at 13:13
4
\$\begingroup\$

37 instructions:

begin
l 4
begin
l 4
begin
l 4
l 4
begin
l 4
l 4
begin
l 4
l 4
l 4
begin
l 4
l 4
l 4
l 4
begin
l 4
r 5 5
l 3
r 5 5
l 3
r 5 5
l 3
l 3
r 5 5
l 3
r 5 5
l 3
r 3 2
end
r 3 2
r 3 2
end
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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