Simulate gravity

Given how simple this is, I'm pretty surprised there wasn't a question on here for this already. The task for this question is to simulate n-body gravity!

Simple? I thought the n-body problem was famously unsolved!

Yeah, yeah; whatever. There's (provably) no analytic equation, but gravity really just follows one simple rule:

$$F = G \frac{m_1m_2}{r^2}$$

That's it. There's no big gatchas until you start dealing with relativity, and relativity puts gatchas on everything. We're actually going to simplify our simulation even more, and say all our masses are one kg, and exist in a magical world where the gravitational constant G is 1\$ \text m^3 \over \text{kg} \cdot \text{s}^2 \$, so the equation you're going to simulate is

$$\ddot r_i = \sum_{j\ne i} \frac{\hat r_{ij}}{|r_{ij}|^2} \quad \forall i$$

"Gah," I hear you cry. "You tricked me, what are all these extra symbols you've added! There's dots and sums and hats and bars! And your A's upside down, the pointy bit goes up!"

Don't Panic!
Mathematicians love code golf too, most of these symbols are just fancy loops. We'll go one step at a time, from the outside in.
The upside down A is the closest you get to an actual for loop in math, and it means that this whole equation individually applies to each of our bodies, represented by a variable \$i\$. It's basically equivalent to for i in bodies
The double dot is a little more tricky. In math terms, it's the second derivative with respect to time, but we can keep it simpler than that. A derivative (in time) is a fancy way to say "the amount something changes (per second)," so this double dot equation is defining the change of the change of each radius. Our pseudocode now looks like this:

for i in bodies {
    v[i] += equation
    r[i] += v[i]
}

(for the math buffs that just started complaining, see this video for why we update velocity first)

The next piece is the summation. This is also a for loop, except you just sum all the terms and return the result. The thing on the bottom is the values we're looping over. This means equation now looks like equation = sum(fraction(i,j) for j in bodies if j != i)

Almost there! The ij subscript means the vector from \$r_i\$ to \$r_j\$, which you calculate by taking the vector difference: rij = r[j] - r[i].
The bars mean finding the magnitude, which you do by taking the square root of the sum of the squares of the components. In code that's rij_mag = sqrt(rij[1]^2 + rij[2]^2 + rij[3]^2)
The hat means normalizing a vector, which you do by dividing the magnitude; but if you look closely at our fraction we're already doing that! Dividing one more time just means incrementing the exponent.

Putting that all together, our pseudocode is:

for i in range(num_bodies) {
    v[i] += sum(
        (r[j]-r[i]) / sqrt(
            ( r[j][1]-r[i][1] )^2 + ( r[j][2]-r[i][2] )^2 + ( r[j][3]-r[i][3] )^2
        )^3
        for j in range(num_bodies)
        if j != i
    )
    r[i] += v[i]
}

Requirements

Your task for this code-golf challenge is to simulate one second of gravity. That is, your code should do the equivalent of running the above for loop once. You will be given \$n\$ bodies, where each body has a velocity and position. You may take these \$6n\$ numbers however you like, but you should return the updated \$6n\$ numbers in the same way. (ie, your code should accept its own output as a new input)

You can assume that two bodies will never perfectly overlap (so there's no division by zero), and you don't need to worry about precision (so just use the default floaty numeric type)

Test cases

{velocities}, {positions} -> {v}, {r}

{}, {} -> {}, {}
{[10, 5, 1]}, {[1, 2, 3]} -> {[10, 5, 1]}, {[11, 7, 4]}
{[0,0,0], [0,0,0], [0,0,0]}, {[1,0,0], [0,1,0], [0,0,1]} -> {[-.7071, .3535, .3535], [.3535, -.7071, .3535], [.3535, .3535, -.7071]}, {[.2928, .3535, .3535], [.3535, .2928, .3535], [.3535, .3535, .2928]}

Brownie Points

We simplified some stuff here, but we've done the hardest part of a fully fledged n-body gravity simulation. If you want extra brownie points, you can add those complications back in.
First, we want the gravitational constant G.
Then, we allow for masses on each bodies with a mass[] array
Finally, we'll take t and dt for total time and step time

Our updated pseudocode is:

T=0
while T < t {
    for i in range(num_bodies) {
        v[i] += G * sum(
            mass[j] * (r[j]-r[i]) / norm(r[j] - r[i])^3
            for j in range(num_bodies)
            if j != i
        ) * dt
        r[i] += v[i] * dt
    }
    T += dt
}

Can you Shut The Box?

Shut The Box is a simple dice game, where a player attempts to "shut" all of the numbered tiles (traditionally, 1 through 9) by rolling dice. The way the game works:

• The box has 9 numbered and hinged tiles, numbered 1, 2, 3, etc. up to 9. Initially, all 9 begin "open".
• A player rolls two 6-sided dice and total the two dice.
• They then "shut" any combination of tiles that sum to the dice total.
• Repeat until all tiles are shut, or no more open tiles can sum to the dice total.
• The player's final score is the total of all remaining open tiles, with a lower score being better.

Note that there are multiple ways that one dice roll can shut different tiles. For example, rolling a total of 5 can close either the 5 tile, the 4 and 1 tiles, or the 3 and 2 tiles. Importantly, there is only one of each numbered tile, so once a tile has been used, it cannot be used again. Thus, for a roll of 6, the combination of 3 and 3 isn't valid, but the 3, 2 and 1 tiles are.

Given a non-empty list of positive integers ranging from 2 to 12 inclusive, output the lowest possible score for that series of dice rolls, in that order. You may take input in any acceptable and reasonable format and method, but please note that, as order matters, the manner in which you take input must distinguish different orders of the same integers.

This is a code-golf challenge, so the shortest code in bytes in each language wins.

Test cases

Input -> Output
[10, 10, 10, 10, 5] -> 0

Inference a transformer

Outgrow all computable functions

SCR max speed calculator

SCR is a train driving game on Roblox. Distances are measured in miles, and speeds in miles per hour. The driving guide dictates specific speeds for specific scenarios:

• The speed should never be higher than either the maximum speed of the train or the imposed speed limit.
• If the train is less than or equal to 0.35 miles from the station, the train should go no more than 35mph.
• If it is a terminating station, it should be no more than 15mph.
• If the signal is a single yellow aspect, it should be no more than 45mph.
• If the signal is a red aspect and the distance to the signal is less than the distance to the station, the train should be at a complete stop (0mph). If the station is closer, normal station approach rules apply.
• Double yellow and green aspects do not carry speed restrictions by themselves.

Given the train’s maximum speed, the current speed limit, the distance to the next station, the distance to the next signal, and the current signal aspect, output the maximum speed the train is allowed to move at in mph. If the next signal aspect is red and the station is closer than the next signal, you may assume that the train is at most 0.35mi away from the next station. Shortest code wins, standard loopholes apply.

Too complex?

Find the outcome of a Cortex Prime dice roll

(Formal language theory) Regular expression for an even number of 0s and an odd number of 1s

Similar to Make a regex that matches certain binary numbers with the following differences:

1. Only formal language theory regular expressions are allowed. Most importantly, lookahead/lookbehind is not available, and neither are backreferences like \1. More on this below.
2. It must be perfectly correct. False positives or false negatives are not allowed. (The linked challenge allowed up to 10% false negative and false positive rates.)

Create a regular expression that matches a string of 1s and 0s with an even number of 0s and an odd number of 1s.

This is a regular language with a simple DFA of only 4 states.

Allowed regular expression features

Solutions must be regular expressions as defined in formal language theory. This means the only operators allowed are *, |, and concatenation.

Effectively (unless I missed something) this means the allowed characters are: 01()|*, and technically also ∅ and ε but I highly doubt they would be useful and are not as simple to convert to a programming regex.

Start and end anchors are implied or not needed. That is, if your answer is REG, the programming regex that must match the requirement is ^(REG)$. Your score would be 3 characters.

Testing sample, generated using Python:

Should match:
1
010
001
111
100
1100100
0010110
1011101
0010011
1001010
0101111
0010000
0000010
1101000
1011110
1110011
0001110
0100000
1010001
1110101
100110001111011
011000011010000
001010100011101
001111111101000
100111001000011
010010011010101
101110110001110
110001011100111
100110000000011
001011011110101
001011100011010
000000010101011
001001101011111

Should not match:
0
101
000
011
110
1000
0010
0011
1001
1011
0111
1111
0101
1010
1110
0100
0110
1100
0001
0000
1101
010100
111001
010111
101101
110100
001011
000010
011111
110011
101111
011001
101011
011000
011110
111000
101001
100101
111011
111110
110001
110000
101010
010101
001101
0100001
0111001
0101011
1000010
0101000
1100101
0011000
1001000
1000100
0101110
0011011
1001011
0110110
01111111
01001110
10011111
11110111
10111001
11100111
00011100
00101111
10100010
11100001
11101100
10010111
11111011
00001101
00100011
11110000
11110001
00001111
01000100
10000100
01111010
01111001
00011000
10100011
00010001
10010000
11111110
00100111
1101001110
1100000011
0010110101
0010001011
0001001001
0010100001
0110011101
1110100011
0110111111
1011111001
1011010101
1110000100
0111110000
1110111000
1011111110
1111001101
0100111101
1011011110
1010100010
1001110001
0010100110
0000011011
0011000001
0010001100
0000100011
1110001000
1011011011
0110101110
1001111111
0010001001
101011000100001
101011100101010
111111111000001
000010101000100
110111011001000
011001011010000
010010111001000
001100011101000
100000010000011
011011100101001
011001110111000
100110001010001
101001101000010
101000011100001
010110000000010
111011001010111
011011110001100

The minimal DFA for this language has only 4 states, but in my attempt to create a regular expression for it, I ended up with over 220 characters and I wonder if anyone can do better. I have also used a DFA to regex converter, and it output a slightly smaller expression, but I wonder if other people can do better.

To be honest, I just wanted to put this question out there and see what people can do. I have no interest in being a judge, so if posting a challenge to this exchange requires more than a "fire and forget", I would be more comfortable if anyone so inclined would post it on my behalf.

In my surface-level online searching I didn't find any existing solutions, however I did find these:

This question is close, but not the same: https://stackoverflow.com/questions/20485486/shortest-regex-for-binary-number-with-even-number-of-0s-or-odd-number-of-1s (or instead of and)

The previous challenge which I linked before allowed all regex features (and allowed some amount of incorrect results), and has a very short solution using backtracking by the user Howard: https://codegolf.stackexchange.com/a/16152

Title: Finding Chord Segments with Integer Length

A math teacher wants to give his students an interesting geometry problem.

He has the following idea (Fig. 1):

Let \$AB\$ and \$CD\$ be two chords of a circle with center \$M\$, intersecting orthogonally at point \$S\$. Find the lengths of \$CS\$ and \$DS\$ if \$AS\$ is \$n\$ cm, \$BS\$ is \$m\$ cm, and the circle radius is \$r\$ cm.

Now he needs to choose the appropriate values ​​for \$n,\:m\$ and \$r\$ for the problem. According to established convention, where possible, both the results and the given values ​​are integers. This would allow the students to intuitively understand whether their solution is correct. Unfortunately, the math teacher cannot find a combination of three integer input values ​​that would result in two integers.

The Challenge

Write a program or a function that will find all possible combinations of the three segments [m, n, r] that have integer lengths and integer solutions.

Input and output

A program or a function that inputs a limiting number \$X\$ and outputs all combinations of \$m, n, r ≤ X\$.

The output is arranged such that \$m\$ and \$n\$ precede \$r\$.

Rules

m + n < 2*r

This is code-golf. Standard i/o. Standard loopholes.

Test case:

X = 100:

         m   n    r
 [1,]    4   76   85
 [2,]    9   41   65
 [3,]    4   44   25
 [4,]    8   22   25
 [5,]    6   72   65
 [6,]    8   58   65
 [7,]   17   49   65
 [8,]   11   91   85
 [9,]   23   49   85
[10,]    8   88   50
[11,]   16   44   50
[12,]   14   64   65
[13,]    9   39   25
[14,]   13   27   25
[15,]   15   87   85
[16,]   27   53   85
[17,]   23   55   65
[18,]   24   66   75
[19,]   38   64   85
[20,]   32   88  100
[21,]   17   95   65
[22,]   19   85   65
[23,]   18   78   50
[24,]   26   54   50
[25,]   21   99   65
[26,]   27   77   65
[27,]   36   68   65
[28,]   27   93   65
[29,]   31   81   65
[30,]   39   81   75
[31,]   30   96   65
[32,]   40   72   65
[33,]   55   81   85
[34,]   38   88   65
[35,]   44   76   65
[36,]   62   88   85
[37,]   64   90   85

Return the minimum Conjunctive Normal Formula equivalent to the one given in input.

Translated by Google + some my changes

A conjunctive normal formula (abbreviated here CNF) is a conjunction of clauses, which are disjunctions of variables. It is represented by writings such as

(A∨B∨∼C∨∼D)∧(Q∨R∨∼P∨∼K)∧...∧(∼M)

where (A∨B∨∼C∨∼D), (Q∨R∨∼P∨∼K), ..., (∼M) are each the clauses of the CNF above, where A B C D ... M are "variables" of the respective clauses. Each of these variables can take on any value in the set TF={1,0}. Once a value in the set TF has been assigned to each variable, the value of the CNF can be calculated by performing the functions ∨ ∧ ∼ with the binary values ​​0 1 of each variable.

The operation ∨ is defined by

1∨0=1; 0∨1=1; 1∨1=1; 0∨0=0

The operation ∧ is defined by

1∧0=0; 0∧1=0; 1∧1=1; 0∧0=0

The function ∼ is defined by

∼1=0; ∼0=1

Two CNFs A(x1,x2,...xn) and B(y1,y2,...yn), with variables {x1,x2,...xn} and {y1,y2,...yn}, are said to be equivalent if any assignment {x1,x2,...xn} ∪ {y1,y2,...yn} with values ​​in the set TF={1,0} yields the same final Boolean value (performing all calculations with the functions ∨ ∧ ∼) in CNF A and CNF B.

If A and B are two conjunctive normal formulas, we say that A is less than B if the sum of all occurence of ∧ and or ∨ of A is less than the sum of all occurence of the and ∧ and or ∨ of B

Examples: Let's say two CNFs A and B with

A=(a1∨a2)∧(a3∨a4) and B=(a1∨a2)∧a3

then B<A because numbers of ∧ and ∨ of B is 2 that is less than the number of ∧ and ∨ of A that is 3.

Here we require a program that, given a CNF A, returns a CNF B that is as small as possible and equivalent to A. The winner is the one who finds the minimum number of the sum of all the or[∨] and and[∧] that appear in all the CNF results of below exercises.

If two answers are tied, then the winner is the one with the smallest program in terms of number of bytes in the source code.

Exercises (the formulas are the same as those in Prove me wrong!)

(P∨∼Q∨∼R)∧(Q∨R∨∼P)∧(Q∨∼P∨-R)
(∼P)∧(S)∧(R∨∼P)∧(U∨∼Q)∧(X∨∼R)∧(Q∨∼S)∧(∼P∨∼U)∧(W∨∼Q∨∼U)
(∼P∨∼Q)∧(Q∨P)∧(P∨∼Q)∧(Q∨∼P)
(P)∧(∼P∨∼S)∧(P∨T)∧(Q∨∼R)∧(∼R∨∼S)∧(∼P∨∼Q∨∼R)∧(∼P)
(T∨∼S)∧(∼S)∧(Q∨∼R)∧(∼R∨∼S)∧(∼P∨∼Q∨∼R)∧(∼P)

These formulas can be represented in the code with maximum freedom, for example,

(P∨∼Q∨∼R)∧(Q∨R∨∼P)∧(Q∨∼P∨-R)

could be represented as an array of 3 strings:

('P-Q-R')('QR-P')('Q-P-R')

Examples:

In finding a smaller equivalent CNF for (P∨∼Q∨∼R)∧(Q∨∼R∨∼P)∧(Q∨∼P∨-R) I would have found (Q∨∼P)∧(P∨∼Q∨∼R). It has 1 and ∧, and 3 or ∨ in total so 4 is the length of this result formula that is more little of the one of input that has length 6 or and 2 and that would be 8.

Could be useful these equivalences

A∨B∨..∨D is equivalent to each permutations of variables A B..D 
A∧B∧..∧D is equivalent to each permutations of variables A B..D 
A∨B∨..∨∼A∨..∨D is equivalent to 1 or always true, 1 is the name of that proposition 
A∧B∧..∧∼A∧..∧D is equivalent to ∼1 or always false or 0 zero
A∨∼1 is equivalent to  A
A∨ 1 is equivalent to  1
A∧∼1 is equivalent to ∼1 (that is 0 too)
A∧ 1 is equivalent to  A
A∧(A∨∼A) is equivalent to A
A∧(B∨∼A) is equivalent to A∧B
(P∨Q)∧(P∨R) is equivalent to P∨(Q∧R) useful when R is ∼Q
(A∨B∨C∨D)∧(Q∨R∨P∨K)∧(A∨B) is equivalent to (Q∨R∨P∨K)∧(A∨B)

tag logic codegolf

Sort the Test Tubes

Find the paths and cycles

Given a finite digraph with all in-degrees and out-degrees at most 1, find its partition into directed paths and cycles.

The problem is potentially interesting because paths and cycles are slightly different - combining the two may inspire some ingenious approaches.

Input

A sequence of pairs of vertices representing the directed edges of the graph, which might appear in any order. You can assume:

• The vertices are precisely the integers 0,...,n for some n>0.

• Every such integer appears in some pair (so there are no isolated vertices).

• Every such integer appears at most once on the left of a pair and at most once on the right of the pair (so in-degrees and out-degrees are at most 1).

Output

A sequence of lists of vertices representing the directed cycles and maximal directed paths of the graph.

• A path must be represented by its vertices in order.

• A cycle must be represented by its vertices in order starting from an arbitrary vertex with the initial vertex repeated once at the end.

• The paths and cycles must include all vertices between them, with no repeats except for the repeat of the beginning and end of each cycle.

• Thus, the edges of the input should be precisely the ordered consecutive pairs within each list of the output (in some order).

• The paths and cycles can be output in any order. Each cycle can be started from any of its vertices.

Any reasonable representation of "list of lists of integers" is acceptable for input and output.

Examples

This is code-golf, so shortest program in each language wins!

Rational quadratics sequences code-golf math sequence

Let's define a rational quadratics sequence \$a_1, a_2, \cdots, a_n\$ of length \$n\$ one that satisfies all of the following:

• The integers from 1 to \$n\$ appear exactly once each.
• For \$1 \le i \le n - 2\$, at least one of the equations of the form \$a_{i} x^2 \pm a_{i+1} x \pm a_{i+2} = 0\$ has rational roots. In more direct terms, at least one of \$a_{i+1}^2 \pm 4 a_i a_{i+2}\$ is a square number.

Given a positive integer \$n\$, find the number of rational quadratics sequences of length \$n\$.

sequence I/O rules apply. This means you can choose to implement one of the following:

• Take \$n\$ and give the answer for \$n\$.
• Take \$n\$ and give the answers for \$1, \cdots, n\$.
• Without input, give all answers for \$1, 2, 3, \cdots\$.

Test cases

1 => 1
2 => 2
3 => 6
4 => 4
5 => 4
6 => 4
7 => 4
8 => 10
9 => 4
10 => 32
11 => 10
12 => 26
13 => 32
14 => 68
15 => 136

The first occurrence of k zeros in \$^\infty 3\$

Given k, find the first(lowest) occurrence of k continuous zeros in \$^\infty 3\$ in 10-adic.

Here, 10-adic mean base-10 but extend infinitely to left, and \$^\infty 3\$ is defined as limit of sequence \$a_1=3, a_{i+1}=3^{a_i}\$. It can be proven that every digits eventually get stable.

Your program should run in reasonable time and space for k=3.

The value ends with 05496638003222348723967018485186439059104575627262464195387, so you should return 19(0-index) for k=1.

Test cases

• 1 => 19
• 2 => 49
• 3 => 356
• 4 => 3448

code-golf

Notes

Inspired by Are there G(63) continuous zeros in G(64)?, which I'd say G(64) is much larger than G(63) for this purpose and can be treated \$^\infty 3\$.

This may be not fun as fastest-code due to likely unique and well-explored path

Maybe this is better posted as "Output 3^^inf" don't count zeros

Add two rational numbers... esoterically

Objective

Build a binary operator \$\star : \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}\$ such that, there exists a bijection \$i : \mathbb{Z} \to \mathbb{Q}\$ such that, for every integer \$M\$ and \$N\$, \$M \star N = i^{-1}(i(M) + i(N))\$ holds.

Or in mathematical terms, build a binary operator \$\star\$ that admits a group isomorphism from \$(\mathbb{Z}, \star)\$ to \$(\mathbb{Q}, +)\$.

I/O Format

Flexible. Standard loopholes apply.

Scoring

This is a fastest-algorithm challenge. The submission whose the asymptotic worst-case time complexity of \$\star\$ is the fastest wins.

The parameter \$n\$ for the time complexity is \$s(M) + s(N)\$, where \$s\$ is defined as follows:

• \$s(0) = s(-1) = 0\$.
• For every integer \$D > 0\$, \$s(D) = \lfloor \log_2 D \rfloor + 1\$.
• For every integer \$D < -1\$, \$s(D) = \lfloor \log_2 (-D-1) \rfloor + 1\$.

Note that only worst-case time complexity is considered; as such, for example, \$O(n)\$ is not considered faster than \$\Theta(n)\$.

In case that multiple submissions are tied, the earliest submission wins.

Notes and Rules

Note that each bijection \$i\$ induces \$\star\$ uniquely. As such, your submission must specify your choice of \$i\$.

List directories needed to exist to reach a path ("mkdir -p --dry-run")

(The challenge has been posted.)

Get BB(k-1) from BB(k)

Here BB(k) is the longest running step of k-state, 2-symbol deterministic Turing machine. A movement of tape head is required per step, as data source does.

Test cases:

47176870 => 107 # BB(5)=>BB(4)
107 => 21 # BB(4)=>BB(3)

Explain your code as there's technical difficulty to test answers.

Translate BBCode into HTML

Pick and Flip

code-golf array

Challenge

Given an array of integers, perform the Pick and Flip algorithm, which is defined like this:

1. Set n to 1 (if 1-indexed) or 0 (if 0-indexed).
2. Set i to the n-th element of the array. If it doesn't exist, stop and return the array.
3. Reverse the i-th element of the array, if it exists. For example, 15 reverses to 51, and 20 reverses to 2.
4. Increase n by 1 and return to step 2.

Test Cases

1-indexed:

  3   5  19   6 720  50    Input
 [3]  5  19   6 720  50    Pick
  3   5 (91)  6 720  50    Flip
  3  [5] 91   6 720  50    Pick
  3   5  91   6 (27) 50    Flip
  3   5 [91]  6  27  50    Pick
  3   5  91   6  27  50    Flip
  3   5  91  [6] 27  50    Pick
  3   5  91   6  27  (5)   Flip
  3   5  91   6 [27]  5    Pick
  3   5  91   6  27   5    Flip
  3   5  91   6  27  [5]   Pick
  3   5  91   6 (72)  5    Flip
  3   5  91   6  72   5    Output

0-indexed:

  2   4  19   5 720  40    Input
 [2]  4  19   5 720  40    Pick
  2   4 (91)  5 720  40    Flip
  2  [4] 91   5 720  40    Pick
  2   4  91   5 (27) 40    Flip
  2   4 [91]  5  27  40    Pick
  2   4  91   5  27  40    Flip
  2   4  91  [5] 27  40    Pick
  2   4  91   5  27  (4)   Flip
  2   4  91   5 [27]  4    Pick
  2   4  91   5  27   4    Flip
  2   4  91   5  27  [4]   Pick
  2   4  91   5 (72)  4    Flip
  2   4  91   5  72   4    Output

Restrictions

• Every integer in the array will be at least 1 (if 1-indexed) or 0 (if 0-indexed).
• The array will not be empty.

Scoring

• You may use a function or a full program.
• Standard loopholes and I/O methods apply.
• This is code-golf, so shortest code in bytes wins.

My research group recently published a paper. As a way of celebrating I'm issuing a code-golf challenge based on one of the algorithms we present in the paper. (The main algorithm is a little too complicated unfortunately. This is another algorithm we present). I will present the problem concisely, then I will give the algorithm from the paper, then lastly I will explain the problem in more detail. You do not have to implement the exact same algorithm (whatever that means) you simply have to produce the same output.

The challenge is:

Given a word in a free group on two generators, determine if that word can appear as a contiguous subword of a primitive word (i.e. a word automorphic to one of the generators.)

We call a word that doesn't appear as a contiguous subword of any primitive word a "primitivity blocking" word.

The input will be a reduced word in a free group. These are strings on an alphabet of four characters: \$a\$, \$b\$, \$a^{-1}\$, and \$b^{-1}\$, with the special rule that \$x\$ and \$x^{-1}\$ will never appear directly adjacent to each other (this special rule is the "reduced" part).

We will call a run of one type of character (which is not a part of a longer run) a "syllable". We will write syllables using a shorthand so that \$x^n\$ is \$x\$ repeated \$n\$ times, and \$x^{-n}\$ is \$x^{-1}\$ repeated \$n\$ times.

The algorithm from adapted from the paper is as follows:

Call our algorithm \$\mathcal A(u)\$ and let \$F_2\$ be generated by \$a\$ and \$b\$. After each step we will replace \$u\$ by the result of that step and still call it \$u\$. Each new \$u\$ will be guaranteed to be primitivity blocking iff the last one was.
The first two steps will bring our input to a normal form by swapping signs and switching the roles of the generators as necessary. We want syllables of \$a\$ to have exponent \$1\$ and we want all syllables of \$b\$ to have positive exponent. Steps one and two will determine if this is possible swapping the roles and switching the signs of exponents (globally), rejecting words that can't and converting words that can.

Step 1. Check whether \$a\$ appears with exponent of only \$1\$, if it does skip to Step 2.. Otherwise if \$a\$ appears with exponent of only \$-1\$, replace all \$a^{-1}\$s with \$a^1\$s and proceed to Step 2. If neither of these are the case swap all \$a\$s with \$b\$s, and check again. If it fails a second time \$u\$ is primitivity blocking.
Step 2. Now \$\mathcal A\$ checks whether all the exponents on \$b\$ in \$u\$ have the same sign. If not, then \$u\$ is primitivity-blocking, so we stop. Otherwise \$\mathcal A\$ flips the sign on all exponents of \$b\$, if necessary, to make all the exponents on \$b\$ positive.

Step 3. \$u\$ is now of the form \$b^{n_0}ab^{m_1} a \dots ab^{m_p}ab^{n_1}\$ where \$m_1, \dots , m_p\$ are positive and \$n_0\$ and \$n_1\$ are non-negative. If there \$p=0\$, i.e. the word is of the form \$b^{n_0}ab^{n_1}\$ then \$u\$ is not primitivity blocking. Otherwise \$\mathcal A\$ checks whether there is a pair \$m_i\$, \$m_j\$ which differ by more than \$1\$. If so, \$u\$ is primitivity-blocking. Otherwise continue, letting \$t = \max m_i − 1\$.
Step 4. \$\mathcal A\$ checks whether \$n_0\$ or \$n_1\$ is greater than \$\min m_i + 1\$. If so, then \$u\$ is primitivity-blocking.
Step 5. \$\mathcal A\$ will transform the word to be of the form \$ab^{t0} a \dots ab^{t_p}\$ , where each \$t_i\$ is in \$\left\{t, t+1\right\}\$. In order to do this \$\mathcal A\$ checks whether \$n_0\$ is the largest exponent of \$b\$ appearing in \$u\$. If it is, then A replaces \$u\$ by \$au\$. Otherwise it removes the \$b^{n_0}\$ from the front of \$u\$. This does not change the primitivity-blocking property . Then if \$n_1 < t\$, then \$\mathcal A\$ replaces the syllable \$b^{n_1}\$ with \$b^t\$.
Step 6. \$\mathcal A\$ removes \$b^t\$ from each \$b\$ syllable in \$u\$.
Step 7. Now every \$b\$ syllable has exponent \$1\$, so \$\mathcal A\$ swaps \$a\$ with \$b\$. It then checks whether the word \$u\$ has two or fewer syllables. If it does, \$\mathcal A\$ stops and returns that \$u\$ is not primitivity-blocking. If the word \$u\$ has more than two syllables, then \$\mathcal A\$ continues to Step 3.

In progress ... I just want to save it here.

Sorites nightmare

abstract-algebra code-golf decision-problem ragged-list

We will deal with expressions which can be defined in any of the following ways:

• A ragged list of integers in which every element contains exactly 3 elements.
• A rooted ternary tree with integer labeled leaves.
• The following ADT (given in pseudocode):

  type Exp := Leaf Integer | Branch Exp Exp Exp
  

• The free monad for lists of length 3 generated by integers.

We will define a sense of equality for this type which goes as follows:

1. Two expressions are equal if they are equal integers.
2. [a,b,c] = [a,b,c] where a, b, and c are expressions.
3. [[a,b,c],d,e] = [a,b,[c,d,e]]
4. [[a,b,c],d,e] = [a,[d,c,b],e]
5. [a,a,a] = a

So for example to show that [[[[1,2,3],3,2],1,1],2,3] = [1,2,3] we can use the following chain of equalies

[[[[1,2,3],3,2],1,1],2,3] = [[[1,2,[3,3,2]],1,1],2,3]
                          = [[1,2,[[3,3,2],1,1]],2,3]
                          = [[1,2,[3,[1,2,3],1]],2,3]
                          = [1,2,[[3,[1,2,3],1],2,3]]
                          = [1,2,[3,[1,2,3],[1,2,3]]]
                          = [[1,2,3],[1,2,3],[1,2,3]]
                          = [1,2,3]

Here's another example:

[[[[[1,2,3],3,2],2,2],1,1],2,3] = [[[[1,2,3],3,[2,2,2]],1,1],2,3]
                                = [[[[1,2,3],3,2],1,1],2,3]
                                = [[[1,2,[3,3,2]],1,1],2,3]
                                = [[1,2,[[3,3,2],1,1]],2,3]
                                = [[1,2,[3,[1,2,3],1]],2,3]
                                = [1,2,[[3,[1,2,3],1],2,3]]
                                = [1,2,[3,[1,2,3],[1,2,3]]]
                                = [[1,2,3],[1,2,3],[1,2,3]]
                                = [1,2,3]

One last example:

[[[[[[[1,2,3],4,5],5,4],3,2],1,1],2,3],4,5] = [[[[[[[1,2,3],4,5],5,4],3,2],1,1],2,3],4,5]
                                            = [[[[[[[1,2,3],4,5],5,4],3,2],1,1],2,3],4,5]
                                            = [[[[[[[1,2,3],4,5],5,4],3,2],1,1],2,3],4,5]
                                            = [[[[[[1,2,3],4,5],5,4],3,2],1,[1,2,3]],4,5]
                                            = [[[[[1,2,3],4,5],5,4],3,2],1,[[1,2,3],4,5]]
                                            = [[[[1,2,3],4,5],5,4],[1,2,3],[[1,2,3],4,5]]
                                            = [[[1,2,3],4,5],[[1,2,3],4,5],[[1,2,3],4,5]]
                                            = [[1,2,3],4,5]

Challenge

Take two expressions as input. You can use any of the described definitions as the type of an expression. Your program will decide if the input expressions are equal for the defined sense of equality.

You should output one of two distinct value if the input expressions are equal and the other if they are not equal.

This is code-golf the goal is to minimize the size of your code as measured in bytes.

Title?

It might be unclear why I've chosen this title for this challenge. This challenge is a problem in abstract-algebra simplified for a (slightly) broader audience (broadened from code-golf nerds who know abstract algebra to code-golf nerds). The underlying problem here is to solve the word problem in a free idempotent semiheap.

Sorites paradox is a paradox having to do with the ambiguity of language. It asks "How many grains of sand make a 'heap'?" or something to that effect. Of course here we have not only heaps, but semiheaps and idempotent semiheaps which are something in between heaps and semiheaps. There are also generalized heaps which are between idempotent semiheaps and heaps.

I don't know if Sorites would be delighted or horrified by this taxonomy of nearly heaps, but it would be one of the two.

And lastly, for what it's worth, the word problem for both free semiheaps and free heaps is pretty boring. I've chosen idempotent semiheaps here because they are trickier.

Sample algorithm

I'll give a sample algorithm which solves this problem. I think this is a fun challenge to solve on your own, but if you want to skip to implementing an algorithm this is for you.

This algorithm will convert the inputs to a normal form. Once we have converted both the inputs to this normal form good old structural equality will solve the remainder of the problem.
First we observe that one can fairly easily left associate the entire to the left using rules 3 and 4. In other words, any place we have [a,b,[c,d,e]] or [a,[d,c,b],e] replace it with [[a,b,c],d,e] and keep doing this until you can't any more.
At this point you have something that looks like [[[....[[[[a,b,c],d,e],f,g],...],y,z]. This is basically a list, so let's make it one. We just collect the elements in order into a list. (Note that this list will always have odd length).
Now we need to account for 5. This is simple. Find a place in the list where there is a contiguous subsequence of odd length, \$w\$, which is followed by the reverse of \$w\$, which is followed by \$w\$ again. Replace the entire subsequence (\$w\$, \$w\$ reversed, and \$w\$ again) with one single copy of \$w\$ For example if our list is [2,1,3,1,3,2,2,3,1,3,1,1,3,1,3,2,3,1,2,1] then we have [2,(1,3,1,3,2),(2,3,1,3,1),(1,3,1,3,2),3,1,2,1] and so our result after replacement is [2,1,3,1,3,2,3,1,2,1]

Repeating this replacement process until no \$w\$ exists gives our normal form. We can see how each of the rules plays into our algorithm. It should make intuitive sense why this works. I won't prove the algorithm correct though.

Test cases

TODO

Help me Warholize United Nation's Flag

Please write us a GFORTH dictionary drawing the United Nations emblem but more concise than https://en.wikipedia.org/wiki/Flag_of_t15s1515s15h15s15e_United_Nations#/media/File:UN_emblem_blue.svg/2

<svg viewBox="0 0 470 400" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" fill="#009EDC">
<path id="branch" d="m121 336c-19-16-22-39-30-59-5-13-14-24-23-35 12 34 5 58 34 82-5-2-10-6-14-9-23-19-57-22-71-53 4 23 22 43 41 56 19 12 43 11 63 18m50 12c3-1 7-1 11-2-14-2-27-7-37-16-15-14-28-28-44-39 17 34 23 48 51 54 0 0-8-1-12-2-30-6-66 2-88-23 9 16 26 29 42 35 26 8 53-1 77-7m40-2c-48 0-73 42-120 14 23 28 60 30 90 11 12-8 23-19 38-19 23 0 48 24 69 46 4-3 7-6 10-9-22-21-54-43-87-43m-135-47s-6-11-8-18c-7-27-3-60-15-86 2 15-4 28-5 42-2 19 5 32 10 41 0 0-7-9-10-14-14-22-43-37-45-64-4 59 37 75 73 99m-14-175c4-8 6-18 8-27-2 4-4 8-7 11-19 16-30 25-35 50l2-22c2-22-10-46 3-65-13 14-20 32-20 50 0 24 14 41 15 64 4-24 24-41 34-61m-7-44c9-8 20-15 28-25 9-12 17-26 29-37-16 7-34 13-45 30-6 10-7 22-12 32m-20 48c4-8 11-16 18-22 18-13 36-30 37-52-10 24-41 28-48 53 0 0 4-15 5-18 5-17 4-37 21-48-33 7-35 43-33 70 0 6 1 11 0 17m5 116s-2-19 1-27c8-24 16-50 15-75-8 30-33 40-22 81-4-8-5-17-8-25-6-22-23-41-18-67-8 23-8 41 0 65 5 18 23 31 32 48"/>
<use transform="matrix(-1,0,0,1,470,0)" xlink:href="#branch"/>
<g id="grid" stroke="#009EDC" stroke-width="4" fill="none">
<circle cx="235" cy="167" r="163"/>
<circle cx="235" cy="167" r="129"/>
<circle cx="235" cy="167" r="98"/>
<circle cx="235" cy="167" r="64"/>
<circle cx="235" cy="167" r="33"/>
<path d="m235 4v130m0 66v130m-115-278 92 92m46 46 92 92m-278-115h130m66 0h130m-278 115 92-92m46-46 92-92"/>
</g>
<g id="map" transform="matrix(.1 0 0 .1 211 140)">
<path d="m161 672c4-8 12-40 22-30s16 0 16 0 5 5 2 15c-2 10-5 20-11 22-6 1-11 5-19 6-6 1-10-13-10-13zm82-13c2-2 5 8 10 6 5-1 7 9 2 9s-5 6-5 9 0 9-4 13-7 1-12-1c-5-3-7-3-14-3-6 0-1 10-1 10s-26-1-21-5 10-5 6-8 0-5 0-10 12-3 9-6c-4-4 0-18 6-10l4-9c-4-4-1-5-9-8-7-3-1-18-1-18l1-10c2-13 27-14 29-3 1 11 0 19 0 19l7 3s-1 8-7 8 0 4-4 8zm921-608c-7 7-22 10-22 10l-5 19-8 7s2 5 0 17-17 19-17 19l-7 8s-40 2-45 0c-15-7-5-27 5-25s-2-29-2-29l13-2s2-30 7-30-2-10-8-15c-7-5-15-22-22-20s-33 0-33 0l-5 10-18 3s2 13-2 17c-10 12-48 37-32-5l5-10v-15l-30-2s-15-5-15-12-2-15-2-15l-35-39-42-5-3-8-25-3c-30-15-57-2-52 24 5 25 13 35-3 35-17 0-20-13-20-13s-13-5-13 2-5 20 0 27-7 17-12 12-18-20-15-25-23-37 3-42c27-5-2-20 8-24l13-7h13l8-7-22-3-13-2-25-2c-25 17-30 37-30 37-13 25-45-10-33-24s-37-2-45 5-33 3-33 3c-5 15-28-2-22-12 7-10 7-17 7-17l-8-2-10 19c-23 0-30 13-25 22 5 8-7-2-10 10s2 12 12 17-5 5 2 13 27 0 15 12-35 7-35 7c-2 15-33 12-37 7-3-5-28-35-28-35l-32-2c-3-24 15-12 22-30 7-19 10-49 10-49s-27-2-28 7c-2 8-18 14-18 14s-13 5-8 12-10 10-10 10 3 11-2 15c-13 14-47 2-52-3l-20-8-20-13-23 10-7 7h-25l-2 20 45 5 3 42-18-6h-12l-5-10-10-2v37l10 8 8 8 17 2 3 20 42 2 5 8 25 2 48 49-3 15-8 5c3 12-22 5-22 5v10l12 2 12 7 17-29c18-12 27 5 28 15 2 10-8 8-8 8v24l10 3c17 20-7 32-7 32l-5 17c-5 15-23 12-23 12l-7 10-20 5 39 5c4-14 14-17 19-10s5 19 5 19l10 2-2 19 10 3v54l12 13c20-8 20 5 10 12s-3 37-3 37l-8 8v14l-10 7v19c-17-8-37-5-42 0-15-10-47-7-47 2 10 13-12 17-12 17l-12 13c8 17-8 19-8 19v32l-20 19 2 44c0 12 25 13 30 7 5-7 25 14 25 14h15l3-30-10-5v-49l17-19c20-7 13 44 13 49 2 19 10 17 18 13 17-7 3 19-10 17s-5 17-5 17l8 3-15 12-13 15-17-5-20-2-7-12-12-2-2 24-8 10-20 20c27 0-3 19-10 19 15 5-2 20-40 8v12l-13 2 12 13 13 2-5 29c0 22-55 7-60 2l-2 30-10 2 2 20-2 29 18-3v12l45 2 65-69 38-8c3-17 20 3 20 3 17-2 20 10 20 10l22 3c18 5 7 7 8 14 2 10 10 7 10 7l3-22 10 2-10-12-18-8-20-8c-13-19 3-15 17-13h22s25 34 25 42 12 10 12 10l15-2 5 12h15l5 10h30l2-15-28-5-2-17-20-5c-7-29 5-37 13-24l10 2-3-25 12-3-3-35-10-3v-12l42 2c-3-22 2-32 2-32h12l2 8 51 5 36-41c-2-3 4-5 0-9-5-5-12 0-20-5s0-34-2-40c-2-7 28-17 23-2s0 22 0 22c22-20 40 2 38 7s12 10 20 5 18 15 15 25-33 8-35-2-7-7-10-2-18 8-27 3c-2-1-2-2-3-3l-36 41h2c20 12 10 27 3 30s-18 3-18 3l-3 7-43 3-3 17c-22-3-30 20-25 32s0 22 0 22l18 8 23-7c3-17 18-20 32-30 13-10 35 19 28 32s-7 19-7 19l2 15-17 7-13 7-2 8h-45l-8 8-22 2-7 10-15 2s-25 12-15 25c10 14-42 12-53-7-3 17-22 2-22 2l-18-5-2-25c-3-17-35-17-33-5s-60 5-60 5l-20 10-18 11-2 8-30 3-13 7-5-10h-13l-13 19c-35 2-68 22-65 30s-13 17-13 17l-15 5-10 15-20 7-3 35-10 7v15l-12 3v8l-17 2 10 25 13 7c23 3 13 32 13 32l13 2 7 19 13 27c5 20 20 15 27 14 7-2 13 20 13 20l66 2s-3 7 8 10c12 3 88 7 91 2-3-15 42-19 60-5 18 13 43 5 43 5l25 30 17 37 28 8 20 5 7 29 15 2 5 19c18 13-5 42-5 42v37l13 7-2 14 22 22 25 2 63 67 50 15 8 27 13-2 10-8 40-2 20-19 22-3 185-157-17-10v-37c30-22 32-61 3-64-21-3-12-25 8-29l12-5v-15l38-35v-27l-83-69c-37-13 0-94 25-93 25 2-2-125-2-125l-13-7 3-41h-18l-30 39-8 27c-3 35-106 29-111 24s-40-20-40-20-27-22-32-15-28-8-28-3-22-12-22-12l-33-12 25-5-5-20 43 22c5 7 27 5 27 5l7 8s13-2 22 8c8 10 52 2 52 2l12 10 18 7 52 2 2-32 10-10-2-20 12-10v-17l10-3 2-37 8-2v-81l-25-24c-2 8-28 8-28 8s-7 12-12 12 7 15 3 25c-3 10-17 10-17 10l-25 7-7 8h-27l-3-22 30-8 17-8 8-17c2-17 22-15 22-15s38-32 40-47 15-57 38-57h43c17-7 12-29 12-29l22-3 3 12s30 3 33-2 10-17 18-12 35-12 35-12c2-12 43-7 43-7l5-15s-28-39-33-39-32-24-35-15c-27-7-25-44-25-44l-10-24c0-14-25-42-30-39-25-19-7-40 0-42s23-25 23-25l8-24 28-8 3-22-15-2s17-30 25-30 63 0 68-3 15-30 15-35 13-7 18-8c5-2 17-15 20-22 9-17-2-59-9-52zm461 539c-1-3-2-6-5-7-7-3-20 2-26 6l6 8c6-4 15-6 16-5v-1zm43 201-10-1c-1 8 1 18 9 19l2-10s-1-4-1-8zm37-40c3 10 6 20 6 21l9-4s-4-10-6-20zm22-8v-2c0-3-1-7-3-11l-9 5c1 2 1 5 2 7 0 3 1 6 3 8 2 1 4 2 7 1l-2-10c0 1 1 1 2 2zm-85 72c7-4 16-13 15 6s-9 13-15 19-10-19 0-25zm-401 130 1-15 16 2-1 14zm1 33c-2-9-12-12-13-12l-3 10c1 0 2 1 3 2l2 9c-1 1-2 2-2 3l7 7c5-8 7-13 6-19zm-1243 312-10 9-5 4 5 4 12 8 6-8-7-5 5-4zm118 121-4 9 10 5-3 4 7 7 13-13-6-4zm-459-2170 10 10-7 7-10-10zm302 315 10 8-6 8-10-8zm-38 7 2 19h25c10 0-8-12-8-12s-20 2-19-7zm548-470-17-2-1 10 14 1 11 17 8-6-11-18-2-2zm45-354-5 9 13 8 3 2 2-2 19-12-6-8-15 10zm89 48-8-9-7 8 15 15 3-3 17-14-7-8zm-552 351c-1-6 33-7 38-2s2 14 17 14 8 10 7 15c-2 5-18 3-20-2s-27-7-27-7-13-10-15-18zm191-19c26 8 35 2 37-5s3-8 13-10-2-22-12-20-20-3-22-12c-2-8-18-30-20-13s-12 17-10 29c3 11 8 29 14 31zm165-285c-4-15-25 19-3 25 22 7 43 0 43 0l5-10 83 2c7-7 10-17 10-17s20-7 28-3c8 3 2-24-7-20-8 3-25 2-25 2h-30c-2-12-28-7-30 0-1 6-11 8-11 8l-38 3c-4 10-23 17-25 10zm3 83-22-22v-19l-7-7-7-24-22-7-22 8-23 15-25 3-13 15 53 5 10 17 38 3 25 25c23 10 28 0 15-12zm77 162 7-16 9 5-7 15zm497-17c-3-13 33-25 42-15 8 10 32 12 35 62 1 18-30-19-30-19l-25-8c-14-3-21-11-22-20zm-175 44c-5 15-7 35-15 35s-5 22-5 22 22 0 28 2c7 2 7 19 7 19 25-2 35 32 32 41-3 8 10 8 10 8s0 27-3 34 22 12 28 22c7 10-3 44-8 46s13 7 12 15c-2 8 5 0 7 14 2 13 5 42 5 42l23 2c3-22 46-23 53-20 28 10 50 54 50 64s-18 12-18 12l3 49c28 8 52 49 48 56-3 7 20 5 20 5 3-30 32-20 33-10 2 10 7 32 7 32l8 15 12 12 18-2 5 10 22 3s18 20 20 25 27 3 33 5c7 2 17 7 18 15 2 8 12 22 12 22s20 5 22 12 10 22 10 22l17 14 2 15 18 2 5 20 30-2 17-12c22-12 37-27 38-34 2-7 5-32 22-27s5-37 5-37-23-17-22-25c2-8-23-25-22-32 2-7-22-20-20-27s-12-25-12-25l-25-24-3-15-20-2-40-49 2-14-12-2v-19l-12-7-18-2-37-40-3-19h-18l3-35c12-15 5-44 5-44s-23 12-35 7 5-17 5-17v-13l-10-10s-28 3-30-2-7-27-7-27l-2-29-12-5-2-10-18 2v-20l-10-3-10-5-2-20-37-2-12-17-13-20-42-3-10-10-17-3-12-5-5 8-32 2-2 10c-14 7-80 0-82 5zm-306-10c3 5 23 10 23 10 13 0 22 10 22 15s18 3 18 3l2-12-13-17-12-8s-18-2-18-7c0-4-19 11-22 16zm0 57-13-3v15l18 2zm185 186v-13s-2-13-10-13-23-10-20-17-28-14-28-14-28-27-18-24 5-12 5-12-20 3-25 2c-5-2-3-17-3-17s-20-5-20 0 7 5 10 15 2 27 17 30 18 7 20 14 20 8 20 8l13 7zm13 45c-2-7-5-30 5-29 10 2 3 0 15 5s13-8 13-8h18l23 19-3 15-17 2c-8-13-25-8-22 3 3 12-8 34-15 35-7 2-28 2-27-8 3-10 10-34 10-34zm274 230 12-37c-17-3-13-22-13-22-2-15-25-32-33-27s-5-35-5-35 15-10 22-5-57-84-70-76-43-8-42-24c2-15-60-66-60-66s-20-13-23-3-10 17 0 22 8-8 20 3c12 12 33 27 25 37s-18 14-18 14l12 14h18l3 29s20 10 25 22 5 19 0 25c-5 7-15 19-13 30 2 12 15 17 15 17l13 2 10 5v22c13-3 35 15 33 27s3 5 20 17 12 14 23 22c11 7 21 2 26-13zm-382 216c0 5-3 12 7 14s28-7 30 3 2 17 15 22 22 7 32 7 32-3 32-3 24 4 28 8c18 19 30 24 35 15 5-8-2-27-3-34-2-7-25-39-33-32s-10 0-25 5-47 2-48-5c-2-7-25-10-25-17s-17-15-15-5-12 15-15 12c-5-4-15 10-15 10zm-83 18-2 12 18 2s8 7 8 12 12 10 18 10c7 0 25-14 25-14s8-24 2-22c-7 2-20 12-22 2s-22-5-22-5zm-86 19 5-1 3 9-5 2zm6-16 10-2 3 15-9 2zm28 2 1 10 36-1v-10zm324-8 17-2 1 10-17 2zm44 37 5-12 9 4-5 12zm145-169 17-1 1 10-17 1zm28 10h10v8h-10zm30-142-10 1-2-15 10-1zm-10 210h10v12h-10zm22 6 9 4-5 11-9-5zm-49-133c10 0-3 39 23 35 27-3 2 12 22 13 20 2 15-15 22-27s3-19-8-22c-12-3-12-3-15-17-3-13-17-17-17-17l-5-20-22 13-22 29c0 24 12 13 22 13zm65 92c13-7 42-7 40-17s17-13 17-13l5 20 15 10 2 19s5-3-13 2-7 13-7 13l-40 2-5-17zm-215 141c8-2 28-3 32 2 3 5-12 12-12 12l-20 3c-6-8-8-15 0-17zm107-15c9 9-50 7-50 0s5-30 20-25 17-30 17-30-13 2-2-5c12-7 0-17-5-22s-10-14-10-14h23c10-7 13-39 13-39 20 7 30-7 30-7s3 10 10 19c7 8-17 12-8 17 8 5 12 20 8 25-3 5-22 2-22-5s-7 8 0 17c7 8-8 20-12 20-3 0-25 3-7 14 18 10 38 5 38 5s15-2 20 7c5 8-2 10-10 10s-48-3-48-3-10 11-5 16zm194-191c-5-7-10-12-17-15s-12-7-18-7c-7 0-13-7-10-15s-5-12-5-19 5-7 13-2 7 7 13 15c7 8 10 17 17 15s12 15 18 10c7-5 5 12 5 12zm-16 16c5 7 15 12 15 19s-3 12 7 13c10 2 17-2 20 7 3 8 3 22 2 29-2 7 2 17 10 17s10 2 10 7 10-19 10-19c-8-7-15-22-15-22s-8-24-8-27-12-7-17-8c-5-2-13-17-13-17zm108 273-7-15s0-13 3-20-7-13-12-15-3-15-5-22-13-12-13-12-3-25-3-30-15-12-10-17 8-12 13-15-5-27 3-22 8 14 12 20c3 7-2 30 7 35 8 5-2 22 12 22 13 0 5 32 5 32s-3 24 5 25c8 2 3 42 3 42zm5 129 5-10 9 5-5 10zm11-55 10 1-1 14-10-2zm-21-56-13-2-30 5-17 32s8 5 15 17 10 81-10 93 2 5 2 5l-3 37c5 17 13 8 18 0s10-10 17-19c7-8 17-24 18-35 2-12 10-30 5-35s5-29 5-29 7-14 0-27c-7-14 2-29 7-35zm-73-172h-25s8 3-15-19-38 5-38 5l-27 3v27l-13 5 2 17 18-2s0 20 5 12 47 2 43 22c-1 8 42 30 37 57 22 3 17 25 17 25l28 3 8-17 8 2v-10l-18-5-3-54-12-8 3-14-13-5 7-22zm-62 414 10-4-4-8-2-6-5 3-12 7-11-7-5 9 13 8 3 2 2-2 10-5zm44-22 18 3 2-10-18-3zm-34 216c-7-10 33-27 40-7s0 17-7 15c-6-2-23 5-33-8zm-172 325h12v32h-12zm77 309c-3 13-15 20-22 15s8 8 12 15c3 7 13 7 17 0 3-7 2-22 5-29 3-6-10-8-12-1zm37 68 15 7 2 29c20 20 85 3 85-2s-3-62-3-62l-8-8-2-42c7-22-32-54-35-47s-25 2-25 8c0 7-13 40-7 52 7 12-5 12-7 24-2 10-19 30-15 41zm-468-361-5-8-14 8 6 9zm-254 33c-8 8-6 15 0 21m52 20 11-19-9-3-12 8 5 5zm-10-527c7 15 5 37 30 54 8 6-5 17-13 12s-32-42-32-42v-22c5-13 12-8 15-2zm-88 88c4 15 3-24 10-22s2-24 2-24l-30 22c14 2 16 17 18 24zm-90 108c-2 20-27 27-27 27l-18-5-10-8-2-24 15-2 3 10zm-27-204v-24l-3-22-25-12-18 17-3 24v15l-17 3-3 46-13 5 2 17-36 10-3 22-13 8-7 20-8 49s15 29 23 15c8-13 22-15 22-15l5-12 45 2c3-19 25-12 25-3 0 8 17 2 17 2l12-19h18l2-20 8-5v-30c27-8 23-34 23-34l7-8-3-12c-13-5-7-17 2-14 8 3-12-15-12-15-10 8-18-10-18-10zm-76-69-13 3-30 29-2 13-8 12-10 25-35 2-7 30 5 26 30 12 3-17 10-5 2-17 7-12 10-12 3-13 17-10 20-4 8-10 3-20 2-15 7-11 20-8v-32h-10l-2-12-18-2-4 9h-8l-2 13h10l2 11-7 6zm-528 203c0 4-3 7-7 7s-7-3-7-7 3-7 7-7 7 3 7 7zm-1 193c0 4-3 7-7 7s-7-3-7-7 3-7 7-7 7 3 7 7zm-18-28c4 0 7-3 7-7s-3-7-7-7-7 3-7 7 3 7 7 7zm-20 40-14 2v12l14-2zm15-86-12 2-1 13 13 2zm-3-91 1-12-25 17-16-10v40l26 36 10-24 4-15-12-5 2-25zm-10-142-30-3 2 12h8c13 24 2 81 2 81s-20 2-23-8-12 22-5 27 30 0 32 19 15-12 15-12zm670-334h-18l-3-37 10-7v-19h-58l-2-19 8-5-13-5-10 13-3 15-17 3v8h-12v22l-47 39-93-3c-7 15-23-2-23-2-3-10-27 0-27 0 0 19-32-8-32-8l-58-42c-33-30-83 8-85 17 2 24-38 5-38 5s-33-10-38 3-27 10-27 10l-3 7-17 3-3 10-20 3 50-2c13-2-5 29-13 27l-23 2-8 8h-22l-10 14-32-2s-18 15-17 20c2 5-3 20-8 20s-15 15-12 20-10 22-10 22l-3 17-10 3v46l-20 14v20l-30 32 3 27-25 27 3 27-15 5-3 12-7 35 17 2c8-3 7 22 0 25s-25 10-15 17-27 5-27-5-20-19-25-15c-5 3-13-15-13-15-18-19-75 2-75 2l-8 27c-18 3-30 34-30 34-15 5-27 24-22 29s-8 7-8 7v37l-8 12 2 40c10 0 8 19 8 19-17 2-13 24-13 24l-35 12-7 10-43-2-12 12-12-12h-83l-3-8-17-3-2-19-25 2-5 10-27 2c2 17-27 42-30 35s-22-25-13-29c8-3 30-7 30-7v-12l-62-2-7 10-25 2v27l-12 3c-8 5 2 24 2 24 12 12-2 30-2 30-10 10 8 29 8 29 13 3-8 13-8 13 3 17 13 22 13 22-10 17 7 25 7 25l2 29 12 7v19l7 12h27l-2-42c-23-27 20-34 22-24s20 15 20 15c3 25 32 40 40 15s15-10 20 2 37 41 37 41h25l3 24c28-2 37 2 48 40 12 39 43 49 43 49l23-2c0-20 23 3 23 14 0 10 45 49 45 49l45 10 42 34 32-3h13c8-29 48 2 52 12 3 10 30 27 33 19s22-3 25 22 15 20 15 20l95-2 33-29 85-2c43-2 17-61 8-61-15-12 5-61 5-61l-121-113c-28 0-3-41-3-41 22-14-5-35-5-35 3-20-12-44-12-44-30-20-22-59-22-59v-27c-25-24 10-27 10-27 12-20-8-35-8-35l-2-22-27-3-3-79-60-86c-12-3-3-24-3-24 15-8-3-29-3-29l-2-37 35-3 8-13h17l-2-44c8-22 28-10 28-10l23 2 13-25 3-20-18-2c-20-12-10-56-10-56 32-47 68-20 68-20l23-2c35 24 3 67 3 67-7 10-3 42-3 42l8 54-22 19c-18 10-18 34 2 39 13 2 8 34-12 12-30 0 17 27 3 20 30 15 23-13 23-13l40-32c15-12 42 25 42 30s66 2 66 2c18 12 25 42 25 42 18-24 57-2 28 12 27 17 27 32 27 32 22-7 22 10 22 15s7-25 7-25c-25-19 33-25 17 8l-10 15 17 13 2 39c37-3 27-49 27-49l17-3c0-15 12-7 12-7-12-57 27-67 27-67 22-5 23-51 23-51-15-7-7-30 10-10s-10-41-10-41l-13-12-18-2-2-19h-30l-5 24-11 5-3-7-5 19h-30l-2-20 18-5 7-10 5-27h22l28-8c2-29 17-22 17-22l25 20 2 10-10 5-2 14 5 19h13c5-27 40-27 50-10l10-24c-23-12 0-30 6-22 7 8 22-22 22-22s12 15 0-5 8-30 8-30c-3-20 22-17 22-17l2-27-23-2c-5 24-25 3-15-2s20-15 20-15v-17l10-3 2-17h25l22-10 5-8 23-2 33-30-3-13c-20 0 0-15 0-15zm-903 1517-13-20 20 3 21 18 9 22-12 7-7-10-16-5zm-367-506 8 23 12 9 11 25-6 12-19-17-13-19-7-15-11-30zm-100-90h-8v17h13v22h10l-2-25-13-5zm1308-1028 10-2 2 10-10 2zm12-6 3-10 13 4-2 10zm24-10 1-10-11-2-2 10zm17-22h13v10h-13zm85 12 1-10 12 1-2 10zm33 7 1-10-12-2-1 10zm12 1h13v10h-13zm15 17v12l10-1v-12z"/>
</g>
</svg>

Golf every byte in Dis

code-golf

Write 256 programs in Dis language (Ben Olmstead, 1998) that: for each n-th program (where n is 0-indexed), output a byte n while not outputting anything else and halt. None of your program may use input command character } as a command. Your environment has 8 bits as a byte: outputting a byte more than 255 means outputting x%256 for value x.

Example program to output a byte 0:

{!

Example program to output a byte 239:

|{!

Scored with sum of each program length. Shortest programs wins.

Meta

Language-specific challenge.

Program for generate all functions from two sets

If A and B are two sets (so two list that have no repetition where order is not important), a set f is a function if and only if

1. f is a subset of AxB
2. if x∊A than exist one only element y∊B with (x,y)∊f

Write one program or function that if the input are the sets A and B, return as output all the functions from A to B.

The program or function that wins is the one that has length of less bytes.

Example

if the input is A={1,2,3} and B={1} the output, the set of all functions froma A to B should be

 ( ((1,1),(2,1),(3,1)) )

if the input is A={1,2,3} and B={1,2} the output, the set of all functions froma A to B should be

(    
 ((1,1),(2,1),(3,1)),
 ((1,2),(2,2),(3,2)),   
 ((1,1),(2,1),(3,2)),
 ((1,1),(2,2),(3,1)),
 ((1,2),(2,1),(3,1)),
 ((1,2),(2,2),(3,1)),
 ((1,2),(2,1),(3,2)),
 ((1,1),(2,2),(3,2))
)

if the input is A='ab' and B='cd' the output, the set of all functions froma A to B should be

┌4──────────────────────────────────────────────────────┐
│┌2──────────┐ ┌2──────────┐ ┌2──────────┐ ┌2──────────┐│
││┌2──┐ ┌2──┐│ │┌2──┐ ┌2──┐│ │┌2──┐ ┌2──┐│ │┌2──┐ ┌2──┐││
│││ ac│ │ bc││ ││ ac│ │ bd││ ││ ad│ │ bc││ ││ ad│ │ bd│││
││└───┘ └───┘2 │└───┘ └───┘2 │└───┘ └───┘2 │└───┘ └───┘2│
│└∊──────────┘ └∊──────────┘ └∊──────────┘ └∊──────────┘3
└∊──────────────────────────────────────────────────────┘

it seems that the output has to have as number of elements the number |B|^|A|, where |A| is the number of elements of A and |B| is the number of element of B.

[N]th Quarter Language Jam, [Year] popularity-contestlanguage-design

For this challenge, you'll be designing and implementing a new language! Read the rules below, then view the spoiler for the theme:

[theme here, eg: lost]

Rules:

• A submission must meaningfully reflect the theme in at least 2 of the following (with explanation as to why and how):
  1. Syntax / surface structure
  2. Execution model / semantics
  3. Memory model
  4. Control flow
  5. Data representation
  6. Error handling / failure modes
• In addition to this, your language will have to follow a restriction which is updated along with the theme. This is obligatory to be followed among all answers. For this challenge, the restriction is

[restriction here, eg: must be deterministic]

• There are two deadlines present in this challenge. The first, on [roughly 3 months after posting] is the deadline for answer submissions. Answers are allowed after this, but they will not be contenders for winning this month's challenge. The second deadline, [roughly 4 months after posting], will be the deadline by which answers will (hopefully) have accumulated enough votes to mitigate the FGITW effect and later answers get a fairer chance to win. I will select the highest voted answer on this deadline, complying with these rules.
• For this challenge, valid contenders will have to be accompanied by a proof of their Turing-completeness. You have time until the second deadline to provide this. If your answer was supposed to be the winner, following all the other rules, but supplied with a proof after the winner was decided, you can ping me in The Nineteenth Byte to update the winner.
• An implementation in any language (interpreter/compiler) should be provided in your answer.
• Answers cannot be pre-existing languages. For example, if the theme was lost, you cannot submit Lost as an answer.
• Please document the implemented features, or at the very least link to an external source providing this. To showcase the utility of your language, write two programs in it that would be valid answers to the Hello World! and Is this number a prime? challenges, following our I/O defaults. If your language doesn't support any of the I/O methods, use whatever it natively has.

Voting:

As mentioned before, answers must contain features themed across any two (or even more) characteristics as mentioned in rule #1. This is a popularity contest, where most net votes wins, and so the onus is on the voter to decide the winner of this challenge. No one can force you to vote any way they want, but here are some guidelines for you to follow when voting:

• How significant is the connection to the theme, especially while considering the themed features of this language?
• How usable is this language (especially in the service of code-golf, fastest-code, etc. don't pigeonhole yourself into just golfing)?

and so on. If you're here just to vote, please do so only after the first deadline, so that you can compare all the contenders and give them all an equal chance at receiving your vote and winning. You're still free to post your languages, but do note they will not be contending to win. What's more important is that you vote for the languages you deem most creative, and maybe even post some answers in them to other challenges...

Good luck and have fun!

\$b^k\$-repeat Numbers

code-golfsequenceintegermath

Repdigits are numbers that are composed of only the same digit, such as \$555\$ or \$888888888\$.

The above Wikipedia link provides a formula: $$\frac{\left(\left(n\cdot\left(10^{\left\lfloor\log_{10}\left(n\right)\right\rfloor+1}+1\right)\right)-n\right)^k-n^k}{\left(\left(n\cdot\left(10^{\left\lfloor\log_{10}\left(n\right)\right\rfloor+1}+1\right)\right)-2\cdot n\right)\cdot n^{\left(k-2\right)}}$$ where \$n\$ is the digit to be repeated and \$k\$ is the number of repetitions. The article notes that this formula does not produce valid repdigits for \$n\ge10\$, and instead provide non-digit numbers concatenated with themselves. These "invalid repdigits", for example \$2323232323\$, we will here call "repeat numbers".
Note: For the purposes of this challenge, repdigits are considered repeat numbers!

A \$b^k\$-repeat number is then a number which is a number concatenated with itself \$k\$ times in the base \$b\$. The number above, \$2323232323\$, is a \$10^5\$-repeat number (the 23rd, in fact), and \$2925\$ is a \$2^4\$-repeat number, as its base-2 representation is \$101101101101_2\$, the string \$101\$ repeated 4 times.

The Challenge:

As this is a sequence challenge, you may do any one of the following:

• Given three inputs b k and n, output the \$n\$th \$b^k\$-repeat number.
• Given three inputs b k and n, output the first \$n\$ \$b^k\$-repeat numbers.
• Given two inputs b and k, output \$b^k\$-repeat numbers indefinitely.

You may assume that b k and n are all integers, that \$b\ge2\$, and that \$n\$ and \$k\ge1\$. You may take inputs in any order and in any convenient format. Output can be in any convenient format, but please specify if it is not simply output as an integer. Standard loopholes forbidden. Standard code-golf scoring.

Test Cases:

The following test cases take three inputs in the order b, k, n and output the \$n\$th \$b^k\$-repeat number.

10,  5, 23 -> 2323232323
 2,  4,  5 ->       2925
 4,  6,  3 ->       4095
99,  1,  1 ->          1
10,  1, 50 ->         50
 2, 10,  1 ->       1023

Meta

Open to criticism and suggestions, especially with the test cases.

It's entirely possible that this (or a challenge like it) is already up, but I wasn't able to find it. Also please let me know if these numbers have a more established name, or if you think a better one (or just better notation) is called for.

Play Beggar My Neighbor

Pretty-print a table

Objective

Given an ASCII string that encodes a table in the format defined below, pretty-print it using Unicode box-drawing characters.

Input format

The input format identifies the cells of the table using ASCII control characters, namely \v (vertical tab; 0x0B), \t (horizontal tab; 0x09), and \f (form feed; 0x0C), as follows:

• \v declares a new row and its first cell.
• \t appends a new cell to the row it's in.
• \f ends the table.

Note that each cell may contain \n (line feed; 0x0A).

It is assumed that:

• All inputted characters other than these control characters are in the code range of (space; 0x20)—~(tilde; 0x7E).
• All involved control characters are used where they're intended as above, and nowhere else. (So the inputted string must start with a \v and end with a \f.)

Otherwise flexible.

Output format

The row separators and the column separators of the inputted table is printed using the Unicode characters ─│┌┐└┘├┤┬┴┼ (U+2500, U+2502, U+250C, U+2510, U+2514, U+2518, U+251C, U+2524, U+252C, U+2534, and U+253C).

The widths and the heights of the cells are chosen to be as smallest as they can accommodate all their contents, while the cells in each row must have the same height and the cells in each column must have the same width. For this purpose, the 0x20 ASCII space is used to fill the "vacant spaces".

Note that the rows may have different numbers of cells, depending on the number of its \t.

It is assumed that:

• Each row has height of at least one.
• The font printing the output is monospaced.

Otherwise flexible.

Examples

"Input"
Output

"\vHello, world!\f"
┌─────────────┐
│Hello, world!│
└─────────────┘

"\vThe quick brown fox\tjumps over\tthe lazy dog.\f"
┌───────────────────┬──────────┬─────────────┐
│The quick brown fox│jumps over│the lazy dog.│
└───────────────────┴──────────┴─────────────┘

"\vThe quick brown fox\tjumps over\vthe lazy dog.\f"
┌───────────────────┬──────────┐
│The quick brown fox│jumps over│
├───────────────────┼──────────┘
│the lazy dog.      │
└───────────────────┘

"\vThe quick brown fox\vjumps over\tthe lazy dog.\f"
┌───────────────────┐
│The quick brown fox│
├───────────────────┼─────────────┐
│jumps over         │the lazy dog.│
└───────────────────┴─────────────┘

"\vThe quick brown fox\njumps over\tthe lazy dog.\f"
┌───────────────────┬─────────────┐
│The quick brown fox│the lazy dog.│
│jumps over         │             │
└───────────────────┴─────────────┘

"\vThe quick brown fox \njumps over\tthe lazy dog.\v\f"
┌────────────────────┬─────────────┐
│The quick brown fox │the lazy dog.│
│jumps over          │             │
├────────────────────┼─────────────┘
│                    │
└────────────────────┘

"\v\t\v\t\f"
┌┬┐
│││
├┼┤
│││
└┴┘

"\v \t\n\f"
┌─┬┐
│ ││
│ ││
└─┴┘

posted