title: Fastest Mini-Flak Quine

text:
# Question
Title: Fastest Mini-Flak Quine
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.

# Answer
# 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 60*x* \+ 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.
> 43 votes

# Answer
# 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.
> 18 votes

---
Tags: restricted-source, quine, fastest-code, brain-flak
---


title: golf atan2

text:
# Question
Title: golf atan2
Sometimes it really is a struggle to convert Cartesian coordinates `(x,y)` to Polar coordinates `(r,phi)`. While you can calculate `r = sqrt(x^2+y^2)` quite easily, you often need some distinction of cases when calculating the angle `phi` because `arcsin`,`arccos` and `arctan` and all other trigonometric functions have a co-domain that each only spans *half* the circle.

In many languages there are built-ins for converting rectangular to polar coordinates, or at least have an `atan2` function, which - given `(x,y)` \- calculate the angle `phi`.

### Task

Your task is to write a program/function that takes two (floating point, not both zero) Cartesian coordinates `(x,y)`, and outputs the corresponding polar angle `phi`, where `phi` has to be in degrees, radians or grades (with *grades* I mean *gradians* which are 1/400 of the full circle), whichever is more convenient for you.

The angle is measured in positive orientation, and we have the zero angle for `(1,0)`.

### Details

You may not use built-ins that calculate the angle `phi` given two coordinates, including `atan2`,`rect2polar`,`argOfComplexNumber` and similar functions. However you can use the usual trigonometric functions and their reverses, that only take one argument. Any unit symbols are optional.

The radius `r` must be non-negative, and `phi` must be in the range `[-360°, 360°]` (it does not matter whether you output `270°` or `-90°`).

### Examples

```
Input       Output
(1,1)       45°
(0,3)       90°
(-1,1)      135°
(-5,0)      180°
(-2,-2)     225°
(0,-1.5)    270°
(4,-5)      308.66°

```

# Answer
> 9 votes
# MATL, 12 bytes

```
yYy/X;0G0<?_

```

The result is in radians.

Try it online! Or verify all test cases.

### Explanation

MATL doesn't have an `atan` function (it has `atan2`, but it can't be used for this challenge). So I resorted to `acos`.

```
y     % Take x, y implicitly. Duplicate x onto the top of the stack
Yy    % Compute hypothenuse from x, y
/     % Divide x by hypothenuse
X;    % Arccosine (inverse of cosine function)
0G    % Push y again
0<    % Is it negative?
?_    % If so, change sign. Implicitly end conditional branch. Implicitly display

```

# Answer
> 5 votes
## JavaScript (ES6), ~~50~~ 40 bytes

```
(x,y)=>(Math.atan(y/x)||0)+Math.PI*(x<0)

```

The result is in radians. Edit: Saved 10 bytes when I noticed that it's allowed for the result to be between -90° and 270°. Previous version with `-Math.PI<=result<Math.PI`:

```
(x,y)=>(Math.atan(y/x)||0)+Math.PI*(x<0)*(y>0||-1)

```

# Answer
> 4 votes
# MATLAB / Octave, 24 bytes

```
@(x,y)atan(y/x)+pi*(x<0)

```

This defines an anonymous function that produces the result in radians.

Try it on ideone.

# Answer
> 3 votes
# Javascript ES6, 54 bytes

```
(x,y,m=Math)=>x<0&!y?m.PI:m.atan(y/(m.hypot(x,y)+x))*2

```

Uses radians.

# Answer
> 2 votes
# Python 3, ~~75~~ 67 bytes

8 bytes thanks to Dennis.

```
from math import*
lambda x,y:pi*(x<0==y)or atan(y/(hypot(x,y)+x))*2

```

Ideone it!

# Answer
> 2 votes
# Jelly, 11 bytes

```
<0×ØP+÷@ÆṬ¥

```

Output is in radians. Jelly had a sign bug in its division atoms which was fixed.

Try it online! or verify all test cases (converted to degrees).

### How it works

```
<0×ØP+÷@ÆṬ¥  Main link. Left argument x. Right argument: y

<0           Compare x with 0.
  ×ØP        Multiply the resulting Boolean by Pi.
          ¥  Combine the two links to the left into a dyadic chain.
      ÷@     Divide y by x.
        ÆṬ   Apply arctan to the result.
     +       Add the results to both sides.

```

# Answer
> 2 votes
# APL (Dyalog Unicode), ~~12~~ 10 bytesSBCS

-2 thanks to ngn.

Anonymous tacit infix function. Uses alephalpha's formula. Takes `x` as right argument and `y` as left argument. Result is in radians.

```
11○∘⍟0J1⊥,

```

Try it online!

`,` concatenate the `y` and `x`

`0J1⊥` Evaluate as base *i* digits (i.e. y*i*¹+x*i*⁰)

natural logarithm of that

then

`11○` imaginary part of that

# Answer
> 1 votes
# x86 machine language (32 bit Linux), ~~25~~ 13 bytes (noncompeting)

```
0:       55                      push   %ebp
1:       89 e5                   mov    %esp,%ebp
3:       dd 45 08                fldl   0x8(%ebp)
6:       dd 45 10                fldl   0x10(%ebp)
9:       d9 f3                   fpatan
b:       c9                      leave
c:       c3                      ret

```

To try it online, compile the following C program (don't forget `-m32` flag on x86\_64)

```
#include<stdio.h>
#include<math.h>
const char j[]="U\x89\xe5\335E\b\335E\20\xd9\xf3\xc9\xc3";
int main(){
  for(double f=-1;f<1;f+=.1){
    for(double g=-1;g<1;g+=.1){
      printf("%.2f %.2f %f %f\n",f,g,atan2(f,g),((double(*)(double,double))j)(f,g));
    }
  }
}

```

# Answer
> 1 votes
# Mathematica, 16 bytes

I am not sure whether `Log` is considered as a built-in that calculates the angle given two coordinates.

```
N@Im@Log[#+I#2]&

```

### Example:

```
In[1]:= N@Im@Log[#+I#2]&[1,1]

Out[1]= 0.785398

In[2]:= N@Im@Log[#+I#2]&[4,-5]

Out[2]= -0.896055

```

# Answer
> 1 votes
# , 10 bytes

Anonymous tacit infix function. Uses alephalpha's formula. Takes `x` as left argument and `y` as right argument. Result is in radians.

```
11 o.^.@j.

```

Try it online!

`j.` calculate `x` \+ `y`×*i*

`@` then

`^.` natural logarithm of that

`11 o.` imaginary part of that

# Answer
> 0 votes
# Pyth, 26 bytes

```
AQ?|>G0Hy.tcH+@s^R2Q2G5.n0

```

`theta` in radians.

Test suite.

# Answer
> 0 votes
# , 13 chars / 17 bytes

```
î<0)*π+МǍ í/î

```

`Try it here (ES6 browsers only).`

Uses `(x<0)*pi+tan(y/x)`.

# Answer
> 0 votes
# Python 3, 65 bytes

```
from math import*
f=lambda x,y:atan(y/x if x else y*inf)+pi*(x<0)

```

This outputs radians in the range `[-π/2, 3π/2)`, equivalent to `[-90, 270)` degrees.

# Answer
> 0 votes
# Axiom, 58 bytes

```
f(a,b)==(a=0 and b=0=>%i;sign(b)*acos(a*1./sqrt(a^2+b^2)))

```

test (i use only acos() it returns radiants )

```
(40) -> [[a,b,f(a,b)*180/%pi] for a in [1,0,-1,-5,-2,0,4] for b in [1,3,1,0,-2,-1.5,-5] ]
   (40)
   [[1.0,1.0,45.0], [0.0,3.0,90.0], [- 1.0,1.0,135.0], [- 5.0,0.0,180.0],
    [- 2.0,- 2.0,- 135.0], [0.0,- 1.5,- 90.0],
    [4.0,- 5.0,- 51.3401917459 09909396]]
                                            Type: List List Complex Float

```

# Answer
> 0 votes
# Python 2, 59 bytes

```
lambda x,y:acos(x/hypot(x,y))/(-1,1)[y>0]
from math import*

```

Try it online!

Outputs in radians in range `[-pi,pi)`

---
Tags: code-golf, math, geometry, trigonometry
---


title: Type "Hello, World!"

text:
# Question
Title: Type "Hello, World!"
Write a program which generates keyboard events which type `Hello, World!`.

It doesn't have to be platform-independent.

It can't leave any keys pressed. For example, in Java, `Robot.KeyPress('H');` will leave `H` pressed, so you must release it with `Robot.KeyRelease('H');`

You may assume that the caps lock is off when your program is run. Capital letters can be typed either by holding shift and pressing the letter, or by toggling caps lock. For the `!`, you'll probably have to use the shift method.

Shortest code wins.

# Answer
# C (Linux), 186 bytes

```
#include<sys/ioctl.h>
#include<fcntl.h>
#include<stdio.h>
main(){char*s="Hello, World!",d[99],*c;fscanf(popen("tty","r"),"%s",d);int D=open(d,O_RDWR);for(c=s;*c;c++)ioctl(D,TIOCSTI,c);}

```

After applying ugoren's suggestions:

## 111 bytes

```
main(D){char*c,d[99];fscanf(popen("tty","r"),"%s",d);D=open(d,2);for(c="Hello, World!";*c;)ioctl(D,21522,c++);}

```
> 10 votes

# Answer
# AppleScript, 50 bytes

```
tell app"System Events"to keystroke"Hello, World!"

```

Thanks to marinus for the suggestion.
> 18 votes

# Answer
# Autohotkey, 20 bytes

```
send Hello, World{!}

```

***Please don't count this one.*** I don't want to cheat out people who have actually done this with a language not meant for sending keystrokes. This answer is just for completion :P
> 13 votes

# Answer
# C in Windows 7, 201 bytes

```
#include<windows.h>
#include<winable.h>
#define S SendInput(1,&k,28);
int k[7]={1};main(i){char*s="^HELLO, ^WORLD^1";for(i=0;i<16;i++){k[2]=0;if(s[i]>90){k[1]=16;S i++;}k[1]=s[i];S k[2]=2;S k[1]=16;S}}

```

Program result:

```
C:\My\Directory>type.exe

C:\My\Directory>Hello, World!

```
> 3 votes

# Answer
# Emacs Lisp, 34 bytes

`(execute-kbd-macro"Hello, World!")`
> 3 votes

# Answer
# Ducky Script for USB Rubber Ducky, 22 bytes

```
String "Hello, World!"

```
> 1 votes

# Answer
# AutoIt3, 21 bytes

```
Send("Hello, World!")

```
> 1 votes

# Answer
# Tcl, 46 bytes

```
package r Expect;spawn bash;send Hello,\ World

```

# Expect, 29 bytes

```
spawn bash;send Hello,\ World

```
> 1 votes

# Answer
# VBScript, 54 bytes

```
createobject("wscript.shell").sendkeys "Hello, World!"

```
> 1 votes

# Answer
# InstantEXE 3.0, 20 bytes

```
Keys "Hello, World!"

```
> 0 votes

# Answer
# PowerShell, 55 bytes

```
(New-Object -c wscript.shell).sendkeys('Hello, World!')

```
> 0 votes

# Answer
## Python 3,67 bytes

```
from pynput.keyboard import*
s=Controller()
s.type("Hello, World!")

```

*No module named pynput on tio*
> 0 votes

---
Tags: code-golf, hello-world
---


title: Sequential Multiplication

text:
# Question
Title: Sequential Multiplication
Your objective is to write a program that takes an input, and, when chained together `N` times, performs "sequential multiplication". What is sequential multiplication, you may ask? It's a sequence with a seed `a` defined as thus:

```
f(0) = a
f(n+1) = f(n)*(f(n)-1)

```

So, let `a = 5`. Thus, `f(0) = 5`, `f(1) = f(0)*(f(0)-1) = 5*4 = 20`, and `f(2) = f(1)*(f(1)-1) = 20*19 = 380`.

If your program was `ABC`, then `ABC` should take input `a` and output `f(1)`. Program `ABCABC` should output `f(2)`, etc. Your program series should only take input once and only output once.

This is a code-golf so the shortest program in bytes wins. Standard loopholes are banned.

# Answer
> 13 votes
# Jelly, 3 bytes

```
×’$

```

Try it online!

### How it works

```
×’$    Main link (or part thereof). Argument (initially input): n

 ’     Compute n - 1.
×      Multiply n by (n - 1).
  $    Combine the previous two atoms into a monadic quicklink.

```

Repeating the snippet **n** times will execute it **n** times, resulting in the desired output.

# Answer
> 4 votes
## Seriously, 4 bytes

```
,;D*

```

Explanation:

```
,;D*
,     push input (NOP once input is exhausted)
 ;D   dupe and push n-1
   *  multiply
      (implicit output at EOF)

```

Just like in Dennis's Jelly answer, repeating this program `n` times will result in it running `n` times. That's one of the many advantages of imperative stack-based languages.

Try it online!

# Answer
> 4 votes
# MATL, 3 bytes

```
tq*

```

You can try it online! Basically similar to the Seriously and Jelly answers. First, it duplicates the top of the stack (get's input first time when the stack is empty). Decrements the top of the stack and multiplies the two elements to give the next input, or result.

# Answer
> 4 votes
## Python 3, 56 bytes

```
+1if 0else 0
try:n
except:n=int(input())
n*=n-1
print(n)

```

Just wanted a solution without output-overwriting trickery. The lack of a trailing newline is important.

# Answer
> 3 votes
# CJam, 5 bytes

```
r~_(*

```

Try it online!

### How it works

```
r     e# Read a whitespace-separated token from STDIN.
      e# This pushes the input (when called for the first time) or an empty string.
 ~    e# Evaluate.
      e# This turns the input into an integer or discards an empty string.
  _   e# Copy the top of the stack.
   (  e# Decrement.
    * e# Multiply.

```

# Answer
> 3 votes
# pl, 5 bytes

```
_▼•=_

```

Try it online.

Would be 4 bytes if I hadn't been lazy and not implemented "assign to \_"...

## Explanation

```
_▼•=_

_       push _ (input var)
 ▼      decrement last used var (_)
  •     multiply, since it is off by one it auto-adds _ to the arg list
   =_   assign result to _

```

# Answer
> 2 votes
# JavaScript REPL, ~~25~~ 20 bytes

```
a=prompt();
a*=a-1//

```

Will work on eliminating a REPL

# Answer
> 2 votes
# 05AB1E, 3 bytes

Code:

```
D<*

```

Explanation:

```
D    # Duplicate top of the stack, or input when empty
 <   # Decrement on top item
  *  # Multiply

```

Try it online!

# Answer
> 2 votes
## Lua, ~~35~~ 18 Bytes

It's something that Lua can do pretty easily for once!

**Edit: I've discovered a lot of things in Lua since I did this, so I'm updating it :)**

```
print(...*(...-1))

```

`...` contains the command-line argument unpacked, inlining it will use it's first value in this case as it won't be allowed to expend, resulting in just printing `n*(n-1)`.

# Answer
> 2 votes
# GolfScript, 5 bytes

```
~.(*`

```

Try it online.

De-golfed and commented:

```
~    # Eval the input to turn it from a string into a number.
.    # Duplicate the number.
(    # Decrement one of the copies by one.
*    # Multiply the copies together.
`    # Un-eval the number, turning it back into a string.

```

The GolfScript interpreter automatically reads the input and places it on the stack, but as a string, not as a number. Thus, we need to turn the input into a number with `~`, and stringify it again afterwards with ```. At the end, the interpreter will automatically print out the stringified number on the stack.

(Now, if the challenge had been to iterate `f(n+1) = f(n)*(-f(n)-1)`, I could've done that in 4 bytes with `~.~*`. Figuring out how and why *that* works is left as an exercise. :)

# Answer
> 1 votes
# , 7 bytes

```
jzC:t*!

```

Try it here!

This is how it works: `j` takes numeric input. `z` activates implicit printing. `C` begins a new link. `:` duplicates the value on the stack, and `t` decrements it, leaving us with `[a a-1]`. Then, we get `[a*a-a]` from `*`. `!` skips the next command; on EOF, it does nothing. When chained together, it skips the input command, and the process begins again.

# Answer
> 1 votes
# Jolf, 6 bytes

Try it here!

```
oj*jwj

```

## Explanation

```
oj*jwj
oj      set j to
  *jwj  j times j-1
        implicit output

```

# Answer
> 1 votes
# , 5 chars / 7 bytes

```
ï×‡ï;

```

`Try it here (Firefox only).`

Must I truly explain this? Oh well, here goes...

# Explanation

It basically evaluates to `input*=--input;` in JS.

# Answer
> 1 votes
# Perl, 23 bytes

```
l;$_|=<>;$_*=~-$_;print

```

### Alternate version, 10 bytes

```
$_*=~-$_;

```

This requires the `-p` switch. I'm not sure if it is fair game in a question.

# Answer
> 1 votes
## Haskell, ~~14~~ 11 bytes

```
(*)=<<pred$

```

Usage example

```
Prelude> (*)=<<pred$5
20
Prelude> (*)=<<pred$(*)=<<pred$5
380
Prelude> (*)=<<pred$(*)=<<pred$(*)=<<pred$5
144020

```

Maybe this isn't a proper function. If you're nitpicking you can go with `(*)=<<pred$id` (\<-there's a space at the end) for 14 bytes.

Edit: @Zgarb rewrote the function using the function monad and saved 3 bytes. Thanks!

# Answer
> 1 votes
# Pure bash (no utilities), 40

```
((a=a?a:$1,a*=a-1))
trap 'echo $a' exit

```

# Answer
> 1 votes
# TI-Basic, 6 5 bytes

*Runs on TI-83/84 calculators*

```
:Ans²-Ans

```

This program works due to the fact that an expression on the last line of a program is printed instead of the regular `Done` text.

# Answer
> 1 votes
# Mathcad, 39 "bytes"

From user perspective, Mathcad is effectively a 2D whiteboard, with expressions evaluated from left-to-right,top-to-bottom. Mathcad does not support a conventional "text" input, but instead makes use of a combination of text and special keys / toolbar / menu items to insert an expression, text, plot or component. For example, type ":" to enter the definition operator (shown on screen as ":="), "\[" to enter an array index, or "ctl-\]" to enter a while loop operator (inclusive of placeholders for the controlling condition and one body expression). What you see in the image above is exactly what appears on the user interface and as "typed" in.

For golfing purposes, the "byte" count is the equivalent number of keyboard operations required to enter an expression.

One thing I'm even less sure about (from an "byte" equivalence point of view) is how to count creating a new region (eg, a:=5 or k:=0..n-1). I've equated each move to a new region as being equal to a newline, and hence 1 byte (in practice, I use the mouse to click where I want the region).

I've only included the active statements and not the comments, and I've included 2 bytes each for the a and n inputs but not the values themselves (5 and 7 in the example).

# Answer
> 0 votes
# Haskell, 72 bytes

This challenge is not friendly to Haskell.. However, the following works if input is in unary and the code is executed in GHCI:

```
(\x->if odd x then let y=until((>x).(10^))(+1)0 in y*(y-1)else x*(x-1))$

```

# Explanation:

Unary is always odd, so the first application will convert to decimal. `x*(x-1)` is always even, so otherwise it returns `x*(x-1)`, where `x` is the input. Because Haskell is strongly typed and 'special' symbols cannot be called like `&1`, I believe that this is pretty much the only way to complete this in Haskell, unless one used global variables or an even odder input form.

# Answer
> 0 votes
# C++ (gcc), 173 / 176 bytes

Both versions have a crucial newline at the end.

## Macro version, 173 bytes

```
#ifndef M
#define M(a,b)a##b
#define W(z,x)M(z,x)
#define B int W(m,__LINE__)=x++
#include<iostream>
int x,n;int main(){for(std::cin>>n;x--;)n*=n-1;std::cout<<n;}
#endif
B;

```

Try it online!

## Template version, 176 bytes

Somewhat more C++ish:

```
#ifndef B
#define B template
#include<iostream>
int x,n;B<int N>struct A{static int i;};int main(){for(std::cin>>n;x--;)n*=n-1;std::cout<<n;}
#endif
B<>int A<__LINE__>::i=x++;

```

Try it online!

# Answer
> 0 votes
## Burlesque - 5 bytes

```
J?d?*

blsq ) 5 J?d?*
20
blsq ) 5 J?d?* J?d?*
380
blsq ) 5 J?d?* J?d?* J?d?*
144020

```

---
Tags: code-golf, source-layout
---


title: Conjugation in Real Life

text:
# Question
Title: Conjugation in Real Life
In @Adám's Dyalog APL Extended, the  (under) operator means conjugation: apply one function, then a second function, then the inverse of the first. It's fun to think of real-life actions in terms of conjugation:

> A problem is transformed by g into another domain where it more readily solved by f , and then transformed back into the original domain. An example from real life is “under anesthetics”:
>
> ```
> apply anesthetics
>     perform surgery
> wake up from anesthetics
> ```

## Challenge

The inverse of a line `g` is "un" prepended to `g`, and vice versa. Define any line between `s` and its inverse, in that order, as being "under" `s`. For each line `f` in input in order:

* If `f` and its inverse both occur, do nothing
* If `f` is not "under" any other action, print `f`
* If `f` is "under" a line `g`, print `f + " under " + g` where `+` is concatenation.

### Input

A nonempty multiline string, or list of strings, etc., consisting of spaces and lowercase letters (you may instead use uppercase). Exactly one line will begin with "un"; and it will be the inverse of some other line. No line will be empty.

### Output

Output in the same format you took input in, or as allowed by Standard I/O.

### Test cases:

```
Input:
apply anesthetics
perform surgery
unapply anesthetics

Output:
perform surgery under apply anesthetics

Input:
unite asia
establish the silk road
ite asia

Output:
establish the silk road under unite asia

Input:
desire a book
walk to store
take the book
pay for the book
unwalk to store
read the book

Output:
desire a book
take the book under walk to store
pay for the book under walk to store
read the book

Input:
drink excessively
undrink excessively

Output:
[empty string]

```

# Answer
# Brachylog, 90 bytes

```
;Ṡ{hhH↰₂gB&hb~c[A,B,C]&tT;C↔↰U∧" under ",H,T;A↔↰,U|tT&hh,TgJ&hb;T↰Q∧J,Q|h}
~↰₃|↰₃
∧"un";?c

```

I made this while being under the impression that this could be recursive and multiple unders could be stacked. Probably not optimized. Also as this is bracylog, plumbing takes quite some bytes.

Try it online!
> 3 votes

# Answer
# Python 2, 106 bytes

```
s=input()
x=''
l=[]
for i in s:
 if'un'==i[:2]or'un'+i in s:x=(' under '+i)*(not x)
 else:l+=[i+x]
print l

```

Try it online!

If the input can be a list from STDIN and the output be newline-separated, we then have this 94-byte solution:

```
s=input()
x=''
for i in s:
 if'un'==i[:2]or'un'+i in s:x=(' under '+i)*(not x)
 else:print i+x

```
> 2 votes

# Answer
# Retina, 82 bytes

```
m{A`^(un)?(.+)¶(?(1)|un)\2$
^((un)?(.+)¶)(.+)¶((.+¶)*(?(2)|un)\3)$
$4 under $1$1$5

```

Try it online! Link includes test cases. Explanation:

```
m{

```

Run the whole program in multiline mode (so that `^` and `$` match the beginning and end of individual lines) and repeat until there are no changes.

```
A`^(un)?(.+)¶(?(1)|un)\2$

```

Look for lines that might begin with `un` and are followed by a line that begins with `un` only if the previous line does not while the rest of the line is the same, and delete both lines. (This is a change of behaviour from Retina 0.8.2, which splits the lines before trying to match and therefore can never delete lines if the match needs to span more than one line at once.)

```
^((un)?(.+)¶)(.+)¶((.+¶)*(?(2)|un)\3)$

```

Look for lines that might begin with `un`, followed by at least one line, followed by a line that begins with `un` only if the original line does not while the rest of the line is the same.

```
$4 under $1$1$5

```

Move the original line down one line, and also append it with `under` to the line just traversed. (Additional lines will be handled by the repeat.)
> 2 votes

# Answer
# JavaScript (Babel Node), 91 bytes

Takes input as an array of strings in lowercase. Returns another array of strings.

```
a=>a.flatMap(s=>s==r|'un'+s==r?(u=u?'':' under '+s,[]):s+u,u='',r=a.find(s=>/^un/.test(s)))

```

Try it online!

### Commented

```
a =>                     // a[] = input array
  a.flatMap(s =>         // for each string s in a[]:
    s == r |             //   if s matches the reference string
    'un' + s == r ? (    //   or its opposite:
      u =                //     update u:
        u ?              //       if u is not an empty string:
          ''             //         turn it to an empty string
        :                //       else:
          ' under ' + s, //         set it to s with the ' under ' prefix
      []                 //     yield an empty array so that this entry is removed
    ) :                  //   else:
      s + u,             //     yield s followed by u
    u = '',              //   initialize u to an empty string
    r = a.find(s =>      //   initialize r ...
      /^un/.test(s)      //     ... to the string beginning with 'un'
    )                    //
  )                      // end of flatMap()

```
> 1 votes

# Answer
# Clean, 147 bytes

```
import StdEnv,Data.List
a=inits;b=tails
$l=hd[w++[e++[' under ':u]\\e<-z]++y\\i<-a l&t<-b l,w<-a i&u<-i,z<-a t&[x:y]<-b t|u==['un':x]||x==['un':u]]

```

Try it online!
> 1 votes

---
Tags: code-golf, string, parsing, apl
---


title: Iterated Prisoner's Trilemma

text:
# Question
Title: Iterated Prisoner's Trilemma
CHALLENGE STATUS: **OPEN**

Comment, open a PR, or otherwise yell at me if I'm missing your bot.

---

Prisoner's dilemma ... with three choices. Crazy, huh?

Here's our payoff matrix. Player A on the left, B on the top

```
A,B| C | N | D
---|---|---|---
 C |3,3|4,1|0,5
 N |1,4|2,2|3,2
 D |5,0|2,3|1,1

```

The payoff matrix is engineered so that it's best for both players to always cooperate, but you can gain (usually) by choosing Neutral or Defection.

Here's some (competing) example bots.

```
# turns out if you don't actually have to implement __init__(). TIL!

class AllC:
    def round(self, _): return "C"
class AllN:
    def round(self, _): return "N"
class AllD:
    def round(self, _): return "D"
class RandomBot:
    def round(self, _): return random.choice(["C", "N", "D"])

# Actually using an identically-behaving "FastGrudger".
class Grudger:
    def __init__(self):
        self.history = []
    def round(self, last):
        if(last):
            self.history.append(last)
            if(self.history.count("D") > 0):
                return "D"
        return "C"

class TitForTat:
    def round(self, last):
        if(last == "D"):
            return "D"
        return "C"

```

Your bot is a Python3 class. A new instance is created for every game, and `round()` is called each round, with your opponent's choice from last round (or None, if it's the first round)

There's a 50 rep bounty for the winner in like a month.

## Specifics

* Every bot plays every other bot (1v1), including itself, in \[REDACTED\] rounds.
* Standard loopholes disallowed.
* No messing with anything outside your class or other underhanded shenanigains.
* You may submit up to five bots.
* Yes, you can implement handshake.
* Any response other than `C`, `N`, or `D` will be silently taken as `N`.
* Each bot's points from every game they play will be totaled up and compared.

## Controller

Check!

## Other Languages

I'll throw together an API if anyone needs it.

## Scores: 2018-11-27

```
27 bots, 729 games.

name            | avg. score/round
----------------|-------------------
PatternFinder   | 3.152
DirichletDice2  | 3.019
EvaluaterBot    | 2.971
Ensemble        | 2.800
DirichletDice   | 2.763
Shifting        | 2.737
FastGrudger     | 2.632
Nash2           | 2.574
HistoricAverage | 2.552
LastOptimalBot  | 2.532
Number6         | 2.531
HandshakeBot    | 2.458
OldTitForTat    | 2.411
WeightedAverage | 2.403
TitForTat       | 2.328
AllD            | 2.272
Tetragram       | 2.256
Nash            | 2.193
Jade            | 2.186
Useless         | 2.140
RandomBot       | 2.018
CopyCat         | 1.902
TatForTit       | 1.891
NeverCOOP       | 1.710
AllC            | 1.565
AllN            | 1.446
Kevin           | 1.322

```

# Answer
# EvaluaterBot

```
class EvaluaterBot:
    def __init__(self):
        self.c2i = {"C":0, "N":1, "D":2}
        self.i2c = {0:"C", 1:"N", 2:"D"}
        self.history = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
        self.last = [None, None]

    def round(self, last):
        if self.last[0] == None:
            ret = 2
        else:
            # Input the latest enemy action (the reaction to my action 2 rounds ago)
            # into the history
            self.history[self.last[0]][self.c2i[last]] += 1
            # The enemy will react to the last action I did
            prediction,_ = max(enumerate(self.history[self.last[1]]), key=lambda l:l[1])
            ret = (prediction - 1) % 3
        self.last = [self.last[1], ret]
        return self.i2c[ret]

```

Wins against all previously submitted bots except (maybe) the random bot (but it could have an advantage, because it picks D in a draw and D should optimal) and plays a constant draw against themself.
> 10 votes

# Answer
# TatForTit

```
class TatForTit:
    def round(self, last):
        if(last == "C"):
            return "N"
        return "D"

```

This bot will alternate picking D N D N while TitForTat alternates C D C D, for an average net gain of 3 points per round if I have read the payout matrix correctly. I think this might be optimal against TitForTat. Obviously it could be improved to detect a non-TFT opponent and adopt other strategies, but I was just aiming for the original bounty.
> 8 votes

# Answer
# NashEquilibrium

This bot has taken a game theory class in college but was lazy and didn't go to the class where they covered iterated games. So he only plays single game mixed nash equilibrium. Turns out 1/5 2/5 2/5 is the mixed NE for the payoffs.

```
class NashEquilibrium:
    def round(self, _):
        a = random.random()
        if a <= 0.2:
            return "C"
        elif a <= 0.6:
            return "N"
        else:
            return "D"

```

**Constant Abusing Nash Equilibrium**

This bot picked up a lesson or two from his lazy brother. His lazy brother's problem was that he didn't take advantage of fixed strategies. This version checks if the opponent is a constant player or titfortat and plays accordingly, else it plays the regular nash equilibrium.

It's only downside is that it averages 2.2 points per turn playing against itself.

```
class NashEquilibrium2:

    def __init__(self):
        self.opphistory = [None, None, None]
        self.titfortatcounter = 0
        self.titfortatflag = 0
        self.mylast = "C"
        self.constantflag = 0
        self.myret = "C"

    def round(self, last):
        self.opphistory.pop(0)
        self.opphistory.append(last)

        # check if its a constant bot, if so exploit
        if self.opphistory.count(self.opphistory[0]) == 3:
            self.constantflag = 1
            if last == "C":
                 self.myret = "D"
            elif last == "N":
                 self.myret = "C"
            elif last == "D":
                 self.myret = "N"

        # check if its a titfortat bot, if so exploit
        # give it 2 chances to see if its titfortat as it might happen randomly
        if self.mylast == "D" and last == "D":
            self.titfortatcounter = self.titfortatcounter + 1

        if self.mylast == "D" and last!= "D":
            self.titfortatcounter = 0

        if self.titfortatcounter >= 3:
            self.titfortatflag = 1

        if self.titfortatflag == 1:
            if last == "C":
                 self.myret = "D"
            elif last == "D":
                 self.myret = "N"
            elif last == "N":
                # tit for tat doesn't return N, we made a mistake somewhere
                 self.titfortatflag = 0
                 self.titfortatcounter = 0

        # else play the single game nash equilibrium
        if self.constantflag == 0 and self.titfortatflag == 0:
            a = random.random()
            if a <= 0.2:
                self.myret = "C"
            elif a <= 0.6:
                self.myret = "N"
            else:
                self.myret = "D"

        self.mylast = self.myret
        return self.myret

```
> 7 votes

# Answer
# PatternFinder

```
class PatternFinder:
    def __init__(self):
        import collections
        self.size = 10
        self.moves = [None]
        self.other = []
        self.patterns = collections.defaultdict(list)
        self.counter_moves = {"C":"D", "N":"C", "D":"N"}
        self.initial_move = "D"
        self.pattern_length_exponent = 1
        self.pattern_age_exponent = 1
        self.debug = False
    def round(self, last):
        self.other.append(last)
        best_pattern_match = None
        best_pattern_score = None
        best_pattern_response = None
        self.debug and print("match so far:",tuple(zip(self.moves,self.other)))
        for turn in range(max(0,len(self.moves)-self.size),len(self.moves)):
            # record patterns ending with the move that just happened
            pattern_full = tuple(zip(self.moves[turn:],self.other[turn:]))
            if len(pattern_full) > 1:
                pattern_trunc = pattern_full[:-1]
                pattern_trunc_result = pattern_full[-1][1]
                self.patterns[pattern_trunc].append([pattern_trunc_result,len(self.moves)-1])
            if pattern_full in self.patterns:
                # we've seen this pattern at least once before
                self.debug and print("I've seen",pattern_full,"before:",self.patterns[pattern_full])
                for [response,turn_num] in self.patterns[pattern_full]:
                    score = len(pattern_full) ** self.pattern_length_exponent / (len(self.moves) - turn_num) ** self.pattern_age_exponent
                    if best_pattern_score == None or score > best_pattern_score:
                        best_pattern_match = pattern_full
                        best_pattern_score = score
                        best_pattern_response = response
                    # this could be much smarter about aggregating previous responses
        if best_pattern_response:
            move = self.counter_moves[best_pattern_response]
        else:
            # fall back to playing nice
            move = "C"
        self.moves.append(move)
        self.debug and print("I choose",move)
        return move

```

This bot looks for previous occurrences of the recent game state to see how the opponent responded to those occurrences, with a preference for longer pattern matches and more recent matches, then plays the move that will "beat" the opponent's predicted move. There's a lot of room for it to be smarter with all the data it keeps track of, but I ran out of time to work on it.
> 6 votes

# Answer
# Jade

```
class Jade:
    def __init__(self):
        self.dRate = 0.001
        self.nRate = 0.003

    def round(self, last):
        if last == 'D':
            self.dRate *= 1.1
            self.nRate *= 1.2
        elif last == 'N':
            self.dRate *= 1.03
            self.nRate *= 1.05
        self.dRate = min(self.dRate, 1)
        self.nRate = min(self.nRate, 1)

        x = random.random()
        if x > (1 - self.dRate):
            return 'D'
        elif x > (1 - self.nRate):
            return 'N'
        else:
            return 'C'

```

Starts out optimistic, but gets progressively more bitter as the opponent refuses to cooperate. Lots of magic constants that could probably be tweaked, but this probably isn't going to do well enough to justify the time.
> 5 votes

# Answer
# Ensemble

This runs an ensemble of related models. The individual models consider different amounts of history, and have the option of either always choosing the move that will optimize the expected payout difference, or will randomly select a move in proportion to expected payout difference.

Each member of the ensemble then votes on their preferred move. They get a number of votes equal to how much more they've won than the opponent (which means that terrible models will get negative votes). Whichever move wins the vote is then selected.

(They should probably split their votes among the moves in proportion to how much they favor each, but I don't care enough to do that right now.)

It beats everything posted so far except EvaluaterBot and PatternFinder. (One-on-one, it beats EvaluaterBot and loses to PatternFinder).

```
from collections import defaultdict
import random
class Number6:
    class Choices:
        def __init__(self, C = 0, N = 0, D = 0):
            self.C = C
            self.N = N
            self.D = D

    def __init__(self, strategy = "maxExpected", markov_order = 3):
        self.MARKOV_ORDER = markov_order;
        self.my_choices = ""
        self.opponent = defaultdict(lambda: self.Choices())
        self.choice = None # previous choice
        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }
        self.total_payoff = 0

        # if random, will choose in proportion to payoff.
        # otherwise, will always choose argmax
        self.strategy = strategy
        # maxExpected: maximize expected relative payoff
        # random: like maxExpected, but it chooses in proportion to E[payoff]
        # argmax: always choose the option that is optimal for expected opponent choice

    def update_opponent_model(self, last):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            self.opponent[hist].C += ("C" == last)
            self.opponent[hist].N += ("N" == last)
            self.opponent[hist].D += ("D" == last)

    def normalize(self, counts):
        sum = float(counts.C + counts.N + counts.D)
        if 0 == sum:
            return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)
        return self.Choices(
            counts.C / sum, counts.N / sum, counts.D / sum)

    def get_distribution(self):
        for i in range(0, self.MARKOV_ORDER):
            hist = self.my_choices[i:]
            #print "check hist = " + hist
            if hist in self.opponent:
                return self.normalize(self.opponent[hist])

        return self.Choices(1.0 / 3.0, 1.0 / 3.0, 1.0 / 3.0)

    def choose(self, dist):
        payoff = self.Choices()
        # We're interested in *beating the opponent*, not
        # maximizing our score, so we optimize the difference
        payoff.C = (3-3) * dist.C + (4-1) * dist.N + (0-5) * dist.D
        payoff.N = (1-4) * dist.C + (2-2) * dist.N + (3-2) * dist.D
        payoff.D = (5-0) * dist.C + (2-3) * dist.N + (1-1) * dist.D

        # D has slightly better payoff on uniform opponent,
        # so we select it on ties
        if self.strategy == "maxExpected":
            if payoff.C > payoff.N:
                return "C" if payoff.C > payoff.D else "D"
            return "N" if payoff.N > payoff.D else "D"
        elif self.strategy == "randomize":
            payoff = self.normalize(payoff)
            r = random.uniform(0.0, 1.0)
            if (r < payoff.C): return "C"
            return "N" if (r < payoff.N) else "D"
        elif self.strategy == "argMax":
            if dist.C > dist.N:
                return "D" if dist.C > dist.D else "N"
            return "C" if dist.N > dist.D else "N"

        assert(0) #, "I am not a number! I am a free man!")

    def update_history(self):
        self.my_choices += self.choice
        if len(self.my_choices) > self.MARKOV_ORDER:
            assert(len(self.my_choices) == self.MARKOV_ORDER + 1)
            self.my_choices = self.my_choices[1:]

    def round(self, last):
        if last: self.update_opponent_model(last)

        dist = self.get_distribution()
        self.choice = self.choose(dist)
        self.update_history()
        return self.choice

class Ensemble:
    def __init__(self):
        self.models = []
        self.votes = []
        self.prev_choice = []
        for order in range(0, 6):
            self.models.append(Number6("maxExpected", order))
            self.models.append(Number6("randomize", order))
            #self.models.append(Number6("argMax", order))
        for i in range(0, len(self.models)):
            self.votes.append(0)
            self.prev_choice.append("D")

        self.payoff = {
            "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
            "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
            "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
        }

    def round(self, last):
        if last:
            for i in range(0, len(self.models)):
                self.votes[i] += self.payoff[self.prev_choice[i]][last]

        # vote. Sufficiently terrible models get negative votes
        C = 0
        N = 0
        D = 0
        for i in range(0, len(self.models)):
            choice = self.models[i].round(last)
            if "C" == choice: C += self.votes[i]
            if "N" == choice: N += self.votes[i]
            if "D" == choice: D += self.votes[i]
            self.prev_choice[i] = choice

        if C > D and C > N: return "C"
        elif N > D: return "N"
        else: return "D"

```

# Test Framework

In case anyone else finds it useful, here's a test framework for looking at individual matchups. Python2. Just put all the opponents you're interested in in opponents.py, and change the references to Ensemble to your own.

```
import sys, inspect
import opponents
from ensemble import Ensemble

def count_payoff(label, them):
    if None == them: return
    me = choices[label]
    payoff = {
        "C": { "C": 3-3, "N": 4-1, "D": 0-5 },
        "N": { "C": 1-4, "N": 2-2, "D": 3-2 },
        "D": { "C": 5-0, "N": 2-3, "D": 1-1 },
    }
    if label not in total_payoff: total_payoff[label] = 0
    total_payoff[label] += payoff[me][them]

def update_hist(label, choice):
    choices[label] = choice

opponents = [ x[1] for x
    in inspect.getmembers(sys.modules['opponents'], inspect.isclass)]

for k in opponents:
    total_payoff = {}

    for j in range(0, 100):
        A = Ensemble()
        B = k()
        choices = {}

        aChoice = None
        bChoice = None
        for i in range(0, 100):
            count_payoff(A.__class__.__name__, bChoice)
            a = A.round(bChoice)
            update_hist(A.__class__.__name__, a)

            count_payoff(B.__class__.__name__, aChoice)
            b = B.round(aChoice)
            update_hist(B.__class__.__name__, b)

            aChoice = a
            bChoice = b
    print total_payoff

```
> 5 votes

# Answer
## OldTitForTat

Old school player is too lazy to update for the new rules.

```
class OldTitForTat:
    def round(self, last):
        if(last == None)
            return "C"
        if(last == "C"):
            return "C"
        return "D"

```
> 4 votes

# Answer
# LastOptimalBot

```
class LastOptimalBot:
    def round(self, last):
        return "N" if last == "D" else ("D" if last == "C" else "C")

```

Assumes that the opposing bot will always play the same move again, and chooses the one that has the best payoff against it.

Averages:

```
Me   Opp
2.6  2    vs TitForTat
5    0    vs AllC
4    1    vs AllN
3    2    vs AllD
3.5  3.5  vs Random
3    2    vs Grudger
2    2    vs LastOptimalBot
1    3.5  vs TatForTit
4    1    vs NeverCOOP
1    4    vs EvaluaterBot
2.28 2.24 vs NashEquilibrium

2.91 average overall

```
> 3 votes

# Answer
# NeverCOOP

```
class NeverCOOP:
    def round(self, last):
        try:
            if last in "ND":
                return "D"
            else:
                return "N"
        except:
            return "N"

```

If the opposing bot defects or is neutral, choose defect. Otherwise if this is the first turn or the opposing bot cooperates, choose neutral. I'm not sure how good this will work...
> 3 votes

# Answer
# CopyCat

```
class CopyCat:
    def round(self, last):
        if last:
            return last
        return "C"

```

Copies the opponent's last move.
I don't expect this to do well, but no one had implemented this classic yet.
> 3 votes

# Answer
# Historic Average

```
class HistoricAverage:
    PAYOFFS = {
        "C":{"C":3,"N":1,"D":5},
        "N":{"C":4,"N":2,"D":2},
        "D":{"C":0,"N":3,"D":1}}
    def __init__(self):
        self.payoffsum = {"C":0, "N":0, "D":0}
    def round(this, last):
        if(last != None):
            for x in this.payoffsum:
               this.payoffsum[x] += HistoricAverage.PAYOFFS[last][x]
        return max(this.payoffsum, key=this.payoffsum.get)

```

Looks at history and finds the action that would have been best on average. Starts cooperative.
> 2 votes

# Answer
# Improved Dirichlet Dice

```
import random

class DirichletDice2:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 1, 'N' : 1, 'D' : 1},
                N = {'C' : 1, 'N' : 1, 'D' : 1},
                D = {'C' : 1, 'N' : 1, 'D' : 1}
        )
        self.myLast = [None, None]
        self.payoff = dict(
                C = { "C": 0, "N": 3, "D": -5 },
                N = { "C": -3, "N": 0, "D": 1 },
                D = { "C": 5, "N": -1, "D": 0 }
        )

    def DirichletDraw(self, key):
        alpha = self.alpha[key].values()
        mu = [random.gammavariate(a,1) for a in alpha]
        mu = [m / sum(mu) for m in mu]
        return mu

    def ExpectedPayoff(self, probs):
        expectedPayoff = {}
        for val in ['C','N','D']:
            payoff = sum([p * v for p,v in zip(probs, self.payoff[val].values())])
            expectedPayoff[val] = payoff
        return expectedPayoff

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #draw probs for my opponent's roll from Dirichlet distribution and then return the optimal response
        mu = self.DirichletDraw(self.myLast[0])
        expectedPayoff = self.ExpectedPayoff(mu)
        res = max(expectedPayoff, key=expectedPayoff.get)

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res

```

This is an improved version of Dirichlet Dice. Instead of taking the expected multinomial distribution from the Dirichlet distribution, it draws a Multinomial distribution randomly from the Dirichlet distribution. Then, instead of drawing from the Multinomial and giving the optimal response to that, it gives the optimal expected response to the given Multinomial using the points. So the randomness has essentially been shifted from the Multinomial draw to the Dirichlet draw. Also, the priors are more flat now, to encourage exploration.

It's "improved" because it now accounts for the points system by giving the best expected value against the probabilities, while maintaining its randomness by drawing the probabilities themselves. Before, I tried simply doing the best expected payoff from the expected probabilities, but that did badly because it just got stuck, and didn't explore enough to update its dice. Also it was more predictable and exploitable.

---

Original submission:

# Dirichlet Dice

```
import random

class DirichletDice:
    def __init__(self):

        self.alpha = dict(
                C = {'C' : 2, 'N' : 3, 'D' : 1},
                N = {'C' : 1, 'N' : 2, 'D' : 3},
                D = {'C' : 3, 'N' : 1, 'D' : 2}
        )

        self.Response = {'C' : 'D', 'N' : 'C', 'D' : 'N'}
        self.myLast = [None, None]

    #expected value of the dirichlet distribution given by Alpha
    def MultinomialDraw(self, key):
        alpha = list(self.alpha[key].values())
        probs = [x / sum(alpha) for x in alpha]
        outcome = random.choices(['C','N','D'], weights=probs)[0]
        return outcome

    def round(self, last):
        if last is None:
            self.myLast[0] = 'D'
            return 'D'

        #update dice corresponding to opponent's last response to my
        #outcome two turns ago
        if self.myLast[1] is not None:
            self.alpha[self.myLast[1]][last] += 1

        #predict opponent's move based on my last move
        predict = self.MultinomialDraw(self.myLast[0])
        res = self.Response[predict]

        #update myLast
        self.myLast[1] = self.myLast[0]
        self.myLast[0] = res

        return res

```

Basically I'm assuming that the opponent's response to my last output is a multinomial variable (weighted dice), one for each of my outputs, so there's a dice for "C", one for "N", and one for "D". So if my last roll was, for example, a "N" then I roll the "N-dice" to guess what their response would be to my "N". I begin with a Dirichlet prior that assumes that my opponent is somewhat "smart" (more likely to play the one with the best payoff against my last roll, least likely to play the one with the worst payoff). I generate the "expected" Multinomial distribution from the appropriate Dirichlet prior (this is the expected value of the probability distribution over their dice weights). I roll the weighted dice of my last output, and respond with the one with the best payoff against that dice outcome.

Starting in the third round, I do a Bayesian update of the appropriate Dirichlet prior of my opponent's last response to the thing I played two rounds ago. I'm trying to iteratively learn their dice weightings.

I could have also simply picked the response with the best "expected" outcome once generating the dice, instead of simply rolling the dice and responding to the outcome. However, I wanted to keep the randomness in, so that my bot is less vulnerable to the ones that try to predict a pattern.
> 2 votes

# Answer
# Handshake

```
class HandshakeBot:
  def __init__(self):
    self.handshake_length = 4
    self.handshake = ["N","N","C","D"]
    while len(self.handshake) < self.handshake_length:
      self.handshake *= 2
    self.handshake = self.handshake[:self.handshake_length]
    self.opp_hand = []
    self.friendly = None
  def round(self, last):
    if last:
      if self.friendly == None:
        # still trying to handshake
        self.opp_hand.append(last)
        if self.opp_hand[-1] != self.handshake[len(self.opp_hand)-1]:
          self.friendly = False
          return "D"
        if len(self.opp_hand) == len(self.handshake):
          self.friendly = True
          return "C"
        return self.handshake[len(self.opp_hand)]
      elif self.friendly == True:
        # successful handshake and continued cooperation
        if last == "C":
          return "C"
        self.friendly = False
        return "D"
      else:
        # failed handshake or abandoned cooperation
        return "N" if last == "D" else ("D" if last == "C" else "C")
    return self.handshake[0]

```

Recognizes when it's playing against itself, then cooperates. Otherwise mimics LastOptimalBot which seems like the best one-line strategy. Performs worse than LastOptimalBot, by an amount inversely proportional to the number of rounds. Obviously would do better if there were more copies of it in the field \*cough\**wink\*.
> 2 votes

# Answer
# Kevin

```
class Kevin:
    def round(self, last):
        return {"C":"N","N":"D","D":"C",None:"N"} [last]

```

Picks the worst choice. The worst bot made.

# Useless

```
import random

class Useless:
    def __init__(self):
        self.lastLast = None

    def round(self, last):
        tempLastLast = self.lastLast
        self.lastLast = last

        if(last == "D" and tempLastLast == "N"):
            return "C"
        if(last == "D" and tempLastLast == "C"):
            return "N"

        if(last == "N" and tempLastLast == "D"):
            return "C"
        if(last == "N" and tempLastLast == "C"):
            return "D"

        if(last == "C" and tempLastLast == "D"):
            return "N"
        if(last == "C" and tempLastLast == "N"):
            return "D"

        return random.choice("CND")

```

It looks at the last two moves done by the opponent and picks the most not done else it picks something random. There is probably a better way of doing this.
> 2 votes

# Answer
# Weighted Average

```
class WeightedAverageBot:
  def __init__(self):
    self.C_bias = 1/4
    self.N = self.C_bias
    self.D = self.C_bias
    self.prev_weight = 1/2
  def round(self, last):
    if last:
      if last == "C" or last == "N":
        self.D *= self.prev_weight
      if last == "C" or last == "D":
        self.N *= self.prev_weight
      if last == "N":
        self.N = 1 - ((1 - self.N) * self.prev_weight)
      if last == "D":
        self.D = 1 - ((1 - self.D) * self.prev_weight)
    if self.N <= self.C_bias and self.D <= self.C_bias:
      return "D"
    if self.N > self.D:
      return "C"
    return "N"

```

The opponent's behavior is modeled as a right triangle with corners for C N D at 0,0 0,1 1,0 respectively. Each opponent move shifts the point within that triangle toward that corner, and we play to beat the move indicated by the point (with C being given an adjustably small slice of the triangle). In theory I wanted this to have a longer memory with more weight to previous moves, but in practice the current meta favors bots that change quickly, so this devolves into an approximation of LastOptimalBot against most enemies. Posting for posterity; maybe someone will be inspired.
> 1 votes

# Answer
# Tetragram

```
import itertools

class Tetragram:
    def __init__(self):
        self.history = {x: ['C'] for x in itertools.product('CND', repeat=4)}
        self.theirs = []
        self.previous = None

    def round(self, last):
        if self.previous is not None and len(self.previous) == 4:
            self.history[self.previous].append(last)
        if last is not None:
            self.theirs = (self.theirs + [last])[-3:]

        if self.previous is not None and len(self.previous) == 4:
            expected = random.choice(self.history[self.previous])
            if expected == 'C':
                choice = 'C'
            elif expected == 'N':
                choice = 'C'
            else:
                choice = 'N'
        else:
            choice = 'C'

        self.previous = tuple(self.theirs + [choice])
        return choice

```

Try to find a pattern in the opponent's moves, assuming they're also watching our last move.
> 1 votes

# Answer
# ShiftingOptimalBot

```
class ShiftingOptimalBot:
    def __init__(self):
        # wins, draws, losses
        self.history = [0,0,0]
        self.lastMove = None
        self.state = 0
    def round(self, last):
        if last == None:
            self.lastMove = "C"
            return self.lastMove
        if last == self.lastMove:
            self.history[1] += 1
        elif (last == "C" and self.lastMove == "D") or (last == "D" and self.lastMove == "N") or (last == "N" and self.lastMove == "C"):
            self.history[0] += 1
        else:
            self.history[2] += 1

        if self.history[0] + 1 < self.history[2] or self.history[2] > 5:
            self.state = (self.state + 1) % 3
            self.history = [0,0,0]
        if self.history[1] > self.history[0] + self.history[2] + 2:
            self.state = (self.state + 2) % 3
            self.history = [0,0,0]

        if self.state == 0:
            self.lastMove = "N" if last == "D" else ("D" if last == "C" else "C")
        elif self.state == 1:
            self.lastMove = last
        else:
            self.lastMove = "C" if last == "D" else ("N" if last == "C" else "D")
        return self.lastMove

```

This bot uses LastOptimalBot's algorithm as long as it's winning. If the other bot starts predicting it, however, it will start playing whichever move its opponent played last (which is the move that beats the move that would beat LastOptimalBot). It cycles through simple transpositions of those algorithms as long as it continues to lose (or when it gets bored by drawing a lot).

Honestly, I'm surprised that LastOptimalBot is sitting in 5th as I post this. I'm fairly certain this will do better, assuming that I wrote this python correctly.
> 1 votes

# Answer
# HandshakePatternMatch

```
from .patternfinder import PatternFinder
import collections

class HandshakePatternMatch:
    def __init__(self):
        self.moves = [None]
        self.other = []
        self.handshake = [None,"N","C","C","D","N"]
        self.friendly = None
        self.pattern = PatternFinder()
    def round(self, last):
        self.other.append(last)
        if last:
            if len(self.other) < len(self.handshake):
                # still trying to handshake
                if self.friendly == False or self.other[-1] != self.handshake[-1]:
                    self.friendly = False
                else:
                    self.friendly = True
                move = self.handshake[len(self.other)]
                self.pattern.round(last)
            elif self.friendly == True:
                # successful handshake and continued cooperation
                move = self.pattern.round(last)
                if last == "C":
                    move = "C"
                elif last == self.handshake[-1] and self.moves[-1] == self.handshake[-1]:
                    move = "C"
                else:
                    self.friendly = False
            else:
                # failed handshake or abandoned cooperation
                move = self.pattern.round(last)
        else:
            move = self.handshake[1]
            self.pattern.round(last)
        self.moves.append(move)
        return move

```

Why pattern match yourself? Handshake and cooperate away.
> 0 votes

# Answer
# Hardcoded

```
class Hardcoded:
    sequence = "DNCNNDDCNDDDCCDNNNNDDCNNDDCDCNNNDNDDCNNDDNDDCDNCCNNDNNDDCNNDDCDCNNNDNCDNDNDDNCNDDCDNNDCNNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNNDDNDCDNCNDDCDNNDDCCNDNNDDCNNNDCDNDDCNNNNDNDDCDNCDCNNDNNDDCDNDDCCNNNDNDDCNNNDNDCDCDNNDCNNDNDDCDNCNNDDCNDNNDDCDNNDCDNDNCDDCNNNDNDNCNDDCDNDDCCNNNNDNDDCNNDDCNNDDCDCNNDNNDDCDNDDCCNDNNDDCNNNDCDNNDNDDCCNNNDNDDNCDCDNNDCNNDNDDCNNDDCDNCNNDDCDNNDCDNDNCDDCNDNNDDCNNNDDCDNCNNDNNDDCNNDDNNDCDNCNDDCNNDCDNNDDCNNDDNCDCNNDNDNDDCDNCDCNNNDNDDCDCNNDNNDDCDNDDCCNNNDNNDDCNDNDNCDDCDCNNNNDNDDCDNCNDDCDNNDDCNNNDNDDCDNCNNDCNNDNDDNCDCDNNNDDCNNDDCNNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDDNDDCNCDNNDCDNNNDDCNNDDCDCDNNDDCNDNCNNDNNDNDNDDCDNCDCNNNDNDDCDNCNNDDCDNNDCNNDDCNNDDCDCDNNDDCNDNCNNNDDCDNNDCDNDNCNNDNDDNNDNDCDDCCNNNDDCNDNDNCDDCDCNNNDNNDDCNDCDNDDCNNNNDNDDCCNDNNDDCDCNNNDNDDNDDCDNCCNNDNNDDCNNDDCDCNNDNNDDCNNDDNCNDDNNDCDNCNDDCNNDDNDCDNNDNDDCCNCDNNDCNNDNDDCNNDDNCDCDNNDCNNDNDDCDCDNNNNDDCNNDDNDCCNNDDNDDCNCDNNDCNNDDNDDCDNCNDDCNNNNDCDNNDDCNDNDDCDNCNNDCDNNDCNNDNDDNCDCNNDNDDCDNDDCCNNNNDNDDCNNDDCDCNNDNNDDCDCDNNDDC"
    def __init__(self):
        self.round_num = -1
    def round(self,_):
        self.round_num += 1
        return Hardcoded.sequence[self.round_num % 1000]

```

Just plays a hardcoded sequence of moves optimized to beat some of the top deterministic bots.
> 0 votes

---
Tags: king-of-the-hill, python
---