title: Recreate the Stack Overflow logo

text:
# Question
Title: Recreate the Stack Overflow logo
> In response to here.
>
> Unlike the previous one, this focuses on and a new logo, no longer consisting of 6 sticks and the graying-effect as the position of the sticks go deeper.

Make the Stack Overflow logo using the following criteria:

**The tray:**

* Make a gray tray shaped like a bracket facing upwards using the following RGB values: 188, 187, 187 (#bcbbbb)
* The dimensions of the tray by pixels:

**The sticks:**

* Make 5 orange sticks using the following RGB values: 244, 128, 36 (#f48024)
* Each stick has a dimension of 44 by 9 pixels.
* The gap between the tray and the bottom stick is 8 pixels:

**The sticks' angles:**

*These angles are relative to the horizontal position which is zero degrees.*

* 1st stick (bottom): 0°
* 2nd stick (second-to-bottom): 10°
* 3rd stick (middle): 25°
* 4th stick (second-to-top): 40°
* 5th stick (top): 50°

**The entire image:**

* The image should look like the image given.
* The entire dimensions of the whole image is 82 by 97 pixels.

**Stick positions (`x, y`):**

*These coordinates refer to the top-left points of each stick. The system used is the top-left point of the entire surface being (0, 0), and the numbers increasing as we go down and to the right. We also assume that the left part of the tray is at the leftmost possible point, i.e. at the far bottom left. Feel free to transcribe this into your system.*

* 1st stick: 17, 71
* 2nd stick: 19, 51
* 3rd stick: 27, 31
* 4th stick: 40, 13
* 5th stick: 55, 0

**Rules:**

* The image should apply all descriptions from above.
* Standard loopholes are forbidden.
* Shortest code in bytes wins.

# Answer
> 5 votes
# HTML+CSS, 550 bytes

```
div {position: absolute;}
.z1 {background:#bcbbbb;top:80px;width:78px;height:34px;}
.z2 {background:#ffffff;left:9px;width:60px;height:25px;}
.s {background: #f48024;top:-15px;width:44px;height:9px;}
.a {top:8px;left:8px;}
.b {transform:rotate(10deg) translate(1px,1px);}
.c {transform:rotate(15deg) translate(2px,-1px);}
.d {transform:rotate(15deg) translate(2px,-1px);}
.e {transform:rotate(10deg) translate(1px,1px);}
```

```
<div class='z1'/>
<div class='z2'/>
<div class='s a'/>
<div class='s b'/>
<div class='s c'/>
<div class='s d'/>
<div class='s e'/>
```

# Answer
> 2 votes
# Python + Pygame, ~~319~~ ~~303~~ ~~273~~ ~~260~~ 252 bytes

Many bytes shaved off thanks to @ovs and p1131.

```
from pygame import*
e=display
s=e.set_mode((82,97))
s.fill(T:=8**8-1)
R=draw.rect
R(s,0xbcbbbb,b'\0?N"')
R(s,T,b'    ?<')
for*i,x in b'GH',b'3F',b'C',b'(\r@',b'7\0>':A=Surface(b',   ',4**8);A.fill("#f48024");s.blit(transform.rotate(A,x*5),i)
e.update()

```

# Answer
> 2 votes
# JavaScript (Canvas API), ~~379~~ ~~341~~ ~~339~~ ~~328~~ 292 bytes

I tweaked the angles a bit to get it closer to the actual logo, but you could change them back to the original suggestions easily (via the `s()` function).

292 bytes == the minified JS code in the snippet at the bottom plus the HTML line (not including `<script>` tags which don't appear in the snippet).

**Ungolfed:**

```
<canvas>
<script>
  c = document.body.children[0].getContext`2d`;

  s = (x, y, d, p = "#f48024", w = 44, h = 9) => (
    c.translate(x, y),
    c.rotate(d),
    c.translate(-x, -y),
    (c.fillStyle = p),
    c.fillRect(x, y, w, h),
    c.setTransform()
  );

  s(0, 63, 0, "#BCBBBB", 78, 34);
  s(9, 63, 0, "#fff", 60, 25);
  s(17, 71);
  s(20, 51, 0.22);
  s(27, 32, 0.43);
  s(40, 13, 0.7);
  s(55, 0, 0.93);
</script>

```

**Minified:**

```
c=document.body.children[0].getContext`2d`,s=(a,b,e,d="#f48024",f=44,g=9)=>(c.translate(a,b),c.rotate(e),c.translate(-a,-b),c.fillStyle=d,c.fillRect(a,b,f,g),c.setTransform()),s(0,63,0,"#BCBBBB",78,34),s(9,63,0,"#fff",60,25),s(17,71),s(20,51,.22),s(27,32,.43),s(40,13,.7),s(55,0,.93);
```

```
<canvas>
```

Edits:

* @ophact's suggestion to remove quotes from the `canvas` ID field saves two bytes
* @ovs's byte-save
* remove all unnecessary html / API characters and elements

# Answer
> 2 votes
# HTML + CSS, 21 + 232 = 243 bytes

### HTML

```
<a><b><c><d><e><e><d>

```

### CSS

```
a,a *{height:100vh;margin:auto;display:grid;transform:rotate(var(--))}b{border:9px solid#bcbbbb;border-top:0;width:60px;height:25px}b *{background:#f48024;width:44px;height:9px}d{--:10deg;margin:-15px 1px}e{--:15deg;margin:-17px 1px

```

### Try it:

```
// (Remove <script>s inserted into Stack Overflow snippet)
while(document.scripts.length) document.scripts[0].remove()
```

```
a,a *{height:100vh;margin:auto;display:grid;transform:rotate(var(--))}b{border:9px solid#bcbbbb;border-top:0;width:60px;height:25px}b *{background:#f48024;width:44px;height:9px}d{--:10deg;margin:-15px 1px}e{--:15deg;margin:-17px 1px
```

```
<a><b><c><d><e><e><d>
```

---

# HTML + CSS, 21 + 195 = 216 bytes

This can be simplified considerably if we space the five stack items equally at 12.5 degrees:

```
a,b,s{height:100vh;margin:auto;display:grid}b{border:9px solid#bcbbbb;border-top:0;width:60px;height:25px}s{background:#f48024;width:44px;height:9px}s s{transform:rotate(12.5deg);margin:-16px 1px
```

```
<a><b><s><s><s><s><s>
```

# Answer
> 2 votes
# PostScript, 209 bytes

Code (compressed version):

```
<</c{setrgbcolor}/r{rectfill}/s{gsave translate rotate 0 0 44 -9 r grestore}>>begin .74 .73 .73 c 0 0 78 34 r 1 1 1 c 9 9 60 25 r .96 .5 .14 c 0 17 26 s -10 19 46 s -25 27 66 s -40 40 84 s -50 55 97 s showpage

```

Code (uncompressed version):

```
% define some short-named procedures for later use
<<
  /c { setrgbcolor }
  /r { rectfill }
  /s {              % operands on stack: angle x y
      gsave
      translate
      rotate
      0 0 44 -9 r
      grestore
  }
>> begin
.74 .73 .73 c       % gray
0 0 78 34 r
1 1 1 c             % white
9 9 60 25 r
.96 .5 .14 c        % orange
  0 17 26 s
-10 19 46 s
-25 27 66 s
-40 40 84 s
-50 55 97 s
showpage

```

Result:

# Answer
> 1 votes
# C (gcc), ~~280~~ ~~278~~ ~~277~~ ~~275~~ ~~268~~ 265 bytes

(Non-printables are in `hex`)

```
#define r(s...)printf(R"X(<rect x="%d" y="%d" transform="rotate(%d,%1$d,%2$d)" width="%d" height="9" fill="#%x"/>)X",s,63,90,34,c)
c=0xbcbbbb,*p=L"`b4`P=\n3`13``19``1f``1b`(\r(2`00`7";main(){r(!r(9),88,!puts("<svg>"),78,c);for(r(78);*p;)r(*p++,*p++,*p++,44,0xf48024);puts("</svg>");}
```

Try it online!

* -2 bytes by using 180 degree rotation, using `*p++`, and reordering the LUT for GCC's reverse ordering.
* -1 byte for blatant `for` loop optimization
* -2 bytes for abusing the return value of `printf` and `puts` for `0`
* -7 bytes using C++-style raw literals thanks to p1131
* -3 bytes abusing vararg macros thanks again to p1131

~~I beat Python, I feel somewhat accomplished.~~ Edit: said words now taste salty.

With macros expanded and commented

```
// LUT is encoded as a raw wide string literal
// expanded
LUT[] =
    // Rot,  y,  x
       180, 80, 61, // first is upside down to avoid an inconvenient null byte
        10, 51, 19,
        25, 31, 27,
        40, 13, 40,
        50,  0, 55,
         0 // implicit null terminator
};

c = 0xbcbbbb, *p = L"...";
main()
{
    // Note that GCC evaluates function parameters
    // from right to left, so these are bottom line up
    printf(
       // GCC supports raw string literals in C mode
       // We use this to avoid \"
       R"X(<rect x="%d" y="%d" transform="rotate(%d,%1$d,%2$d)" width="%d" height="9" fill="#%x"/>)X",
       // !printf == 0 for non-empty strings
       // x = 0
       // Called second
       !printf(
          "<rect ...>",
          9,   // x
          63,  // y
          90,  // rot
          34,  // width
           c   // color
       ),
       88, // y
       // Called first
       // rot = 0
       !puts("<svg>"),
       78, // width
        c, // Color
       // garbage arguments left in that printf doesn't use
       63, 90, 34, c
    );
    // Loop through our LUT for the 5 orange bars
    for (
        // Typical printf optimization
        printf("<rect ...>", 78, 63, 90, 34, c);
        // loop until null terminator
        *p;
    )
        // More eval order abuse
        printf(
            "<rect ...>",
            *p++, // x = p[2]
            *p++, // y = p[1]
            *p++, // rot = p[0]
            44,   // width
            0xf48024, // color
            63, 90, 34, c // garbage
        );
    // Closing tag
    puts("</svg>");
}

```

**Ungolfed:** (different order, but clean)

```
#include <stdio.h>
// Note that macro compression is used to save a few bytes.

// Color constants
static const int GRAY = 0xbcbbbb;
static const int ORANGE = 0xf48024;

// encoded raw as a string in the golfed code
static const int LUT[] = {
    // x, y, rotation
    17, 71,  0,
    19, 51, 10,
    27, 31, 25,
    40, 13, 40,
    55,  0, 50,
    0 // null terminate
};

// golfed version uses a macro
static void rect(
    int x,
    int y,
    int width,
    int color,
    int rotation
)
{
    // This could definitely be golfed better if I figure out the arithmetic for positioning
    printf("<rect "
              "x=\"%d\" "
              "y=\"%d\" "
              "width=\"%d\" "
              "height=\"9\" "
              "fill=\"#%x\" "
              // rotate at top left corner
              "transform=\"rotate(%d,%1$d,%2$d)\""
           "/>", x, y, width, color, rotation);
}
int main(void)
{
    // Print SVG header
    puts("<svg>");
    // Loop through all 5 lines
    for (const int *ptr = LUT; *ptr != 0; ptr += 3) {
        rect(/*x*/ ptr[0], /*y*/ ptr[1], /*width*/ 44, /*color*/ ORANGE, /*rotation*/ ptr[2]);
    }
    // Output the box
    rect(/*x*/  9, /*y*/ 63, /*width*/ 34, /*color*/ GRAY, /*rotation*/ 90);
    rect(/*x*/  0, /*y*/ 88, /*width*/ 78, /*color*/ GRAY, /*rotation*/  0);
    rect(/*x*/ 78, /*y*/ 63, /*width*/ 34, /*color*/ GRAY, /*rotation*/ 90);
    // Output closing SVG tag
    puts("</svg>");
}

```

This outputs the following SVG file to standard output when run (whitespace added to make it readable):

```
<svg>
  <rect x="9" y="63" transform="rotate(90,9,63)" width="34" height="9" fill="#bcbbbb"/>
  <rect x="0" y="88" transform="rotate(0,0,88)" width="78" height="9" fill="#bcbbbb"/>
  <rect x="78" y="63" transform="rotate(90,78,63)" width="34" height="9" fill="#bcbbbb"/>
  <rect x="61" y="80" transform="rotate(180,61,80)" width="44" height="9" fill="#f48024"/>
  <rect x="19" y="51" transform="rotate(10,19,51)" width="44" height="9" fill="#f48024"/>
  <rect x="27" y="31" transform="rotate(25,27,31)" width="44" height="9" fill="#f48024"/>
  <rect x="40" y="13" transform="rotate(40,40,13)" width="44" height="9" fill="#f48024"/>
  <rect x="55" y="0" transform="rotate(50,55,0)" width="44" height="9" fill="#f48024"/>
</svg>

```

Stack snippet containing raw output:

```
<svg>
<rect x="9" y="63" transform="rotate(90,9,63)" width="34" height="9" fill="#bcbbbb"/><rect x="0" y="88" transform="rotate(0,0,88)" width="78" height="9" fill="#bcbbbb"/><rect x="78" y="63" transform="rotate(90,78,63)" width="34" height="9" fill="#bcbbbb"/><rect x="61" y="80" transform="rotate(180,61,80)" width="44" height="9" fill="#f48024"/><rect x="19" y="51" transform="rotate(10,19,51)" width="44" height="9" fill="#f48024"/><rect x="27" y="31" transform="rotate(25,27,31)" width="44" height="9" fill="#f48024"/><rect x="40" y="13" transform="rotate(40,40,13)" width="44" height="9" fill="#f48024"/><rect x="55" y="0" transform="rotate(50,55,0)" width="44" height="9" fill="#f48024"/></svg>
```

---

# C (gcc), boring semi-cheating version, ~~236~~ 231 bytes

```
main(){puts(R"(<svg><path fill="#bcbbbb" d="M9 63v25H0V63zM0 88h78v9H0zm78-25v25h-9V63z"/><path fill="#f48024" d="M61 80H17v-9h44zM19 51l43 8-1 9-44-8zm8-20l40 19-4 8-40-19zm13-18l34 28-6 7-34-28zM55 0l28 34-7 5L48 6z"/></svg>)");}

```

Try it online!

-5 bytes for using raw string literals as well.

This is literally just SVGOMG on the lowest setting, so I don't take credit for it. I can't even tell what it is doing.

It does have much lower precision, though.

```
<svg>
    <path fill="#bcbbbb" d="M9 63v25H0V63zM0 88h78v9H0zm78-25v25h-9V63z"/>
    <path fill="#f48024" d="M61 80H17v-9h44zM19 51l43 8-1 9-44-8zm8-20l40 19-4 8-40-19zm13-18l34 28-6 7-34-28zM55 0l28 34-7 5L48 6z"/>
</svg>

```

```
<svg><path fill="#bcbbbb" d="M9 63v25H0V63zM0 88h78v9H0zm78-25v25h-9V63z"/><path fill="#f48024" d="M61 80H17v-9h44zM19 51l43 8-1 9-44-8zm8-20l40 19-4 8-40-19zm13-18l34 28-6 7-34-28zM55 0l28 34-7 5L48 6z"/></svg>
```

# Answer
> 1 votes
# HTML + JavaScript, 13 + 226 bytes = 239 bytes

```
with(c.getContext`2d`)(F=(x,y,r,f='#f48024',w=44,h=9)=>setTransform(translate(x,y),rotate(r),fillStyle=f,fillRect(0,0,w,h))||F)(0,63,0,'#bcbbbb',78,34)(9,63,0,'#fff',60,25)(17,71)(19,51,.175)(27,31,.436)(40,13,.698)(55,0,.873)
```

```
<canvas id=c>
```

# Answer
> 0 votes
# SVG, ~~240~~ 238 bytes

Path data from the official spritesheet, with some minor edits for golfing.

```
<svg><path fill=#BCBBBB d=M26,41v-9h4v13H0V32h4v9h22z /><path fill=#F48024 d=M23,34l.8-3-16.1-3.3L7,31l16,3zM9.2,23.2l15,7,1.4-3-15-7-1.4,3zm4.2-7.4L26,26.4l2.1-2.5-12.7-10.6-2.1,2.5zM21.5,8l-2.7,2,9.9,13.3,2.7-2L21.5,8zM7,38h16v-3H7v3z >
```

---
Tags: code-golf, graphical-output
---


# Question
Title: Final tribute to John Conway: FRACTRAN self-interpreter
It's time to conclude the series of John Conway challenges of mine.

## Background

A **FRACTRAN** program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

You can find some tips and tricks for writing FRACTRAN programs in the previous challenge Collatz in FRACTRAN.

## Challenge

Write a FRACTRAN program that

* takes a FRACTRAN program **P** and its input number **N** encoded as an integer, and
* halts if and only if the program **P** halts with the input **N**.

Use the following procedure for encoding **P** to get a single positive integer **f(P)**:

* Write down the numerator and denominator of each fraction in P in base `b`, using the value `b` as a separator.
* Read the whole thing as a single number in base `b+1`.

You can choose the value of `b`, whether to put a separator at either end or not, and which number (numerator/denominator, first fraction/last fraction) comes first in the representation. One possible encoding is:

```
[455/33, 11/13, 1/11, 3/7, 11/2, 1/3]
int("1a3a11a2a3a7a1a11a11a13a455a33", 11) = 3079784207925154324249736405657

```

The input value must be in the form of \\$p^{f(P)} q^N n\\$, where \\$p, q\\$ are two distinct primes and \\$n\\$ is a number coprime to \\$pq\\$. You can choose the values of \\$p,q,n\\$. (This format is consistent with the 84-fraction answer on SO and the 48-fraction one linked below.)

The shortest program in terms of **the number of fractions** wins.

The best record available is ~~**48**~~ ~~**30**~~ **24 fractions** by benrg!

# Answer
# 30 fractions

```
37^1/41^1
43^1/47^1
41^10*31^1*13^1/37^10*29^1
1/37^10
47^9*5^1/43^9*7^1
47^9/43^9*17^1
47^9/43^9*13^1
47^9/43^9*23^1
41^1*47^8/37^1*43^8*29^1
41^6*47^3/37^1*43^8*53^2
41^2*47^7*23^1*7^1/37^2*43^7*13^1*5^1
47^9*53^2/37^2*43^7*13^1
41^3*47^6*13^1/37^3*43^6*23^1
41^2*47^7*23^1*7^1*29^1/37^3*43^6*13^1*5^1
41^3*47^6/37^3*43^6*13^1
41^4*47^5*11^1/37^4*43^5*17^1
41^5*47^4*5^1/37^5*43^4*13^1
41^5*47^4/37^5*43^4*7^1
41^5*47^4/37^5*43^4*29^1
41^5*47^4*3^1/37^5*43^4*2^1
41^6*47^3*17^1/37^6*43^3*13^1
41^7*47^2*23^1/37^7*43^2*3^1
41^8*47^1*3^1*2^3/37^8*43^1*23^4
41^1*47^8*2^3*53^1/37^8*43^1*23^3
41^8*47^1*11^1*2^1/37^8*43^1*23^1
41^9*31^3/37^9*29^1
41^7*47^2*23^1*29^2/37^9*3^1
29^1/31^1
37^10*13^1/11^1
37^1/43^1

```

p = 2, q = 5, n = 37^5 * 43^4 * 53^1

b = 3, denominators first, last fraction first, separator at start and not at end

## How does this work?

To make it easier to understand, assign meaningful names to the primes used:

```
ifracs=2 ifracsw=3 inum=5 inum_r=7 multiplicand=11 products=13 denominator=13 numerator=17 temp=23 multiplier=29 multiplier_r=31 stateA=37 stateA_r=41 stateB=43 stateB_r=47 p_indicator=53

```

Convert denominators to negative exponents, and then we can omit the `^` and `*` symbols (always including exponents even if 1). This produces a notation similar to Subtractpocalypse (which, as the linked page notes, becomes equivalent to FRACTRAN with a single change). Together with this, we use the name of a prime to refer to the exponent of that prime in the current number.

### The state mechanism

`stateA` and `stateB` together form a state. 10 standard states (0,9), (1,8), (2,7), ..., (9,0) are chosen such that none has both components greater than or equal to another's; this way, an instruction can single out one state that it will execute only in, by subtracting the appropriate values from `stateA` and `stateB`.

To restore the state (same or different), we can't simply add back to `stateA` and `stateB`, as that would give the numerator and denominator a common factor. Instead, we add values corresponding to the new state to `stateA_r` and `stateB_r`, and the first two instructions transfer those values back to `stateA` and `stateB`:

```
# At the start
stateA_r -1  stateA +1
stateB_r -1  stateB +1

```

We use an abbreviated notation for these common parts:

```
State[M -> N] = stateA -M  stateB -(9-M)  stateA_r +N  stateB_r +(9-N)
State[N] = State[N -> N]

```

Also, the last instruction is used to automatically advance from one state to the next when nothing else executes:

```
# At the end
stateA +1  stateB -1

```

### Parsing f(P)

```
# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1

```

We start in state 5. There are some other instructions in state 5, but they do nothing at the start.

First, the value of f(P) is transferred from `ifracs` to `ifracsw`. The instruction in state 6 does nothing at the start.

The value is transferred from `ifracsw` to `temp` next. Then, in state 8, divide by 4 by repeatedly subtracting 4 from `temp` and adding 1 to `ifracsw`; simultaneously, 'refill' `ifracs` by adding the difference, which is 3, to it. After this finishes, the remainder will be left in `temp`.

The next instruction tests for the separator (3), changing to state 1 and also incrementing `p_indicator` and 'refilling' `ifracs`.

Suppose we haven't reached a separator. To reconstruct the base-3 number, we need to multiply the digits by 1, 3, 9, etc. This uses...

### The multiplication subroutine

Multiplication happens automatically whenever the end of a state is reached, before moving on to the next state, with `multiplicand` nonzero. It adds to `products` the product of `multiplicand` and (`multiplier`+1), for a few reasons. It is implemented by these instructions:

```
# Multiplication (near the start)
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10

# Multiplication (near the end)
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1

```

The fourth of these instructions executes first. It decrements `multiplicand`, increments `products` (for the 1 added to `multiplier`), and adds 10 to `stateA`, enabling the upper two instructions. Then the first instruction runs repeatedly, transferring `multiplier` to `multiplier_r` while adding to `products`. The second instruction subtracts the added 10 from `stateA`, exiting this section, then the third instruction transfers `multiplier_r` back to `multiplier`, and this repeats until `multiplicand` is zero.

### Back to parsing f(P)

```
State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2

```

To activate multiplication, the last instruction of state 8 transfers `temp` to `multiplicand`, while 'refilling' `ifracs`. Multiplication occurs before the transition to state 9, adding the appropriate value for this digit to `products`.

Finally, we need to triple the effective multiplier, which means tripling `multiplier` and adding 2 to it. The instructions in state 9 accomplish that; the second one duplicates the instruction in state 7 as a way of testing whether we have reached the end of `f(P)`, ending the program (since this is the last state) if so. (Note that, because we specified that `f(P)` begins with a separator, the end always happens after only one digit 0 is read, with `multiplier`=0, avoiding an infinite loop.)

Changing state immediately after filling `multiplier_r` from `multiplier` avoids a similar infinite loop. Going to state 7, the process repeats to read the next digit of f(P).

### Handling the fraction

```
State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1

```

`p_indicator` is initialised to 1, and incremented upon changing from state 8 to state 1. Thus, after reading the first (in this process; the last in the base-4 expansion) of each pair of numbers, which we have specified to be the numerator, `multiplier` is reset to 0, and since `p_indicator` is now 2, it becomes 0 with a change to state 6, where the value is transferred from `products` to `numerator`.

After reading the denominator, state 1 ends with `p_indicator`=1.

(Note that `denominator` is an alias for `products` -- they refer to the same prime.)

In state 2, the first instruction transfers `denominator` to `temp` and `inum` to `inum_r` simultaneously. This ends when `denominator` or `inum` reaches zero.

The second instruction checks for `denominator` being nonzero, which indicates that the number (original value of `inum`) was not divisible by the (original) `denominator`; it changes to state 0 while increasing `p_indicator` to 3. Then, the instructions in state 0 transfer `inum_r` back to `inum`, clear several values, and then continue to state 1 to clear `multiplier` and proceed to state 6 to resume reading f(P), with `p_indicator` reduced back to 1.

In state 3, `temp` is transferred back to `denominator`, and the second instruction returns to state 2 while repeating its first instruction (as before, this checks for completion) and incrementing `multiplier`.

If the loop exits here, then the number (original value of `inum`) was divisible by the (original) `denominator`, and `multiplier` contains the quotient minus 1 (for each iteration except the last).

```
State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1

```

The final instruction of state 3 clears `denominator` (which is `product`). Then, in state 4, we transfer `numerator` to `multiplicand`, and with the transition to state 5, that value is multiplied by the quotient (recall that the multiplication subroutine uses `multiplier`+1). In state 5, we transfer `products` to `inum`, clear some values, and continue to repeat from the start.

## The whole program with the updated notation

```
# Initialise: ifracs, inum; p_indicator=1, stateA=5, stateB=4
stateA_r -1  stateA +1
stateB_r -1  stateB +1

# Multiplication
stateA -10  stateA_r +10  multiplier -1  multiplier_r +1  products +1
stateA -10

State[0] inum_r -1  inum +1
State[0] numerator -1
State[0] denominator -1
State[0] temp -1

State[1] multiplier -1
State[1 -> 6] p_indicator -2
State[2] denominator -1  temp +1  inum -1  inum_r +1
State[2 -> 0] denominator -1  p_indicator +2
State[3] temp -1  denominator +1
State[3 -> 2] denominator -1  temp +1  inum -1  inum_r +1  multiplier +1

State[3] denominator -1
State[4] numerator -1  multiplicand +1
# Multiplication occurs
State[5] products -1  inum +1
State[5] inum_r -1
State[5] multiplier -1

# Start here-ish
State[5] ifracs -1  ifracsw +1
State[6] products -1  numerator +1
State[7] ifracsw -1  temp +1
State[8] temp -4  ifracsw +1  ifracs +3
State[8 -> 1] temp -3  ifracs +3  p_indicator +1
State[8] temp -1  multiplicand +1  ifracs +1
# Multiplication occurs
State[9] multiplier -1  multiplier_r +3
State[9 -> 7] ifracsw -1  temp +1  multiplier +2

# Multiplication
multiplier_r -1  multiplier +1
multiplicand -1  stateA +10  products +1

stateA +1  stateB -1

```
> 20 votes

# Answer
# 24 fractions

$$\frac{2}{3}, \frac{5}{7}, \frac{7^{12} 41}{5^{12} 23}, \frac{7^{13}}{5^{13} 37}, \frac{3^{10} 7^3 13}{5^{13} 31}, \frac{3^2 7^{11} 19^1 41}{2^2 5^{11} 29}, \frac{3^3 7^{10} 19^1 23}{2^3 5^{10} 29^1 41}, \frac{3^1 7^{12} 19^1 37}{2^3 5^{10} 29}, \frac{3^4 7^8 29}{2^4 5^8 19}, \frac{3^4 7^8 11^b 31}{2^4 5^8 13^{b+1}}, \frac{3^{13} 11^b}{2^4 5^9 13^b 41}, \frac{3^{12} 7^1 11^b 19}{2^5 5^8 13^b}, \frac{3^2 7^{10} 11}{2^4 5^8 13}, \frac{3^8 7^4 19^b}{2^8 5^4 29}, \frac{3^8 7^4 13}{2^8 5^4 31}, \frac{3^{12}}{2^{12} 29}, \frac{3^{13} 17^1 19}{2^{13} 37}, \frac{7^{13}}{2^{12} 5^1 23}, \frac{3^{12} 7^1 31}{2^{12} 5^1 11}, \frac{3^{12} 7}{2^{12} 5^1 17}, \frac{3^{10} 7}{2^{10} 5^1 41}, \frac{3^{10} 7^3 37}{2^{10} 5^3 17}, \frac{3^3 7^4}{2^1 5^6}, \frac{3^4 7^4}{2^8}$$

Plug in a base \\$b\ge2\\$ of your choice. The start state is \\$31^{f(P)} 17^N 5^{13} 19\\$. The program encoding has a sentinel digit on the high end only (same as m90's), and the denominator on the low end (opposite of m90's). If \\$b=10\\$, the program \\$\frac{22}{7},\frac{355}{113}\\$ encodes to `int("a355a113a22a7", 11) = 32383861120629`.

### Explanation and annotated listing

This program uses the same double/quadruple state system as m90's 30-fraction program, but I'll call them "modes" to avoid confusion with FRACTRAN states.

A lot of the improvement of this solution comes from the observation that fractions can match ranges of modes as easily as single modes. Instead of using a subroutine or a loop variable (like m90's `p_indicator`) for code reuse, I use different modes with adjacent numbers, which can have any mix of shared and unshared code. Also, where m90's program has a single mode fallthrough rule at the bottom, I have two: if the mode is 1-7 then it's increased by 2, otherwise it's decreased by 4. Those two rules account for the majority of the control flow.

The basic algorithm is:

* Modes 2, 4, 6, 8 read the denominator.
* Modes 1, 3, 5, 7, 9 read the numerator while calculating \\$\text{divmod}(\text{state} \times \text{numerator}, \text{denominator})\\$. The intermediates (numerator and product) are never stored anywhere.
* Modes 0 and 10-13 test the remainder, update the state, rewind the program, etc.

I tried to assign similar-looking (in base 10) register numbers to related purposes. The registers are:

* 2,3,5,7 are the mode variables.
* 11,13,31 hold the program. 13 and 31 are used to parse it, and 11 is a "counterweight" adjusted so that the full program is preserved as the sum. (m90 used a similar trick.)
* 23 and 41 hold the remainder and divisor (denominator). Values of (0, d-1), (1, d−2), …, (d−1, 0) represent a divisor of d and a remainder of 0, 1, … d-1.
* 17 and 37 hold the old state (saved in case the remainder is nonzero) and the new state (quotient of the division).
* 19 and 29 hold the place value when reading the denominator, and the old state times the place value when reading the numerator (so state × numerator is calculated for free).

I'll write \\$\[a{,}b\]\rightarrow\[c{,}d\]\\$ (where \\$d-c=b-a\ge 0\\$), or just \\$\[a{,}b\]\\$ if \\$a=c\\$, for a factor of \\$\displaystyle \frac{3^c \\, 7^{13-d}}{2^a \\, 5^{13-b}}\\$, which means "if we're in modes \\$a\\$ to \\$b\\$ inclusive then switch to modes \\$c\\$ to \\$d\\$ and also do whatever else is in this fraction."

Also, I'll give the two-digit primes slightly more descriptive names: prg11, prg13, prg31, div23, div41, st17, st37, plc19, plc29.

Stack Exchange tables and MathJax don't play well together, so no MathJax in the table.

|  |  |
| --- | --- |
| 3−1 2+1,
7−1 5+1 | Mode management, same as m90's program. |
| \[0,0\] st37−1,
\[0,1\] div23−1 div41+1,
\[0,0\]→\[10,10\] prg31−1 prg13+1 | Mode 0: the designated starting point and also reached when division fails. Clear the quotient (st37) and remainder (div23). Halt if the program is exhausted, otherwise go to mode 10. The second instruction is shared with mode 1 (in fact, it's the only instruction in mode 1 aside from the default mode transition). |
| \[10,12\] div41−1,
\[10,10\] st17−1 st37+1 | Mode 10: clear the divisor and copy the saved FRACTRAN state back, then go to mode 8 (via the empty mode 6). The first instruction is shared with mode 12 (mode 11 is unused). |
| \[8,9\] plc29−1 plc19+b,
\[8,9\] prg31−1 prg13+1 | Mode 8 (denominator) or 9 (numerator): multiply the place value by b (does nothing on initial entry), and move the program to prg13, then go to mode 4/5. |
| \[4,5\] plc19−1 plc29+1,
\[4,5\] prg13−(b+1) prg31+1 prg11+b | Mode 4/5 (den./num.): move the place value back to plc29, and compute prg31, prg13 = divmod(prg13, b+1). |
| \[4,4\]→\[13,13\] prg13−b prg11+b div41−1,
\[5,5\]→\[12,12\] prg13−b prg11+b plc19+1 | Mode 4/5: exit the loop if the sentinel digit is reached. Duplicated because they need different off-by-one fixups: after reading the denominator, decrement it, and after reading the numerator, set the place value to 1 for next time. |
| \[4,5\]→\[2,3\] prg13−1 prg11+1 | Mode 4/5: if the digit is anything else, go to mode 2/3 to add the place value an appropriate number of times, then go to mode 8/9 (via the empty 6/7) |
| \[2,2\] plc29−1 plc19+1 div41+1 | Mode 2/3: if we're reading the denominator, just add the place value. |
| \[3,3\] plc29−1 plc19+1 div41−1 div23+1,
\[3,3\]→\[1,1\] plc29−1 plc19+1 st37+1 | Mode 2/3: if we're reading the numerator, increment the remainder, or if it's equal to divisor−1, zero it (using mode 1) and increment the quotient. Exit to mode 4/5. |
| \[12,13\] plc29−1 | Mode 12/13 (found the sentinel digit): discard the place value. |
| \[13,13\] st37−1 st17+1 plc19+1 | Mode 13 (finished with the denominator): copy it to the place value and go to mode 9 to read the numerator. |
| \[12,12\]→\[0,0\] div23−1,
\[12,12\] prg11−1 prg31+1,
\[12,12\] st17−1 | Mode 12 (finished with the numerator): if the remainder is nonzero then go to mode 0; otherwise, restore the original program, discard the divisor (see mode 10) and old state, and go to mode 8 to read the denominator. |
| \[1,7\]→\[3,9\],
\[8,13\]→\[4,9\] | Default mode transitions. |

### Can this be improved?

Probably. It's just a PITA to satisfy all the constraints:

* The modes have to be numbered to take advantage of default fallthrough, and also to keep modes with shareable instructions together, and also the halting mode has to be on the edge so it doesn't get caught in the default-fallthrough whirlpool.
* One-time adjustments to registers can only be done during mode changes, but most of the mode changes are shared across a large number of modes. For example, m90's program tracks the place value minus 1. But that means that after you multiply it by b, you have to add b−1. But the mode transition where that would need to happen in my program is handled by the default rule, so I can't do it, or at least I don't see how.
* The challenge has strict input requirements that limit potential optimizations. For example, if I could compute the quotient (new state) minus one, it would avoid an off-by-one error when the state is added to the place value which would otherwise be 1. But then there would be no point in the loop where the interpreter state had the form \\$p^\text{state}q^\text{program}n\\$; the closest you'd get would be \\$p^{\text{state}-1}q^\text{program}n\\$.

I think the ripest candidate for improvement is the unshared fractions in modes 4 and 5. The mode offsets of the jumps are different, but that's easy to fix by rearranging the modes. plc19+1 could be shared if I could subtract one from the state somewhere (as mentioned above). div41−1 could be eliminated by decrementing the program before parsing the denominator. The failed-division path does that anyway, but there's no place to do it in the successful-division path. That would be a nonissue if the challenge allowed the input state to be \\$p^\text{state}q^{\text{program}-1}n\\$. (It's funny that both input parameters seem to be improved by subtracting 1.)
> 14 votes

# Answer
Here are a few solutions not written by me! If one of these is yours, please feel free to post it separately and I'll remove it from this answer. These have all been in this comment for a while, but I'm converting it to an answer for greater visibility.

## Collected Answers
> 3 votes

---
Tags: interpreter, atomic-code-golf
---


# Question
Title: Sequence of integers not the sum of powers of earlier terms
Starting with 1, output the sequence of integers which cannot be represented as the sum of powers of earlier terms. Each previous term can be used at most once, and the exponents must be non-negative integers.

This sequence starts:

```
1, 2, 6, 12, 25, 85, 194, 590, 1695, 4879, 19077, 83994, 167988

```

For example, after 1 and 2:

* \\$ 3 = 1^1 + 2^1 \\$, so 3 is not in the sequence
* \\$ 4 = 2^2 \\$, so 4 is not in the sequence
* \\$ 5 = 1^1 + 2^2 \\$, so 5 is not in the sequence
* \\$ 6 \\$ cannot be represented in this way, so 6 is in the sequence
* etc.

The powers can also be 0; for example, \\$ 24 = 1^1+2^4+6^1+12^0 \\$, so 24 is not in the sequence.

This is OEIS A034875.

## Rules

* As with standard challenges, you may choose to either:
    + Take an input `n` and output the `n`th term of the sequence
    + Take an input `n`and output the first `n` terms
    + Output the sequence indefinitely, e.g. using a generator
* You may use 0- or 1-indexing
* You may use any standard I/O method
* Standard loopholes are forbidden
* This is , so the shortest code in bytes wins

# Answer
# Python 3, <sup>~~121~~ ~~107~~ ~~105~~ ~~102~~</sup> 101 bytes

-3 inspired by Neil's comments, and another -1 thanks to Neil!

Prints the sequence indefinitely. Runs out of memory before finding 25 on TIO.

```
d,*r=0,
while m:=1:
 d+=1
 for v in r:
  w=m
  for p in range(d):m|=w<<v**p
 if~m>>d&1:r+=d,;print(d)

```

Try it online!

---

# Python 3, ~~186~~ ~~178~~ 166 bytes

Fast version, produces all terms on the OEIS page in 2 minutes locally. Assuming this is correct, the next two terms are \\$3828253274\\$ and \\$24694834727\\$. Because of the time is spent in arithmetic with large numbers (native code), a naïve C+gmp translation is only ~2 times faster, and very ungolfy.

```
m=d=1;r=[]
print(1)
while q:=3:
 s=(~m&m+1).bit_length()-1;d+=s;m>>=s
 for v in r:
  w=q;l=1
  while l<=d:q|=w<<l;l*=v
  if q&1<<d:break
 else:r+=d,;print(d)
 m|=q>>d

```

Try it online!
> 5 votes

# Answer
# Jelly, ~~24~~ 22 bytes

```
*þṀŻ$ZŒpŒP€Ẏ§‘ḟ$Ṃ;
⁸Ç¡

```

Try it online!

Takes \\$n\\$ via STDIN and outputs the first \\$n\\$ terms in reverse order. +1 byte if the output has to be in ascending order.

Incredibly slow, can handle up to \\$n = 4\\$ on TIO. If \\$a\_n\\$ is our sequence so far, then, to generate \\$a\_{n+1}\\$, the code runs in approximately \\$O((2a\_n + 2)^n)\\$ time.

-2 bytes thanks to Jonathan Allan

## How it works

```
*þṀŻ$ZŒpŒP€Ẏ§‘ḟ$Ṃ; - Helper link. Given a list L of integers, returns the list with the next term prepended
    $              - To L:
  Ṁ                -   Maximum
   Ż               -   [0, ..., max(L)]
 þ                 - Over each pair (l, i), l ∈ L, i ∈ [0, ..., max(L)]:
*                  -   Raise l to the ith power
     Z             - Transpose
      Œp           - Cartesian product of rows
        ŒP€        - Powerset of each
           Ẏ       - Collapse into a list of lists
            §      - Sums
               $   - To our list of sums:
             ‘     -   Increment
              ḟ    -   Remove elements in the list of sums
                Ṃ  - Minimum
                 ; - Prepend it to L

⁸Ç¡                  - Main link. No arguments.
⁸                    - Set the return value to []
  ¡                  - Read n from STDIN. Starting with [], do n times:
 Ç                   -   Call the helper link, updating the argument with the previous return value each time

```

---

Alternatively, a much faster version at 36 bytes that can do up to \\$n = 8\\$ on TIO.
> 3 votes

# Answer
# Jelly, 22 bytes

```
-rṀṗL‘a*@ɗ⁸§‘ḟ$Ṃ;@
⁸Ç¡

```

A full program that accepts an integer, `n`, from STDIN and prints the Jelly representation of the first `n` terms so STDOUT.

**Try it online!** (6 will time out on TIO.)

### How?

```
-rṀṗL‘a*@ɗ⁸§‘ḟ$Ṃ;@ - Link 1, getNext: list KnownTerms
  Ṁ                - maximum of KnownTerms (given an empty list yields 0)
-                  - -1
 r                 - inclusive range -> Exponents (-1 is an indicator to exclude the base)
    L              - length of KnownTerms
   ṗ               - Cartesian power -> all sets of exponents of size NumberOfTerms
         ɗ⁸        - last three links as a dyad - f(Sets, KnownTerms)
     ‘             - increment all Exponents in the Sets
       *@          - KnownTerms exponentiate Sets (vectorises)
      a            - logical AND (vectorises) (i.e. replace with 0 when the exponent was -1)
           §       - sums
              $    - last two links as a monad:
            ‘      -   increment all the found values
             ḟ     -   filter out the found values
               Ṃ   - minimum
                ;@ - concatenate to KnownTerms

⁸Ç¡ - Main Link: no arguments
⁸   - empty list
  ¡ - repeat...
    - ...times: implicitly take an integer from STDIN
 Ç  - ...action: call Link 1 as a monad
    - implicit print

```
> 3 votes

# Answer
# JavaScript (V8), 104 bytes

Prints the sequence forever. Not tremendously fast, but fast enough to reach \\$19077\\$ on TIO.

```
for(a=N=[];;g``||a.push(N)&print(N))g=(q,i=1,n=++N)=>n<0|!a[i]?0:n<2||g(Q=q*a[i]||1,i,n+q-Q)||g(0,i+1,n)

```

Try it online!

### Note

The way this algorithm works, it would be a bit painful to use \\$1^k\\$ because we'd need some extra testing to avoid an infinite loop. Instead, we don't use it at all and try to reach either \\$n\\$ or \\$n-1\\$ with the other integers. This is why the search function \\$g\\$ starts at index \\$i=1\\$ in the array \\$a\[\\:\]\\$.

---

# JavaScript (V8), 101 bytes

Slower but a little shorter.

```
for(a=N=[];;g``||a.push(N)&print(N))g=(q,i=1,n=++N)=>n*a[i]>=0&&n<2|g(Q=q*a[i]||1,i,n+q-Q)|g(0,i+1,n)

```

Try it online!
> 2 votes

# Answer
# Charcoal, 42 bytes

```
Ｎθ≔⁰ηＷ‹Ｌυθ«≦⊕η≔⟦η⟧ζＦυＦ⮌ζＦλ⊞ζ⁻λＸκμ¿Πζ⊞υη»Ｉυ

```

Try it online! Link is to verbose version of code. Explanation: Port of @ovs' Python answer, except outputs the first `n` terms.

```
Ｎθ

```

Input `n`.

```
≔⁰η

```

Start looking for terms.

```
Ｗ‹Ｌυθ«

```

Repeat until enough terms have been found.

```
≦⊕η

```

Try the next integer.

```
≔⟦η⟧ζ

```

Start with a list of just that integer, corresponding to no powers of earlier terms yet.

```
Ｆυ

```

For each earlier term...

```
Ｆ⮌ζ

```

... for each value in a (reversed because it's the golfiest way to) copy of the list...

```
Ｆλ⊞ζ⁻λＸκμ

```

... subtract some powers of the earlier term and add the results to the list.

```
¿Πζ⊞υη

```

If there were no zeros in the list (i.e. the product is nonzero), meaning that no sums of powers added to the current integer, then add it as a term.

```
»Ｉυ

```

Output all of the found terms.

~~76~~ 74 bytes for a somewhat faster version based on @ovs' faster version:

```
Ｎθ≔³ε≔⁰ζ⊞υ¹Ｗ‹Ｌυθ«Ｗ＆εＸ²ζ≦⊕ζ≔³εＦυ«≔εδ≔¹ιＷ∧⊖κ¬›ιζ«≧｜×δＸ²ιε≧×κι»»¿¬＆εＸ²ζ⊞υζ»Ｉυ

```

Try it online! Link is to verbose version of code.
> 2 votes

# Answer
# Python 3, 179 bytes

```
from itertools import*
def f(n):
	x,N=[1],2
	while len(x)<n:x=[x+[N],x][N in[sum([N**p for N,p in zip(x,e)if-1<p])for e in product(*[list(range(-1,N))for _ in x])]];N+=1
	return x

```

Try it online!

It is quite slow, the TIO link will only let you test up to `n=5`

# Explanation

```
from itertools import*
def f(n):
    x,N=[1],2                                                              # Initialise the list, start testing from 2
    while len(x)<n:                                                        # Condition to get the first n terms of the sequence
                   [N in                                                   # Returns False (indexes 0) if N not in list,
        x=[x+[N],                                                          # appending N to the list,
                 x]                                                        # else leave the list unchanged
                        [sum([N**p for N,p in zip(x,e)                     # Sum of the previous sequence terms raised to their respective powers,
                            if-1<p])                                       # unless it's not in this permutation (a power of -1 is used to represent a 0 multiplier)
                                for e in product(                          # Permutations of the possible powers for the previous terms of the sequence
                                    *[list(range(-1,N))for _ in x])]];     # Possible powers for each previous term of the sequence.
                                                                      N+=1 # Increment number
    return x                                                               # Return the sequece

```

The main reason this runs so slow is because there are so many permutations for all the powers, and because list comprehension is used it has to calculate all permutations. Currently all possible powers from `0` to `n-1` are considered, as this was the shortest way to do it in bytes (and still theoretically be able to calculate for any `n`). A faster solution would be to limit the possible powers, for example by replacing `[list(range(-1,N))for _ in x]` with `([[-1,0]]+[[-1]+[i for i in range(int(math.log(N,j))+1)]for j in x[1:]])`, which only lets each term go up to the power such that \\$t\_i^p\<N\\$
> 1 votes

# Answer
# Ruby, 93 bytes

```
*r=p a=1;a+=1while[a]-[0].product(*r.map{|w|[0]+(0..a).map{|e|w**e}}).map(&:sum)==[]||r<<p(a)

```

Try it online!
> 1 votes

# Answer
# Perl 5, 119 bytes

```
while(){map{$o=$_;my$s;map{$s+=$o%$m?$_**($o%$m-1):0;$s-$t||next;$o/=$m}@s}0..($m=2+log(++$t)/.69)**@s;push@s,$t;say$t}

```

Try it online!

Dog slow. *Try it online* found 1, 2, 6, 12, 25, 85, 194 within its 60 second timeout. Same code found 85 within 0.7 seconds on my laptop, 194 within 8 seconds and 590 took 14 minutes.
> 1 votes

# Answer
# 05AB1E, 28 bytes

```
2Lλ∞λ©K.Δ®sÝδm0δšÅ»â}θ€˜Oyå≠

```

Outputs the infinite sequence.

Should have been 27 bytes, but a regular reduce-by `.»â}` instead of 'keep last after cumulative reduce-by' `Å»â}θ` doesn't work for some reason.. :/

Try it online.

**Explanation:**

```
  λ            # Start a recursive environment,
               # to generate the infinite sequence
2L             # Starting with a(0)=1 and a(1)=2
               # Where every next a(n) is calculated as:
   ∞           #  Push an infinite positive list [1,2,3,...]
    λ          #  Push a list of all previous terms [a(0),a(1),...,a(n-1)]
     ©         #  Store it in variable `®` (without popping)
      K        #  Remove those values from the infinite list
   .Δ          #  Then find the first value which is truthy for:
     ®         #   Push the list of previous terms `®`
      s        #   Swap so the current value is at the top
       Ý       #   Pop and push a list in the range [0,value]
        δ      #   Apply double-vectorized:
         m     #    Exponentiation
           δ   #   Map over each inner list:
          0 š  #    Prepend a 0
     Å»        #   Cumulative right-reduce by:
       â       #    Cartesian product of both list to create pairs
      }θ       #   After the cumulative right-reduce, leave the final result
        €˜     #   Flatten each inner list
          O    #   Sum each inner list
           yå≠ #   Check that the current value is NOT in this list of sums
               #   (after which the result is output implicitly)

```
> 1 votes

---
Tags: code-golf, number, sequence
---


title: Tips for King of the Hill bots

text:
# Question
Title: Tips for King of the Hill bots
What general tips do you have for creating a bot to participate in a King of the Hill challenge? What strategies do you use to go from considering the challenge to creating your bot? What data structures do you find most useful?

Please post one tip per answer.

# Answer
> 6 votes
## Finding Nash Equilibria

This is a very important concept when the KOTH involves a relatively simple set of decisions, involves only a few players (typically 2), and is deterministic. A Nash equilibrium describes a "gridlock" position: if the two players have decided upon their two strategies, then the two players are effectively locked in those positions: either player changing their strategy simply creates additional vulnerabilities.

Examples of games where Nash equilibria are important are:

* Rock-Paper-Scissors(-Lizard-Spock), in which an "unbeatable" strategy is random play
* Morra, which has a "spectrum" of equilibria. Peter Taylor wrote a good example in his answer here.
* Prisoner's Dilemma, a cooperative game notable for having an "everybody loses" gridlock

**How to find an equilibrium**

Finding an equilibrium actually is actually pretty simple for most simple games, and is often pretty intuitive. A *ton* of detail about the various methods can be found on the internet. The basic concept, which is normally applicable, is to create a list of possible strategies that the two players can use (the options provided by the game). If one strategy is "dominated" by another, then that strategy can be removed from the list, and the process is repeated. By "domination," I mean that if strategy A always gives an equal-or-better result than strategy B, against all of the remaining opponent strategies, then strategy B can be removed from the list.

**Example: Rock-Paper-Scissors**

RPS has something called a "mixed" equilibrium, meaning that a *distribution* is involved. Rather than playing the same move repeatedly (which will lead to quick defeat), the equilibrium is to play 1/3 rock, 1/3 paper, and 1/3 scissors in a random distribution. If I play randomly, there is nothing my opponent can do to get an edge on me, period. If my opponent chooses not to play randomly, then that only creates a vulnerability on his part.

Games with mixed equilibrium are probably the most common on PPCG, since they can take many forms (the *only* interesting game I can think of with a pure equilibrium is prisoner's dilemma). I should note that the mixed equilibrium doesn't have to be *uniformly random*, simply something other than playing the same move every time.

**Using this information**

The Nash equilibrium of a game often represents the "baseline" from which you should try to operate. In RPS, playing randomly guarantees a finishing spot around the middle of the pack. In order to move to the top, you have to start identifying other player's weaknesses.

To do this, you should stick to the equilibrium when unsure of the opponent's weaknesses. Once those weaknesses have been identified (you have detected that your opponent is not in equilibrium), then you need to gently shift out of equilibrium to take advantage of your opponent. This action, in turn, creates weaknesses on your own part. You must then detect when your opponent is changing his strategy, so that you can then stop the attack and resume random play.

**Detecting variation from equilibrium**

This is pretty difficult, and I am not an expert. Variations can come in many forms:

* Favoring some options above/below others for no reason, like an RPS player that plays rock twice as often as scissors, or one that avoids playing paper. Some relatively simple statistics can detect this.
* Basing a current move off past moves, in some predictable pattern. This includes copy-cats, "beats what beats your last move" bots, or "cycling" bots. This takes additional logic to detect, since the overall move distribution can be evenly-distributed, even though the moves aren't random. You should attempt to take the record of moves and find correlations like "the move I made 2 turns ago and the move my opponent made now" and "the move he made 1 turn ago, and the move he made now", etc.
* Bots whose move distribution is based off of yours. The vulnerability in these bots is often not created (in a measurable quantity) until *after* you have yourself varied from a random distribution. Generally, your own bot falls into this category.

# Answer
> 5 votes
# Use a meta strategy

For almost every clever strategy there's another strategy that beats it: For example, your opponent might use exactly the same reasoning as you to anticipate your next move and then counteract it. Now you might try to second-guess your opponent again, but it's hard to know when to stop.

Another problem is that a strategy that is good at second-guessing a clever opponent might be far from optimal against more simple opponents.

How can you solve this? You let your bot decide on the fly which strategy to use!

For this, you start off with giving your bot a repertoire of different strategies. Then, before each move, your bot looks at the recorded history of the game so far and evaluates how these different strategies would have fared. It then pics the one that would have been most successful.

Including strategies that are strong in the first place will help to give your bot good options to choose from. But you should also include really simple ones, because they often work better against dumb opponents.

You might consider to put a bias on some strategies, either to avoid overfitting (e.g. trying to beat a pattern where the opponent just acts randomly) or to favor certain strategies in the beginning when there isn't yet much information.

Of course, this approach will only work for certain kinds of king-of-the-hill challenges. It did really well for me in a Rock-Paper-Scissors-Lizard-Spock match. In other games it can be almost impossible to evaluate how a certain strategy would have fared if it was not actually played.

An extreme form of this meta approach (that borders on cheating) would be to include the known behavior of all other bots into your own bot, such that it can perfectly anticipate their moves.

# Answer
> 3 votes
# Be specific about the requirements to run your bot

Bots can be written in a variety of languages (and versions of those languages), so it helps everyone out when you:

1. Test it in the environment the OP specifies (or as close to it as you can).
2. Test it in a variety of other environments if possible (to help others who want to run it).
3. Be specific about the language and version you use, and explain how to run your bot.

As a bonus: if you are using a lesser known language, make a link to where people can download the binary/source to run it.

# Answer
> 2 votes
# If team based, work together with your team

While you can usually write a bot that works solo to complete tasks to help your team, there's a much greater advantage when you coordinate both in and out of the game. A prime example of this can be seen in Red vs. Blue - Pixel Team Battlebots.

During development, teams were able to chat and discuss how to coordinate their bots to function better than alone. While technically the same bot, SphiNotPi3000 was written to work in tandem with another of itself, and was able to move in ways that accounted for the weaknesses it would have faced if it were on its own. The end result was that they were able to almost completely dominate the battlefield, even when it was just the two of them against the entire other team.

So outside the game, plan and coordinate with your teammates on what strategies to cover. Maybe someone has a bot that scans the map diagonally? Have yours scan horizontally (just an example). Inside the game, if the challenge allows for team communication, take advantage of it. In the battlebots game for example, you could send a message to your teammates on the position of bots outside their field of vision, and then encourage them to write their bots in a compatible way to make use of those signals.

# Answer
> 0 votes
# Add Randomness (if allowed)

Making your bot move somewhat randomly, especially if there are multiple options that seem to be equally good, makes it far harder to predict the behavior of the bots. In some challenges, it's even worth having a probability of making a suboptimal move if other bots are designed to take the optimal move, as it makes it less likely you end up doing the same thing, which is a disadvantage in many challenges.

As a bonus, if hardcoding behavior to go after a specific bot or calculating what moves they will make is allowed, randomness makes it significantly more likely you can put up a fight against them.

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


title: Golf the prime numbers in Shue

text:
# Question
Title: Golf the prime numbers in Shue
I'd like to introduce a new? programming language I call Shue (Simplified Thue). It has very simple syntax.

Here is a program that checks if an input is divisible by three:

```
yes
no
3=0
4=1
5=2
6=0
7=1
8=2
9=0
00=0
01=1
02=2
10=1
11=2
12=0
20=2
21=0
22=1
0=yes
1=no
2=no

```

Try it online!

At the top we can see two lines. These are the output strings, "yes" and "no".

Next are the replacement rules. Let's look at `3=0`. This means that whenever we see a `3` we can replace it by `0` (but not the other way round). `12=0` means that the string `12` can be replaced with the string `0`.

Then these replacements are performed non-deterministically on the input string until we reach an output state.

For example, if we have the input `14253`, it can be reduced to an output state like so:

```
14253
11253 - 4=1
11223 - 5=2
2223  - 11=2
2220  - 3=0
210   - 22=1
00    - 21=0
0     - 00=0
yes   - 0=yes

```

Here the answer is `yes`, and it's pretty easy to prove that `yes` is the only output state reachable using these rules and this input. This means that the program is well-defined. A program is well-defined if there is at most one output state reachable for every input.

That's it! There are basically no other rules or syntax. There is no way to restrict where or when a substring is replaced (as long as it's possible it will happen). There are no special characters or patterns that match the start or end of the string. Shue is Turing-complete, but only capable of having a finite output set. If the syntax or execution of a Shue program is not completely clear, there are more formal and more precise rules later.

Here are some possibly useful example programs:

### Recognize the string "a"\*x+"b"\*x

```
yes
no
=|
a|b=|
|=yes
=L
=R
a|R=|R
L|b=L|
a|R=no
L|b=no
ba=#
#a=#
#b=#
a#=#
b#=#
#=no

```

Try it online!

### Semi-recognize the string "a"\*x+"b"\*y+"c"\*(x+y)

```
yes
=|
=!
a|=|b
b!c=!
|!=yes

```

Try it online!

### Recognize the string "a"\*x+"b"\*y+"c"\*(x+y)

```
yes
no
=|
=!
a|=|b
b!c=!
|!=yes
b!=!B
BB=B
|!c=C|!
CC=C
C|!=no
|!B=no
ba=#
ca=#
cb=#
#a=#
#b=#
#c=#
a#=#
b#=#
c#=#
#=no

```

Try it online!

### Semi-recognize the string "a"\*x+"b"\*x+"c"\*x

```
yes
=|
=!
a|b=|>
>b=b>
>!c=!
|!=yes

```

Try it online!

## Exact definition of Shue

The source code is interpreted as a list of bytes. The only characters with special meaning are the newline, the equals sign and the backslash. `\n` corresponds to a literal newline, `\=` to a literal equals sign and `\\` to a literal backslash. Any other use of `\` is an error. Every line must contain 0 or 1 unescaped equals signs.

Or in other words, to be syntactically valid, the program has to match the following regex: `/([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?(\n([^\n=\\]|\\=|\\n|\\\\)*(=([^\n=\\]|\\=|\\n|\\\\)*)?)*/`

Here is the mathematical definition of a Shue program:

A Shue program is a set of terminator strings \\$T\_e\\$, and a set of transformation rules \\$T\_r\\$, which are pairs of strings.

The execution of a Shue program on a input string \\$i\\$ is defined as follows. Let \\$U\\$ be the minimal set, so that \\$i\in U\\$ and \\$\forall a,x,y,b: axb \in U \land (x,y) \in T\_r \rightarrow ayb \in U\\$. Let \\$S=U\cap T\_e\\$.

If \\$S=\\{x\\}\\$, then the program will terminate, and \\$x\\$ will be printed to stdout.

If \\$S=\emptyset\\$ and \\$|U|=\aleph\_0\\$, then the program will enter an infinite loop.

In all other cases, the behavior is undefined (yes, Shue isn't memory safe).

## A compiler

Speaking of not being memory safe, here is the Optimizing Shue Transpiler (osht) version 0.0.2. This is a python program that transpiles a Shue program to C. I wouldn't recommend reading the source code (it even contains some debug prints). But the binaries produced are faster than the interpreter, and *seem* to work just fine with most inputs.

## The actual challenge

Your task is to make a program that checks if a unary input (string matching regex /1\*/) is prime in this programming language. That is, is the length of the input string a prime. You must have two output states, one for yes and the other one for no. Shortest code wins.

## Test cases (You can use other strings for yes and no)

```
"" -> "no"
"1" -> "no"
"11" -> "yes"
"111" -> "yes"
"1111" -> "no"
"11111" -> "yes"

```

# Answer
> 13 votes
# Shue, ~~533~~ ~~218~~ ~~208~~ 204 bytes

My original solution was very Turing machine-esque, so here is an improved solution. Unfortunately this solution is difficult to simulate as it's very highly nondeterministic, so there is no TIO link available.

The semi-Thue outputs and productions appear with comments below. Byte count is exclusive of comments.

```
// [x] is the count of character x.
// Output states: (> prime, (} not prime.
(>
(}
// Start.
=[
=)
// Special cases: 0, 1 not prime.
[)=(}
[1)=(}
// 1. L->R: [a] := [1] - 1.
[1=(1B
B1=a1B
// Move as right of 1s.
a1=1a
// 2. Start of a loop where [a] decreases,
//    and we have checked all divisors between [1] - 1
//    and [a] + 1.
// Prime exit: succeed if [a] == 1.
aB)=>
1>=>
// 3. Begin to check [a].
//     R->L: [b] := x, 0 <= x < [a]; change ) to ] at right if x = 0.
aB)=Cab)
aB)=Da]
aC=Cab
aC=Da
aD=Da
// Move as right of bs.
ab=ba
// 4. R->L: We add [1] ds and y cs, where 0 <= y <= [1] - 1.
// The cs are allowed to move freely to the right, and add one b
// when they pass right of an a; they may vanish at the right end.
// Also, ds move right of 1s, and ds and bs may annihilate each other.
// Overall, the effect is that there is an invariant
// I := [b] - [d] + sum_{each c present} [a to the right of the c]
//    = x + y [a] - [1].
1D=Ed1
1E=Ecd1
1E=Ed1
cd=dc
c1=1c
ca=abc
cb=bc
c]=]
c)=)
d1=1d
db=
// 5. L->R: Move right without passing bs, cs and ds.
// We can only reach the right end if I = 0, i.e., [1] = x + y [a].
(E=(F
F1=1F
Fa=aF
// 6. Composite exit: If ] is at the right, then x = 0, so [1] = y [a] is composite.
F]=}
a}=}
1}=}
// 7. If there is ) at the right, then [1] = x + y [a] with 0 < x < [a],
//    so [1] is not divisible by [a].  Decrement [a] and return to step 2.
Fa)=B)

```

# Answer
> 3 votes
# 136 bytes

```
P!
C!
=C!
1=C!
=P
11=nq!
qn=nq
rn=nr
r1=1r
1n=r
n1=r
P=P;
;1=1;
;n=.
.n=n.
.r=1.
.q=q.
.!=q!
;r=n,
,q=nq,
,r=r,
,!=!
Pq=P
P1=C
Cq=C
C1=C

```

### Explanation

It implements this primality-testing algorithm (for \\$x\ge 2\\$):

```
def isprime(x):
    # r+s+1 is the current divisor (starts at x-1 and counts down)
    # q and r are the quotient and remainder of the division
    # n is the unprocessed part of x
    n, q, r, s = 1, 1, 0, x-2
    while True:
        assert (r + s + 1) * q + r + n == x
        if n and s:  # (1) decrement n, increment remainder
            n, r, s = n-1, r+1, s-1
        elif n:      # (2) clear remainder, increment quotient
            n, q, r, s = n-1, q+1, 0, r
        elif r:      # (3) decrement divisor
            n, r = q+1, r-1
        else:        # prime iff the first divisor was 1
            return s == 0

```

The values of \\$n\\$, \\$q\\$, \\$r\\$, \\$s\\$ are stored as the number of `n`, `q`, `r`, `1` \[sic\] characters in the string.

`=C!`, `1=C!`, `=P`, `11=nq!` are scary angelic nondeterminism rules that handle the 0 and 1 special cases, and convert a longer string like `11111` to `P111nq!`. See below for a proof that they do nothing else.

`qn=nq`, `rn=nr`, `r1=1r` bubble sort the variables into the order `[1n]rq`.

`1n=r`, `n1=r` implement transition (1).

`P=P;`, `;1=1;` start a left-to-right update pass that will implement transition (2) or (3).

`;n=.`, `.n=n.`, `.r=1.`, `.q=q.`, `.!=q!` implement transition (2).

`;r=n,`, `,q=nq,`, `,r=r,`, `,!=!` implement transition (3).

`Pq=P`, `P1=C`, `Cq=C`, `C1=C` run when \\$n=r=0\\$, and turn the string into `C!` if it contains any `1`s and `P!` otherwise.

### "Proof" that it works

There is a clear path from any input to the correct final state. I've verified that it works in a simulator if you always apply the earliest applicable rule at the leftmost position, except that the first four rules are handled specially and `P=P;` is moved to just above `Pq=P` and chosen only if there is a `n` or `r` in the string.

Proving that there is no path to the incorrect final state is harder, but I'll attempt it and handwave some parts.

The first four rules: All other rules conserve the number of `PC` and `!` characters, so unless the first or second rule is used exactly once, or the third and fourth rules once each, the string will never evolve to either of the two terminal states. There are no rules that can delete all the characters left of `P` or `C` or right of `!`, so if `C!` is added here, it must be the whole string, and if `P` and `!` are added they must be at the ends.

The final four rules: All other rules keep all `q`s to the right of all `r`s and `1`s, so if `Pq=P` matches, there must be only `q` and `n` and punctuation to the right of it. If there are any `n`s, it will get stuck, so `Pq=P` can only lead to a final state if \\$n=r=s=0\\$ after any ongoing updates complete, i.e., if the number is prime. The other three teardown rules delete the only `P`, which halts updates. So they can't violate the invariants of the main algorithm while it's still running; they can stop it early, but they'll just get stuck unless \\$n=r=0\\$.

The middle rules: It's tricky to define invariants that are preserved by each individual rule while there are arbitrarily many rolling updates in progress, but the updates as a whole preserve the invariants of the primality-testing algorithm. These rules seem safe and well behaved to me compared to the first and last four which violate the invariants, so I'm going to handwave it and say they're fine.

---

### An interesting no-go result that I found while writing this

**Theorem:** A Shue program that solves this challenge can't be a POSIX-compliant text file.

**Proof:** POSIX requires nonempty text files to end with a newline. Per the Shue spec, that means that ϵ is a valid output state. It is also a valid input state which must be judged composite, so ϵ must mean composite. `1` must also be judged composite, so there must be a path by which `1` evolves into ϵ. Therefore, there is a path by which any unary input evolves into ϵ.

So my program contains no final newline not merely to save bytes, but because it would be incorrect otherwise.

---
Tags: code-golf, decision-problem, primes
---


title: The Binary Eyes

text:
# Question
Title: The Binary Eyes
A binary eye is an odd set of digits, with all of its digits except the center one set to 1 or 0, and the center one set to the opposite of the others. Thus, there are two binary eyes for a given odd number of digits:

| x | eyes |
| --- | --- |
| 1 | 1,0 |
| 3 | 101,010 |
| 5 | 11011,00100 |
| 7 | 1110111,0001000 |
| 9 | 111101111,000010000 |

Make the smallest program possible, in any language, that prints out x number of binary eyes. For example, with an input of two, the program would output
1,0 and 101,010.
With 3 it should output that and the next, and with 4 the next as well, and so on. with 5 it should output the complete table above. You can also have it just continue giving outputs, as long as it outputs only correct outputs, and at least the number of outputs asked for.

# Answer
> 7 votes
# Python 3, 45 bytes

```
n=1
while[print(f'{0:1^{n}},{1:0^{n}}')]:n+=2

```

Try it online!

# Answer
> 6 votes
# Python, 48 bytes

```
s,t="01"
while[print(s,t)]:s,t=f"1{s}1",f"0{t}0"
```

Attempt This Online!

-5 thanks to @loopy walt

---

# JavaScript (V8), 42 bytes

```
for([s,t]='01';!print(s,t);t=0+t+0)s=1+s+1

```

Try it online!

-9 bytes using the same trick loopy walt suggested for the Python answer.

# Answer
> 6 votes
# Haskell, 31 bytes

```
g[0]
g x=x:map(0^)x:g(1:x++[1])

```

Try it online!

Infinite sequence

# Answer
> 3 votes
# Jelly, 6 bytes

```
ṬŒḄ¬Ƭ)

```

Try it online!

Add another byte if the pairs can't be backwards.

# Answer
> 3 votes
# Vyxal `M`, 6 bytes

```
ƛÞǔ∞₍†

```

Try it Online!

```
ƛÞǔḂḢJ:†"
ƛ        # Map implicit input (implicit range, flag M means inclusive zero range)
 Þǔ      # Untruth
   ∞     # Palindromise
    ₍†   # Parallel wrap apply with vectorised NOT

```

# Answer
> 3 votes
# Factor \+ `combinators.extras`, 69 bytes

```
"0""1"[ 2dup ","glue print "1""1"rot "0""0"[ surround ] 3bi@ t ] loop

```

Try it online!

## Explanation

Outputs increasing binary eyes forever. In older versions of Factor (such as the build on TIO), whitespace is not required after strings.

##### The combinators

* `[ ... t ] loop` Do `...` forever.
* `3bi@` Apply a quotation to two sets of three things.

```
"0""1"             ! "0" "1"
2dup               ! "0" "1" "0" "1"
"," glue           ! "0" "1" "0,1"
print              ! "0" "1"         (output w/ newline)
"1""1"             ! "0" "1" "1" "1"
rot                ! "0" "1" "1" "1"
"0""0"             ! "0" "1" "1" "1" "0" "0"
[ surround ] 3bi@  ! "101" "010"
                                     (and so forth...)

```

# Answer
> 3 votes
# x86-64 machine code, 32 bytes

```
31 D2 B8 31 34 01 AA 34 01 89 D1 F3 AA F6 DC 78 F3 C6 07 0A AE 7B F0 FF C2 39 F2 75 EA 88 0F C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string, and takes the input number in ESI.

In assembly:

```
f:  xor edx, edx    # Set EDX to 0.
    .byte 0xB8, 0x31# These bytes combine with the next two instructions to form
            #  mov eax, 0xAA013431. In particular, the lowest byte (AL) is 0x31 ('1')
            #  and the second-lowest byte (AH) is 0x34, which is positive.
a:  xor al, 1       # Change AL from '0' to '1' or vice versa.
    stosb           # Write AL to the string, advancing the pointer.
b:  xor al, 1       # Change AL from '0' to '1' or vice versa.
    mov ecx, edx    # Set ECX to EDX.
    rep stosb       # Write AL to the string that many times, advancing the pointer.
    neg ah          # Negate the value of AH.
    js a            # Jump if it is negative (every other time).
    mov BYTE PTR [rdi], 10  # Put 10 (line feed) at the current output address.
    scasb           # Set flags based on AL minus that value, advancing the pointer.
    jpo b           # Jump if that has an odd number of 1 bits,
                    #  true if AL is '0' and not if AL is '1'.
    inc edx         # Add 1 to EDX.
    cmp edx, esi    # Compare that with the input number.
    jne b           # Jump if they are not equal.
    mov [rdi], cl   # Put the low byte of ECX, which is 0
                    #  (REP STOSB counts it down to 0), at the current output address.
    ret             # Return.

```

# Answer
> 2 votes
# Retina 0.8.2, 32 bytes

```
.+
$*
1
$`0$`¶$`0$`¶
T`10`d`¶.+¶

```

Try it online! Explanation:

```
.+
$*

```

Convert `n` to unary using the Retina 0.8.2 default character of `1`.

```
1
$`0$`¶$`0$`¶

```

Create all of the prefixes of `n` `1`s, and wrap `0` with them, duplicating each time.

```
T`10`d`¶.+¶

```

Switch the `1`s and `0`s over in alternate duplicates.

# Answer
> 2 votes
# Charcoal, 13 bytes

```
ＥＮＥ²⪫Ｅ²⭆ι¬λＩλ

```

Try it online! Link is to verbose version of code. Explanation:

```
 Ｎ              First input as a number
Ｅ               Map over implicit range
   ²            Literal integer `2`
  Ｅ             Map over implicit range
      ²         Literal integer `2`
     Ｅ          Map over implicit range
        ι       Outer index
       ⭆        Map over implicit range and join
          λ     Inner index
         ¬      Logical Not
    ⪫           Joined by
            λ   Inner index
           Ｉ    Cast to string
                Implicitly print

```

# Answer
> 2 votes
# PARI/GP, 51 bytes

```
i=!o=0;while(!print(o","i),o=Str(1o,1);i=Str(0i,0))
```

Attempt This Online!

---

# PARI/GP, 57 bytes

```
for(i=0,oo,printf("%o,%0"j=2*i+1"o\n",(8^j-1)/7-k=8^i,k))
```

Attempt This Online!

I don't understand why `printf` doesn't support binary.

# Answer
> 2 votes
# Perl 5 \+ `-M5.10.0`, 30 bytes

Outputs infinitely ignoring input.

```
$,.=0while$}.=say"$}0$} $,1$,"
```

Try it online!

## Explanation

Uses a `while` loop where the condition appends the result of calling `say` (which is `1`) to `$}` which will always be truthy and the body appends `0` to `$,`.

# Answer
> 1 votes
## Batch, 111 bytes

```
@set/ai=1,o=0
@for /l %%i in (1,1,%1)do @call:c
@exit/b
:c
@echo %i%
@echo %o%
@set i=0%i%0
@set o=1%o%1

```

Unfortunately string substitution fails for unset (i.e. empty) strings, otherwise the following would work for 108 bytes:

```
@set s=
@for /l %%i in (1,1,%1)do @call:c
@exit/b
:c
@echo %s%1%s%
@echo %s:0=1%0%s:0=1%
@set s=0%s%

```

# Answer
> 1 votes
# Bash, 50 bytes

```
s=0;t=1;while echo $s $t;do t=0${t}0;s=1${s}1;done

```

Try it online!

# Answer
> 1 votes
# , 56 bytes

```
a=0
b=1
`[`=paste0
repeat{cat(a,b,"")
a=1[a,1]
b=0[b,0]}

```

Try it online!

Takes no input and outputs binary eyes separated by spaces.

# Answer
> 1 votes
# Haskell, 64 bytes

```
flip take$[1]:[0]:(drop 2$[0]#[1]);x#y=x:y:(1:x++[1])#(0:y++[0])

```

Try it online!

# Answer
> 1 votes
# V (vim), 20 bytes

```
i1,0ÀñÙé0wé0lá1Á1ñd

```

Try it online!

Hexdump:

```
00000000: 6931 2c30 1bc3 80fe 58c3 b1c3 99c3 a930  i1,0....X......0
00000010: 77c3 a930 6cc3 a131 c381 31c3 b164 c3bf  w..0l..1..1..d..
00000020: c3                                       .

```

Explanation:

```
i1,0                   " Insert the text '1,0'
    <esc>              " Return to normal mode
         Àñ            " Arg times...
           Ù           "   Duplicate a line downwards
            é0         "   Prepend a '0'
              w        "   Move forward one word
               é0      "   Append a '0'
                 l     "   Move one character right
                  á1   "   Append a '1'
                    Á1 "   Append a '1' to the end of this line
                       " (implicitly end the loop)

```

This does one loop too many, but that seems to be allowed by the rules. To fix that, add `ñd` to the end (`ñ` is "explicitly end the loop" and `d` is "delete one line").

An infinite version saves one byte:

```
i1,0<esc>ÒÙé0wé0lá1Á1

```

# Answer
> 1 votes
# Common Lisp, 65 bytes

```
(do((i 1(+ 2 i)))(())(format t"~v,,,'1:@<0~> ~v,,,'0:@<1~> "i i))

```

Try it online!

**Explanation**

Infinite loop, does not read input. It works by centering a 0 (resp. a 1) using the `~:@<...~>` directive in a field of size `2i + 1`, where the padding character is a 1 (resp. a 0).

# Answer
> 0 votes
# C (GCC), 90 bytes

```
n;main(b,i){for(;++n;)for(b=2;--b+1;putchar(b?44:10))for(i=n;i>1-n;)putchar(48|--i!=0^b);}
```

Attempt This Online!

# Answer
> 0 votes
# Burlesque, 23 bytes

```
q1j{0+]0[+}jC!ClJm{)n!}

```

Try it online!

```
q1        # Block containing 1
j         # Reorder stack
{0+]0[+}  # Surround with 0s ({1} -> {0 1 0})
jC!       # Put user input as argument for continue many
Cl        # Collect results
Jm{)n!}   # Duplicate and create `not`ed copy

```

# Answer
> 0 votes
# Ruby, 42 bytes

```
a="0,1";loop{puts a;a[?,]="1,0";a=?1+a+?0}

```

Try it online!

# Answer
> 0 votes
# 05AB1E, 8 bytes

```
0L[=εN.ø

```

Outputs indefinitely.

Try it online.

**Explanation:**

```
0L        # Push list [1,0]
  [       # Start an infinite loop:
   =      #  Print the current pair with trailing newline (without popping)
    ε     #  Map over both values:
     N    #   Push the current (0-based) map-index
      .ø  #   Surround the value with this index as leading/trailing item

```

# Answer
> 0 votes
# MATLAB, 48 bytes

```
function b(n),1,o=0,for i=3:2:n,o=[1 o 1],~o,end

```

prints to command window. start off with a hard-coded 0 and 1, storing o as 0. Then in a for loop, loop through every 2 integers from 3 to input n (if n is 1, the loop is skipped) and add ones to either end of o, using a comma instead of a semicolon so the output is put to the command window. At the same time, this becomes the new value of o. Taking the logical not operator to o inverts the zeroes and ones.

Try it online!

# Answer
> 0 votes
# sed, 40

```
:x
s/^$/1/p
h
y/10/01/
p
x
s/.*/0&0/p
bx

```

Try it online!

# Answer
> 0 votes
# Brainfuck, 116 bytes

```
++++++++++[->+>+++++<<]>>->,[->[->+<<<.>>]<<-.+>>>[-<+<<.>>>]<<<-----.++++>>[->+<<<.>>]<<+.->>>[-<+<<.>>>]<+<<+<.>>]

```

Try it online!

Explanation:

```
memory map: unused;nl;character;loop_count;digit_counter;digit_counter_copy
++++++++++[->+>+++++<<]>>- create newline and set character to "1"
>,             read loop_count
[-             loop loop_count times
 >+            increase digit counter
 @ [->+<<<.>>] print the "1"s and move digit_counter to digit_counter_copy
 @ <<-.        set character to "0" and print
 @ +           set character to "1"
 @ >>>         go to digit counter_copy
 @ [-<+<<.>>>] print "1"s and move digit_counter_copy to digit_counter
 <<<-----.     set character to "," and print
 ++++          set character to "0"
 >>            go to digit counter

               now follows copy of previous block denoted by @
               it is just slightly modified to ouput oposite eye
 @ [->+<<<.>>] print the "0"s and move digit_counter to digit_counter_copy
 @ <<+.        set character to "1" and print
 @ -           set character to "0"
 @ >>>         go to digit counter_copy
 @ [-<+<<.>>>] print "0"s and move digit_counter_copy to digit_counter
 <<<+          set character back to "1"
 <.            print newline
 >>            got back to loop_count
]

```

---
Tags: code-golf, sequence, binary
---