Fastest Mini-Flak Quine

26

5

Mini-Flak is a subset of the Brain-Flak language, where the <>, <...> and [] operations are disallowed. Strictly speaking it must not match the following regex:

.*(<|>|\[])

Mini-Flak is the smallest known Turing complete subset of Brain-Flak.


A little while ago I was able to make a Quine in Mini-Flak, but it was too slow to run in the lifetime of the universe.

So my challenge to you is to make a faster Quine.


Scoring

To score your code put a @cy flag at the end of your code and run it in the Ruby interpreter (Try it online uses the ruby interpreter) using the -d flag. Your score should print to STDERR as follows:

@cy <score>

This is the number of cycles your program takes before terminating and is the same between runs. Since each cycle takes about the same amount of time to be run your score should be directly correlated to the time it takes to run your program.

If your Quine is too long for you to reasonably run on your computer you can calculate the number of cycles by hand.

Calculating the number of cycles is not very difficult. The number of cycles is equivalent to 2 times the number of monads run plus the number of nilads run. This is the same as replacing every nilad with a single character and counting the number of characters run in total.

Example scoring

  • (()()()) scores 5 because it has 1 monad and 3 nilads.

  • (()()()){({}[()])} scores 29 because the first part is the same as before and scores 5 while the loop contains 6 monads and 2 nilads scoring 8. The loop is run 3 times so we count its score 3 times. 1*5 + 3*8 = 29


Requirements

Your program must...

  • Be at least 2 bytes

  • Print its source code when executed in Brain-Flak using the -A flag

  • Not match the regex .*(<|>|\[])


Tips

  • The Crane-Flak interpreter is categorically faster than the ruby interpreter but lacks some of the features. I would recommend testing your code using Crane-Flak first and then score it in the ruby interpreter when you know it works. I would also highly recommend not running your program in TIO. Not only is TIO slower than the desktop interpreter, but it will also timeout in about a minute. It would be extremely impressive if someone managed to score low enough to run their program before TIO timed out.

  • [(...)]{} and (...)[{}] work the same as <...> but do not break the restricted source requirement

  • You can check out Brain-Flak and Mini-Flak Quines if you want an idea of how to approach this challenge.

Post Rock Garf Hunter

Posted 2016-12-30T22:00:32.810

Reputation: 55 382

1"current best" -> "current only" – HyperNeutrino – 2017-05-24T17:19:22.380

Answers

33

Mini-Flak, 6851113 cycles

The program (literally)

I know most people aren't likely expecting a Mini-Flak quine to be using unprintable characters and even multi-byte characters (making the encoding relevant). However, this quine does, and the unprintables, combined with the size of the quine (93919 characters encoded as 102646 bytes of UTF-8), make it fairly difficult to place the program into this post.

However, the program is very repetitive, and as such, compresses really well. So that the entire program is available literally from Stack Exchange, there's an xxd reversible hexdump of a gzip-compressed version of the full quine hidden behind the collapsible below:

00000000: 1f8b 0808 bea3 045c 0203 7175 696e 652e  .......\..quine.
00000010: 6d69 6e69 666c 616b 00ed d9db 6a13 4118  miniflak....j.A.
00000020: 0060 2f8b f808 0d64 a1c1 1dc8 4202 c973  .`/....d....B..s
00000030: 4829 4524 0409 22e2 5529 a194 1242 1129  H)E$..".U)...B.)
00000040: d2d7 ca93 f9cf 4c4c d45b 9536 e6db 6967  ......LL.[.6..ig
00000050: 770e 3bc9 ffed eca9 edb7 b1a4 9ad2 6a1d  w.;...........j.
00000060: bfab 75db c6c6 6c5f 3d4f a5a6 8da6 dcd8  ..u...l_=O......
00000070: 465b d4a5 5a28 4bd9 719d 727b aa79 f9c9  F[..Z(K.q.r{.y..
00000080: 43b6 b9d7 8b17 cd45 7f79 d3f4 fb65 7519  C......E.y...eu.
00000090: 59ac 9a65 bfdf 8f86 e6b2 69a2 bc5c 4675  Y..e......i..\Fu
000000a0: d4e4 bcd9 5637 17b9 7099 9b73 7dd3 fcb2  ....V7..p..s}...
000000b0: 4773 b9bc e9bd b9ba 3eed 9df7 aeaf 229d  Gs......>.....".
000000c0: e6ed 5eae 3aef 9d46 21b2 5e4d bd28 942e  ..^.:..F!.^M.(..
000000d0: 6917 d71f a6bf 348c 819f 6260 dfd9 77fe  i.....4...b`..w.
000000e0: df86 3e84 74e4 e19b b70e 9af0 111c fa0d  ..>.t...........
000000f0: d29c 75ab 21e3 71d7 77f6 9d8f f902 6db2  ..u.!.q.w.....m.
00000100: b8e1 0adf e9e0 9009 1f81 f011 18d8 1b33  ...............3
00000110: 72af 762e aac2 4760 6003 1bd8 698c c043  r.v...G``...i..C
00000120: 8879 6bde 9245 207c 04ae 5ce6 2d02 e1bb  .yk..E |..\.-...
00000130: 7291 4540 57f8 fe0d 6546 f89b a70b 8da9  r.E@W...eF......
00000140: f5e7 03ff 8b8f 3ad6 a367 d60b f980 679d  ......:..g....g.
00000150: d3d6 1c16 f2ff a767 e608 57c8 c27d c697  .......g..W..}..
00000160: 4207 c140 9e47 9d57 2e50 6e8e c215 b270  B..@.G.W.Pn....p
00000170: bdf6 9926 9e47 9d05 ce02 0ff0 5ea7 109a  ...&.G......^...
00000180: 8ba6 b5db 880b 970b 9749 2864 47d8 1b92  .........I(dG...
00000190: 39e7 9aec 8f0e 9e93 117a 6773 b710 ae53  9........zgs...S
000001a0: cd01 17ee b30e d9c1 15e6 6186 7a5c dc26  ..........a.z\.&
000001b0: 9750 1d51 610a d594 10ea f3be 4b7a 2c37  .P.Qa.......Kz,7
000001c0: 2f85 7a14 8fc4 a696 304d 4bdf c143 8db3  /.z.....0MK..C..
000001d0: d785 8a96 3085 2acc 274a a358 c635 8d37  ....0.*.'J.X.5.7
000001e0: 5f37 0f25 8ff5 6854 4a1f f6ad 1fc7 dbba  _7.%..hTJ.......
000001f0: 51ed 517b 8da2 4b34 8d77 e5b2 ec46 7a18  Q.Q{..K4.w...Fz.
00000200: ffe8 3ade 6fed b2f2 99a3 bae3 c949 9ab5  ..:.o........I..
00000210: ab75 d897 d53c b258 a555 1b07 63d6 a679  .u...<.X.U..c..y
00000220: 4a51 5ead a23a 6a72 9eb6 d569 960b f3dc  JQ^..:jr...i....
00000230: 9ceb 53fa 658f 345f ad07 6f6f efce 06ef  ..S.e.4_..oo....
00000240: 0677 b791 cef2 f620 57bd 1b9c 4521 b241  .w..... W...E!.A
00000250: 4d83 2894 2eaf a140 8102 050a 1428 50a0  M.(....@.....(P.
00000260: 4081 0205 0a14 2850 a040 8102 050a 1428  @.....(P.@.....(
00000270: 50a0 4081 0205 0a14 2850 a040 8102 050a  P.@.....(P.@....
00000280: 1428 50a0 4081 0205 0a14 2850 a040 8102  .(P.@.....(P.@..
00000290: 050a 1428 50a0 4081 0205 0a14 2850 a040  ...(P.@.....(P.@
000002a0: 8102 050a 1428 50a0 4081 0205 0a14 2850  .....(P.@.....(P
000002b0: a040 8102 050a 1428 50a0 4081 0205 0a14  .@.....(P.@.....
000002c0: 2850 a040 8102 050a 1428 50a0 4081 0205  (P.@.....(P.@...
000002d0: 0a14 2850 a040 8102 050a 1428 50a0 4081  ..(P.@.....(P.@.
000002e0: 0205 0a14 2850 a040 8102 050a 1428 50a0  ....(P.@.....(P.
000002f0: 4081 0205 0a14 2850 a040 8102 050a 1428  @.....(P.@.....(
00000300: 50a0 4081 0205 0a14 2850 a040 8102 050a  P.@.....(P.@....
00000310: 1428 50a0 4081 0205 0a14 2850 a040 8102  .(P.@.....(P.@..
00000320: 050a 1428 50a0 4081 0205 0a14 2850 a040  ...(P.@.....(P.@
00000330: 8102 050a 1428 50a0 4081 0205 0a14 2850  .....(P.@.....(P
00000340: a040 8102 050a 1428 50a0 4081 0205 0a14  .@.....(P.@.....
00000350: 2850 a040 8102 050a 1428 50a0 4081 0205  (P.@.....(P.@...
00000360: 0a14 2850 a040 8102 050a 1428 50a0 4081  ..(P.@.....(P.@.
00000370: 0205 0a14 2850 a01c 14ca 7012 cbb4 a6e9  ....(P....p.....
00000380: e6db e6b1 e4b1 9e4c 4ae9 d3be f5f3 745b  .......LJ.....t[
00000390: 37a9 3d6a af49 7489 a6e9 ae5c 96dd 488f  7.=j.It....\..H.
000003a0: d31f 5da7 fbad 5d56 3e73 5277 7cf5 aa7b  ..]...]V>sRw|..{
000003b0: 3fbc df7c e986 c3ba 5ee4 3c6f 74f7 c3e1  ?..|....^.<ot...
000003c0: 301a bb45 d795 9afb fbdc 1495 65d5 6d9b  0..E........e.m.
000003d0: baf7 a5b4 a87d 4a5b d7fd b667 b788 ec27  .....}J[...g...'
000003e0: c5d8 28bc b96a 9eda 7a50 524d 290a a5cb  ..(..j..zPRM)...
000003f0: cbef 38cb c3ad f690 0100                 ..8.......

(Yes, it's so repetitive that you can even see the repeats after it's been compressed).

The question says "I would also highly recommend not running your program in TIO. Not only is TIO slower than the desktop interpreter, but it will also timeout in about a minute. It would be extremely impressive if someone managed to score low enough to run their program before TIO timed out." I can do that! It takes about 20 seconds to run on TIO, using the Ruby interpreter: Try it online!

The program (readably)

Now I've given a version of the program that computers can read, let's try a version that humans can read. I've converted the bytes that make up the quine into codepage 437 (if they have the high bit set) or Unicode control pictures (if they're ASCII control codes), added whitespace (any pre-existing whitespace was converted to control pictures), run-length-encoded using the syntax «string×length», and some data-heavy bits elided:

␠
(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                («()×35» («()×44» («()×44» («()×44» («()×44» («()×45»
                … much more data encoded the same way …
                («()×117»(«()×115»(«()×117»
                «000010101011┬â┬ … many more comment characters … ┬â0┬â┬à00␈␈
                )[({})(
                    ([({})]({}{}))
                    {
                        ((()[()]))
                    }{}
                    {
                        {
                            ({}(((({}())[()])))[{}()])
                        }{}
                        (({}))
                        ((()[()]))
                    }{}
                )]{}
                %Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'×almost 241»
                ,444454545455┬ç┬ … many more comment characters … -a--┬ü␡┬ü-a␡┬ü
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

(The "almost 241" is because the 241st copy is missing the trailing ', but is otherwise identical to the other 240.)

Explanation

About the comments

The first thing to explain is, what's up with the unprintable characters and other junk that isn't Mini-Flak commands? You may think that adding comments to the quine just makes things harder, but this is a speed competition (not a size competition), meaning that comments don't hurt the speed of the program. Meanwhile, Brain-Flak, and thus Mini-Flak, just dump the contents of the stack to standard output; if you had to ensure that the stack contained only the characters that made up the commands of your program, you'd have to spend cycles cleaning the stack. As it is, Brain-Flak ignores most characters, so as long as we ensure that junk stack elements aren't valid Brain-Flak commands (making this a Brain-Flak/Mini-Flak polyglot), and aren't negative or outside the Unicode range, we can just leave them on the stack, allow them to be output, and put the same character in our program at the same place to retain the quine property.

There's one particularly important way we can take advantage of this. The quine works by using a long data string, and basically all the output from the quine is produced by formatting the data string in various ways. There's only one data string, despite the fact that the program has multiple pieces; so we need to be able to use the same data string to print different parts of the program. The "junk data doesn't matter" trick lets us do this in a very simple way; we store the characters that make up the program in the data string by adding or subtracting a value to or from their ASCII code. Specifically, the characters making up the start of the program are stored as their ASCII code + 4, the characters making up the section that's repeated almost 241 times as their ASCII code − 4, and the characters making up the end of the program are stored as their ASCII code − 8. We can then print any of these three parts of the program via printing every character of the data string with an offset; if, for example, we print it with 4 added to every character code, we get one repeat of the repeated section, with some comments before and after. (Those comments are simply the other sections of the program, with character codes shifted so that they don't form any valid Brain-Flak commands, because the wrong offset was added. We have to dodge Brain-Flak commands, not just Mini-Flak commands, to avoid violating the part of the question; the choice of offsets was designed to ensure this.)

Because of this comment trick, we actually only need to be able to output the data string formatted in two different ways: a) encoded the same way as in the source, b) as character codes with a specified offset added to every code. That's a huge simplification that makes the added length totally worth it.

Program structure

This program consists of four parts: the intro, the data string, the data string formatter, and the outro. The intro and outro are basically responsible for running the data string and its formatter in a loop, specifying the appropriate format each time (i.e. whether to encode or offset, and what offset to use). The data string is just data, and is the only part of the quine for which the characters that make it up are not specified literally in the data string (doing that would obviously be impossible, as it would have to be longer than itself); it's thus written in a way that's particularly easy to regenerate from itself. The data string formatter is made of 241 almost identical parts, each of which formats a specific datum out of the 241 in the data string.

Each part of the program can be produced via the data string and its formatter as follows:

  • To produce the outro, format the data string with offset +8
  • To produce the data string formatter, format the data string with offset +4, 241 times
  • To produce the data string, format the data string via encoding it into the source format
  • To produce the intro, format the data string with offset -4

So all we have to do is to look at how these parts of the program work.

The data string

(«()×35» («()×44» («()×44» («()×44» («()×44» («()×45» …

We need a simple encoding for the data string as we have to be able to reverse the encoding in Mini-Flak code. You can't get much simpler than this!

The key idea behind this quine (apart from the comment trick) is to note that there's basically only one place we can store large amounts of data: the "sums of command return values" within the various nesting levels of the program source. (This is commonly known as the third stack, although Mini-Flak doesn't have a second stack, so "working stack" is likely a better name in the Mini-Flak context.) The other possibilities for storing data would be the main/first stack (which doesn't work because that's where our output has to go, and we can't move the output past the storage in a remotely efficient way), and encoded into a bignum in a single stack element (which is unsuitable for this problem because it takes exponential time to extract data from it); when you eliminate those, the working stack is the only remaining location.

In order to "store" data on this stack, we use unbalanced commands (in this case, the first half of a (…) command), which will be balanced within the data string formatter later on. Each time we close one of these commands within the formatter, it'll push the sum of a datum taken from the data string, and the return values of all the commands at that nesting level within the formatter; we can ensure that the latter add to zero, so the formatter simply sees single values taken from the data string.

The format is very simple: (, followed by n copies of (), where n is the number we want to store. (Note that this means we can only store non-negative numbers, and the last element of the data string needs to be positive.)

One slightly unintuitive point about the data string is which order it's in. The "start" of the data string is the end nearer the start of the program, i.e. the outermost nesting level; this part gets formatted last (as the formatter runs from innermost to outermost nesting levels). However, despite being formatted last, it gets printed first, because values pushed onto the stack first are printed last by the Mini-Flak interpreter. The same principle applies to the program as a whole; we need to format the outro first, then the data string formatter, then the data string, then the intro, i.e. the reverse of the order in which they are stored in the program.

The data string formatter

)[({})(
    ([({})]({}{}))
    {
        ((()[()]))
    }{}
    {
        {
            ({}(((({}())[()])))[{}()])
        }{}
        (({}))
        ((()[()]))
    }{}
)]{}

The data string formatter is made out of 241 sections which each have identical code (one section has a marginally different comment), each of which formats one specific character of the data string. (We couldn't use a loop here: we need an unbalanced ) to read the data string via matching its unbalanced (, and we can't put one of those inside a {…} loop, the only form of loop that exists. So instead, we "unroll" the formatter, and simply get the intro/outro to output the data string with the formatter's offset 241 times.)

)[({})( … )]{}

The outermost part of a formatter element reads one element of the data string; the simplicity of the data string's encoding leads to a little complexity in reading it. We start by closing the unmatched (…) in the data string, then negate ([…]) two values: the datum we just read from the data string (({})) and the return value of the rest of the program. We copy the return value of the rest of the formatter element with (…) and add the copy to the negated version with {}. The end result is that the return value of the data string element and formatter element together is the datum minus the datum minus the return value plus the return value, or 0; this is necessary to make the next data string element out produce the correct value.

([({})]({}{}))

The formatter uses the top stack element to know which mode it's in (0 = format in data string formatting, any other value = the offset to output with). However, just having read the data string, the datum is on top of the format on the stack, and we want them the other way round. This code is a shorter variant of the Brain-Flak swap code, taking a above b to b above a + b; not only is it shorter, it's also (in this specific case) more useful, because the side effect of adding b to a is not problematic when b is 0, and when b is not 0, it does the offset calculation for us.

{
    ((()[()]))
}{}
{
    …
    ((()[()]))
}{}

Brain-Flak only has one control flow structure, so if we want anything other than a while loop, it'll take a bit of work. This is a "negate" structure; if there's a 0 on top of the stack, it removes it, otherwise it places a 0 on top of the stack. (It works pretty simply: as long as there isn't a 0 on top of the stack, push 1 − 1 to the stack twice; when you're done, pop the top stack element.)

It's possible to place code inside a negate structure, as seen here. The code will only run if the top of the stack was nonzero; so if we have two negate structures, assuming the top two stack elements aren't both zero, they'll cancel each other out, but any code inside the first structure will run only if the top stack element was nonzero, and the code inside the second structure will run only if the top stack element was zero. In other words, this is the equivalent of an if-then-else statement.

In the "then" clause, which runs if the format is nonzero, we actually have nothing to do; what we want is to push the data+offset to the main stack (so that it can be output at the end of the program), but it's there already. So we only have to deal with the case of encoding the data string element in source form.

{
    ({}(((({}())[()])))[{}()])
}{}
(({}))

Here's how we do that. The {({}( … )[{}()])}{} structure should be familiar as a loop with a specific number of iterations (which works by moving the loop counter to the working stack and holding it there; it'll be safe from any other code, because access to the working stack is tied to the nesting level of the program). The body of the loop is ((({}())[()])), which makes three copies of the top stack element and adds 1 to the lowest. In other words, it transforms a 40 on top of the stack into 40 above 40 above 41, or viewed as ASCII, ( into ((); running this repeatedly will make ( into (() into (()() into (()()() and so on, and thus is a simple way to generate our data string (assuming that there's a ( on top of the stack already).

Once we're done with the loop, (({})) duplicates the top of the stack (so that it now starts ((()… rather than (()…. The leading ( will be used by the next copy of the data string formatter to format the next character (it'll expand it into (()(()… then (()()(()…, and so on, so this generates the separating ( in the data string).

%Wwy$%Y%ywywy$wy$%%%WwyY%$$wy%$$%$%$%$%%wy%ywywy'

There's one last bit of interest in the data string formatter. OK, so mostly this is just the outro shifted 4 codepoints downwards; however, that apostrophe at the end may look out of place. ' (codepoint 39) would shift into + (codepoint 43), which isn't a Brain-Flak command, so you may have guessed that it's there for some other purpose.

The reason this is here is because the data string formatter expects there to be a ( on the stack already (it doesn't contain a literal 40 anywhere). The ' is actually at the start of the block that's repeated to make up the data string formatter, not the end, so after the characters of the data string formatter have been pushed onto the stack (and the code is about to move onto printing the data string itself), the outro adjusts the 39 on top of the stack into a 40, ready for the formatter (the running formatter itself this time, not its representation in the source) to make use of it. That's why we have "almost 241" copies of the formatter; the first copy is missing its first character. And that character, the apostrophe, is one of only three characters in the data string that don't correspond to Mini-Flak code somewhere in the program; it's there purely as a method of providing a constant.

The intro and outro

(((()()()()){}))
{{}
    (({})[(()()()())])
    (({})(
        {{}{}((()[()]))}{}
        (((((((({})){}){}{})){}{}){}){}())
        {
            ({}(
                (␀␀!S␠su! … many more comment characters … oq␝qoqoq)
                …
            )[{}()])
        }{}
        {}({}())
    )[{}])
    (({})(()()()()){})
}{}{}␊

The intro and outro are conceptually the same part of the program; the only reason we draw a distinction is that the outro needs to be output before the data string and its formatter are (so that it prints after them), whereas the intro needs to be output after them (printing before them).

(((()()()()){}))

We start by placing two copies of 8 on the stack. This is the offset for the first iteration. The second copy is because the main loop expects there to be a junk element on top of the stack above the offset, left behind from the test that decides whether to exist the main loop, and so we need to put a junk element there so that it doesn't throw away the element we actually want; a copy is the tersest (thus fastest to output) way to do that.

There are other representations of the number 8 that are no longer than this one. However, when going for fastest code, this is definitely the best option. For one thing, using ()()()() is faster than, say, (()()){}, because despite both being 8 characters long, the former is a cycle faster, because (…) is counted as 2 cycles, but () only as one. Saving one cycle is negligible compared to a much bigger consideration for a , though: ( and ) have much lower codepoints than { and }, so generating the data fragment for them will be much faster (and the data fragment will take up less space in the code, too).

{{} … }{}{}

The main loop. This doesn't count iterations (it's a while loop, not a for loop, and uses a test to break out). Once it exits, we discard the top two stack elements; the top element is a harmless 0, but the element below will be the "format to use on the next iteration", which (being a negative offset) is a negative number, and if there are any negative numbers on the stack when the Mini-Flak program exits, the interpreter crashes trying to output them.

Because this loop uses an explicit test to break out, the result of that test will be left on the stack, so we discard it as the first thing we do (its value isn't useful).

(({})[(()()()())])

This code pushes 4 and f − 4 above a stack element f, whilst leaving that element in place. We're calculating the format for the next iteration in advance (while we have the constant 4 handy), and simultaneously getting the stack into the correct order for the next few parts of the program: we'll be using f as the format for this iteration, and the 4 is needed before that.

(({})( … )[{}])

This saves a copy of f − 4 on the working stack, so that we can use it for the next iteration. (The value of f will still be present at that point, but it'll be in an awkward place on the stack, and even if we could manoeuvre it to the correct place, we'd have to spend cycles subtracting 4 from it, and cycles printing the code to do that subtraction. Far easier simply to store it now.)

{{}{}((()[()]))}{}

A test to see if the offset is 4 (i.e. f − 4 is 0). If it is, we're printing the data string formatter, so we need to run the data string and its formatter 241 times rather than just once at this offset. The code is fairly simple: if f − 4 is nonzero, replace the f − 4 and the 4 itself with a pair of zeros; then in either case, pop the top stack element. We now have a number above f on the stack, either 4 (if we want to print this iteration 241 times) or 0 (if we want to print it only once).

(
    ((((((({})){}){}{})){}{}){}){}
    ()
)

This is an interesting sort of Brain-Flak/Mini-Flak constant; the long line here represents the number 60. You may be confused at the lack of (), which are normally all over the place in Brain-Flak constants; this isn't a regular number, but a Church numeral, which interprets numbers as a duplication operation. For example, the Church numeral for 60, seen here, makes 60 copies of its input and combines them all together into a single value; in Brain-Flak, the only things we can combine are regular numbers, by addition, so we end up adding 60 copies of the top of the stack and thus multiplying the top of the stack by 60.

As a side note, you can use an Underload numeral finder, which generates Church numerals in Underload syntax, to find the appropriate number in Mini-Flak too. Underload numerals (other than zero) use the operations "duplicate top stack element" : and "combine top two stack elements" *; both those operations exist in Brain-Flak, so you just translate : to ), * to {}, prepend a {}, and add enough ( at the start to balance (this is using a weird mix of the main stack and working stack, but it works).

This particular code fragment uses the church numeral 60 (effectively a "multiply by 60" snippet), together with an increment, to generate the expression 60x + 1. So if we had a 4 from the previous step, this gives us a value of 241, or if we had a 0, we just get a value of 1, i.e. this correctly calculates the number of iterations we need.

The choice of 241 is not coincidental; it was a value chosen to be a) approximately the length at which the program would end up anyway and b) 1 more than 4 times a round number. Round numbers, 60 in this case, tend to have shorter representations as Church numerals because you have more flexibility in factors to copy. The program contains padding later on to bring the length up to 241 exactly.

{
    ({}(
        …
    )[{}()])
}{}

This is a for loop, like the one seen earlier, which simply runs the code inside it a number of times equal to the top of the main stack (which it consumes; the loop counter itself is stored on the working stack, but visibility of that is tied to the program's nesting level and thus it's impossible for anything but the for loop itself to interact with it). This actually runs the data string and its formatter 1 or 241 times, and as we've now popped all the values we were using for our control flow calculation from the main stack, we have the format to use on top of it, ready for the formatter to use.

(␀␀!S␠su! … many more comment characters … oq␝qoqoq)

The comment here isn't entirely without interest. For one thing, there are a couple of Brain-Flak commands; the ) at the end is naturally generated as a side effect of the way the transitions between the various segments of the program work, so the ( at the start was manually added to balance it (and despite the length of the comment inside, putting a comment inside a () command is still a () command, so all it does is add 1 to the return value of the data string and its formatter, something that the for loop entirely ignores).

More notably, those NUL characters at the start of the comment clearly aren't offsets from anything (even the difference between +8 and -4 isn't enough to turn a ( into a NUL). Those are pure padding to bring the 239-element data string up to 241 elements (which easily pay for themselves: it would take much more than two bytes to generate 1 vs. 239 rather than 1 vs. 241 when calculating the number of iterations required). NUL was used as the padding character because it has the lowest possible codepoint (making the source code for the data string shorter and thus faster to output).

{}({}())

Drop the top stack element (the format we're using), add 1 to the next (the last character to be output, i.e. the first character to be printed, of the program section we just formatted). We don't need the old format any more (the new format is hiding on the working stack); and the increment is harmless in most cases, and changes the ' at one end of the source representation of the data string formatter into a ( (which is required on the stack for next time we run the formatter, to format the data string itself). We need a transformation like that in the outro or intro, because forcing each data string formatter element to start with ( would make it somewhat more complex (as we'd need to close the ( and then undo its effect later), and we'd somehow need to generate an extra ( somewhere because we only have almost 241 copies of the formatter, not all 241 (so it's best that a harmless character like ' is the one that's missing).

(({})(()()()()){})

Finally, the loop exit test. The current top of the main stack is the format we need for the next iteration (which just came back off the working stack). This copies it and adds 8 to the copy; the resulting value will be discarded next time round the loop. However, if we just printed the intro, the offset was -4 so the offset for the "next iteration" will be -8; -8 + 8 is 0, so the loop will exit rather than continuing onto the iteration afterwards.

ais523's temporary account

Posted 2016-12-30T22:00:32.810

Reputation: 1 331

16

128,673,515 cycles

Try it online

Explanation

The reason that Miniflak quines are destined to be slow is Miniflak's lack of random access. To get around this I create a block of code that takes in a number and returns a datum. Each datum represents a single character like before and the main code simply queries this block for each one at a time. This essentially works as a block of random access memory.


This block of code has two requirements.

  • It must take a number and output only the character code for that character

  • It must be easy to reproduce the lookup table bit by bit in Brain-Flak

To construct this block I actually reused a method from my proof that Miniflak is Turing complete. For each datum there is a block of code that looks like this:

(({}[()])[(())]()){(([({}{})]{}))}{}{(([({}{}(%s))]{}))}{}

This subtracts one from the number on top of the stack and if zero pushes %s the datum beneath it. Since each piece decrements the size by one if you start with n on the stack you will get back the nth datum.

This is nice and modular, so it can be written by a program easily.


Next we have to set up the machine that actually translates this memory into the source. This consists of 3 parts as such:

(([()]())())
{({}[(
  -Look up table-
 )]{})
 1. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}(([{}]))(()()()()()))]{})}{}

 2. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
      (({}[(
      ({}[()(((((()()()()()){}){}){}))]{}){({}[()(({}()))]{}){({}[()(({}((((()()()){}){}){}()){}))]{}){({}[()(({}()()))]{}){({}[()(({}(((()()()()())){}{}){}))]{}){([(({}{}()))]{})}}}}}{}
      (({}({}))[({}[{}])])
     )]{}({})[()]))
      ({[()]([({}({}[({})]))]{})}{}()()()()()[(({}({})))]{})
    )]{})}{}

 3. (({}[()])[(())]()){(([({}{})]{}))}{}{([({}{}
     (({}(({}({}))[({}[{}])][(
     ({}[()(
      ([()](((()()[(((((((()()()){})())){}{}){}){})]((((()()()()())){}{}){})([{}]([()()](({})(([{}](()()([()()](((((({}){}){}())){}){}{}))))))))))))
     )]{})
     {({}[()(((({})())[()]))]{})}{}
     (([(((((()()()()){}){}()))){}{}([({})]((({})){}{}))]()()([()()]({}(({})([()]([({}())](({})([({}[()])]()(({})(([()](([({}()())]()({}([()](([((((((()()()())()){}){}){}()){})]({}()(([(((((({})){}){}())){}{})]({}([((((({}())){}){}){}()){}()](([()()])(()()({}(((((({}())())){}{}){}){}([((((({}))){}()){}){}]([((({}[()])){}{}){}]([()()](((((({}())){}{}){}){})(([{}](()()([()()](()()(((((()()()()()){}){}){}()){}()(([((((((()()()())){}){}())){}{})]({}([((((({})()){}){}){}()){}()](([()()])(()()({}(((((({}){}){}())){}){}{}(({})))))))))))))))))))))))))))))))))))))))))))))))
     )]{})[()]))({()()()([({})]{})}{}())
    )]{})}{}

   ({}[()])
}{}{}{}
(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

The machine consists of four parts that are run in order starting with 1 and ending with 3. I have labeled them in the code above. Each section also uses the same lookup table format I use for the encoding. This is because the entire program is contained in a loop and we don't want to run every section every time we run through the loop so we put in the same RA structure and query the section we desire each time.

1

Section 1 is a simple set up section.

The program tells first queries section 1 and datum 0. Datum 0 does not exist so instead of returning that value it simply decrements the query once for each datum. This is useful because we can use the result to determine the number of data, which will become important in future sections. Section 1 records the number of data by negativizing the result and queries Section 2 and the last datum. The only problem is we cannot query section 2 directly. Since there is another decrement left we need to query a non-existant section 5. In fact this will be the case every time we query a section within another section. I will ignore this in my explanation however if you are looking a the code just remember 5 means go back a section and 4 means run the same section again.

2

Section 2 decodes the data into the characters that make up the code after the data block. Each time it expects the stack to appear as so:

Previous query
Result of query
Number of data
Junk we shouldn't touch...

It maps each possible result (a number from 1 to 6) to one of the six valid Miniflak characters ((){}[]) and places it below the number of data with the "Junk we shouldn't touch". This gets us a stack like:

Previous query
Number of data
Junk we shouldn't touch...

From here we need to either query the next datum or if we have queried them all move to section 3. Previous query is not actually the exact query sent out but rather the query minus the number of data in the block. This is because each datum decrements the query by one so the query comes out quite mangled. To generate the next query we add a copy of the number of data and subtract one. Now our stack looks like:

Next query
Number of data
Junk we shouldn't touch...

If our next query is zero we have read all the memory needed in section 3 so we add the number of data to the query again and slap a 4 on top of the stack to move onto section 3. If the next query is not zero we put a 5 on the stack to run section 2 again.

3

Section 3 makes the block of data by querying our RAM just as section 3 does.

For the sake of brevity I will omit most of the details of how section 3 works. It is almost identical to section 2 except instead of translating each datum into one character it translates each into a lengthy chunk of code representing its entry in the RAM. When section 3 is done it tells the program to exit the loop.


After the loop has been run the program just needs to push the first bit of the quine ([()]())(()()()()){({}[(. I does this with the following code implementing standard Kolmogorov-complexity techniques.

(([(((((()()()()){}){}())){}{})]((({}))([()]([({}())]({}()([()]((()([()]((()([({})((((()()()()){}){}()){})]()())([({})]({}([()()]({}({}((((()()()()()){}){}){}))))))))))))))))))

I hope this was clear. Please comment if you are confused about anything.

Post Rock Garf Hunter

Posted 2016-12-30T22:00:32.810

Reputation: 55 382

About how long does this take to run? It times on TIO. – Pavel – 2017-01-05T06:32:28.167

@Pavel I don't run it on TIO because that would be incredibly slow, I do use the same interpreter that TIO uses (the ruby one). It takes about 20 minutes to run on an old rack server I have access to. It takes about 15 minutes in Crain-Flak, but Crain-Flak doesn't have debug flags so I cannot score it without running it in the Ruby interpreter.

– Post Rock Garf Hunter – 2017-01-05T16:00:24.883

@Pavel I ran it again and timed it. It took 30m45.284s to complete on a rather low end server (roughly the equivalent of a average modern desktop) using the ruby interpreter. – Post Rock Garf Hunter – 2017-01-05T16:38:42.083