title: Reverse busy beaver problem

text:
# Question
Title: Reverse busy beaver problem
In this challenge, Turing machines operate on a zero-initialized binary tape that is infinite in both directions.

You are given an integer \\$N\\$, where \\$1 \le N \le 20000\\$. Your program has to output a Turing machine that takes exactly \\$N\\$ steps to halt, including the final step. Alternatively, you can write a program that outputs all 20000 machines.

Your program should complete within 2 hours for all 20000 inputs, when tested on my computer (AMD Ryzen 2600 12-thread CPU). If your program solves all test cases on the same thread, sequentially and independently, your program's running time is divided by 4.

Your score is the total number of states in all 20000 outputs of your program. The lowest-scoring program wins.

## Output

Below is described the (recommended) output format for a *single* test case.

In the first line, output a number \\$M\\$, the number of states of the machine. In the next \\$M\\$ lines, output the transitions from the states, in order from the first to the last, if the cell under the pointer is zero. In the next \\$M\\$ lines, output the corresponding transitions, if the cell under the pointer is one.

The output format for transitions is **`movement newval newstate`**, where **`movement`** stands for either `L` \- move left, `R` \- move right, `S` \- do not move, or `H` \- halt, **`newval`** is the new value of the cell under the pointer (it can be equal to the original one), and **`newstate`** is an integer from \\$1\\$ to \\$M\\$, the state the machine will be in in the next step.

Python 3 checker that inputs in the format described above and outputs the number of steps the Turing machine takes to halt. If you use a different output format, please include a link to a program that can be used to simulate your Turing machines (it's likely a good idea to simply modify my checker).

# Answer
> 10 votes
# Python 3, ~~275,467~~ 255,540 states

*Thanks @mypronounismonicareinstate for suggesting to add \\$I\\$ into the \\$B \rightarrow C\\$ loop, which ultimately saves about \\$20k\\$ states.*

```
def print_machine(states):
 print(len(states[0]))
 for i in 0,1:
  for s in states[i]:
   # if s is None (state unused), puts dummy value in there
   move, new_val, new_state = s or ["H", 0, 0]
   print(move, new_val, new_state+1)

# simple machine that uses ceil(step/2) states
# used for small cases
def generate_simple_machine(steps):
 n_states = (steps+1)//2
 # states[cur_char][state_id]
 states = [[], []]
 for i in range(n_states):
  states[0].append(["S", 1, i])
  states[1].append(["S", 0, i+1])
 states[1][-1][0] = "H"
 if steps%2==1: states[0][-1][0] = "H"
 return states

BASE_STEPS = [(1<<i+2)-i-3 for i in range(20)]
BASE_STEPS[0] = -999

def generate_counter_machine(steps, do_print=True):
 # how many bits/states needed?
 for n_bits, max_steps in enumerate(BASE_STEPS):
  if max_steps > steps:
   break
 n_bits -= 1
 n_states = n_bits + 2
 extra = steps - BASE_STEPS[n_bits]
 if extra >= (1 << (n_bits+1)):
  n_states += 1

 # if small number of steps, use simple machine
 n_states_simple = (steps+1)//2
 if not do_print:
  return min(n_states_simple, n_states)
 if n_states >= n_states_simple :
  states = generate_simple_machine(steps)
  print_machine(states)
  return n_states_simple

 # states[cur_char][state_id]
 # use 0 indexed state
 states = [[None]*n_states, [None]*n_states]

 # state indices
 I_STATE  = 0
 B_STATE  = 1
 E_STATE  = n_states - 1
 C_STATES = [i+2 for i in range(n_bits)]

 # initial state
 states[0][I_STATE] = ["R", 1, C_STATES[0]]
 states[1][I_STATE] = ["H", 0, 0]  # not used initially

 # go back state
 states[0][B_STATE] = ["L", 0, B_STATE]
 states[1][B_STATE] = ["R", 1, C_STATES[0]]

 # ith-digit check states
 for i in C_STATES:
  states[0][i] = ["L", 1, B_STATE]
  states[1][i] = ["R", 0, i+1]
 states[1][C_STATES[-1]][0] = "H"

 # dealing with extras
 # first, figure out how many half-state
 # goes between B_1 -> C1_x
 t = 1<<n_bits
 q1 = t - 1
 q2 = q1 + t
 q3 = q2 + t
 if  extra < q1:
  extra_state = I_STATE
 elif extra < q2:
  # connect B_1 -> I_0 -> C1_?
  states[1][B_STATE] = ["S", 0, I_STATE]
  extra -= q1
  extra_state = I_STATE
 elif extra < q3:
  # connect B_1 -> I_0 -> I_1 -> C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["R", 1, C_STATES[0]]
  extra -= q2
  extra_state = E_STATE
 else:
  # connect B_1 -> I_0 -> I_1 -> E_0 -> C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["S", 0, E_STATE]
  states[0][E_STATE] = ["R", 1, C_STATES[0]]
  extra -= q3
  extra_state = E_STATE

 # then put a half-state between Cx_0 -> B
 # if needed
 if extra > 0:
  states[1][extra_state] = ["L", 1, B_STATE]
  for i in reversed(C_STATES):
   if extra%2==1:
    states[0][i] = ["S", 1, extra_state]
   extra //= 2
 print_machine(states)
 return n_states

```

Try it online! or Verify all machines from 1 to 20k

### Big idea

We want to construct a Turing machine that has a large time complexity compared to the number of states. In this answer, I used a binary counter to count all integers with \\$n\\$ bits, which has a time complexity of \\$O(2^n)\\$. The binary counter was chosen because it is very simple to construct, easy to scale, and flexible enough to add any small number of steps.

### Binary counter

Let's say we want to count all integers with 4 bits. The tape layout will be as follows:

```
1 x x x x
e.g.
1 0 0 0 0
1 1 0 0 0
....
1 0 1 1 1
1 1 1 1 1

```

where the left most 1 is used to mark the start of the number, and `xxxx` is the current number in binary, in reverse order (the least significant bit first). We start with `10000`, and end with `11111`.

At each cycle, we increase the number by 1 as follows:

* Find the left most 0. E.g.

```
1 1 1 0 1
      ^

```
* Set that digit to 1, and all previous digits to 0. The previous example becomes `1 0 0 1 1`.

We then repeat these steps until the tape is `1 1 1 1 1`.

### Binary counter Turing machine

The counter machine for \\$b\\$-bit integers will have \\$b+2\\$ states: the initial state \\$I\\$, \\$b\\$ digit check states \\$C\_1\\$ to \\$C\_b\\$, and the "go back" state \\$B\\$:

* The initial state \\$I\\$ simply sets the left most cell to 1: `R 1 C1 / x x x`.
* The \\$i^{th}\\$ digit check state \\$C\_i\\$ is only called if all previous digits are 1, and the pointer is currently on the \\$i^{th}\\$ left most digit.

+ If the current digit is 0, then we've found the left most 0. Set the current digit to 1, and enter "go back" state: `L 1 B`.
    + If the current digit is 1, set that digit to 0 and enter the next digit check state: `R 0 C(i+1)`. If this is the last digit check state (\\$C\_b\\$), then halts, since this means the current number is `111..1`.
* "Go back" state \\$B\\$ is called after the number is incremented, to reset the pointer to the unit digit and start a new cycle. This state simply moves left until it sees the 1 that marks the start of the number. It then moves one step right to the unit digit, and calls the first digit check state \\$C\_1\\$: `L 0 B / R 1 C1`.

### Time complexity

With \\$n\\$ states (counting \\$n-2\\$ bit integers), a counter machine runs for \\$2^n-n-1\\$ steps.

```
states  steps
     3      4
     4     11
     5     26
     6     57
     7    120
     8    247
     9    502
    10   1013
    11   2036
    12   4083
    13   8178
    14  16369
    15  32752

```

### Bridging the gap

The above scheme only allows us to generate machines with the exact number of steps in the table above. This means that we are stuck if the number of steps falls in the "gaps" between the above numbers. Thankfully, there is a simple scheme that allow us to add some extra steps to a machine, at the cost of at most 1 state.

For example, from the above table, we know that a counter with 6 states runs for 57 steps, and a machine with 7 states runs for 120 steps. There are 62 numbers in the gap between them (58 to 119). This means that we need to be able to extend a 6-state machine to have 1 to 62 extra steps. (In general, we need a scheme to extend an \\$n\\$-states machine by 1 to \\$2^n-2\\$ steps).

First, some notation: let's \\$S^0\\$ and \\$S^1\\$ be the "half-states" of \\$S\\$, aka \\$S\\$ when the current cell is 0 or 1.

Let's look at how many time each half-state is called in an original 6-state counter machine:

```
                I    B   C1   C2   C3   C4
cur_char = 0    1   11    8    4    2    1
cur_char = 1    0   15    8    4    2    1

```

**Observation 1**

The number of times each digit check half-state is called is always a power of 2. Furthermore, the transition afterward is always \\$C\_i^0 \rightarrow B^x\\$ (refer to the state transition diagram above). This means that we can add an extra half-state in between (aka \\$C\_i^0 \rightarrow X \rightarrow B^x\\$). The extra half-state simply wastes a step before transitioning to \\$B\\$. The number of extra steps gained is equal to the number of times \\$C\_i^0\\$ is called.

By selecting which \\$C\_i^0\\$ are connected to this extra half-state \\$X\\$, we can add **any number of extra steps from 1 to 15** (since \\$15=8+4+2+1\\$), at the cost of 1 extra half-state.

For example, in the modified counter above, \\$C\_1^0\\$ and \\$C\_3^0\\$ transitions through \\$X\\$ before reaching \\$B\\$. Since \\$C\_1^0\\$ is called 8 times and \\$C\_3^0\\$ is called 2 times, \\$X\\$ is called 10 times in total, adding an extra 10 steps to the machine.

**Observation 2**:

Both \\$B^1\\$ and \\$I^0\\$ transitions to state \\$C\_1\\$. Furthermore, both \\$B^1\\$ and \\$I^0\\$ sets the current cell to 1, then moves right. Thus, we can have \\$B^1 \rightarrow I^0 \rightarrow C\_1^x\\$. This gives us an extra 15 steps for free.

Furthermore, for each additional half-state inserted between \\$I^0\\$ and \\$C\_1^x\\$, the machine runs for 16 extra steps. For example, using 2 extra half-state, we can gain \\$15+16+16=47\\$ extra steps.

By combining the 2 observations, we can reach any number of extra steps between 1 and 62 inclusive, using at most 3 extra half-states (1 half-state in observation 1, 2 in observation 2, which gives at most \\$15 + 47 = 62\\$ extra steps).

For example, in the machine above, \\$I^0\\$ and 2 extra half-states are added between \\$B^1\\$ and \\$C\_1^x\\$, adding \\$15+16+16 = 47\\$ extra steps. Another extra half-state is added between the digit checks and \\$B\\$, adding 10 extra steps. In total, this machine has 57 extra steps compared to the base machine.

This process can be generalized to any \\$n\\$-state counter machine.

Note that since \\$I^1\\$ is unused in the base machine, we already start with a free half-state. This means that we only need at most 1 extra state \\$E\\$ (aka 2 half-states \\$E^0\\$ and \\$E^1\\$).

### Code explanation

If you want to take a look at the code, the states are ordered as follow:

* Initial state \\$I\\$
* Go back state \\$B\\$
* Digit check states from \\$C\_1\\$ to \\$C\_b\\$
* Extra state \\$E\\$ (if needed)

# Answer
> 4 votes
# Python 2, ~~265426~~ 255462 states

```
t = 0
for i in range(1, 20001):
 b = bin(i + 3)[2:]
 if i < 5: t += -~i / 2
 else: t += len(b) - (not int(b[1:])) - (not int(b[1]))
print t
print
n = input()
if n < 5:
 m = -~n / 2
 print m
 for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
 for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1
else:
 b = bin(n + 3)[2:]
 e1 = int(b[1:]) and 2
 e2 = int(b[1]) and 3
 m = len(b) - (not e1) - (not e2)
 print m
 for i in range(m):
  if i == e2 - 1:
   if int(b[2]): print "S", 1, 3
   else: print "R", 1, 4
  elif i == e1 - 1: print "L", 0, 1
  elif i:
   if int(b[i - m]): print "S", 0, 2
   else: print "L", 0, 1
  elif int(b[1:3]): print "S", 1, 2
  else: print "R", 1, 1 + max(1, e1)
 for i in range(m):
  if i == m - 1: print "H", 0, 1
  elif i == e2 - 1: print "R", 1, 4
  elif i == e1 - 1:
   if e2: print "S", 0, 3
   else: print "R", 1, 3
  elif i: print "R", 0, i + 2
  else: print "L", 1, 1

```

Try it online! I was trying to come up with a different binary counter that didn't need @SurculoseSputum's initial state, but I then forgot about it, which is why this post is so late. Thanks to his help I was able to remove 9964 states so it's now actually slightly better than his answer. It's based on a basic machine of \\$ m \\$ states that takes \\$ 2 ^ { m + 1 } - 3 \\$ steps. The following states are created:

1. A "go back" state.
2. An optional state that is divided into two half states:
    * An extra half state to drop into state 1 more slowly so that up to \\$ 2 ^ { m - 1 } - 1 \\$ extra steps can be added.
    * An extra half state before the first digit state which adds \\$ 2 ^ { m - 1 } \\$ extra steps.
3. An optional state that is divided into two half states, one or both of which are inserted before the first digit state to add a further \\$ 2 ^ { m - 1 } \\$ or \\$ 2 ^ m \\$ extra steps.
4. A number of bit counter states.

Note: It's technically possible to save a further state for values of the form \\$ 3 \left ( 2 ^ m - 1 \right ) \\$ but as it only saves 11 states I haven't bothered to code this up yet.

# Answer
> 2 votes
# C++, score need testing

```
#include <stdio.h>
#include <thread>
#include <chrono>
#include <random>
#include <bitset>
#include <atomic>
#include <string.h>
#include <map>
// N = space of each buf, D = Amount of threads - 2, TIME = allowed time(ms), W = MaxOut
const int N = 50, D = 16, TIME = 7200 * 999, W=20000;
struct strat {int n, w, m;} mem[D][W+1][N][2];
int res[D][W+1], spl[W+1];
std::atomic_ullong cnt;
volatile bool timeout;

void putStrat(int i, int det=0, int then=-1) { //fprintf (stderr, "%6d%5d%4d%6d\n", i, det, then, spl[i]);
    // printf ()
    if (spl[i] && then<0) { //printf ("(%d=%d+%d)", i, spl[i], i-spl[i]);
        putStrat(spl[i], det, det + res[0][spl[i]]); //fprintf (stderr, "a");
        putStrat(i-spl[i], det + res[0][spl[i]], then); //fprintf (stderr, "b");
        return;
    }
    int n = res[then==-1][i]; //fprintf (stderr, "c");
    strat (*x)[2] = mem[then==-1][i];
    if (n>9999) {
        printf ("Not Found(%d,%d,%d)",i,det,then);
    } else
    for (int i=0; i<n; ++i) {
        int d0 = x[i][0].n<0 ? then : x[i][0].n+det;
        int d1 = x[i][1].n<0 ? then : x[i][1].n+det;
        printf ("[%2d %c %c|%2d %c %c]",
                d0, "01"[x[i][0].w], "LSR"[x[i][0].m],
                d1, "01"[x[i][1].w], "LSR"[x[i][1].m]);
    }
}
int run(strat (*A)[2]) {
    int p = W+4, i=0;
    int cur_state = 0;
    std::bitset<W*2+8> Q;
    for (i=0; ++i<W+1; ) { //fprintf (stderr, "%d %d %d%d%d%d%d%d%d%d\n", cur_state, p, (int)Q[1020], (int)Q[1021], (int)Q[1022], (int)Q[1023], (int)Q[1024], (int)Q[1025], (int)Q[1026], (int)Q[1027], (int)Q[1028]);

        auto& o = A[cur_state][Q[p]];
        cur_state = o.n;
        if (cur_state == -1) break;
        Q[p] = o.w;
        p += o.m-1;
    }
    return i;
}
void fallbackGen(int k, int v) {
    strat A[100][2];
    A[0][0] = {4,1,2};  A[0][1] = {3,1,2};
    A[1][0] = {2,1,0};  A[1][1] = {3,0,2};
    A[2][0] = {-1,0,2}; A[2][1] = {1,1,0};
    A[3][0] = {1,0,0};  A[3][1] = {0,1,2};
    //A[4][0] = {5,1,2};
    //A[5][0] = {6,1,2};
    //A[6][0] = {1,1,2};
    for (int i=4; i<k; ++i) {
        A[i][0] = {i+1, i%2?1:1&(v>>(k-i)/2), 2};
        A[i][1] = {-1,0,2};
    }
    A[k-1][0].n = 1;
    int r = run(A);
    for (int i=3; i<k; ++i) {
        if (r>W) return;
        if (k<res[1][r]) {
            res[1][r] = k;
            memcpy (mem[1][r], A, k*sizeof(*A));
        }
        ++r;
        if (i==3) {
            A[2][0].n = 4;
        } else {
            A[i][1].n = i+1;
        }
    }
    { r+=2;
        if (r>W) return;
        A[k][0] = {-1,0,0};
        A[k][1] = {k-1,0,2};
        ++k;
        if (k<res[0][r]) {
            res[0][r] = k;
            memcpy (mem[0][r], A, k*sizeof(*A));
        }
    }
}
void fallbackGene() {
    mem[0][1][0][0] = {-1,0,0}; res[0][1] = 1;
    mem[0][2][0][0] = {0,1,1}; mem[0][2][0][1] = {-1,0,0}; res[0][2] = 1;
    for (int k=5; k<32; k+=2) {
        for (int v=0; v<std::min(W,1<<(k-1)/2); ++v) {
            fallbackGen(k, v);
        }
    }
}
void f(int d) {
    std::mt19937 R(d);
    for (; !timeout; ++cnt) {
        strat A[N][2];
        static const int Coll[] = {1,2,3,4,4,5,5,5,5,6,6,6,10};
        int n = Coll[(unsigned)R()%13];
        for (int i=0; i<n; ++i) {
            for (int j=0; j<2; ++j) {
                A[i][j].n = (unsigned)R() % n;
                A[i][j].w = (unsigned)R() % 2;
                A[i][j].m = (unsigned)R() % 8 ? (unsigned)R() % 2 * 2 : 1;
            }
        }
        int halt_state = (unsigned)R() % N;
        int halt_bin = (unsigned)R() % 2;
        A[halt_state][halt_bin].n = -1;
        int i = run(A);
        if (i<W+1 && res[d][i]>n) {
            res[d][i] = n;
            memcpy (mem[d][i], A, n * sizeof(*A));
        }
    }
}
int main() {
    freopen ("unBB.txt", "w", stdout);
    memset(res, 1, sizeof(res));
    std::thread A[D];
    A[1] = std::thread(fallbackGene);
    for (int i=2; i<D; ++i) A[i] = std::thread([i](){f(i);});
    std::this_thread::sleep_for(std::chrono::milliseconds(TIME));
    timeout = 1;
    for (int i=1; i<D; ++i) A[i].join();
    printf ("%llu Tries\n", (unsigned long long)cnt);

    int s=0;
    setvbuf (stdout, 0, _IONBF, 0);
    for (int i=1; i<W+1; ++i) {
        int m=0x7fffffff; strat (*x)[2]; //fprintf (stderr, "p");
        for (int j=0; j<D; ++j) {
            if (res[j][i] < m) {
                m = res[j][i];
                x = mem[j][i];
            }
        }//fprintf (stderr, "q");

        if (mem[1][i] != x && m<9999) {
            res[1][i] = m;//fprintf (stderr, "%d", m);
            memcpy (mem[1][i], x, m*sizeof(*x));
        }//fprintf (stderr, "r");
        for (int j=1; j<i; ++j) {
            if (res[0][j] + res[1][i-j] < res[1][i]) {
                res[1][i] = res[0][j] + res[1][i-j];
                spl[i] = j;
            }
        }//fprintf (stderr, "s");
        printf ("%6d %6d ", i, res[1][i], res[0][i]);
        putStrat(i);
        puts("");
    }
    return s;
}

```

Build with blocks that run some steps leaving the tape empty

# Answer
> 2 votes
# Python 2, 75012500 states

```
n = input()
m, l = n / 8, n & 7
print m * 3 + [0, 1, 1, 2, 2, 3, 2, 3][l]
for i in range(m):
 print "L", 1, i * 3 + 2
 print "R", 1, i * 3 + 1
 if l or i + 1 < m:print "R", 0, i * 3 + 4
 else:print "H", 0, i * 3 + 3
if l == 7:
 print "L", 1, m * 3 + 2
 print "R", 1, m * 3 + 1
 print "H", 0, m * 3 + 3
elif l == 6:
 print "L", 1, m * 3 + 2
 print "R", 1, m * 3 + 1
else:
 for i in range(-~l / 2):
   if i * 2 < l - 1: print "S", 1, m * 3 + i + 1
   else: print "H", 1, m * 3 + i + 1
for i in range(m):
 print "R", 1, i * 3 + 2
 print "R", 0, i * 3 + 3
 print "R", 0, i * 3 + 3
if l == 7:
 print "R", 1, m * 3 + 2
 print "R", 0, m * 3 + 3
 print "H", 0, m * 3 + 3
elif l == 6:
 print "R", 1, m * 3 + 2
 print "H", 0, m * 3 + 3
else:
 for i in range(-~l / 2):
   if i * 2 < l - 2: print "S", 0, m * 3 + i + 2
   else: print "H", 0, m * 3 + i + 1

```

Try it online! Uses a six-step two-state busy beaver for `n=6`, then anonther state to clear enough tape in two steps to be able to run the busy beaver again. This handles all numbers whose remainder (modulo 8) is 0, 6 or 7; any remaining steps are handled by some probably suboptimal states.

# Answer
> 2 votes
# C (gcc), Score <sup>~~622410~~</sup> 442766 states

***Now ported from bash to C so it's much faster!*** *(The program constructs all 20,000 Turing machines on TIO in about 10 seconds total.)*

Note that this version of the program always computes all 20,000 Turing machines (saving them in 20,000 separate files). This is handy if you download the program and run it on your own computer. (TIO appears to delete all files as soon as the program halts, so the 20,000 files aren't very useful in that environment.)

It also displays one of the Turing machines on stdout (as determined by an argument you pass to it). This is practical for TIO.

---

***Thanks to Surculose Sputum*** *for pointing out that state `t+3` in the original version was superfluous. Taking it out reduced the total number of states considerably!*

***Other changes:*** *Reduced the base cases from 6 to 4. Fixed a few typos in the documentation, and improved the explanation a bit.*

---

This program is based on a recursive construction: the idea is to construct an \\$n\\$-step Turing machine by taking a previously constructed \\$\frac{n}{2}\\$-step Turing machine and running it twice (except that this is adjusted a bit to take overhead into account).

I like this construction because it's easy to understand.

The program computes the Turing machines for 1 up to 20000, and it writes each Turing machine to a separate file.

It also accepts an argument \\$n,\\$ and displays the \\$n\\$-step Turing machine that was constructed on stdout (the default value for \\$n\\$ is 20000).

The score is correct for the challenge even if you request one of the smaller Turing machines, since, no matter what you pass as an argument, it always computes all 20,000 Turing machines and prints the correct codegolf challenge score for all 20,000 machines total.

If you run this on your own computer, run it in a directory by itself, because it will create files T1, T2, T3, ..., T20000 in the directory it's run in (one for each Turing machine).

```
/**********

INTRODUCTION

For each n from 1 to 20000, this program computes a Turing
machine Tn which takes exactly n steps when it runs.

The program writes all the computed Turing machines to
files T1, T2, T3, ..., T20000.

The total number of states for all 20000 machines is then
displayed.  (This is the score for the codegolf challenge.)

Also, one argument n is accepted on the command line; if provided,
it must be a number between 1 and 20000.  Turing machine Tn is
displayed on stdout.

If no argument is provided, the default is 20000.

Note that all 20000 machines are always computed and written
to the files on disk, but only the one you specify is written
to stdout.

Total time taken is about 10 seconds on TIO.

**********/

/**************

HOW TO COMPILE AND RUN

Save this file as tm.c, and compile it with the command

gcc -O3 -o tm tm.c

or, if you prefer,

gcc -O3 -Wall -Werror -W -o tm tm.c

Run it with a command like

./tm

or

./tm 50

This will display the Turing machine requested (T20000 or T50, in
the two examples above).

But you can look at all 20000 Turing machines in any case, since
they're all saved in files T1, T2, T3, ..., T20000.

(On TIO, the system will delete the saved files as soon as the
program finishes running, so they're not very useful in that
environment.)

**************/

/***************

FUNDAMENTAL IDEA

The idea is to compute a Turing machine which takes n steps to
run, by doing something as close as possible to the following:

Recursively take a machine that takes about n/2 steps to halt,
and run it twice.  (The base case for the recursion will be
n <= 4.)

This needs to be adjusted slightly because there are 3 steps
needed for overhead, so we need to use a machine that takes
(n-3)/2 steps to halt, instead of n/2 steps.

Also, if n is even, this leaves us one step short, so we
need to add an extra step in that case.

Since the challenge is to compute a machine for each n up to
20,000, there's no need to implement this using recursion in
the code.  Instead we just run through a loop, computing a
Turing machine for each n in turn.  But each computation
uses the previous results, just as the recursion suggests.

***************/

/***************

PROPERTIES OF THE CONSTRUCTED TURING MACHINES

These Turing machines never move to the left of position 0
  (the starting position of the tape head).

If the all the cells from the starting position to the right
  are initially 0, then Tn will take exactly n steps to run.

Each Turing machine leaves everything exactly as it found it
  (tape cell data and tape head position).

Output format:
  The program will write Turing machine Tn to a file called Tn
     (where n is replaced by the actual number).

During execution, the Turing machine Tn is divided into 3 separate pieces:
     The array element stateCountArray[n]  holds the number of states.
     The file An holds tuples in the form   movement newval newstate  for when
         the tape head is looking at a 0.
     The file Bn holds tuples in the form   movement newval newstate  for when
         the tape head is looking at a 1.

     An and Bn have one tuple for each state, in order from
         state 1 to the number of states.

The eventual machine Tn will consist of stateCountArray[n], An, and Bn, in that order.

***************/

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#define MAXn (20000)

int stateCountArray[MAXn + 1];
char filenameTemplate[] = "X99999";
int score = 0;

void openTupleFiles(int n, FILE **file0, FILE **file, char *fileMode);
void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1);

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file);
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.
**********/

void basis(void);

void invalidArgument(void);

int getNumericalArgument(int argc, char **argv);

void openTupleFiles(int n, FILE **file0, FILE **file1, char *fileMode)
/**********
Given n, opens the two files An and Bn, and returns them in the file
descriptors file1 and file2.  The two files are opened in the indicated
mode: "r", "w", ....
**********/
   {
    sprintf(filenameTemplate, "A%d", n);
    *file0 = fopen(filenameTemplate, fileMode);
    *filenameTemplate = 'B';
    *file1 = fopen(filenameTemplate, fileMode);
   }

void createOnePrecomputedTuringMachine(int n, int numberOfStates, char *tuplesFor0, char *tuplesFor1)
/**********
Used by the function basis.

Sets up stateCountArray[n], An, and Bn as specified,
and updates score.
**********/
   {
    FILE *theFile;

    stateCountArray[n] = numberOfStates;

    sprintf(filenameTemplate, "A%d", n);
    theFile = fopen(filenameTemplate, "w");
    fputs(tuplesFor0, theFile);
    fclose(theFile);

    sprintf(filenameTemplate, "B%d", n);
    theFile = fopen(filenameTemplate, "w");
    fputs(tuplesFor1, theFile);
    fclose(theFile);

    score += numberOfStates;
   } // createOnePrecomputedTuringMachine

void adjustStates(int firstUnusedState, FILE *oldFile, FILE *file)
/**********
The routine adjustStates takes a previously computed Turing
machine and makes the changes necessary to incorporate it into the
Turing machine currently being computed.

oldFile should already be open for reading, and file should be open for writing.

Reads tuples from oldFile, writes tuples to file.

All states are shifted up by 1.

Each halting state is changed to a tuple which moves left and changes the state
to firstUnusedState.
**********/
   {
    char movement;
    int newValue;
    int newState;

    while (3 == fscanf(oldFile, "%c%d%d%*c", &movement, &newValue, &newState))
       {
        if ('H' == movement)
          {
           movement = 'L';
           newState = firstUnusedState;
          }
        else
          newState++;

        fprintf(file, "%c %d %d\n", movement, newValue, newState);
       } // while
   } // void adjustStates

void basis(void)
/**********
This handles values of n from 1 through 4, which form the basis of the recursion.

These Turing machines are precomputed.
**********/
   {
    createOnePrecomputedTuringMachine(1, 1, "H 0 1\n", "H 0 1\n");
    createOnePrecomputedTuringMachine(2, 1, "S 1 1\n", "H 0 1\n");
    createOnePrecomputedTuringMachine(3, 2, "S 1 1\nH 0 1\n", "S 1 2\nH 0 1\n");
    createOnePrecomputedTuringMachine(4, 2, "S 1 1\nS 1 2\n", "S 0 2\nH 0 1\n");
   } // basis

void invalidArgument(void)
   {
    printf("Usage: tm\n   or: tm n\nwhere n is a number between 1 and 20000\n(default is 20000).\n");
    exit(1);
   }

int getNumericalArgument(int argc, char **argv)
   {
    char * arg;
    char *p;
    int k = 0;

    if (argc < 2)
      return 20000;

    if (argc > 2)
      invalidArgument();

    arg = argv[1];

    if (0 == *arg)
      return 20000;

    for (p = arg; *p; p++)
      {
       if ((*p < '0') || ('9' < *p))
         invalidArgument();

       k = 10 * k + *p - '0';

       if (k > 20000)
         invalidArgument();
      }

     return k;
    }

#define BUFFERSIZE (4096)

int main(int argc, char **argv)
   {
    int n;
    int m;
    FILE *An;
    FILE *Bn;
    int t;
    FILE *Am;
    FILE *Bm;

    FILE *TuringMachineFile;
    char byteArray[BUFFERSIZE];
    int numberOfBytesRead;
    int argument;

    if (argc > 2)
      invalidArgument();

    argument = getNumericalArgument(argc, argv);

// For each values of n, we compute stateCountArray[n] and the two files An and Bn.

// First take care of the basis, n = 1 through 4.
    basis();

// Now start the main loop for n = 5 and up:
    for (n = 5; n <= MAXn; n++)
       {

// We'll go through 2 runs of the machine Tm that we
// computed earlier, where m = floor((n-3)/2).

// There are 3 steps of overhead, and we add in one
// extra step if n happens to be even, because in that
// case, 2 * floor((n-3)/2) + 3 is n-1, not n.
// This will get us to exactly n steps.

        m = (n - 3)/2;

// Open files An and Bn for writing.
        openTupleFiles(n, &An, &Bn, "w");

// Go through two runs of machine Tm.
// The cell at position 0 will keeep track of which run
// we're on (0 for the first run, 1 for the second).

// At the beginning, position 0 holds a 0, so we
// move right to position 1 and go to state 2.
        fputs("R 0 2\n", An);

// For even n, at the end of the entire run of Tn, we'll
// find ourselves back in state 1 at position 0, but the
// contents of that cell will be 0, and we'll halt.
// (For odd n, the machine will halt without going back
// to state 1.)
        fputs("H 0 1\n", Bn);

// Compute the number of states in the new machine Tn.
// It's two more than the number if states in Tm.
        t = stateCountArray[m] + 2;

// Open files Am and Bm for reading.
        openTupleFiles(m, &Am, &Bm, "r");

// The two calls below to the function adjustStates copy machine Tm
// into the Turing machine that we're building, with the following
// modifications:
//   - Use states 2 through t+1 instead of 1 through t.
//   - Halt tuples (H) get altered to tuples that don't halt
//       but instead move left (L) and change to state t+2.

        adjustStates(t, Am, An);
        fclose(Am);

        adjustStates(t, Bm, Bn);
        fclose(Bm);

// Since we're in state 2 at position 1, we're all set to run
// the altered copy of Tm, so that happens next.

// After running the altered copy of Tm, we're back at position 0,
// since the original Tm would have left us at position 1, but the
// altered version changed every H to an L, causing the tape head
// to move left one position, to position 0.

// If the tape head is looking at 0 in position 0,
// we just finished the first of the two runs of Tm.
// In that case, write a 1 to position 0 to indicate
// that we're on the second run now.
// Move right to position 1 and change to state 2.
// That will start the second run of Tm.

        fputs("R 1 2\n", An);
        fclose(An);

// If the tape head is looking at a 1 in position 0,
// we just finished our second run of Tm.  We're ready
// to halt, except that if n is even, we need to add
// one extra step.
        if (n % 2)
          {  // n is odd, so halt.
           fputs("H 0 1\n", Bn);
          }
        else
          { // n is even, so change to state 1 (which
            // will take the extra step we need).
            // State 1 will then halt because it's
            // looking at a 1.
           fputs("S 1 1\n", Bn);
          }

        fclose(Bn);

// Store the number of states for Tn in stateCountArray,
// and update the score..
        stateCountArray[n] = t;
        score += t;
       } // for n

// Print the codegolf challenge score (the total number of
// states in all 20000 Turing machines).

    printf("Score (up to 20000) = %d\n\n", score);

// Write each Turing machine Tn to the file called Tn (where
// n is the actual number).
// First write stateCountArray[n], then copy file An, and
// after that copy file Bn.

// Also delete the files An and Bn.

    for (n = 1; n <= MAXn; n++)
       {
        openTupleFiles(n, &An, &Bn, "r");

        sprintf(filenameTemplate, "T%d", n);
        TuringMachineFile = fopen(filenameTemplate, "w");

        fprintf(TuringMachineFile, "%d\n", stateCountArray[n]);

        numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, An);
        fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
        fclose(An);

        numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, Bn);
        fwrite(byteArray, sizeof(char), numberOfBytesRead, TuringMachineFile);
        fclose(Bn);

        fclose(TuringMachineFile);

        *filenameTemplate = 'A';
         unlink(filenameTemplate);

        *filenameTemplate = 'B';
        unlink(filenameTemplate);
       } // for n

// Finally print the requested Turing machine to stdout.

    (void) printf("Turing machine which halts after exactly %d steps:\n", argument);
    sprintf(filenameTemplate, "T%d", argument);
    TuringMachineFile = fopen(filenameTemplate, "r");
    numberOfBytesRead = fread(byteArray, sizeof(char), BUFFERSIZE, TuringMachineFile);
    fwrite(byteArray, sizeof(char), numberOfBytesRead, stdout);
    fclose(TuringMachineFile);

    exit(0);
   } // main

```

Try it online!

# Answer
> 1 votes
# Python 2, 100010000 states

```
n = input()
m = -~n / 2
print m
for i in range(m): print "S" if i * 2 < n - 1 else "H", 1, i + 1
for i in range(m): print "S" if i * 2 < n - 2 else "H", 0, -~i % m + 1

```

Try it online! Just to get the ball rolling.

---
Tags: code-challenge, metagolf
---


title: Solve a separable differential equation

text:
# Question
Title: Solve a separable differential equation
A first order separable ordinary differential equation is (arguably) the easiest type of differential equation to solve, and takes the form of

$$N(y)\frac{dy}{dx} = M(x) \\ y(x\_0) = y\_0$$

For two given functions \\$N(y)\\$ and \\$M(x)\\$ and an initial condition \\$y(x\_0) = y\_0\\$.

Your task is to take \\$N(y)\\$, \\$M(x)\\$, \\$x\_0\\$ and \\$y\_0\\$ and output the solution to that differential equation.

## How to solve a separable differential equation

The differential equation

$$N(y)\frac{dy}{dx} = M(x)$$

can be solved through the following method:

$$ \begin{align} N(y)\frac{dy}{dx} & = M(x) \\ \int{N(y)\frac{dy}{dx}dx} & = \int{M(x)dx} \\ \int{N(y)dy} & = \int{M(x)dx} \end{align} $$

Once the integrals have been calculated, we can remove one of the constants of integration, leaving the equation

$$f(y) = g(x) + c$$

where

$$ f(y) = \int{N(y)dy} \\ g(x) = \int{M(x)dx} $$

After this, \\$c\\$ can be calculated by applying the initial condition:

$$ c = f(y\_0) - g(x\_0) $$

and a final solution for \\$f(y)\\$ can be given.

## Challenge

You are to take in four inputs:

* The function \\$N(y)\\$
* The function \\$M(x)\\$
* \\$x\_0\\$
* \\$y\_0\\$

Both \\$x\_0\\$ and \\$y\_0\\$ can be any real number, and can be taken as input in many reasonable manner (i.e. a list, tuple, two integers etc.). The functions, in order to avoid having to focus on parsing mathematical input, will be limited to a type of Laurent polynomials \- i.e polynomials in the form

$$ p(x) = \alpha \cdot x^n + \beta \cdot x^{n-1} + \dots + \gamma + \delta \cdot x^{-2} + \epsilon \cdot x^{-3} + \dots + \zeta \cdot x^{-m+1} + \eta \cdot x^{-m} \\ \alpha, \beta, \dots, \eta \in \mathbb{R}, \\:\\: n, m \in \mathbb{N} $$

Notice that we'll never have \\$x^{-1}\\$ in the polynomial, and that because of this, the integrals will always be Laurent polynomials of the same form (with \\$x^{-1}\\$ included *after* integrating).

With inputs in this format, there are multiple ways you could represent them for input. As with the mapping, any reasonable representation is acceptable, and if you aren't sure, ask. However, here are some that are definitely allowed (for the example \\$p(x) = 3x^2 + x + 6 - 2x^{-2} + 7x^{-5}\\$):

* Nested list: `[[3, 2], [1, 1], [6, 0], [-2, -2], [7, -5]]`
* A pair of lists of coefficients: `[3, 1, 6] and [0, -2, 0, 0, 7]`
* A string representation: `"3x^2 + x + 6 - 2x^-2 + 7x^-5"`
* etc.

Given these four inputs, you are to output the solution to the differential equation they represent.

In order to avoid having to algebraically manipulate your solutions to get into the form \\$y(x) = ...\\$, you can output *two* Laurent polynomials, in the same form as the input; one representing \\$y\\$ and the other \\$x\\$.

This is so the shortest code in bytes wins!

## Test cases

Both the MathJax and text-based inputs will be included for each example, where the text based will use the nested list input format above. In addition, I will walk through the first example for clarity.

```
In:
  N = [[1, -2]]
  M = [[6, 1]]
  1 -> 1/25 = 0.04
Out:
  y = [[-1, -1]]
  x = [[3, 2], [28, 0]]

```

$$ \begin{align} \frac{1}{y^2}\frac{dy}{dx} & = 6x \\ y(1) & = \frac{1}{25} = 0.04 \\ \\ \int{N(y)dy} & = \int{M(x)dx} \\ \int{\frac{1}{y^2}dy} & = \int{6xdx} \\ -\frac{1}{y} & = 3x^2 + c \\ -25 & = c + 3 \implies c = -28 \\ -\frac{1}{y} & = 3x^2 - 28 \end{align} $$

```
In:
  N = [[2, 1], [-4, 0]]
  M = [[3, 2], [4, 1], [-4, 0]]
  1 -> 3
Out:
  y = [[1, 2], [-4, 1]]
  x = [[1, 3], [2, 2], [-4, 1], [-2, 0]]

```

$$ N(y) = 2y - 4, \\:\\: M(x) = 3x^2 + 4x - 4 \\ y(1) = 3 \\ \\:\\ y^2 - 4y = x^3 + 2x^2 - 4x + c \\ c = -2 \\ y^2 - 4y = x^3 + 2x^2 - 4x - 2 \\ $$

```
In:
  N = [[1, 0]]
  M = [[3, 2], [2, 0]]
  0 -> 0
Out:
  y = [[1, 1]]
  x = [[1, 3], [2, 1]]

```

$$ N(y) = 1, \\:\\: M(x) = 3x^2 + 2 \\ y(0) = 0 \\ \\:\\ y = x^3 + 2x + c \\ c = 0 \\ y = x^3 + 2x \\ $$

# Answer
# Python 2, ~~123~~ 122 bytes

```
def f(p,P):R=[[[a/-~b,b+1]for a,b in F]for F in P];a,b=map(lambda F,x:sum(a*x**b for a,b in F),R,p);R[1]+=[a-b,0],;print R

```

Try it online!

Straight-forward implementation. A function that takes arguments in the form `(y, x), (N, M)`, and prints the resulting 2 polynomials to `STDOUT`.
> 8 votes

# Answer
# SageMath, <sup>~~60~~ ~~59~~</sup> 58 bytes

Saved a byte thanks to Dingus!!!

```
lambda N,M,b:desolve(diff(y,x)*N-M,y,b)
y=function('y')(x)

```

Try it online!

Inputs two functions \\$N(y)\\$ and \\$M(x)\\$ and a boundary condition \\$\[x\_0,y\_0\]\\$ and returns the solution to the differential equation \\$N(y)\frac{dy}{dx}=M(x)\\$ where \\$y(x\_0)=y\_0\\$.
> 5 votes

# Answer
# Wolfram Language (Mathematica), 33 bytes

```
DSolve[{y'@x#==#2,y@#3==#4},y,x]&

```

Try it online!

Tool for the job, and all that. Uses Mathematica's builtin `DSolve`. The TIO link shows the input and output formats (a warning message is issued for the second case, but the solution is correct). This builtin does automatically solve for \\$y\\$ in terms of \\$x\\$.
> 4 votes

# Answer
# Maxima, 50 bytes

```
f(N,M,a,b):=ic1(ode2(N*'diff(y,x)=M,y,x),x=a,y=b);

```

Try it online!

Takes maths-like expressions as input, e.g. `3*x^2+4*x-4`. Outputs a quaint formatted ASCII string!
> 3 votes

# Answer
# JavaScript (ES6), 114 bytes

Just a port of @SurculoseSputum's answer.

Takes input as `([y, x])([N, M])`.

```
p=>P=>(R=P.map(p=>p.map(([a,b])=>[a/++b,b])))[1].push([(g=i=>R[i].reduce((t,[a,b])=>t+a*p[i]**b,0))(0)-g(1),0])&&R

```

Try it online!
> 1 votes

---
Tags: code-golf, math, calculus
---


title: Make true and false global!

text:
# Question
Title: Make true and false global!
We all know `true` and `false`, but what do speakers around the globe say?

```
+----------------------+------------+------------+
| **Language**             | **True**       | **False**      |
+----------------------+------------+------------+
| Arabic               | sahih      | zaif       |
| Armenian             | irakan     | kelc       |
| Assamese             | asol       | misa       |
| Breton               | gwir       | gaou       |
| Bulgarian            | veren      | neveren    |
| Catalan              | veritable  | fals       |
| Cornish              | gwir       | gaw        |
| Czech                | pravdivy   | nepravdivy |
| Danish               | sand       | falsk      |
| Dutch                | waar       | onwaar     |
| English              | true       | false      |
| Esperanto            | vera       | malvera    |
| Finnish              | tosi       | epatosi    |
| French               | vrai       | faux       |
| Galician, Portuguese | verdadeiro | falso      |
| Georgian             | namdvili   | cru        |
| German               | wahr       | falsch     |
| Greek                | alithis    | psevdis    |
| Hebrew               | hiyuvi     | shikri     |
| Hindi, Urdu          | thik       | jhutha     |
| Hungarian            | igaz       | hamis      |
| Icelandic            | sannur     | rangur     |
| Indonesian, Malay    | benar      | salah      |
| Irish                | fior       | breagach   |
| Italian              | vero       | falso      |
| Japanese             | shin       | nise       |
| Korean               | cham       | geojit     |
| Latin                | verus      | falsus     |
| Latvian              | patiess    | nepareizs  |
| Mandarin Chinese     | zhen       | jia        |
| Maori                | pono       | pate       |
| Persian              | dorost     | galat      |
| Polish               | prawdziwy  | falszywy   |
| Romanian             | adevarat   | fals       |
| Russian              | vernyj     | falsivyj   |
| Sardinian            | beru       | falsu      |
| Scottish Gaelic      | fior       | breugach   |
| Spanish              | verdadero  | falso      |
| Swedish              | sann       | falskt     |
| Sylheti              | hasa       | misa       |
| Turkish              | dogru      | yanlis     |
| Volapuk              | veratik    | dobik      |
| Welsh                | gwir       | anwir      |
+----------------------+------------+------------+

```

All words ASCIIfied from Wiktionary: true, false. Preference given to first entry under 'A state in Boolean logic that indicates an affirmative or positive result'/'state in Boolean logic that indicates a negative result', then first entry under 'concurring with a given set of facts'/'untrue, not factual, wrong'. I apologise if your favourite language is not included or the word choice for your language is not optimal - go edit Wiktionary!

Write a program or function that takes one word from the table above as input and outputs a consistent truthy value if the word means 'true' and a consistent falsy value otherwise. Your code must produce the correct output for all 79 possible inputs. Shortest code (in bytes) in each language wins.

Sorted list of unique words meaning 'true':

```
adevarat,alithis,asol,benar,beru,cham,dogru,dorost,fior,gwir,hasa,hiyuvi,igaz,irakan,namdvili,patiess,pono,pravdivy,prawdziwy,sahih,sand,sann,sannur,shin,thik,tosi,true,vera,veratik,verdadeiro,verdadero,veren,veritable,vernyj,vero,verus,vrai,waar,wahr,zhen

```

Sorted list of unique words meaning 'false':

```
anwir,breagach,breugach,cru,dobik,epatosi,fals,falsch,false,falsivyj,falsk,falskt,falso,falsu,falsus,falszywy,faux,galat,gaou,gaw,geojit,hamis,jhutha,jia,kelc,malvera,misa,nepareizs,nepravdivy,neveren,nise,onwaar,pate,psevdis,rangur,salah,shikri,yanlis,zaif

```

# Answer
# Python 2, ~~56~~ 48 bytes

thanks to dingledooper for -8 bytes!

```
lambda s:0x420AF14A5F8266>>hash(s)%3317%890%57&1

```

Try it online!

All these answers do the same thing:

1. Convert the string into an unique integer.
2. Makes these integers smaller by repeated modulo operations. These operations are bruteforced to make the numbers as small as possible while not mixing up the two classes.
3. Index into a binary lookup table.

---

# Python 3, ~~59~~ 58 bytes

```
lambda s:0x48A2D06199310566F06>>int(s[:4],36)%542%400%78&1

```

Try it online!

```
lambda s:0x453CCA1066840810431C1>>int(s,36)%2387%1770%86&1

```

Try it online!

```
lambda s:0x42744262AEA01A914800A12C>>int(s,36)%155687%95&1

```

Try it online!

---

# 05AB1E, ~~30~~ ~~29~~ 28 bytes

```
4öŽ3¹%Ƶ™%84%o•1±87÷Ðˆù³Í:•&Ā

```

Try it online!

```
6öŽ9{%521%76%o•B&¦¿³ʒв F6•&Ā

```

Try it online!
> 18 votes

# Answer
# Ruby `-n`, ~~54~~ ~~49~~ 47 bytes

```
p !/^[fgmryz]a|[ncks][erw]|[bjm][hir]|ep|la|te/

```

Try it online! - truthy

Try it online! - falsy

Thanks to Dingus for a byte saved and Value Ink for inspiring another -2.
> 15 votes

# Answer
# Retina, ~~68~~ ~~67~~ ~~60~~ 58 bytes

```
^(n?a[^n]|be|ch|gw|p[or]|sa[hn]|h?[itvw]|zh)|as|ss|in|og?r

```

Try it online!

Regex that matches all truthy values and none of the falsey ones.

Verify all truthy inputs

Verify all falsey inputs
> 13 votes

# Answer
# C (gcc), ~~55~~ 52 bytes

*-3 bytes thanks to @G. Sliepen*

```
f(s){s=0x4240165C085F34>>a64l(s)%19537U%11702%56&1;}

```

Try it online!

The strategy used is the same as in @ovs's answer. We brute-force values corresponding to each string, making sure that no two `truthy` and `falsey` words share the same value. The answer is then extracted from a binary lookup table.

Here, the `a64l()` function converts a given string into a 32-bit signed integer.
> 7 votes

# Answer
# x86-64 machine code, 27 bytes

Hexdump:

```
6b 01 35 c1 e8 06 6b c8 d3 d1 c1 48 ba 4e 88 00
02 c3 45 88 8b 48 d3 e2 1a c0 c3

```

A function which receives a pointer to the string in `rcx`, and returns the result in `al`.

−1 means `true`, and 0 means `false`.

Assembly source code, using `ml64` (MASM) syntax:

```
.CODE
my PROC
    imul eax, dword ptr[rcx], 53
    shr eax, 6
    imul ecx, eax, -45
    rol ecx, 1;
    mov rdx, 8b8845c30200884eh;
    shl rdx, cl;
    sbb al, al;
    ret;
my ENDP
end

```

Disassembly, while stopped on a breakpoint at the start of the function:

```
00007FF73978F4A0 6B 01 35             imul        eax,dword ptr [rcx],35h
00007FF73978F4A3 C1 E8 06             shr         eax,6
00007FF73978F4A6 6B C8 D3             imul        ecx,eax,0FFFFFFD3h
00007FF73978F4A9 D1 C1                rol         ecx,1
00007FF73978F4AB 48 BA 4E 88 00 02 C3 45 88 8B mov         rdx,8B8845C30200884Eh
00007FF73978F4B5 48 D3 E2             shl         rdx,cl
00007FF73978F4B8 1A C0                sbb         al,al
00007FF73978F4BA C3                   ret

```

It uses hashing, like many other answers. The hash function uses the first 4 bytes of the string - by luck, all strings are at least 4 bytes long (including terminating zero byte). It does the following:

* Multiply by 53, ignoring overflow
* Shift right by 6 bits
* Multiply by -45, ignoring overflow
* Rotate left by 1 bit
* Access the 64-bit hash table, using 6 LSB of the result

Found by brute-force search. The search space was 8 + 5 + 8 + 5 = 26 bits. The "rotate left" bit count is 1 by luck, which reduces code size by 1 byte, compared to the general "rotate left" case.
> 7 votes

# Answer
# Brachylog, 70 bytes

```
¬{~ṇ"pate
shik
dob
sal
ham"∧"nezabrcrpsangagenifa"ġ₂;?,"yeojrkm"∋∋~a₀}

```

Try it online!

Takes input through the output variable and outputs through success or failure.
> 4 votes

# Answer
# Charcoal, 41 bytes

```
¬∨⁼θgaw⊙⪪”&⌈→⊖Ｌ↓＆s⦃R⁹ＣV÷⊕O⸿↔Vf‴λ⌕9↶7”²№θι

```

Try it online! Link is to verbose version of code. Output is a Charcoal boolean, i.e. `-` for true, nothing for false. Explanation:

```
   θ                Input string
  ⁼                 Equals
    gaw             Literal string `gaw`
 ∨                  Boolean Or
         ”...”      Compressed string `bibrcrepfagujhjikekrlamaminenwouseteyaza`
        ⪪     ²     Split into substrings of length 2
       ⊙            Where any is nonzero
               №    Count of
                 ι  Current substring in
                θ   Input string
¬                   Boolean Not
                    Implicitly print

```
> 4 votes

# Answer
# JavaScript (ES6),  ~~63 62~~  60 bytes

*Saved 2 bytes thanks to @Neil*

A regular expression that matches all falsy words and none of the truthy ones.

```
s=>!/ao|mi|ob|w$|[gnst]e|[bck]r|[flz]a|^[ejkmry]|nw/.test(s)

```

Try it online!
> 3 votes

# Answer
# 05AB1E, ~~41~~ 39 bytes

```
.•6ðó_ ï²£Ëý¾Sð7§Ê³®6´¡Žmã•2ôåàI…gawQ~≠

```

-2 bytes by using a shorter compressed string from *@Neil*'s Charcoal answer, who apparently uses the exact same approach.

Try it online or verify all test cases.

**Explanation:**

```
.•6ðó_ ï²£Ëý¾Sð7§Ê³®6´¡Žmã•
         # Push compressed string "bibrcrepfagujhjikekrlamaminenwouseteyaza"
  2ô     # Split it into parts of size 2
    å    # Check for each whether it's a substring of the (implicit) input-string
     à   # And check if any is truthy
I        # Push the input again
 …gawQ   # Check that it's equal to string "gaw"
~        # Check if either of the two is truthy by using a bitwise-OR
 ≠       # And invert the boolean (!= 1)
         # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•6ðó_ ï²£Ëý¾Sð7§Ê³®6´¡Žmã•` is `"bibrcrepfagujhjikekrlamaminenwouseteyaza"`.
> 3 votes

# Answer
# Io, 109 bytes

-10 bytes thanks to Neil.

```
method(x,"bi br cr ep fa gu jh ji ke kr la ma mi ne nw ou se te ya za gaw"split select(i,x findSeq(i))size<1)

```

Try it online!

# Io, 119 bytes

Searches for prefixes of existing values.

```
method(x,"dob fa ga ham an br cr e pate ge j k ma mi ne ni on ps sal shik ra ya za"split select(i,x findSeq(i)==0)size)

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~125~~ \\$\cdots\\$ ~~101~~ 95 bytes

Saved a byte thanks to ceilingcat!!!

```
#define f(s)!index(" %&(-.049;ADHJQRSYZis",*s**s*s[l=strlen(s)-1]*s[l-1]%3519%163%108%92+32)
l;

```

Try it online!

Inputs a string and returns \\$1\\$ for words meaning 'true' and \\$0\\$ for words meaning 'false'.

**How?**

The first, second to last, and last characters of all the word strings form a unique triplet of characters across all words. Multiplying the ASCII values of first character squared and the other two together yields unique 32-bit integers across all words. These numbers modulus values found by a Python script yield a distinct set of integers for all 'false' words in the range \\$(0,96)\\$. These numbers can then be transformed back to printable ASCII characters by adding \\$32\\$ to them. Then it's simply a test if a string put through these calculations yields a character that can be found in a given string (also generated by the Python script).
> 2 votes

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


title: Tips for golfing in TikZ

text:
# Question
Title: Tips for golfing in TikZ
TikZ is a Latex package used for drawing precise images in Latex documents. It has a massive specification and a boatload of features that may be useful for style questions.

What tips do people have for golfing in TikZ? As always, tips should be specific to to TikZ (e.g. "Remove comments" is not an answer), and stick to a single tip per answer.

# Answer
# Use `\def`

`\def` is an incredibly powerful tool when it comes to golfing. `\def` allows you to assign something to a variable.

This can be used simply with the to save a number you may use a bunch of times for instance

```
\def\x{1456}

```

Will define `1456` as `\x` for future use much like saving a variable might in a programming language.

However `\def` is much more powerful than that, because `\def` doesn't define a variable it defines a snippet of code to be substituted into the program whenever it is called.

For example say you want to draw some rectangles using `\draw` you might write the following code:

```
\draw(0,0)rectangle(3,4)rectangle(8,0);\draw(2,2)rectangle(3,3);

```

Using `\def` this could be written as:

```
\def\x{)rectangle(}\draw(0,0\x3,4\x8,0);\draw(2,2\x3,3);

```
> 5 votes

# Answer
# Use `\tikz` instead of the `tikzpicture` environment

Instead of creating a `tikzpicture` environment (36 bytes) you can use the `\tikz` command (7 bytes)

Global options can be set in square brackets in using the tikz command as such `\tikz[options...]{...}`. If the tikz code is one line long the curly braces can be omitted saving an additional two bytes.

### Example:

Both of the following programs output the image at the bottom

```
\documentclass{standalone}\input tikz\begin{document}\tikz{\draw[thick,rounded corners=8pt](0,0)--(0,2)--(1,3.25)--(2,2)--(2,0)--(0,2)--(2,2)--(0,0)--(2,0);\draw(-1.5,0)--(0,1.5);}\end{document}

\documentclass{standalone}\input tikz\begin{document}\begin{tikzpicture}\draw[thick,rounded corners=8pt](0,0)--(0,2)--(1,3.25)--(2,2)--(2,0)--(0,2)--(2,2)--(0,0)--(2,0);\draw(-1.5,0)--(0,1.5);\end{tikzpicture}\end{document}

```

*Credit to WheatWizard for figuring the multiline use of `\tikz`*
> 4 votes

# Answer
# Use `\documentclass[tikz]{standalone}`

By chance I found the following in the manual of the `standalone` package:

> For pictures drawn with TikZ a dedicated `tikz` option is provided which loads the `tikz` package and also configures the `tikzpicture` environment to create a single cropped page.

Thus, instead of

```
\documentclass{standalone}\input tikz\begin{document} ...

```

one can write

```
\documentclass[tikz]{standalone}\begin{document} ...

```

to save 5 bytes.
> 4 votes

# Answer
You can sometimes refrain from using co-ordinate `(0,0)` completely.
That's an easy one.
Here's a more intricate one:
`(,)` is the same as `(1,1)`.
Found out that one rather by accident.
Here's a minimal example:

```
\documentclass[tikz,border=9]{standalone}\def~{document}\begin~\tikz{\draw grid(,);}\end~

```

Output:
> 1 votes

---
Tags: code-golf, tips
---


title: Your code has an uncanny mirror twin…

text:
# Question
Title: Your code has an uncanny mirror twin…
Write two programs, each taking a string `s` and a number `n` ≥ 0, such that:

* The first program prints `s` `n` times, separated by newlines.
* The second program prints each character of `s` `n` times, with repeated characters separated by newlines.
* Every character at column `x`, line `y` in one program equals the character at column `y`, line `x` in the other program.

Both programs must contain at least two lines. You may take input in any reasonable order or format that works for both programs.

This is ; the less bytes, the better. Count bytes from your longer program (that is, the one with more lines than columns).

---

Here's an example in a hypothetical programming language, with `s` = `"Hello, world!"` and `n` = `3`:

### Program A

```
a(b*c
defg
h.ij)

```

### Output

```
Hello, world!
Hello, world!
Hello, world!

```

### Program B

```
adh
(e.
bfi
*gj
c )

```

### Output

```
HHH
eee
lll
lll
ooo
,,,

www
ooo
rrr
lll
ddd
!!!

```

# Answer
# C, 196 bytes

**Regular version: 190 bytes**

```
p;f(char *s,n) {
; while( p++<  n)
puts(s);p; }   /*
f*******u*0**;* /
(///////t/)//}+*
c*)dfppnc(;p(w+/
hs{oo=+;h* u"hs}
a, {r0+)a /t"i)/
rn  (;< r *s l;*
/////// /  / e/
******* *  * (*/

```

**Mirrored version: 196 bytes**

```
p;pf(char/*
; u*/*s,n/*
fwt*/){  /*
(hs*/do{ /*
ci(*/for(/*
hls*/p=0;/*
ae)*/p++</*
r(;*/n;)
  putchar/*
*p;+*/(*
s+ 0); /*
,+}*/puts/*
n< */(""
)  ;}while(
   *++s);/*
{n/ */}/* /
 )*/

```

**Readable regular version:**

```
p; f(char* s, n) {
  ;
  while (p++ < n)
    puts(s);
  p;
}

```

**Readable mirrored version:**

```
p; pf(char* s, n) {
  do {
    for (p = 0; p++ < n; )
      putchar (*s + 0);
    puts("");
  } while (*++s);
}

```
> 15 votes

# Answer
# MATL, 11 bytes

Inputs are `s`, then `n`.

**Normal version** (10 bytes):

```
1!X"
XDD
"

```

Try it online!

**Mirrored version** (11 bytes):

```
1X"
!D
XD
"

```

Try it online!

### Explanation

The **normal version** is parsed as

```
1    % Push 1
!    % Transpose: does nothing to the 1
X"   % Implicit inputs: n, s. Repeat s n times vertcally and 1 time horizontally
XD   % Display the full stack contents. This prints the output
D    % Display. Triggers implicit input, which is not present, and so errors
"    % For each. This statement is not reached

```

The **mirrored version** is parsed as

```
1    % Push 1
X"   % Implicit inputs: n, s. Repeat s n times vertcally and 1 time horizontally
!    % Transpose. This transforms the above into the desired output
D    % Display. This prints the output
XD   % Display all stack contents. The stack is empty, so this does nothing
"    % For each. Triggers implicit input, which is not present, and so errors

```
> 13 votes

# Answer
# perl, 102 bytes

```
$_=<>;$n=<>;print$_ x$n
__END__
=E
<N
>D
;_
$_
;
=
<
>
;
s
/
.
/
$
&
x
$
;
.
"
\
n
"
/
g
e
;
p
r
i
n
t

```

Try it online!

```
$_=<>;$;=<>;s/./$&x$;."\n"/ge;print
__END__
=E
<N
>D
;_
$_
n
=
<
>
;
p
r
i
n
t
$
_

x
$
n

```

Try it online!

The programs are fairly trivial, they just do what is required without any trickery. The only trickery is the `__END__`; this tells perl to ignore anything what is following. That way, hardly anything is shared between the two programs, only the first two bytes are: `$_`, where the `_` is either the name of the variable, or the first character of the `__END__` token.
> 9 votes

# Answer
# Charcoal, 20 bytes

```
ＥＮη¿⁰«
Ｎ
η
‖
↙
¿
⁰
«

```

Try it online! Explanation:

```
ＥＮη

```

Convert the input number to an implicit range, map each entry to the input string, and print the result.

```
¿⁰

```

Execute the rest of the program only if `0` is true (which it isn't).

```
«

```

Wrap the rest of the program in a block, so it doesn't matter what its meaning is, since it never gets executed.

Reflected:

```
ＥＮη‖↙¿⁰«
Ｎ
η
¿
⁰
«

```

Try it online! Explanation: Much like the other program, except that the `‖↙` reflects the output as desired.
> 8 votes

# Answer
# 05AB1E (legacy), 6 bytes

-1 byte thanks to @dingledooper.

```
иø
»
q

```

Try it online!

## Explanation (Horizontal)

```
и   Sequence product.
 ø  Transpose this product.
»   Join the product by newlines.
q   Exit the program.

```

## Explanation (transposed)

и   Sequence product.
 »  Join the product by newlines.
  q Exit the program.

A garbage dump the interpreter ignores:
ø
```
</code></pre>
> 8 votes

# Answer
# Python 2, 95 bytes

**First program: 94 bytes**

```
sfp,n=input();"\
,or";s=sfp+"\n"
print s*n;  """
= n
ict
n
pic
un*
t p
(s;
):"
#""
"""
1;
#\

```

Try it online!

**Second program: 95 bytes**

```
s,p=input()#"1#
for c in s:"";\
print c*p;"""
,"n
n;t
=s
i=s
ns*
pfn
up;
t+
("
)\"
;n"
"""
\

```

Try it online!
> 6 votes

# Answer
# Perl 5 \+ `-pF`, 51 bytes

I feel I can condense this more so I'll likely tinker with it to try and make it more square...

```
$_=$_ x<>;'
; f
=xo
<$r
>;@
;.F
$$;
\/}
.|{
=|
$$'

```

Try it online!

### Explanation

Basically this just runs `$_=$_ x <>` which, since `-p` flag is used, will just print out the string triplicated. The rest of the string is avoid by being inside a single quote.

```
$;=<>;$\.=$
_ x$;.$/||$
=for@F;}{'
$
_

x
<
>
;
'

```

Try it online!

### Explanation

This takes `n` from STDIN (`<>`) and stores in `$;`, next the magic variable `$\` (which is automatically output as the final argument to any call to `print`) is appended to with `$;` copies of `$_`. `$_` is set to each letter of the input during the `for@F`. We need to also close the implicit `while (<STDIN>)` loop (that is added via `-p`) with `}{` so that the global `$_` is empty and when `print` is called, only `$\` is output.
> 3 votes

# Answer
# Mathematica, 114 bytes

Mathematica, with it's long, unsplittable names means that no matter how short I make this, it'll still have obtuse names, the alternative of using \<\> and #&/@ would be shorter for either individual program, but dealing with them in the transposition makes the program longer overall.

```
StringRiffle[
t;Table[##],1*
rT;"\n"]&(*  )
ia
nb
gl
Re
i[
f#
f#
l]
e]
[
C,
h"
a\
rn
a"
c,
t"
e"
r]
s&
[(
1*
*)

```

**Normal**

```
StringRiffle[Characters[1*
t;Table[##]],"\n",""]&(*)
rT;
ia"
nb\
gln
Re"
i[]
f#&
f#(
l]*
e,
[1
 *)

```

**Transposed**

### Base programs:

Normal:

StringRiffle\[Table\[##\],"\n"\]&

Transposed:

StringRiffle\[Characters\[Table\[##\]\],"\n",""\]&
> 3 votes

# Answer
# Jelly, 10 bytes

Unfortunately, for this challenge, the execution of a Jelly program starts with the bottom line of code, so there's quite a bit of work required to get a solution under about 25 bytes!

```
W ñ
ẋY
Z
ñ

```

**Try it online!**

```
WẋZñ
 Y
ñ

```

**Transposed**

### How?

Normal:

```
W ñ - Link 1: s, n
W   - wrap (s) in a list
  ñ - call the next Link (2) as a dyad - f(that, n)

ẋY - Link 2: wrapped s, n
ẋ  - repeat (s) (n) times
 Y - join with newlines

Z - Link 3 (unused)

ñ - Main Link: s, n
ñ - call the next Link (1) as a dyad - f(s, n)
  - implicit (smashing) print

```

Transposed:

```
WẋZñ - Link 1: s, n
W    - wrap (s) in a list
 ẋ   - repeat (that) (n) times
  Z  - transpose
   ñ - call the next Link (2) as a dyad - f(that, n)

 Y - Link 2: transposed, repeated [s]
 Y - join with newlines

ñ - Main Link: s, n
ñ - call the next Link (1) as a dyad - f(s, n)
  - implicit (smashing) print

```
> 2 votes

# Answer
# Stax, 6 bytes

```
]
*M
m

```

Run and debug it

**Mirrored:**

```
]*m
 M

```

Run and debug it
> 2 votes

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


title: Base-phi converter time!

text:
# Question
Title: Base-phi converter time!
The Golden Ratio Bureau is obsessed with this new thing they call base-phi. You see it and decide to code-golf, as is your natural instinct.

To be specific, base-phi is a number system like base 10, except it uses the number phi, or the golden ratio, as its base. A ones digit would be x\*10^y, but in base phi 10 is replaced with phi. Base phi also uses 2 digits, 0 and 1.

Your goal is to accept input that is a base 10 positive natural number, then treat it as such and convert it to base phi.

Due to base phi being able to represent all numbers in more than one way, your program should convert input to its "minimal" representation. This is the representation with the least 1 digits. Output can have trailing characters but only if the language must output them with no circumvention.

Do not use any built-ins for base conversion. You may use a built-in for phi, but the base conversion should rely on string manipulation and other mathematical operations.

Your program must support inputs up to 2147483647, or lower, depending on your language's limit for integers.

Your program can deal with any undefined behavior as you wish.

Testing cases for accuracy can be done at this link. In case you do not wish to use the link, here are the numbers 1-15 in base phi.

```
1 = 1
2 = 10.01
3 = 100.01
4 = 101.01
5 = 1000.1001
6 = 1010.0001
7 = 10000.0001
8 = 10001.0001
9 = 10010.0101
10 = 10100.0101
11 = 10101.0101
12 = 100000.101001
13 = 100010.001001
14 = 100100.001001
15 = 100101.001001

```

The shortest program following these rules wins. Have fun.

# Answer
> 9 votes
# Retina, ~~81~~ 80 bytes

```
K`0.
"$+"{+`(1(\.)|(1\.(0?1)*0?)1)(00|$)
${3}0${2}11
0\.
1.
+0`0?1(\.?)1
10${1}0

```

Try it online! Works by repeatedly adding \\$ 1 \\$. Explanation:

```
K`0.

```

Start off with \\$ 0. \\$.

```
"$+"{`

```

Repeat the number of times given by the input.

```
+`(1(\.)|(1\.(0?1)*0?)1)(00|$)
${3}0${2}11

```

If the \\$ \phi^0 \\$ bit is set, use the identity \\$ \phi^0 = \phi^{-1} + \phi^{-2} \\$ to move bits away until there is enough room.

```
0\.
1.

```

Add \\$ 1 \\$.

```
+0`0?1(\.?)1
10${1}0

```

Minimise the number of bits by reversing the above identity.

# Answer
> 4 votes
# dc, <sup>~~107~~ ~~106~~ ~~110~~</sup> 109 bytes

```
[0sD]sZ0ddsRsK?dsXZF*dkdsN-sM[lX5v1dsD+2/lN^dsY>ZlXlDlY*-sXlDdAlN^*lR+sRlKdlN+lD*-sKlN1-dsNlM!>L]dsLxlRlKk1/p

```

Try it online!

Or verify the test suite: the OP's test cases, 2147483647, and a very large Lucas number (over 400 trillion) which comes out neatly in base \\$\varphi\\$ (see screenshot below for that last test case by itself).

*The program should now work for arbitrarily large numbers, restricted only by the memory capacity of the computer.*

**How it works:**

```
[0sD]sZ    Macro Z, sets D to 0 when called.
0ddsRsK    Initialize R and K to 0, leaving 0 on the stack.
?dsX       Input number, store it in X,
ZF*dkdsN       store 15 times its number of decimal digits in N,
               also set that as the number of decimal places for
               computations,
-sM            and store the negative of that in M.
               M and N are bounds on the powers of phi which
               will be needed for the representation.
               Multiplying by 15 is far more than is needed:
                  For M and N, we could have multiplied by just 5,
                  because ln(10)/ln(phi) < 5.
                  We need some additional decimal places in the
                  computations to handle possible round-off errors,
                  so we conservatively multiply by 15.
[          Start a macro (which will be used as a loop).
 lX                 Push X onto the stack.
 5v1dsD+2/lN^       Set D=1.  Compute phi^N,
 dsY                   and store it in Y.
 >Z                 If phi^N > X, use macro Z to set D=0.
 lXlDlY*-sX         If D is 1, set X = X - phi^N.
 lDdAlN^*lR+sR      R += D * 10^N.
                       This places the digit D in R in the right
                       position, treating R as a number in base 10.
 lKdlN+lD*-sK       If D is 1, set K = -N.
                       (K is used as the number of "decimal"
                       places to print.)
 lN1-dsN            Set N = N-1, leaving the new value of N
                       at the top of the stack.
 lM!>L              If M <= N, call macro L recursively (in
                       other words, start another loop iteration).
]          End the macro,
dsL          save it in register L,
x            and execute it.

       Once the loop is done:
lR         Load the result R.
lKk        Set the precision (number of decimal places) to K.
1/         Divide R by 1 to convert it to the desired precision.
p          Print it.

```

# Answer
> 3 votes
# Perl 5, 135 bytes

```
sub f{(0,1,10.01)[$_=pop]||do{$_=f($_-1);$_.=0until/\..{99}/;s/.\./$&+1/e;1while s/.?2../$&+801/e+s,0?11,100,;s,.{99}$,.$&,;/1.*1/;$&}}

```

Try it online!

This function is no speed monster, but it's O(n). `f(1000000)` returns `10100000100010010000100010001.0001000010100101000100000101` in 15 secs on my laptop.

# Answer
> 1 votes
# PHP, 173 bytes

```
$p=.5+sqrt(5)/2;for($i=45,$a=$argn,$f=1;$a>=.01;){$i?:$a*=$f=1e6;$b=$p**$i*$f;if($i--==-1)$n.='.';if((float)number_format($a-$b,3)>=0){$a-=$b;$n.=1;}else$n.=$n?0:'';}echo$n;

```

Try it online!

It was a real pain mostly because of errors in comparisons and subtraction when values get really small, I had to find a way to circumvent them:

```
$p=(1+sqrt(5))/2;                       //ϕ
for($i=45,$a=$argn,$f=1;$a>=.1;){       //no need to go beyond ϕ^45 to go up to 2147483647. $a is the input, $f a factor
  $i?:$a*=$f=1e7;                       //small numbers fix: multiplying $a and factor $f by 1000000 for following test and exit condition to work (also shortens this condition)
  $b=$p**$i*$f;                         //current power of ϕ multiplied by the factor
  if($i--==-1)$n.='.';                  //decrement $i + if we get to power -1 add the dot '.'
  if((float)number_format($a-$b,3)>=0){ //second fix to be right when difference is very small
    $a-=$b;                             //subtract the current power when ok
    $n.=1;                              //adding a '1'
  }else $n.=$n?0:'';                    //or else a '0' (test $n to avoid leading zeroes)
}
echo$n;                                 //et voilà!

```

I think I can golf it more, we'll see later, I'm open to suggestions. Note that my version of 2147483647 is slightly different than what I saw here, but of course it's me who's right. Haven't tried other big values..

EDIT: saved 1 byte thanks to @mathjunkie and lowered the exit threshold to 0.01 for the 111 case as rightly noticed by @MitchellSpector.. no change to the score

EDIT2: changed the factor from 10000000 to 1000000 to handle another case found by @MitchellSpector, I guess I'll have to do automated tests to detect other cases :D

# Answer
> 0 votes
# APL (Dyalog Unicode), 94 bytes

```
{w←{+\∘⌽⍣⍵⊢1 0}¨⍵-⍳k←2×⍵⋄s/⍨(∨\'0'≠s)∧⌽∨\'1'=⌽s←⍵(↑,'.',↓)⊃∘⍕¨⊢/b/⍨(w+.×b←(0∘⍪,1∘⍪)⍣k⍪⍬)≡¨⊂⍵0}

```

Try it online!

Inefficient as hell. Basically, given n as input, generate all bit patterns with n bits above and n bits below the decimal point, symbolically evaluate it as base phi (to the form `a+b*phi`), extract all patterns whose value is `n+0*phi`, pick the one that is lexicographically highest, and then trim unnecessary zeros/decimal point from both ends.

### Ungolfed with comments

```
f←{                    ⍝ Input: ⍵←n
  v←⍵-⍳2×⍵             ⍝ Vector of n-1, n-2, ..., -n
  w←{+\∘⌽⍣⍵⊢1 0}¨v     ⍝ Reduced base-phi values (a+b×phi) of phi^v
    {          }¨v     ⍝ For each value of v,
            1 0        ⍝ Start with 1+0×phi
     +\∘⌽              ⍝ Apply "reverse then cumulative sum"
         ⍣⍵            ⍝ v times (for negative v, inverse of it |v| times)

  b←(0∘⍪,1∘⍪)⍣(2×⍵)⍪⍬  ⍝ Matrix of all possible bit patterns for 2n bits
                   ⍪⍬  ⍝ Empty matrix of 0 row, 1 column
    (0∘⍪,1∘⍪)          ⍝ Apply "horizontally concat the matrix with
                       ⍝   a 0-row prepended with the one with a 1-row"
             ⍣(2×⍵)    ⍝ 2n times

  a←⊢/b/⍨(w+.×b)≡¨⊂⍵0  ⍝ Find target bit pattern
         (w+.×b)       ⍝ Evaluate each bit pattern as base phi
                ≡¨⊂⍵0  ⍝ Compare with n+0×phi
      b/⍨              ⍝ Filter columns of b where ^ is true
    ⊢/                 ⍝ Pick the rightmost one

  s←⍵(↑,'.',↓)⊃∘⍕¨a    ⍝ Convert to string
              ⊃∘⍕¨a    ⍝ Char-ify each digit
    ⍵(↑,'.',↓)         ⍝ Insert decimal point after n chars

  s/⍨(∨\'0'≠s)∧⌽∨\'1'=⌽s  ⍝ Filter away trailing non-ones and leading zeros
               ⌽∨\'1'=⌽s  ⍝ Boolean mask to filter away trailing non-ones
              ∧           ⍝ And
     (∨\'0'≠s)            ⍝ Boolean mask to filter away leading zeros
  s/⍨                     ⍝ Filter s using ^
}

```

---
Tags: code-golf, math, number
---


title: The Double-Castle Numbers™

text:
# Question
Title: The Double-Castle Numbers™
### Introduction

A double-castle number™ is a positive integer number that has a pattern of $$\underbrace{a\cdots a}\_{m\text{ }a\text{s}}b\underbrace{a\cdots a}\_{m\text{ }a\text{s}}b\underbrace{a\cdots a}\_{m\text{ }a\text{s}}\underbrace{a\cdots a}\_{n\text{ }a\text{s}}b\underbrace{a\cdots a}\_{n\text{ }a\text{s}}b\underbrace{a\cdots a}\_{n\text{ }a\text{s}}$$ Where \\$m\>0\\$, \\$n\>0\\$ and \\$a-b=1\\$ are all non-negative integers, when represented in an integer base \\$B\\$ where \\$B\ge2\\$. It is so named because a bar chart representing the base-\\$B\\$ digits of such a number resembles two castles of the same height place- side by side.

For example, \\$7029\\$* is a double-castle number because when represented in base 2 it becomes \\$1101101110101\_2\\$, which can be split into \\$11011011\\$ and \\$10101\\$.

This is the case when \\$m=2\\$, \\$n=1\\$, \\$a=1\\$, \\$b=0\\$ and \\$B=2\\$.

\\$305421994212\\$ is also a double-castle number because when represented in base 8 it becomes \\$4343444344344\_8\\$, which can be split into \\$43434\\$ and \\$44344344\\$.

This is the case when \\$m=1\\$, \\$n=2\\$, \\$a=4\\$, \\$b=3\\$ and \\$B=8\\$.

For \\$a\>=10\\$, \\$a\\$ should be treated as a single base-\\$B\\$ "digit" with the value of \\$a\\$ in base-10. \\$206247763570426655730674346\\$ is a double-castle number in base-16, whose representation in base-16 is \\$\text{AA9AA9AAAAAA9AAAA9AAAA}\_{16}\\$. Here, \\$a=10\\$ but is treated as a single digit \\$(10)\_{16}=\text{A}\_{16}\\$.

This is the case when \\$m=2\\$, \\$n=4\\$, \\$a=10\\$, \\$b=9\\$ and \\$B=16\\$.

### Challenge

Write a program or function that, given integers \\$m\>0\\$, \\$n\>0\\$, \\$1\le a\<B\\$ and \\$B\ge2\\$, calculate the corresponding double-castle number™ and output it in base-10.

### Test Cases

The input below are in base-10, but in the case say when \\$a=11\\$ and \\$B=12\\$ the input should be understood as \\$B\_{12}\\$.

```
m, n, a,  B  => Output
1, 1, 1,  2  => 693
2, 1, 1,  2  => 7029
1, 2, 3,  4  => 62651375
1, 2, 4,  8  => 305421994212
1, 4, 7,  10 => 7676777776777767777
2, 4, 8,  16 => 164983095594247313234036872
2, 4, 10, 16 => 206247763570426655730674346

```

### Winning Condition

This is a code-golf challenge, the shortest submission in each language wins. No standard loopholes allowed.

\*7029 comes from my ID minus it written reversed.

# Answer
> 6 votes
# Python 2, ~~83 81 79~~ 72 bytes

*-9 bytes thanks to @ovs!*
*-2 bytes thanks to @dingledooper!*

```
m,n,a,B=input()
r=0
for s in n,m+n,m,m:r+=B**n;n-=~s
print~-B**n/~-B*a-r

```

Try it online!

Calculate `aaaa...aaa` in base `B`, then subtract 1 at the appropriate digits.

# Answer
> 5 votes
# C (gcc) -lm, ~~83~~ \\$\cdots\\$ ~~81~~ 80 bytes

Saved ~~1~~ 2 bytes thanks to ceilingcat!!!

```
#define P-pow(B,n
f(m,n,a,B){n=-(1 P*3+3*m+4))/~-B*a P)P-~n)P*3+2+m)P*3+3+2*m);}

```

Try it online!

Calculates the wall to full height first and then crenellation is performed through subtraction.

# Answer
> 4 votes
# 05AB1E, ~~10~~ 12 bytes

```
иεÐ)²<.ý}˜sβ

```

Try it online or verify all test cases.

+2 bytes as bugfix for \\$a\geq10\\$ (initial 10-byter answer: `×εÐ¬<ý}Jsö` \- Try it online or verify all test cases).

**Explanation:**

```
и             # Repeat the second (implicit) input the first (implicit) inputs amount of
              # times as list
              #  i.e. [1,2] and 4 → [[4],[4,4]]
 ε            # Map each to:
  Ð           #  Triplicate the value
              #   i.e. STACK: [4,4],[4,4],[4,4]
   )          #  Wrap them into a list
              #   i.e. STACK: [[4,4],[4,4],[4,4]]
    ²<        #  Push the second input - 1
              #   i.e. STACK: [[4,4],[4,4],[4,4]],3
      .ý      #  Intersperse this list with this value
              #   i.e. STACK: [[4,4],3,[4,4],3,[4,4]]
        }˜    # After the map: flatten the list
              #  i.e. [[[4],3,[4],3,[4]],[[4,4],3,[4,4],3,[4,4]]]
              #   → [4,3,4,3,4,4,4,3,4,4,3,4,4]
          s   # Swap to get the third (implicit) input
           β  # Base-convert the list we created to an integer using the input as base
              #  i.e. [4,3,4,3,4,4,4,3,4,4,3,4,4] and 8 → 305421994212
              # (after which the result is output implicitly)

```

# Answer
> 4 votes
# K (ngn/k), 26 bytes

```
{z/,/(2+3*x)#'(x#'y),'y-1}

```

Explanation

```
{z/,/(2+3*x)#'(x#'y),'y-1} / using x=2 1; y=1; z=2 as an example
              (x#'y)       / (m;n) copies of a;     ex: (1 1;1)
                    ,'y-1  / append b=a-1 to each   ex: (1 1 0;1 0)
     (2+3*x)               / length of each sublist ex: (8;5)
            #'             / copy to each length    ex: (1 1 0 1 1 0 1 1; 1 0 1 0 1)
   ,/                      / join                   ex: (1 1 0 1 1 0 1 1 1 0 1 0 1)
 z/                        / convert from base B    ex: 7029

```

Try it online!

# Answer
> 3 votes
# perl -Mbigint -alp, 87 bytes

```
($m,$n,$a,$B)=@F;$o=$o*$B+$_ for(($a)x$m,$a-1)x2,($a)x$m,(($a)x$n,$a-1)x2,($a)x$n;$_=$o

```

Try it online!

We take the input, turn it into a corresponding list of digits, then convert it to base 10. Input is taken as space separated numbers on `STDIN`.

The TIO code does have some header code; this is just there so it works with multiple inputs -- without the header, it will only do the first line correctly. (those header bytes aren't counted).

# Answer
> 3 votes
# Jelly,  ~~12~~  11 bytes

```
‘3×þṬạṖ€Ẏḅ⁵

```

A full program accepting three arguments: `[m,n] a B` which prints the result.

**Try it online!**

### How?

```
‘3×þṬạṖ€Ẏḅ⁵ - Main Link: [m,n]; a
‘           - increment -> [m+1, n+1]
 3          - three
   þ        -   outer product ([1, 2, 3] by [m+1, n+1]) with:
  ×         -     multiplication -> indexes of low points (with an extra low on the
                                     right for each of castle)
    Ṭ       - un-truth (vectorises) -> two lists of 1s and zeros (1s at low points)
     ạ      - absolute difference (with a) -> convert zeros to a and 1s to a-1=b
      Ṗ€    - pop from each -> remove the extra low points)
        Ẏ   - tighten -> from a list of two lists to a flat list
          ⁵ - programs 5th argument = B
         ḅ  - convert dfrom base
            - implicit print

```

# Answer
> 2 votes
# Charcoal, 27 bytes

```
Ｎθ≔⭆Ｅ²Ｎ⪫Ｅ³×0ι1δＩ⁻×Ｎ⍘⭆δ1θ⍘δθ

```

Try it online! Link is to verbose version of code. Takes input in the order `B, m, n, a`. Explanation:

```
Ｎθ

```

Input `B`.

```
≔⭆Ｅ²Ｎ⪫Ｅ³×0ι1δ

```

Input `m` and `n`. For each value, create a string of that many `0`s. Join 3 of those strings with `1`s. Join the final strings together.

```
Ｉ⁻×Ｎ⍘⭆δ1θ⍘δθ

```

Replace all of the characters in the string with `1`s, convert from base `B`, multiply by `a`, then subtract the string converted from base `B`, and output in decimal.

Note that although Charcoal's string based conversion accepts numeric bases higher than 62 this only succeeds when (as here) all the digit values are less than 62.

Slightly shorter solutions are possible that place upper limits on the supported value of `B`:

```
ＮθＩ↨Ｅ⭆Ｅ²Ｎ⪫Ｅ³×ι℅θ℅⊖θ℅ιＮ

```

Try it online! Link is to verbose version of code. Takes input in the order `a, m, n, B`. Works for `B` up to 65536. Works by creating a string of characters whose ordinal is `a` or `b`, then converting back into ordinals and decoding using base `B`. 22 bytes.

```
ＮθＩ⍘⭆Ｅ²Ｎ⪫Ｅ³×ι⍘θφ⍘⊖θφＮ

```

Try it online! Link is to verbose version of code. Takes input in the order `a, m, n, B`. Works for `B` up to 62. Works by creating a string of characters whose base `B` code is `a` or `b`, then decoding using base `B`. 21 bytes.

```
Ｉ⍘⭆Ｅ²Ｎ⪫Ｅ³×ιεＩ⊖εＮ

```

Try it online! Link is to verbose version of code. Takes input in the order `a, m, n, B`. Works for `B` up to 10. Works by creating a string of characters whose value is `a` or `b`, then decoding using base `B`. 16 bytes.

# Answer
> 2 votes
# Husk, ~~12~~ 11 bytes

```
`BṁȯJ←¹R3`R

```

Try it online! Takes arguments in the order `a [m,n] B`.

# Explanation

```
`BṁȯJ←¹R3`R  Implicit arguments a, [m,n], B.
             Say a=3, m=1, n=2, B=4.
  ṁȯ         Map over [m,n] and concatenate:
               Use n=2 as example.
         `R    Repeat a that many times: [3,3]
       R3      Repeat three times: [[3,3],[3,3],[3,3]]
     ←¹        a decremented: 2
    J          Join by it: [3,3,2,3,3,2,3,3]
             Result: [3,2,3,2,3,3,3,2,3,3,2,3,3]
`B           Interpret in base B: 62651375

```

# Answer
> 2 votes
# APL (Dyalog Unicode), 16 bytes

```
⎕⊥⎕-~1\⍨∊5⍴¨⎕,¨0

```

Try it online!

A full program that takes `m n`, `a`, `B` on three lines of stdin.

### How it works

```
⎕⊥⎕-~1\⍨∊5⍴¨⎕,¨0
            ⎕     ⍝ Take (m n) from stdin
             ,¨0  ⍝ Append 0 to each; (m 0)(n 0)
         5⍴¨      ⍝ Repeat each to length 5; (m 0 m 0 m)(n 0 n 0 n)
        ∊  ⍝ Flatten; (m 0 m 0 m n 0 n 0 n)
     1\⍨   ⍝ Expand 1 by above: m/n become m/n copies of 1, 0 becomes single 0
    ~      ⍝ Boolean negate the above
  ⎕-       ⍝ Subtract each from a (taken from stdin)
⎕⊥         ⍝ Convert from base B (taken from stdin) to integer

```

# Answer
> 2 votes
# , 35 bytes

```
{:@[#.((#10$5$0 1-~{.)~[:,5$"1,.&1)

```

Try it online!

# Answer
> 0 votes
# JavaScript, 75 bytes

There may be rounding errors due to JavaScript's integer limit.

```
(m,n,a,B)=>B**(3*(m+n)+4)/~-B*a-B**(n-~n)-B**(m+3*n+2)-B**(2*m-3*~n)-B**n-1

```

Try it online!

---
Tags: code-golf, number, base-conversion
---


title: Pass The ⚽ Around The Circle

text:
# Question
Title: Pass The ⚽ Around The Circle
The *ball game* is a game in which a number of players sit together in a circle. Each player is first assigned a number \\$ n \\$, either `1`, `2`, or `3`. The game begins with any starting player, and proceeds *clockwise* around the circle. The *current* player with the ball throws it to the *next* player. Who the *next* player is solely depends on the number \\$ n \\$ the *current* player was assigned.

If \\$ n = 1 \\$, the *next* player will be the one sat directly adjacent (one space away), traveling in the current direction.

If \\$ n = 2 \\$, the *next* player will be the one sat two spaces away, traveling in the current direction.

If \\$ n = 3 \\$, the direction of play is first switched *(clockwise to counter-clockwise, and vice-versa)*. The *next* player will then be the one sat directly adjacent, traveling in the new direction.

## Task

You are given a list of numbers \\$ l \\$ all in the range \\$ \[1 - 3\] \\$, denoting the numbers each player was assigned. The elements in \\$ l \\$ are given in clockwise order, and such that the last element of \\$ l \\$ is adjacent to the first element. Your task is to determine the number of players who have touched the ball, before it reaches a player who previously already touched the ball.

### Example

The starting player is at the first index. `X` represents a visited index, `O` represents an index visited twice.

```
[1, 2, 1, 1, 2, 2, 3] ->
[X, 2, 1, 1, 2, 2, 3] ->
[X, X, 1, 1, 2, 2, 3] ->
[X, X, 1, X, 2, 2, 3] ->
[X, X, 1, X, X, 2, 3] ->
[X, X, 1, X, X, 2, X] ->
[X, X, 1, X, X, X, X] ->
[X, X, 1, O, X, X, X]
The answer is 6.

```

## Clarifications

* \\$ l \\$ can be inputted in any reasonable format, but the numbers `1`, `2`, and `3` must not change
* The starting player does not have to be at the first index, but please specify where it would start
* This is , so the shortest code in bytes wins!

## Test Cases

```
Input (start is index 0) -> Output
[1] -> 1
[2] -> 1
[3] -> 1
[3, 2] -> 2
[2, 1] -> 1
[2, 2, 3] -> 3
[1, 1, 1, 1, 1] -> 5
[2, 2, 2, 2, 2] -> 5
[3, 3, 3, 3, 3] -> 2
[1, 3, 2, 1, 2, 3] -> 2
[1, 2, 1, 1, 2, 2, 3] -> 6

```

# Answer
# Python 3, ~~67~~ 55 bytes

```
f=lambda x,*l:x and-~f(*l[x%3-1::1-x//3*2],0,*l[x%2:1])

```

Try it online!

Use @Leo's idea of keeping the current player at a fixed index and transforming the list instead. Be sure to check out and upvote his answer!

If the current list is `[x, a, b, c, d]`, where `x` is the move of the current player, then we want to rotate the list appropriately, and replace `x` with `0`:

* If `x == 1`, the new list is `[a, b, c, d, 0]`
* If `x == 2`, the new list is `[b, c, d, 0, a]`
* If `x == 3`, the new list is `[d, c, b, a, 0]`
* If `x == 0`, this player has already been visited, thus we stop the algorithm.

---

# Python 2, ~~90~~ 85 bytes

```
f=lambda l,d=1,p=0,*t:(p in t)^1and-~f(l,[d,-d][l[p]>2],(-~l[p]%4*d-d+p)%len(l),p,*t)

```

Try it online!

Not every elegant, but does the job.

This recursive function keeps track of the current direction `d`, the position `p`, and the list of seen position `t`.
> 8 votes

# Answer
# Husk, 16 bytes

```
←LU¡Γ!Moëṙ1ṙ2↔IΘ

```

Try it online!

Takes a list of numbers where the ball is currently at the first element and keeps rotating/reflecting the list to keep the ball in the first position while setting any visited element to 0. Returns how many different lists were created this way (-1).

For a more detailed explanation of the code (hard to do, but I'll try):

```
←LU¡Γ!Moëṙ1ṙ2↔IΘ
        ëṙ1ṙ2↔I  List of four functions [rotate by 1, rotate by 2, reflect, do nothing]
      Mo       Θ Make each of these functions prepend a 0 to the list before doing anything

    Γ!           Use the first element of the input list as an index into the list
                 of functions, and apply that function to the rest of the input list.
                 Note that indexing with a 0 returns the last function (do nothing)

   ¡             Iterate this process and keep all the results produced
  U              Discard all results after the first repeated one
←L               Return the number of results minus one

```

I'm a bit sad for all the bytes I'm taking to do `←LU`, but I couldn't find a shorter alternative (damn 1-based indexing!)
> 5 votes

# Answer
# C (gcc), <sup>~~94~~ ~~92~~</sup> 91 bytes

Saved a byte thanks to ceilingcat!!!

```
c;s;i;d;p;f(l,n)int*l,n;{p=1;for(s=i=0;c=l[i];l[i]=!++s,i=(i+p*d+n)%n)d=c>2?p*=-1,1:c;p=s;}

```

Try it online!

Inputs an array of `int` along with its length and returns the number of players touched before a repetitive touch.

**How?**

Passes the ball around setting the last place the ball was to \\$0\\$ and incrementing the counter \\$s\\$. When we arrive back at a \\$0\\$ we're done and return \\$s\\$.

**Commented code**

```
c;s;i;d;p;f(l,n)int*l,n;{
    p=1;                /* polarity is initialised to 1 forwards.
                           -1 is backwards */
    for(s=i=0;          /* initialise counter and index */
        c=l[i];         /* stop looping when we hit a zero
                           and cache the current value in c */
        ++s,            /* after loop bump our count */
        l[i]=0,         /* and zero last player */
        i=(i+p*d+n)%n)  /* and move index d places
                           in polarity p direction
                           adding n so we never go negative
                           when we make it all mod n */
       d=c>2?p*=-1,1:c; /* if number is 3 reverse polarity p
                           and set d to 1 otherwise set d to
                           the number */
    p=s;                /* return s */
}

```
> 3 votes

# Answer
# JavaScript (ES6), 67 bytes

```
a=>(d=1,g=x=>(n=a[x%=w=a.length])&&!(a[x]=0)+g(x+=n-3?n*d:d=w-d))``

```

Try it online!

### Commented

```
a => (                    // a[] = input array
  d = 1,                  // d = direction
  g = x =>                // g is a recursive function taking the current position x
    ( n =                 //   n is the player number at the current position
      a[                  //
        x %=              //   take the wrap-around into account by computing
          w = a.length    //   x modulo w, where w is the length of a[]
      ]                   //
    ) &&                  //   stop the recursion if a[x] is equal to 0
    !(a[x] = 0) +         //   otherwise, set it to 0 and increment the final result
    g(                    //   do a recursive call:
      x +=                //     update the position:
        n - 3 ? n * d     //       add n * d to x if n is not equal to 3
              : d = w - d //       otherwise, reverse the direction and add it to x
    )                     //   end of recursive call
)``                       // initial call to g with a zero'ish value for x

```
> 2 votes

# Answer
# , ~~97~~ ~~87~~ 85 bytes

```
function(p,i=1)sum(while(m<-p[i]){p[i]=0
i=(i+`if`(m>2,T<--T,m*T)-1)%%sum(p|1)+1},!p)

```

Try it online!

*Edit: -10 bytes by tracking direction of travel (instead of flipping list of players)*

*Edit 2: re-arranged to cull 2 more characters*

```
touches=function(p,         # p=player numbers
    i=1)                    # i=current player
    sum(
        while(m<-p[i]){     # while m=number of current player is non-zero
            p[i]=0          # set his number to zero
            i=i+            # calculate new player:
            `if`(m>2,       # if m is 3...
                T<--T,      # flip the direction of travel T and move by this
                m*T)        # otherwise move ahead by T*m
            -1)%%sum(p|1)+1 # -1, modulo number of players, +1
        }                   # (R indices are 1-based)
        !p)                 # sum of null (the return value of 'while')
                            # and the final number of zeros

```
> 2 votes

# Answer
# 05AB1E, ~~22~~ 21 bytes

```
[ć©_#0š„RÀS¤ºª®è.V¼}¾

```

Try it online or verify all test cases.

**Explanation:**

```
[                # Loop indefintely:
 ć               #  Extract head; pop and push remainder-list and first item separately
  ©              #  Store this first item in variable `®` (without popping)
   _             #  Check if its 0
    #            #   And if it is, stop the infinite loop
 0š              #  Prepend a 0 at the start of the list
   „RÀ           #  Push string "RÀ"
      S          #  Convert it to a list of characters: ["R","À"]
                 #  (NOTE: The `ª` already implicitly converts it to a list of
                 #   characters, so this usually isn't necessary; but without it the
                 #  `„RÀ¤` would act like a dictionary string and become "R cry")
       ¤         #  Push its last item (without popping): "À"
        º        #  Double it by mirroring: "ÀÀ"
         ª       #  Append it to the list: ["R","À","ÀÀ"]
          ®è     #  Index `®` into this list (0-based and with wraparound,
                 #  so the 3 will index into the first item "R")
            .V   #  Execute it as 05AB1E code
                 #   "R": Reverse the list
                 #   "À": Rotate the list once towards the left
                 #   "ÀÀ": Rotate the list twice towards the left
              ¼  #  Increase the counter_variable by 1
}¾               # After the infinite loop: push the counter_variable
                 # (after which it is output implicitly as result)

```
> 1 votes

# Answer
# , 39 bytes

```
1-~&#[:({.(|.*1*@+2*[)0,}.)^:a:]+_4*=&3

```

Try it online!

I solved this independently before looking at other answers, but have stumbled on the same high-level approach used by Leo and Surculose Sputum.

A few details appear to be different:

1. `]+_4*=&3` I start by transforming all `3`s in the list into `-1`s, so that I don't have to special case any code. J automatically treats a negative rotation as the reverse direction.
2. Instead of reversing the list when I hit a -1, I multiply all numbers on the list by -1. I avoid special casing here too by always multiplying all numbers on the list by the following quantity: "double current value, add 1, take sign num" `1*@+2*[`. The quantity will be 1 for all values greater than 0, and -1 when the value is -1.
> 1 votes

# Answer
# Perl 5 `-pa`, 66 bytes

```
while($_=$F[$i]){$F[$i]=0;$.*=-1if/3/;$i+=$.+$.*/2/;$i%=@F;$\++}}{

```

Try it online!
> 1 votes

# Answer
# JavaScript (Node.js), 81 bytes

```
s=>s.map(_=>(t=s[r=p%q])?s[p+=t>2?w*=-1:t*w,r]=!++n:0,q=s.length,n=0,p=3*q,w=1)|n

```

Try it online!
> 0 votes

# Answer
# Charcoal, 30 bytes

```
Ｗ⊟θ≔⁺⎇⁼ι²⟦⊟θ⁰⟧⟦⁰⟧⎇⁼ι³⮌θθθＩ⊕№θ⁰

```

Try it online! Link is to verbose version of code. Based on @Leo's idea explained better by @SurculoseSputum. Takes input in reverse order. Explanation:

```
Ｗ⊟θ

```

Let the current list be `[e, d, c, b, a]`. Remove the last element `a`, which represents the current player. Then if it is non-zero, meaning that they have not played yet:

```
≔⁺⎇⁼ι²⟦⊟θ⁰⟧⟦⁰⟧⎇⁼ι³⮌θθθ

```

Create two lists depending on the value of `a`:

1. `[0]` and the rest of the list `[e, d, c, b]`
2. `[b, 0]` (obtained by popping `b` from the list) and the rest of the list `[e, d, c]`
3. `[0]` and the reverse of the rest of the list `[b, c, d, e]`

Concatenate them together to create the new state of the list.

```
Ｉ⊕№θ⁰

```

Print 1 more than the number of `0`s in the list (because we popped `a` so that's no longer in the list).
> 0 votes

# Answer
# perl -M5.010 -a, 84 bytes

```
$:=1;{($;=$F[$,])?do{$:=-$:,$;=1 if$;==3;$"++;$F[$,]=0;$,=($,+$;*$:)%@F;redo}:say$"}

```

Try it online!

This just follows the rule of the game, labelling any visited player as 0, and terminating when it encounters a player labelled 0. Steps are counted and printed at the end.

The code in the header section of TIO is just there to make it work on multiple inputs; leave it off for a single line of input.
> 0 votes

# Answer
# Ruby, 63 bytes

```
f=->a,d=1{x,*a=a;x ?1+f[[p,*a].rotate((2-x%2)*d*=1-x/3*2),d]:0}

```

Try it online!
> 0 votes

---
Tags: code-golf, simulation
---