text:
Golf the smallest circle!
The problem:
Given a non-empty set of points in the Cartesian plane, find the smallest circle that encloses them all (Wikipedia link).
This problem is trivial if the number of points is three or less (if there's one point, the circle has a radius of zero; if there are two points, the line segment that joins the points is the diameter of the circle; if there are three (non-colinear) points, it's possible to get the equation of a circle that touches them all if they form a non-obtuse triangle, or a circle that touches only two points and encloses the third if the triangle is obtuse). So, for the sake of this challenge, the number of points should be greater than three.
The challenge:

Input: A list of 4 or more non-colinear points. The points should have X and Y coordinates; coordinates can be floats. To ease the challenge, no two points should share the same X coordinate.
For example: [(0,0), (2,1), (5,3), (-1,-1)]
Output: A tuple of values, (h,k,r), such that \$(x-h)^2 + (y-k)^2 = r^2\$ is the equation of the smallest circle that encloses all points.

Rules:

You can choose whatever input method suits your program.
Output should be printed to STDOUT or returned by a function.
"Normal", general-purpose, languages are preferred, but any esolang is acceptable.
You can assume that the points are not colinear.
This is code-golf, so the smallest program in bytes wins. The winner will be selected one week after the challenge is posted.

Please include the language you used and the length in bytes as header in the first line of your answer: # Language: n bytes

Test cases:

1:

Input: [(-8,0), (3,1), (-6.2,-8), (3,9.5)]
Output: [-1.6, 0.75, 9.89]

2:

Input: [(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
Output: [-1.73, 0.58, 11.58]

3:

Input: [(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
Output: [5.5, -4, 7.5]

4:

Input: [(6,6), (-6,7), (-7,-6), (6,-8)]
Output: [0, -0.5, 9.60]

Happy golfing!!!

Related challenge:

Area of a 2D convex hull

Link to sandbox post

“if there are three (non co-linear) points, it's possible to get the equation of a circle that touches them all”—but that may not be the smallest enclosing circle. For the three vertices of an obtuse triangle, the smallest enclosing circle is the one whose diameter is the longest side.

@Arnauld Same as you. For test case 2, I get center (-1.73, 0.58) and for test case 3 (5.5, -4).

@Arnauld thanks for your comment. I have edited the post accordingly

@Arnauld oops, sorry. Indeed. Aldo, correcting with your observations

Wolfram Language (Mathematica), 28 27 bytes
#~BoundingRegion~"MinDisk"&

Try it online!
Built-ins are handy here. Output is a disk object with the centre and radius. Like others, I’ve found the 2nd and 3rd test cases to be different to the question.
Thanks to @lirtosiast for saving a byte!
If a list is required as output, this can be done in 35 bytes (at the cost of an additional 8 bytes). Thanks to @Roman for pointing this out.

I was expecting a Mathematica built-in. But I wasn't expecting Mathematica to have "disk objects".

36 bytes to get the output format right: Append@@BoundingRegion[#,"MinDisk"]&

13.3 adds the built-in CircumscribedBall

JavaScript (ES6),  298 ... 243  242 bytes
Returns an array [x, y, r].
p=>p.map(m=([c,C])=>p.map(([b,B])=>p.map(([a,A])=>p.some(([x,y])=>H(x-X,y-Y)>r,F=s=>Y=(d?((a*a+A*A-q)*j+(b*b+B*B-q)*k)/d:s)/2,d=c*(A-B)+a*(j=B-C)+b*(k=C-A),r=H(a-F(a+b),A-F(A+B,X=Y,j=c-b,k=a-c)))|r>m?0:o=[X,Y,m=r]),q=c*c+C*C),H=Math.hypot)&&o

Try it online!
or see a formatted version
How?
Method
For each pair of points \$(A,B)\$, we generate the circle \$(X,Y,r)\$ whose diameter is \$AB\$.
$$X=\frac{A_x+B_x}{2},\;Y=\frac{A_y+B_y}{2},\;r=\sqrt{\left(\frac{A_x-B_x}{2}\right)^2+\left(\frac{A_y-B_y}{2}\right)^2}$$
For each triple of distinct points \$(A,B,C)\$, we generate the circle \$(X,Y,r)\$ which circumscribes the triangle \$ABC\$.
$$d=A_x(B_y-C_y)+B_x(C_y-A_y)+C_x(A_y-B_y)$$
$$X=\frac{({A_x}^2+{A_y}^2)(B_y-C_y)+({B_x}^2+{B_y}^2)(C_y-A_y)+({C_x}^2+{C_y}^2)(A_y-B_y)}{2d}$$
$$Y=\frac{({A_x}^2+{A_y}^2)(C_x-B_x)+({B_x}^2+{B_y}^2)(A_x-C_x)+({C_x}^2+{C_y}^2)(B_x-A_x)}{2d}$$
$$r=\sqrt{(X-A_x)^2+(Y-A_y)^2}$$
For each generated circle, we test whether each point \$(x,y)\$ is enclosed within it:
$$\sqrt{(x-X)^2+(y-Y)^2}\le r$$
And we eventually return the smallest valid circle.
Implementation
In the JS code, the formula to compute \$(X,Y)\$ for the triangle's circumscribed circle is slightly simplified. Assuming \$d\neq0\$, we define \$q={C_x}^2+{C_y}^2\$, leading to:
$$X=\frac{({A_x}^2+{A_y}^2-q)(B_y-C_y)+({B_x}^2+{B_y}^2-q)(C_y-A_y)}{2d}$$
$$Y=\frac{({A_x}^2+{A_y}^2-q)(C_x-B_x)+({B_x}^2+{B_y}^2-q)(A_x-C_x)}{2d}$$
This way, the helper function \$F\$ requires only two parameters \$(j,k)\$ to compute each coordinate:

\$(B_y-C_y,\;C_y-A_y)\$ for \$X\$
\$(C_x-B_x,\;A_x-C_x)\$ for \$Y\$

The third parameter used in \$F\$ (i.e. its actual argument \$s\$) is used to compute \$(X,Y)\$ when \$d=0\$, meaning that the triangle is degenerate and we have to try to use the diameter instead.

maybe writing a Newton-type numerical optimizer is shorter...

Do you have a proof of correctness? I can see that this is a plausible approach, but more than that seems to require quite a bit of work.

@PeterTaylor The algorithm is mentioned on Wikipedia: a naive algorithm solves the problem in time O(n^4) by testing the circles determined by all pairs and triples of points. But unfortunately, there's no link to a proof.

Will it meet problem of precision making there no solution?

@l4m2 I suppose it could happen. But I think that this consensus applies in that case.

@Arnauld If you need some strange numbers to reach, I may say that's fine; If it even fail in easy situation that may be a problem

R, 59 bytes
function(x)nlm(function(y)max(Mod(x-y%*%c(1,1i))),0:1)[1:2]

Try it online!
Takes input as a vector of complex coordinates. Mod is the distance (modulus) in the complex plane and nlm is an optimization function: it finds the position of the center (output as estimate) which minimizes the maximum distance to the input points, and gives the corresponding distance (output as minimum), i.e. the radius. Accurate to 3-6 digits; the TIO footer rounds the output to 2 digits.
nlm takes a numeric vector as input: the y%*%c(1,1i) business converts it to a complex.

Jelly, 100 98 bytes
_²§½
1ịṭƊZIṚṙ€1N1¦,@ṭ@²§$µḢZḢ×Ø1œị$SḤ÷@P§
ZṀ+ṂHƲ€_@Ç+ḷʋ⁸,_²§½ʋḢ¥¥
œc3Ç€;ŒcZÆm,Hñ/$Ʋ€$ñ_ƭƒⱮṀ¥Ðḟ⁸ṚÞḢ

Try it online!
In contrast to my Wolfram language answer, Jelly needs quite a lot of code to achieve this (unless I’m missing something!). This full program takes the list of points as its argument and returns the centre and radius of the smallest enclosing circle. It generates circumcircles for all sets of three points, and diameters for all sets of two points, checks which include all of the points and then picks the one with the smallest radius.
Code for the make_circumcircle bit was inspired by code at this site, in turn inspired by Wikipedia.

I don't understand this code, but rather than diameters and circumcircles separately, could you generate all sets of three points with duplicates and filter out the lists of three identical points?

Python 2 (PyPy), 244 242 bytes
P={complex(*p)for p in input()}
Z=9e999,
for p in P:
 for q in{p}^P:
	for r in{p}^P:R,S=1j*(p-q),q-r;C=S.imag and S.real/S.imag-1jor 1;c=(p+q-(S and(C*(p-r)).real/(C*R).real*R))/2;Z=min(Z,(max(abs(c-t)for t in P),c.imag,c.real))
print Z[::-1]

Try it online!
This uses the brute-force O(n^4) algorithm, iterating through each pair and triangle of points, calculating the centre, and keeping the centre that needs the smallest radius to enclose all points. It calculates the circumcentre of 3 points via finding the intersection of two perpendicular bisectors (or, if two points are equal it uses the midpoint with the third).

Welcome to PPCG! Since you are using Python 2, you can save 1 byte by converting the two spaces on the 5th line to a tab.

P={x+y*1j for x,y in input()} saves 2 bytes as well.

APL(NARS), 348 chars, 696 bytes
f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

This is one 'implementation' of formulas in Arnauld solution...Results and comments:
  s1 (¯8 0)(3 1)(¯6.2 ¯8)(3 9.5)
¯1.6 0.75  9.885469134
  s1 (7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
¯1.732305109 0.5829680042  11.57602798
  s1 (0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
5.5 ¯4  7.5
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)
0 ¯0.5  9.604686356
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
2 ¯1.5  11.67261753
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)(7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
1.006578947 ¯1.623355263  12.29023186
  s1 (1 1)(2 2)(3 3)(4 4)
2.5 2.5  2.121320344
  ⎕fmt s3 (1 1)(2 2)(3 3)(4 4)
┌0─┐
│ 0│
└~─┘

f: finds the combination of alpha ojets in the omega set
f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

((X,Y), r) from now represent one circonference of radius r and center in (X Y).
c: finds if the point in ⍺ is inside the circumference ((X Y) r) in ⍵ (result <=0) ot it is external (result >0)
In the case of circumference input in ⍵ it is ⍬ as input, it would return 1 (out of circumference)
each possible input in ⍺.
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}

p: if ⍵ is an array of ((X Y) r); for each of the ((X Y) r) in ⍵
writes 1 if all points in the array ⍺ are internal to ((X Y) r) otherwise writes 0
NB Here's something that do not goes because I had to round to epsilon= 1e¯13.
in other words in limit cases of points in the plane (and probably built on purpose)
it is not 100% solution insured
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}

s2: from 2-point in ⍵, it returns the circumference in the format ((X Y) r)
that has diameter in those 2 points
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}

s3: from 3 points it return the circumference in the format ((X Y) r) passing through those three points
If there are problems (for example points are aligned), it would fail and return ⍬.
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}

note that -.× find the determinant of a matrix nxn and
  ⎕fmt ⊃{⍵,1}¨(¯8 0)(3 1)(¯6.2 ¯8)
┌3─────────┐
3 ¯8    0 1│     |ax  ay 1|
│  3    1 1│   d=|bx  by 1|=ax(by-cy)-bx(ay-cy)+cx(ay-by)=ax(by-cy)+bx(cy-ay)+cx(ay-by)
│ ¯6.2 ¯8 1│     |cx  cy 1|
└~─────────┘

s: from n points in ⍵, it finds the type circumferences of those found by s2 or those of type s3
that contain all n points.
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}

s1: from the set found from the s above calculates those that have minimum radius and returns
the first one that has minimal radius. The three numbers as arrays
(the first and second coordinates are the coordinates of the center, while the third is the
radius of the circumference found).
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

Python 212 190 bytes
This solution is incorrect, and I have to work now so I do not have time to fix it.
a=eval(input())
b=lambda a,b: ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
c=0
d=1
for e in a:
    for f in a:
        g=b(e,f)
        if g>c:
            c=g
            d=[e,f]
print(((d[0][0]+d[1][0])/2,(d[0][1]+d[1][1])/2,c/2))

Try it online!
I figured out which two points are furthest and then I generated an equation for a circle based off those points!
I know this isn't the shortest in python, but it's the best I could do! Also this is my first attempt at doing one of these, so please be understanding!

This can be golfed some more. For example, you can shorten if g>c:\n c=g\n d=[e,f] to if g>c:c=g;d=[e,f], saving you a lot of whitespace. I don't think you need to initialise d beforehand, also using two variables and E,F=e,f in line 10 will make your print a lot shorter.  I think a solution with max and a list comprehension would be even shorter than two loops, but I might be wrong.
Sadly, however, your solution is not correct. For the points (-1,0), (0,1.41), (0.5, 0), (1,0) your solution computes a circle around 0 with radius 1. But the point (1, 1.41) is not in that circle.

Welcome! Thank you for your answer. As pointed in the comment above, your solution is not correct. A hint for brute-force solution: The smallest possible circle touches either two points or three points. You can start calculating the equation for the circle that touches each pair of points and check if there's one that encloses all points. Then calculate the equation for the circle that touches each triplet of points and check if there's one that encloses all points. Once you get all the possible circles, select the one with the smallest radius.

Alright I'm gonna try to make it work, and then I will update the answer. I need to figure out how to check if a point is contained in a circle.

Once you have the center and radius of the circle, check if the distance between the center and each point is less than or equal to the radius; if that condition is true for all points, that circle is a candidate


text:
Prime parity peregrination
The purpose of this challenge is to graphically depict a walk on the plane, where the direction of each step \$k\$ is determined by the primality of \$k\$ and the parity of its binary expansion. Specifically,

Initial direction is fixed, say North.
All steps have the same length.
The direction of step \$k\$ can be North, West, South or East, and is determined as follows:

If \$k\$ is not prime, the direction does not change.
If \$k\$ is prime and the binary expansion of \$k\$ has an even number of ones, turn right.
If \$k\$ is prime and the binary expansion of \$k\$ has an odd number of ones, turn left.

As a worked example, assume that the initial direction is North. The first steps are:

\$k=1\$ is not prime. So we move one step in the current direction, which is North.
\$k=2\$ is prime, and its binary expansion, 10, has and odd number of ones. So we turn left, and are now facing West. We move one step in that direction.
\$k=3\$ is prime, and its binary expansion, 11, has and even number of ones. So we turn right, and are now facing North. We move one step in that direction.
\$k=4\$ is not prime. So we move one step in the current direction, which is North.

The challenge
Input: positive integer \$N\$.
Output: plot of the \$N\$-step walk as defined above.
Additional rules

The initial direction can be freely chosen (not necessarily North), but should be the same for all \$N\$.
The turning rule can be the opposite to that described above, that is, turn right for odd parity and left for even; but it has to be the same for all \$N\$.
The output has to be a graphical depiction of the walk. For instance:

The walk can be drawn with line segments.
The visited points can be shown with a marker, such as a dot; with or without connecting line segments.
A two-colour raster image can be provided, with one colour corresponding to visited points and another for non-visited.

The scales of the horizontal and vertical axes need not be the same. Also axis labels and similar elements are optional. As long as the walk can be clearly seen, the plot is valid.
Note that some points are visited more than once. The plot is not sensitive to this. For instance, if line segments are shown in the plot, each unit segment is displayed the same no matter how many times it has been traversed.
The code should work for any N given unlimited resources. It is acceptable if in practice it fails for large N due to time, memory or data-type limitations.
Input and output are flexible as usual. In particular, any of the standard means for outputting images can be used.
The shortest code in bytes wins.

Test cases
The following plots use North as initial direction; even parity turns right; and the walk is depicted with line segments.
N = 7:

N = 3000:

N = 20000:

N = 159000:

N = 1200000:

N = 11000000:

Is there a reason only [graphical-output] is allowed? Any reason in particular to disallowed ASCII output, like my now deleted Charcoal answer?

@Kevin I was advised once not to mix both in the same challenge... What do others think?

Well, I can understand the reasoning behind that advice, since output as image/graph vs ASCII art is completely different in some languages. Then again, I have seen graph outputs getting loads of upvotes in ASCII-art challenges and vice-versa, so I guess not everyone agrees. Personally I think it really depends on the challenge. In this case I personally don't see any harm in allowing both in the same challenge, but maybe I'm biased due to my now deleted answer. So I'll ask the same question as you: "What do others think?" @Arnauld Maybe you should post your ASCII Taxi Driver after all ;)

@KevinCruijssen Yes, perhaps a good compromise is to post another similar challenge for ASCII art.

Would be interesting to see this run on various OEIS sequences (true, some would just walk in a straight line or run in circles, but some could be quite something).

@Draco18s Yup. I tried a few things and many give nice looking paths

@LuisMendo out of curiosity, is this your invention, or is this a studied sequence?

@Jonah I came up with it (but there are similar walks that are probably well known; see for example here). I wanted a random-looking but reproducible walk. And I wanted it change direction not too often. So primes came to mind (random-looking, not too abundant). Also I wanted for it to change direction left or right with the same probability. The parity of a prime number is obviously not useful for this. So parity of the sum of binary digits was a natural choice

At N=11000000, it appears to be approximating the map of Europe.

@DigitalTrauma Also, https://chat.stackoverflow.com/transcript/message/46585109#46585109

@DigitalTrauma This phenomenon is known as pareidolia. That said, I do agree that it looks like a map of Europe. ;)

Sledgehammer 0.4, 22 20 bytes
⢂⡐⠥⡄⠡⢒⣩⣀⣼⡝⢄⡎⣛⠅⡉⣱⡆⢀⡠⣽

Decompresses into this Wolfram Language function:
ListPlot[AnglePath[Array[If[PrimeQ@#, ArcSin[(-1)^ThueMorse@#], 0] &, #]]]

Ungolfed
First we define a function that returns the angle to turn at each step:
If[PrimeQ[#],
    ArcSin[(-1)^ThueMorse@#],
    0
]&

ThueMorse is the parity of the sum of binary digits. We use -1^(...) rather than 2*...-1 for a slightly complicated reason: Wolfram Language automatically converts arithmetic expressions in source to a canonical form, so expressions like 2/x are stored as Times[2, Power[x, -1]]. This makes the frequency of Power very high, and thus compressing it very cheap.
(Multiplying by Boole@PrimeQ@ is slightly longer, and implicit Boole casting of Booleans had not been implemented at the time of the challenge.)
From here, Mathematica's AnglePath and ListPlot do exactly what we need:
ListPlot[AnglePath[Array[%, #]]]&

In the interactive app, output is a rescalable vector Graphics object.

Cool! I got down to 77 bytes by combining our solutions. Cheers!

MATL, 25 24 21 bytes
Q:qJyZpbB!sEq*^YpYsXG

Try it at MATL online
Thanks @LuisMendo for a nice golfing session in chat that ultimately led to this 21 byte version, by suggesting Eq*^
Explanation
Q:q % Push 0:n
J   % Push 1i for later use.
y   % Duplicate 0:n from below
Zp  % Vector result of isprime()
b   % Bubble 0:n from bottom of stack
B!s % Sum of bits in binary representation
Eq  % Double minus one to get an odd number
*   % Multiply by isprime result to get either zero or aforementioned odd number
^   % Exponentiate 1i by an odd number or zero to get -i, 1 or i (corresponding to left turn, straight ahead, right turn).
Yp  % Cumulative product to get a vector of directions
Ys  % Cumulative sum to get vector of positions
XG  % Plot

Example for \$k=12345\$:

Wolfram Language (Mathematica), 98 96 91 77 76 63 bytes
ListPlot@AnglePath@Array[Pi/2If[PrimeQ@#,2ThueMorse@#-1,0]&,#]&

-14 bytes: Thanks to @lirtosiast for showing me how to use AnglePath...
-13 bytes: ...and ThueMorse!
usage example:
%[20000]

Step-by-step explanation:

If[PrimeQ@#, 2 ThueMorse@# - 1, 0] & is a function that takes the step index and returns 0 for non-primes, -1 for even-binary primes, and +1 for odd-binary primes. ThueMorse@# replaces the previous solution's Total[#~IntegerDigits~2] (which is the same, modulo 2).
Array[Pi/2*%,#] makes a list of this function with the index going from 1 to the function argument (20000 in the example), and multiplies every element by π/2 to make it into a direction-change angle (radians). We now have 0 for non-primes, -π/2 for even-binary primes, and +π/2 for odd-binary primes.
AnglePath[%] converts this list of direction-change angles into a path. This instruction replaces the previous solution's double-use of Accumulate.
ListPlot[%] converts the list of positions into a XY dot plot. If a line is preferred, use ListLinePlot instead. These plotting functions have lots of options to make the plots look better.

C (gcc), 179 bytes
o;i;d;k;h;f(n,p)char*p;{h=2*n+1;memset(p,0,h*h);p+=h--*n+n;*p=1;for(d=k=0;k++<n;){for(i=1;k%++i%k;);for(o=k;o/2;o=o/2^o&1);i==k?d+=o*2+3:0;p+=(d%2*h+1)*((d&2)-1);*p=1;}return++h;}

Try it online!
A function. First argument is N, second argument is an allocated buffer of size at least \$4 n^2 + 4 n + 1\$ bytes. A square image is written to this buffer, its side length is returned. In the image, 0 is a white pixel, 1 is a black pixel.
C (gcc), 219 bytes
o;i;d;k;h;f(n,p)char*p;{h=2*n+1;p+=sprintf(p,"P1 %d %d ",h,h);memset(p,48,h*h);k=h--*n+n;*(p+2*k+1)=0;p+=k;*p=49;for(d=k=0;k++<n;){for(i=1;k%++i%k;);for(o=k;o/2;o=o/2^o&1);i==k?d+=o*2+3:0;p+=(d%2*h+1)*((d&2)-1);*p=49;}}

Try it online!
A function. First argument is N, second argument is an allocated buffer of size at least \$4 n^2 + 4 n + 2 \times \lfloor log_{10}(2n+1)\rfloor + 9\$ bytes. A square image in PBM format is written to the buffer.
Cropped output for 20000:

Both versions start with west and turn right on odd, left on even.
I tried the larger testcases with neither of them, as the output with 20000 was ~1.5 GB, and 150000 would have been ~90GB. This is all stored in memory while the program executes.
Explanation of the upper one:
o;         /* Temporary variable for calculating parity */
i;         /* Temporary variable for primality test */
d;         /* d % 4 = direction */
k;         /* Step */
h;         /* height/width of image */
f(n,p)char*p;{ /* Function taking int and char pointer */
  h=2*n+1;     /* Image sidelength = 2 * N + 1, so N in each direction */
  memset(p,0,h*h); /* Reset buffer */
  p+=h--*n+n;  /* Position p at image center; decrement h */
  *p=1;        /* Put a dot at center */
  for(d=k=0;   /* Set direction and step to 0 */
    k++<n;){   /* Loop over [1..N] */
    for(i=1;k%++i%k;); /* Primality test */
    for(o=k;o/2;o=o/2^o&1); /* Parity test */
    i==k?d+=o*2+3:0; /* Change direction if necessary */
    p+=(d%2*h+1)*((d&2)-1); /* Move according to direction */
    *p=1; /* Set pixel to black */
  }
  return++h; /* Add 1 back to h and return */
}

I don't think requiring that an allocated buffer be provided as an argument is allowed - per meta policy, any extra input must be empty (which I'd interpret to mean 0 or null pointer in the case of C).

I'm interpreting this as saying I can expect it to be allocated. This is also a pattern used in many standard library functions, such as sprintf.

Ah okay, you're right, that makes sense.

162 bytes

MATL, 31 30 28 26 bytes
J4:^0i:Zpl_G:B!s^*hYs)YsXG

3 Bytes saved thanks to @LuisMendo
2 Bytes saved thanks to @Sanchises
Try it at MATL Online
Explanation
This solution uses complex numbers to represent the X and Y components of the 2D plane
J      % Push the literal complex number 0 + 1j to the stack
4:     % Create the array [1, 2, 3, 4]
^      % Raise 0 + 1j to each power in the array, [1, 2, 3, 4]

At this point, we have four points ((0, 1), (-1, 0), (0, -1), (1, 0)) in an array represented by complex numbers. These are the four cardinal directions. Now we want to use these to "walk".
Essentially the way that this works is that we start heading in the zero'th direction (the 0'th element of the array which is (-1, 0)). For each step, we need to determine the change in this heading. We will use integers to track this change. If we want to turn "right", we increment this integer by 1 (referencing the next element in the 4-point array) and if we want to go "left", we decrement this integer by 1 (referencing the previous element in the 4-point array). If we want to continue on our path, we keep the integer value constant (referencing the same element in the 4-point array).
This part of the code creates an array of all of those 0, -1, and 1 values.
0      % Push a literal 0 to the stack (the starting point)
i      % Explicitly grab the input (N)
:      % Create an array from 1...N
Zp     % Determine if each element is a prime (1) or not (0)
l_     % Push the literal -1 to the stack
G      % Explicitly grab the input again (N)
:      % Create an array from 1...N
B      % Convert to binary representation (each row is the binary representation of
       % each element in the vector)
!      % Transpose
s      % Sum down the columns to count number of 1's
^      % Raise the -1 to each element. For odd number of 1's in the
       % binary expansion this yields -1, and even yields 1

*      % Multiply this -1 or 1 by the result of the prime check (element-wise).
       % For non-primes this yields a 0, for primes with an even number of 1's in
       % the binary representation this is a 1, and for primes
       % with an odd number of 1's in

h      % Horizontally concatenate with the initial 0

Now we have an array of the differences between successive integers so we can compute the cumulative sum of those up to get the indices which we can then use to lookup the direction at each step in the original 4-element array.
Conveniently, MATL has wrap-around indexing such that index 5 wraps around to the beginning of a 4-element array. We can use this to our advantage so that we can increment and decrement this integer without worrying about the fact that the reference direction array is only 4 elements.
Ys     % Compute the cumulative sum
)      % Use this to modularly index into the original array of four points

Now we have an array of directions of steps takes, so we can compute the cumulative sum of these directions to trace out the path that was taken.
Ys     % Compute the cumulative sum
XG     % Plot as a 2D plot

Perl 6, 213 182 bytes
{my @p=[\+] [\*]({{.is-prime??.base(2).comb(~1)%2??i!!-i!!1+0i}(++$)}...*)[^$_];{"<svg viewBox='{.min xx 2,.elems xx 2}'>>.&{"L{.re} {.im}"}}' fill='none' stroke='black'/>"}(minmax |@p».reals)}
{{"<svg viewBox='{{.min,.min,+$_,+$_}(.minmax)}'><path d='{"L"X~$_}' fill='none' stroke='red'/></svg>"}(([\+] [\*]({-{.is-prime*.base(2).comb(~1)R**-1||i}(++$)i}...*)[^$_])».reals)}

Try it online!
(Really managed to pare this one down!)
This function outputs in SVG format.

{ -{ .is-prime * .base(2).comb(~1) R** -1 || i }(++$)i } ... * is an infinite sequence of direction changes for each step, in the form of complex numbers, where 1 means "continue in the same direction," i means "turn left," and -i means "turn right."
[^$_] limits that sequence to the number of steps provided as the function's argument.
[\*] scans that sequence with (complex) multiplication, turning the list of relative direction changes into a list of absolute directions.
[\+] scans that sequence with (complex) addition, producing a list of the visited coordinates.
».reals converts that list of complex numbers into two-element lists of its real and imaginary parts.

The SVG image is just one single path element.
Output (converted to PNG) for N = 20000:

LOGO, 177 171 bytes
to d:c
if :c%2[rt 180
make"c:c-1]if:c<1[stop]d:c/2
end
to p
if:c>1[make"f 2
repeat:c-2[if:c%:f<1[stop]make"f:f+1]rt 90
d:c]end
to g:n
make"c 1
repeat:n[p
fw 2
make"c:c+1]end

To use, do something like this:
reset
pu
fw 100
pd
g 3000

Sorry, but I wasn't able to capture sample output. Explanation:
to d:c
if :c%2[rt 180
make"c:c-1]if:c<1[stop]d:c/2
end

This is a recursive procedure which rotates 180° for every set bit in its parameter, which effectively computes the parity of its binary expansion.
to p
if:c>1[make"f 2
repeat:c-2[if:c%:f<1[stop]make"f:f+1]rt 90
d:c]end

This is a very basic primality test. After special-casing 1, the procedure early returns if a factor is found. If however the current value is found to be prime, it turns right, and then uses the above procedure to change that into a left turn as appropriate.
to g:n
make"c 1
repeat:n[p
fw 2
make"c:c+1]end

This is just a simple loop to test all the numbers up to n for primality and to move two pixels after each one.

Sadly the link no longer works but you can paste the code into this online interpreter.

C, 321 bytes
a,b,A,B,k,p,e,i,t,r;g(n,c,d,x,y,X,Y){x=y=Y=r=0;X=1;for(k=0;k++<=n;){r|=x==c&y==d;a=x<a?x:a;A=x>A?x:A;b=y<b?y:b;B=y>B?y:B;for(p=1,i=k;--i;p=p*i*i%k);for(e=1,i=k;i;e=-e)i&=i-1;if(p)t=X,X=-e*Y,Y=e*t;x+=X;y+=Y;}}f(n,x,y){A=a=B=b=0;g(n);printf("P1%d %d ",A-a+1,B-b+1);for(y=b;y<=B;++y)for(x=a;x<=A;++x)g(n,x,y),putchar(48+r);}

Try it online!
I started working on this before the other C answer was posted, but I figured I might as well post mine as well anyway. This one is a lot longer, but it also crops the output image to the dimensions of the result automatically.
Function is called as f(n), and output is to stdout in netpbm format.
Example output for n=1000:

a,b,A,B,          // used to store x range [a,A] and y range [b,B]
k,p,e,i,t,        // temp variables used in g
r;g(n,c,d,        // takes n + coordinates, sets r to whether (c,d) is visited
x,y,X,Y){         // temp variables - position (x,y) and velocity (X,Y)
x=y=Y=r=0;X=1;    // initialization
for(k=0;k++<=n;){ // loops k over the step number
r|=x==c&y==d;     // set r to 1 if current coordinate is the requested one
a=x<a?x:a;A=x>A?x:A;b=y<b?y:b;B=y>B?y:B;    // update bounds
for(p=1,i=k;--i;p=p*i*i%k);                 // prime test
for(e=1,i=k;i;e=-e)i&=i-1;                  // parity test
if(p)t=X,X=-e*Y,Y=e*t;                      // if prime, turn accordingly
x+=X;y+=Y;}}      // move position in direction of velocity
f(n,x,y){         // main function; x and y are temp variables
A=a=B=b=0;g(n);   // obtain accurate bounds
printf("P1 %d %d\n",A-a+1,B-b+1);           // output netpbm header
for(y=b;y<=B;++y)for(x=a;x<=A;++x)          // loop through all coordinates
g(n,x,y),putchar(48+r);}                    // output 1 if visited, 0 otherwise

The prime test is essentially the one used in Lynn's answer to a different challenge, which relies on Wilson's theorem.
The parity test uses an adaptation of Kernighan's bit-counting method.
Since the prime test is very slow, and the algorithm re-runs the entire path generation function for each pixel drawn, any input much higher than 1000 times out on TIO.

308 bytes

Jelly, 41 bytes
B§ḂḤ’×ıµ1Ẓ?€×\ÄŻÆiZ_Ṃ$€Z‘ḞŒṬµẈḢ⁾P1,;Lṭ@FK

Try it online!
Full program that takes a single argument \$N\$ and outputs a 1-bit PBM to STDOUT. Takes some inspiration from @Sanchises MATL answer. Starts off going South and turns left on odd bit parity.
Sample output for \$N=3000\$:

If ASCII Art were permissible, here’s an alternative 29-byte variant which yields (for \$N=300\$):
0000000000000000000000111110000000000
0000000000000000000000100010000000000
0000001110000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000000000100010000000000
0000001010000000111111111010000000000
0000001010000000100000101010000000000
0000001111111110100000101010000000000
0000000000100010100000101010000000000
0000000000111111100000101010001111111
0000000000000010000000101010001000001
0000000000000011100010101010001000001
0000000000000000100010101010001000001
0000111111100000100011111111111111111
0100100000100000100010001010001000001
0110100000111111100011111111111000111
0010100000000000000010101010000000101
1111100000000000000010101110000000101
1010000000000000000010100000000000101
1010000000000000000011111111111011101
1010000000000000000000100000001010101
1110000000000000000000111111101111101
0000000000000000000000000000100010101
0000000000000000000000000000100010101
0000000000000000000000000000100010101
0000000000000000000000000000111111111
0000000000000000000000000000000010100
0000000000000000000000000000000010100
0000000000000000000000000000000010100
0000000000000000000000000000000011100

JavaScript - 675 668 660 632 556 534 Bytes
First time here on CodeGolf, initially started with ~1500 Bytes Code. Golfed it to less than half nearly more than a third of it. Feel free to continue golfing. Bytes Counted with: this tool
Principle:
Draws into fixed size canvas with N and variable stroke length as input.
Edits:
-07 Bytes - remove of missed if
-08 Bytes - change switch to if/else
-28 Bytes - change to tenary if/else
-76 Bytes - shorter prime test (runtime / 3)
-22 Bytes - use this prime function (runtime * 4)
Golfed Code:
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}

Ungolfed code with whitespaces:
function f(e,r){
    for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){

        // prime and odd/even check
        n=iP(a)?iO(a)?1:2:0;

        var u=i,c=f;

        t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));

        o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),
        i=u,f=c // renew old cords
    }
}

// check prime
function iP(h){
    for(i=n=h;n%--i;);
    return(1==i)
}

// check binary expression even/odd
function iO(e){
    for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)
        "1"==r[n]&&t++;
    return t%2!=0
}

Examples:

N = 7 - Length = 60

f(7, 60);
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
<canvas id="d" width="1900" height="900"/>

N = 3000 - Length = 4

f(3000, 4);
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
<canvas id="d" width="1900" height="900"/>

N = 20000 - Length = 2

f(20000, 2);
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
<canvas id="d" width="1900" height="900"/>

N = 159000 - Length = 1

f(159000, 1);
function f(e,r){for(var t=0,n=0,i=950,f=450,o=document.getElementById("d").getContext("2d"),a=1;a<=e;a++){n=iP(a)?iO(a)?1:2:0;var u=i,c=f;t==0?(t=0==n?(c=f-r,0):1==n?(u=i-r,1):(u=i+r,3)):t==1?(t=0==n?(u=i-r,1):1==n?(c=f+r,2):(c=f-r,0)):t==2?(t=0==n?(c=f+r,2):1==n?(u=i+r,3):(u=i-r,1)):(t=0==n?(u=i+r,3):1==n?(c=f-r,0):(c=f+r,2));o.beginPath(),o.moveTo(i,f),o.lineTo(u,c),o.stroke(),i=u,f=c}}function iP(h){for(i=n=h;n%--i;);return(1==i)}function iO(e){for(var r=(e>>>0).toString(2),t=0,n=0;n<r.length;n++)"1"==r[n]&&t++;return t%2!=0}
<canvas id="d" width="1900" height="900"/>

Color depends on amount of overlapping lines? Cool!

I did not change the stroke style, this should be default black with no pattern or transparancy.
Found here.
Why there might happen a color change could be related to the stroke width I set in the second parameter my function is taking @val. Sorry to maybe disappointing you.

Red, 515 480 471 bytes
-1 byte thanks to Kevin Cruijssen!
func[n][a: 270 x: t: u: v: w: 0 y: 1
b: copy[line 0x0 0x1]repeat i n - 1[p: on
j: i + 1 repeat k i / 2[if j%(k + 1)= 0[p: off]]if p[s: 0
until[if j% 2 = 1[s: s + 1](j: j / 2)< 1]a: a + pick[-90 90]s% 2 + 1]append b 'line
append b as-pair x y x: x + cosine a y: y - sine a append b as-pair x y t: min x t
u: max x u v: min y v w: max y w]c: 500 /(max u - t w - v)view[base white 502x500
draw collect[foreach k b[keep either pair? k[as-pair k/1 - t * c k/2 - v * c][k]]]]]

A significant part of the code (~160 bytes) deals with normalizing the coordinates so that the graphics fits entirely in the canvas regardless of the size of the input.
Initial direction: South.
Here's the result for n = 3000

n = 20000

Out of curiosity, why aren't there any spaces required for the modulos at if j%(k + 1) and if j% 2 = 1, but there are spaces required for most of the other operators (+, /, etc.). Can the space also be removed at the modulo of pick[-90 90]s% 2? Actually, why also aren't there any spaces required at as-pair k/1 - t * c k/2 - v * c for the /?

@KevinCruijssen Yes, the space can be removed for s% 2, thanks! I don't know why, but modulo % is the only operator for which the space in front of it can be dropped, if preceded by a word (variable).  In as-pair k/1 - t * c k/2 - v * c the slashes / serve completely different purpose - they are paths. k is a pair and k/1 is the first element (it can be selected also by k/x, or pick k 1). Spaces are needed almost everywhere, the exceptions are around ()[]{}, beacuse there is no ambiguity.

@KevinCruijssen Most symbols can be used in word names (Red doesn't have variables, everything is either a word or value (or some syntax block like [...] or (...)). So: a*4: 45 -> a word a*4 is assigned a value 45.
% is used as a marker for the file! datatype and maybe that's why it can't be used in word names but can break the rules for the other arithmetic operators.

Ah ok, that makes sense that the / have a different purpose there and the symbols can be used without spaces in variables (or words as they are apparently called for Red). Thanks for the explanation. :) And glad I could (mostly accidentally) save a byte for the s% 2. :)

Processing , 140+ bytes
void f(int N){for(int x,y,i,l,d,k=d=y=x=0;k++<N;d+=i<l?0:Integer.bitCount(k)%2*2-1,d&=3,point(x-=~-d%2,y+=(d-2)%2))for(i=1,l=k;0<l%++i%l;);}

Might not fulfill clearly seen

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

sort: votes


text:
Write the shortest O(n^2) sorting algorithm
Write a sorting algorithm for a list of integers that has an average performance of O(n^2).
This is code-golf, so the shortest code in bytes wins.
RULES:

The characters wasted for the declaration of the list are not counted
(e.g. var c = new List<int>() { 4, 2, 1, 3 }; is not counted)

Builtins to sort a list are not allowed.

The best I did in C# is 82 ('c' is the list to be sorted):
var n=c.ToList();for(int i=0;i<n.Count;i++){int x=c.Min();c.Remove(x);n[i]=x;}c=n;

@AdmBorkBork notable difference is disallowing bogosort and not counting the list declaration, whatever that means.

Welcome to Code Golf Stack Exchange! Since you're new, we do typically recommend using The Sandbox to get feedback on a challenge to make sure it's up to our usual standards or isn't a duplicate of an existing challenge; I think I'd agree with @AdmBorkBork that this really doesn't add much to the existing challenge and should be closed as a duplicate.

Also, for the sake of being self-contained it should probably supply a definition of sorting.

This might be better received if you ask us to golf a specific sorting algorithm. Asking a question of the form "Do this thing but not this way" is generally ill-received (In this case restricting the use of a specific algorithm). Additionally there are other challenges that already ask for a golfed sorting such as the one AdmBorkBork linked. Because of that, this will likely get closed as a duplicate since, as Giuseppe mentioned, this challenge isn't really adding anything interesting over those challenges.

And if bogosort and variants thereof are to be excluded then a rigorous definition of bogosort variant is probably warranted. I feel like p≤₁ in Brachylog is probably not in the spirit of that rule, but it complies with the letter.

@AdmBorkBork I edited the question to clarify it.

Generally on CGCC the code is a full program or function, and input and output are accepted with the default I/O rules.

This challenge was reopened after Bip edited it the first time. Can the folks who closed it again please at least comment to add more context about why it was put on hold again?

"an average performance of O(n^2)" isn't exactly clear, since big-O refers to worst-case time complexity, not average case. Also, perhaps the question should clarify input methods, because the example one uses variable assignment, which we don't generally allow.

Jelly, 5 bytes
ṭ@Ṣ¥/

Try it online!
Jelly's sort builtin Ṣ is too fast, so we had to slow it down a bit, via using it as part of a slower sorting algorithm rather than using it directly. (This algorithm doesn't sort the original list with a builtin, which is what the question banned at the time this answer was written.)
Explanation
ṭ@Ṣ¥/
    /  One element at a time,
ṭ@     append that element to the list so far
   ¥   and
  Ṣ    sort the resulting list

Jelly's sort algorithm (which, behind the scenes, is Python's sort algorithm) is O(n) on lists that have only one element out of place, thus this implements an O(n²) sorting algorithm (specifically insertion sort).

The asker has specified average complexity, of which Python's is $nlog(n)$

@JoKing Do not be confused with Big Theta. Big O only requires a less than relationship. but do not have to be equal.

@tsh Ah sorry, I was assuming ais523 was taking the best case O(n) as the average case, though rereading I see this is addressed in the second explanation

Aw come on, @tsh. You knew what he meant. Typically when people talk about big o in programming they mean big theta. It doesn't mean nearly as much when I say my bubble sort has a big o of n^n

@Poke But it is hard to say O(n^2) since you can do something like foreach (val1 in arr) foreach (val2 in arr) sleep(1); arr.quickSort();. It do be O(n^2) but meaningless.

@Abigail: At the time I wrote this answer, that restriction was worded differently and didn't exclude the first answer here (as it doesn't sort the original list with a builtin). I'll delete the second answer, though, as that pretty clearly violates the requirement of the question.

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Two palindromes are not enough
Some numbers, such as \$14241\$, are palindromes in base 10: if you write the digits in reverse order, you get the same number.
Some numbers are the sum of 2 palindromes; for example, \$110=88+22\$, or \$2380=939+1441\$.
For other numbers, 2 palindromes are not enough; for example, 21 cannot be written as the sum of 2 palindromes, and the best you can do is 3: \$21=11+9+1\$.
Write a function or program which takes integer input n and outputs the nth number which cannot be decomposed as the sum of 2 palindromes. This corresponds to OEIS A035137.
Single digits (including 0) are palindromes.
Standard rules for sequences apply:

input/output is flexible
you may use 0- or 1- indexing
you may output the nth term, or the first n terms, or an infinite sequence

(As a sidenote: all integers can be decomposed as the sum of at most 3 palindromes.)
Test cases (1-indexed):
1 -> 21
2 -> 32
10 -> 1031
16 -> 1061
40 -> 1103

This is code-golf, so the shortest answer wins.

Isn't infinite output also a standard option for sequences?

@UnrelatedString Yes, I'll allow that as well.

Related

@Abigail Given positive integer n, print n-th member of sequence OEIS An? Sounds promising...

@Abigail What's interesting about this is that without any packing just writing out the OEIS identity is nearly as long as the current Jelly answer. For many questions it's actually longer to write the OEIS code.

@Nit let's define a new OEIS sequence as a(n) = the nth OEIS sequence that can be expressed in less characters than the most golfed Jelly function that generates that sequence.

JavaScript (ES6),  93 83 80  79 bytes
Saved 1 byte thanks to @tsh
Returns the \$n\$th term, 1-indexed.
i=>eval("for(n=k=1;k=(a=[...k+[n-k]+k])+''!=a.reverse()?k-1||--i&&++n:++n;);n")

Try it online!
How?
Given \$n\$, we test whether there exists any \$1\le k\le n\$ such that both \$k\$ and \$n-k\$ are palindromes. If we do find such a \$k\$, then \$n\$ is the sum of two palindromes.
The trick here is to process \$k\$ and \$n-k\$ at the same time by testing a single string made of the concatenation of \$k\$, \$n-k\$ and \$k\$.
Example:
For \$n=2380\$:

we eventually reach \$k=1441\$ and \$n-k=939\$
we test the string "\$1441\color{red}{939}1441\$" and find out that it is a palindrome

Commented
NB: This is a version without eval() for readability.
i => {                       // i = index of requested term (1-based)
  for(                       // for loop:
    n = k = 1;               //   start with n = k = 1
    k =                      //   update k:
      ( a =                  //     split and save in a[] ...
        [...k + [n - k] + k] //     ... the concatenation of k, n-k and k
      ) + ''                 //     coerce it back to a string
      != a.reverse() ?       //     if it's different from a[] reversed:
        k - 1                //       decrement k; if the result is zero:
          || --i             //         decrement i; if the result is not zero:
            && ++n           //           increment n (and update k to n)
                             //         (otherwise, exit the for loop)
      :                      //     else:
        ++n;                 //       increment n (and update k to n)
  );                         // end of for
  return n                   // n is the requested term; return it
}                            //

i=>eval("for(n=k=1;k=(s=[...k+[n-k]+k])+''!=s.reverse()?k-1||i--&&++n:++n;);n") 79 bytes

Instead of i=>eval("..."), ES6 allows you to use i=>eval\...``, saving 2 bytes

Also, if no return is specified, eval defaults to the last expression evaluated, so you can remove the ;n at the end.

@VFDan The back-tick trick doesn't work with eval() because it doesn't coerce its argument to a string. Removing ;n would lead to a syntax error and removing just n would cause the function to return undefined.

Jelly,  16 10  9 bytes
-1 byte thanks to Erik the Outgolfer. Outputs the first \$n\$ terms.
2_ŒḂƇ⁺ṆƲ#

Try it online!
I tried to come up with different idea compared to my original approach. Let's review the thinking process:

Initially, the test worked as follows: It generated the integer partitions of that number, then filtered out those that also contained non-palindromes, then counted how many length-2 eligible lists there were. This was obviously not too efficient in terms of code length.
Generating the integer partitions of \$N\$ and then filtering had 2 main disadvantages: length and time efficiency. To solve that issue, I thought I shall first come up with a method to generate only the pairs of integers \$(x, y)\$ that sum to \$N\$ (not all arbitrary-length lists) with the condition that both numbers must be palindrome.
But still, I wasn't satisfied with the "classic way" of going about this. I switched approaches: instead of generating pairs, let's have the program focus on idividual palindromes. This way, one can simply compute all the palindromes \$x\$ below \$N\$, and if \$N-x\$ is also palindrome, then we're done.

Code Explanation

2_ŒḂƇ⁺ṆƲ# – Monadic link or Full program. Argument: n.
2       # – Starting at 2*, find the first n integers that satisfy...
 _ŒḂƇ⁺ṆƲ  – ... the helper link. Breakdown (call the current integer N):
    Ƈ     – Filter. Creates the range [1 ... N] and only keeps those that...
  ŒḂ      – ... are palindromes. Example: 21 -> [1,2,3,4,5,6,7,8,9,11]
 _        – Subtract each of those palindromes from N. Example: 21 -> [20,19,...,12,10]
     ⁺    – Duplicate the previous link (think of it as if there were an additional ŒḂƇ
            instead of ⁺). This only keeps the palindromes in this list.
            If the list is non-empty, then that means we've found a pair (x, N-x) that
            contains two palindromes (and obviously x+N-x=N so they sum to N).
      Ṇ   – Logical NOT (we're looking for the integers for which this list is empty).
       Ʋ  – Group the last 4 links (basically make _ŒḂƇ⁺Ṇ act as a single monad).

* Any other non-zero digit works, for that matter.

Jelly, 11 bytes
⁵ŻŒḂ€aṚ$EƲ#

Try it online!
The full program roughly works like this:

Set z to the input.
Set x to 10.
Set R to [].
For every integer k from 0 up to and including x, check whether both k and x - k are palindromic.
If all elements of L are equal (that is, if either all possible pairs that sum to x have both their elements palindromic, or all such pairs have at most one of their elements be palindromic), set z to z - 1 and append x to R.
If z = 0, return R and end.
Set x to x + 1.
Go to step 4.

You may suspect that step 5 doesn't actually do the job it should. We should really not decrement z if all pairs that sum to x are palindromic. However, we can prove that this will never happen:
Let's first pick an integer \$k\$ so that \$10\le k\le x\$. We can always do so, because, at step 2, we initialize x to be 10.
If \$k\$ isn't a palindrome, then we have the pair \$(k,x-k)\$, where \$k+(x-k)=x\$, therefore not all pairs have two palindromes.
If, on the other hand, \$k\$ is a palindrome, then we can prove that \$k-1\$ isn't a palindrome. Let the first and last digits of \$k\$ be \$D_F\$ and \$D_L\$ respectively. Since \$k\$ is a palindrome, \$D_F=D_L>0\$. Let the first and last digits of \$k-1\$ be \$D'_F\$ and \$D'_L\$ respectively. Since \$D_L>0\$, \$D'_L=D'_F-1\ne D'_F\$. Therefore, \$k-1\$ isn't a palindrome, and we have the pair \$(k-1,x-(k-1))\$, where \$(k-1)+(x-(k-1))=k-1+x-k+1=x\$.
We conclude that, if we start with setting x to a value greater than or equal to 10, we can never have all pairs of non-negative integers that sum to x be pairs of palindromes.

Ah, beat me too it - first n terms saves 1 byte (I went for STDIN and ŻŒḂ€aṚ$Ṁ¬µ#

@JonathanAllan Oh LOL didn't expect that. Anyway, somebody beat us both. :D

For the proof, couldn't you just take the pair $(10, x-10)$, and use the fact that $10$ is not a palindrome? Then the proof is one line.

@RobinRyder Yes, that's also possible. My proof is a generalization that contains this case as well ($11$ is a palindrome).

R, 115 111 bytes
-4 thanks to Giuseppe
function(n,r=0:(n*1e3))r[!r%in%outer(p<-r[Map(Reduce,c(x<-paste0),Map(rev,strsplit(a<-x(r),"")))==a],p,'+')][n]

Try it online!
Most of the work is packed into the function arguments to remove the {} for a multi-statement function call, and to reduce the brackets needed in defining the object r
Basic strategy is to find all palindromes up to a given bound (including 0), find all pairwise sums, and then take the n-th number not in that output.
The bound of n*1000 was chosen purely from an educated guess, so I encourage anyone proving/disproving it as a valid choice.
r=0:(n*1e3)can probably be improved with a more efficient bound.
Map(paste,Map(rev,strsplit(a,"")),collapse="")is ripped from Mark's answer here, and is just incredibly clever to me.
r[!r%in%outer(p,p,'+')][n]reads a little inefficient to me.

111 bytes just by rearranging a couple things.

Haskell, 68 67 63 bytes
[n|n<-[1..],and[p a||p(n-a)|a<-[0..n]]]
p=((/=)=<<reverse).show

Returns an infinite sequence.
Collect all n where either a or n-a is not a palindrome for all a <- [0..n].
Try it online!

Retina, 135 102 bytes
K`0
"$+"{0L$`\d+
*__
L$`
<$.'>$.`>
/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{0L$`\d+
*__
))L$`
<$.'>$.`>
0L`\d+

Try it online! Too slow for n of 10 or more. Explanation:
K`0

Start off by trying 0.
"$+"{

Repeat n times.
0L$`\d+
*__

Convert the current trial value to unary and increment it.
L$`
<$.'>$.`>

Create all pairs of non-negative integers that sum to the new trial value.
/<((.)*.?(?<-2>\2)*(?(2)$)>){2}/{

Repeat while there exists at least one pair containing two palindromic integers.
0L$`\d+
*__
))L$`
<$.'>$.`>

Increment and expand the trial value again.
0L`\d+

Extract the final value.

Perl 5 -MList::Util=any -p, 59 55 bytes
-3 bytes thanks to @NahuelFouilleul
++$\while(any{$\-reverse($\-$_)==reverse}0..$\)||--$_}{

Try it online!
Note: any could be replaced by grep and avoid the -M command line switch, but under the current scoring rules, that would cost one more byte.

small improvement, -3bytes, using while instead of redo

And took one more off of that by eliminating the + after the while.

C# (Visual C# Interactive Compiler), 124 bytes
n=>{int a=0;for(string m;n>0;)if(Enumerable.Range(0,++a).All(x=>!(m=x+""+(a-x)+x).Reverse().SequenceEqual(m)))n--;return a;}

Try it online!

05AB1E, 15 12 bytes
°ÝDʒÂQ}ãOKIè

-3 bytes thanks to @Grimy.
0-indexed.
Very slow, so times out for most test cases.
Try it online or verify the first few cases by removing the Iè.
Much faster previous 15 byter version:
µNÐLʒÂQ}-ʒÂQ}g_

1-indexed.
Try it online or output the first \$n\$ values.
Explanation:
°Ý              # Create a list in the range [0, 10**input]
  D             # Duplicate this list
   ʒÂQ}         # Filter it to only keep palindromes
       ã        # Take the cartesian product with itself to create all possible pairs
        O       # Sum each pair
         K      # Remove all of these sums from the list we duplicated
          Iè    # Index the input-integer into it
                # (after which the result is output implicitly)

µ               # Loop until the counter variable is equal to the (implicit) input-integer
 NÐ             #  Push the loop-index three times
   L            #  Create a list in the range [1, N] with the last copy
    ʒÂQ}        #  Filter it to only keep palindromes
        -       #  Subtract each from N
         ʒÂQ}   #  Filter it again by palindromes
             g_ #  Check if the list is empty
                #   (and if it's truthy: increase the counter variable by 1 implicitly)
                # (after the loop: output the loop-index we triplicated implicitly as result)

12: °LDʒÂQ}ãOKIè (there's probably a better upper bound than 10^x for speed). I guess ∞DʒÂQ}ãOK is technically a 9, but it times out before the first output.

@Grimy Not sure if cartesian product works lazy-loaded on infinite lists. Anyway, as for the 12-byter, it's unfortunately incorrect. It does filter out integers that can be formed by summing 2 palindromes, but not integers that are palindromes themselves. Your sequence (without the trailing Iè) goes like: [1,21,32,43,54,65,76,87,98,111,131,141,151,...] but is supposed to go like [*,21,32,43,54,65,76,87,98,201,1031,1041,1051,1052,...] (the first 1/* can be ignored since we use 1-indexed input).

@Grimy Hmm, I guess a straight-forward fix is changing the 1-based list L to 0-based.. :)

J, 57/60 bytes
0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]

Try it online!
The linked version adds 3 bytes for a total of 60 in order to save as a function that the footer can call.
In the REPL, this is avoided by calling directly:
   0(](>:^:(1 e.q e.]-q=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~] 1 2 10 16 40
21 32 1031 1061 1103

Explanation
The general structure is that of this technique from an answer by Miles:
(s(]f)^:[~]) n
          ]  Gets n
 s           The first value in the sequence
         ~   Commute the argument order, n is LHS and s is RHS
        [    Gets n
      ^:     Nest n times with an initial argument s
  (]f)         Compute f s
         Returns (f^n) s

This saved a few bytes over my original looping technique, but since the core function is my first attempt at writing J, there is likely still a lot that can be improved.
0(](>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)^:[~]
0(]                                                 ^:[~] NB. Zero as the first term switches to one-indexing and saves a byte.
   (>:^:(1&e.p e.]-p=:(#~(-:|.)&":&>)&i.&>:)^:_)&>:)      NB. Monolithic step function.
                                                 >:       NB. Increment to skip current value.
   (>:^: <predicate>                        ^:_)          NB. Increment current value as long as predicate holds.
                   p=:(#~(-:|.)&":&>)&i.&>:               NB. Reused: get palindromes in range [0,current value].
                       #~(-:|.)&":&>                      NB. Coerce to strings keeping those that match their reverse.
                 ]-p                                      NB. Subtract all palindromes in range [0,current value] from current value.
    >:^:(1&e.p e.]-p                                      NB. Increment if at least one of these differences is itself a palindrome.

That's an old format of mine, combining other tricks I learned since then produces a 41 char solution: 1&(_:1&((e.((*&(-:|.)&":"0>:)&i.-))+])+)*

Python 3, 107 bytes
p=lambda n:str(n)!=str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=all(p(k)+p(m-k)for k in range(m))
 return m

Try it online!
Inverting the palindrome checking saved 2 bytes :)
For reference the straight forward positive check (109 bytes):
p=lambda n:str(n)==str(n)[::-1]
def f(n):
 m=1
 while n:m+=1;n-=1-any(p(k)*p(m-k)for k in range(m))
 return m

Red, 142 bytes
func[n][i: 1 until[i: i + 1 r: on repeat k i[if all[(to""k)= reverse
to""k(s: to""i - k)= reverse copy s][r: off break]]if r[n: n - 1]n < 1]i]

Try it online!
Returns n-th term, 1-indexed

APL(NARS), 486 bytes
r←f w;p;i;c;P;m;j
p←{k≡⌽k←⍕⍵}⋄i←c←0⋄P←r←⍬
:while c<w
    i+←1
    :if   p i⋄P←P,i⋄:continue⋄:endif
    m←≢P⋄j←1
    :while j≤m
         :if 1=p i-j⊃P⋄:leave⋄:endif
         j+←1
    :endwhile
    :if j=m+1⋄c+←1⋄r←i⋄:endif
:endwhile

What is the word for break the loop? It seems it is ":leave", right?
{k≡⌽k←⍕⍵} in p is the test for palindrome.
This above function in the loop store all the palindrome found in the set P,
if for some element w of P is such that i-w is in P too
this means that the i is not right and we have increment i. Results:
  f 1
21
  f 2
32
  f 10
1031
  f 16
1061
  f 40
1103
  f 1000
4966
  f 1500
7536


text:
A quine of sorts
Given a string x, output the characters in x sorted according to the order of appearance in your source code.
Examples
Source: ThisIs A Test
 Input: Is it a Test?
Output: TissI   etta?

Source: Harry - yer a wizard.
 Input: I'm a what?
Output: aa  wh'?Imt

Source: Mr. H. Potter, The Floor, Hut-on-the-Rock, The Sea
 Input:
Output:

Rules

Standard loopholes & i/o rules apply
Input & output can be either a string, a list of characters, or a list of bytes.
If a character is used multiple times in the source, use the first occurrence.
If one or more characters does not appear in the source, they should be at the end; their order does not matter, nor does it have to be consistent.
Source must be non-empty
Newlines are treated the same as other characters.
The order in which the code is executed doesn't matter; just the raw string.
The input is in the same encoding as the code.
The input is sorted by characters, not by bytes.
Sorting is case sensitive
This is code-golf, so shortest answer in bytes for each language wins!

let f = (s, i, o) => o.split("").map(x => [x, s.indexOf(x) == -1 ? s.length + 100 : s.indexOf(x)]).sort(([, a], [, b]) => a - b).map(([x]) => x).join("") === o && i.split("").sort().join("") === o.split("").sort().join("");let g = (s, i) => i.split("").map(x => [x, s.indexOf(x) == -1 ? s.length + 100 + Math.random() : s.indexOf(x)]).sort(([, a], [, b]) => a - b).map(([a]) => a).join("");$(() => $("button").click(() => $("#result").text(f($("#source").val(), $("#input").val(), $("#output").val()) ? "Valid" : `Invalid; example output: \`${g($("#source").val(), $("#input").val())}\``)));
body,label{display: flex;flex-direction: column;}*{white-space: pre;font-family: Inconsolata, Consolas, mono-space;font-size: 14px;}
Source: <textarea id="source">ThisIs A Test</textarea>Input: <textarea id="input">Is it a Test?</textarea>Output: <textarea id="output">TissI   etta?</textarea>
<button>Validate</button>

Do unprintable characters need to be accounted for? And if not, what about whitespace?

@negativeseven Any characters from the source code encoding need to be accounted for, including whitespace.

related

You should probably make explicit mention in the spec that matching is case sensitive.

Can we get x encoded in UTF-8 or UTF-16 if our solution isn't encoded in Unicode at all, and the Unicode characters in x represent characters in the solution's code page? For example, some golfing languages use custom code pages to reduce their byte count but still be readable with the naked eye.

@Erik No, the input is in whatever encoding the source code is in, including custom code pages.

If that was allowed, a golfing language answer could probably be a no-op, because none of the characters in the source are in UTF-8.

@tjjfvi I'm not talking about no-ops here (which would be certainly invalid); at least a few of the answers below, instead of taking input in plain bytes (0x00-0xFF), take the input as the UTF-8 string that the byte sequence would represent (e.g. when we post an answer, we usually post the UTF-8 version of our code, not the hexdump), and then use the UTF-8 representation of the source code to sort the input. Is this allowed? I feel like it should be an option too (alongside the plain byte stream), because otherwise solutions in golfing languages with custom codepages would be hindered greatly.

@tjjfvi This is my understanding: We should write some source-code (which is some bytes) and we may use a code-page (which encodes those bytes as some string of characters - whether that be UTF-8 or UTF-16 or ASCII or ...) and running our code must sort an input composed solely of characters that appear on the aforementioned code-page according to their position in the encoded source-code and output that string of characters. We then score our submission by the byte length of the source-code (in bytes, not in whatever encoding is used to display the characters). Is my understanding correct?

@Jonathan Yes, that is correct.

@Erik If the source is valid in encoding X, and is given in encoding X, then it may only handle characters in encoding X. The encoding used by the interpreter etc. is irrelevant.

+1 for "Harry - yer a wizard."

Python 3.8 (pre-release), 102 100 96 85 79 76 68 61 59 60 bytes
c="print(sorted(x:=input(),key=('c=%r;'%c+x).find))";exec(c)

Try it online!
-2 bytes by using this
-4 bytes by realizing that <0 == ==-1 and removing the unnecessary +1
-11 bytes thanks to Neil
-6 bytes thanks to dzaima
-3 bytes thanks to rod
-8 bytes thanks to negative seven pointing out that the program can output a list of chars
-7 bytes due to Embodiment of Ignorance switching back to Python 3.8 and using :=
-2 bytes due to Jo King switching out the variable name s for c, so we could leave out the ;c
+1 bytes because negative seven pointed out that it wasn't filtering ; correctly

('s=%r;exec(s)'%s+x).find(x)?

@Neil Is the current solution invalid, and substituting ('s=%r;exec(s)'%s).find(x) with your code would make it valid?

@Neil Oh, wait, I see your golf

You can switch to input() and save 4 bytes

the c isn't ordered, but can be fixed at the cost of 1 byte

It seems output should be fine as a list of characters.

@JoKing I don't see the different

61 bytes in python 3.8 tinyurl.com/y593h4a9

@EmbodimentofIgnorance Wow, nice golf!

@JoKing I see now. Thanks!

; isn't being sorted correctly in the current version

@negativeseven Fixed

APL (Dyalog Unicode), 14 bytesSBCS
Anonymous tacit prefix function.
'''∘⍋⊃¨⊂'∘⍋⊃¨⊂

⊂ enclose argument (to act on it as a whole)
…⊃¨ from that, pick one character for each of the following indices:
∘⍋ the indices that would sort the argument in the the order given by the following string (all non-members go in order of appearance at the end):
'''∘⍋⊃¨⊂' the characters '∘⍋⊃¨⊂
Try it online!

C# (Visual C# Interactive Compiler), 48 bytes
n=>n.OrderBy((@"n=>.OrdeBy(@""+)Ixf"+n).IndexOf)

Try it online!

Jelly, 14 bytes
“;fɓḟṾⱮ”ṾɓfⱮ;ḟ

A full program accepting a (Python formatted) string (of Jelly code-page characters) which prints the output.
(as a monadic link it yields a list of lists of characters)
Try it online!
How?
“;fɓḟṾⱮ”ṾɓfⱮ;ḟ - Main Link: list of characters, S
“;fɓḟṾⱮ”       - list of characters = [';', 'f', 'ɓ', 'ḟ', 'Ṿ', 'Ɱ']
        Ṿ      - un-evaluate = ['“', ';', 'f', 'ɓ', 'ḟ', 'Ṿ', 'Ɱ', '”']
         ɓ     - start a new dyadic chain, F(S, T=that):
           Ɱ   - for each character, t, in T:
          f    -   (S) filter keep any of (the single character, t)
             ḟ - (S) filter discard any of (the characters in T)
            ;  - concatenate

So... I posted my Jelly answer, and then it clicked on me: the interpreter converts the bytecode to UTF-8 before executing it, hence either the bytecount should be increased, or the code be changed to fit the codepage.

@EriktheOutgolfer I think this one is safe in that respect since this method does not employ any sorting and meets the I/O being in the same encoding (Jelly's code page) criteria.

Eh... I think the f and ḟ work on Unicode characters, because that's what kind of characters the string actually has inside. For example ”ĿO returns 319 if tested locally encoded in JELLY, so it sees the Ŀ and not the C7.

I think f and ḟ work on Unicode too, but is that a problem here? I pass in the restricted set of Unicode characters that appear on Jelly's code page (that is, bytes encoded using that encoding, fulfilling "The input is in the same encoding as the code"); filter them correctly (since these inputted bytes were encoded as Unicode), and then output them correctly. What I then count is the bytes of the code (fulfilling "The input is sorted by characters, not by bytes" and "shortest answer in bytes for each language wins").

The problem is that you're passing it the restricted set of Unicode chars the JELLY encoding represents, but you're supposed to pass it JELLY characters instead. If you test it locally, I'm pretty sure that it won't work, since the arguments aren't converted from JELLY to UTF-8.

@EriktheOutgolfer note the same applies to the 05AB1E, Charcoal and APL answers too as far as I can tell

@EriktheOutgolfer what conversion is necessary? The input is simply bytes which have been encoded to some characters using Jelly's code-page. The sorting happens according to the characters of the byte-code as displayed in that same encoding. Internally the filtering is of characters, by characters. The output is again bytes encoded in the same fashion. It feels to me like that aligns with the bullet points given in the OP.

@JonathanAllan I feel like the  "have been encoded to some characters using Jelly's code-page" is what I'm referring to in my previous comment. Since the code's encoding consists of single bytes from 0x00 to 0xFF, that's what the argument's encoding should consist of too, Instead, the argument is passed after being mapped from JELLY to UTF-8, so each of its characters isn't necessarily a single byte anymore. Basically, the code is in JELLY while the argument is in UTF-8, even though it has been mapped to that from JELLY. While the correct UTF-8 output is returned, it should be JELLY all along.

I suggest continuing the discussion over TNB.

JavaScript (Node.js), 60 58  56 bytes
-2 bytes from  Jo King
f=_=>_.sort((a,b)=>(p=g=>`f=${f+g}`.indexOf(g))(a)-p(b))

Try it online!

Your code seems to only work when the source is f=.... If that is the case, please include that in your submission & byte count.

Perl 6, 56 bytes
<slurp.comb.sort({"<$_>~EVAL$^a".index($a)}).say>~~.EVAL

Try it online!

Jelly, 16 14 bytes (Jelly Code page), 25 bytes (UTF8)
“Ṿv`Ṿ;³³i@Þ”v`

Try it online!
A full program that takes a single argument, the string to be sorted.
Thanks to @JonathanAllan for pointing out a bug!
As per @EriktheOutgolfer, although the code can be input using the Jelly code page, the characters sorted are the equivalent UTF-8 ones rather than the bytes of the source. As such, I’ve included the score in UTF-8 bytes as well. Note the same probably applies to all languages with custom code pages.
Explanation
“Ṿv`Ṿ;³³i@Þ”   | The string "Ṿv`Ṿ;³³i@Þ", referred to below as S
            v` | Evaluate this string as Jelly code using the string itself as the argument

The string above evaluates as:
Ṿ          | Uneval the string S (effectively wraps it in “”)
 v`        | Eval it (effectively removes the “”)
   Ṿ       | Uneval it again, adding back in the “”
    ;³     | Concatenate the input to this
      ³i@Þ | Sort the input with respect to the first occurence of each character in the “”-wrapped string S concatenated to the input

Ṿv` is a no-op effectively here, but exists to ensure all characters are represented.

So... I posted my Jelly answer, and then it clicked on me: the interpreter converts the bytecode to UTF-8 before executing it, hence either the bytecount should be increased, or the code be changed to fit the codepage.

@EriktheOutgolfer I don’t understand what you’re getting st here. How is this different to any other codegolf challenge in this regard?

The self-referential aspect is different, so, in fact, the code sorts UTF-8 characters and not the bytes it's supposed to.

05AB1E, 31 26 19 bytes
Σ'"'ÿs"Σ'ÿÿsìyk"ìyk

-7 bytes by taking inspiration of @EmbodimentOfIgnorance's approach in his C# answer of appending the current character before indexing.
Try it online or try it with added debug-line to see the strings that's being indexed into.
Explanation:
Σ                 # Sort the (implicit) input-string by:
 '"              '#  Push string '"'
   'ÿ            '#  Push string "ÿ"
     s            #  Swap the order of these two strings on the stack
      "Σ'ÿÿsìyk"  #  Push string "Σ'ÿÿsìyk", where the `ÿ` are automatically filled with
                  #  the previous strings we created: `Σ'"ÿsìyk`
                  #  (top to bottom from stack; left to right in string)
       ì          #  Prepend this string in front of the character we're sorting
        yk        #  And then get the index of the character we're sorting in this string
                  # (after the sorting the resulting string is output implicitly)

Strictly speaking I had that inspiration over 12 hours earlier when I golfed 11 bytes of @MilkyWay90's answer...

This is good! I saw that but couldn't see a way to turn mine into this while saving bytes

05AB1E, 24 22 21 bytes
Σ"Σ"'"«"'«Rrk}"«Rrk}R

Try it online!
Explanation:
Σ                    }               # Sort
 "Σ"                                 # Σ string literal
    '"                               # " string literal
       «                             # Concatenate last two literals
        "'«Rrk}"                     # '«Rrk} another literal
                «                    # Concat again
                 R                   # Reverse literal (so: }krR'«'"Σ)
                  r                  # reverse stack
                   k                 # find the current sorting index in our code string
                     R               # reverse our sorted string

First time trying stuff in 05AB1E so probably lots to be saved

Are you sure this is correct? The string it now sorts on is }krR«'«. NOTE: ' is a single character, so just '" is enough (unlike C# where it needs an additional trailing '). Currently your code first pushes the string Σ, then the string ", then the string «, then the string '«Rrk}, and then it does the append, reverse, reverse stack, index. Smart usage of the reverse of the string and at the end, though! I will see if I can find a fix for your answer, and will delete mine afterwards.

@kevincruijssen So can't I just get rid of the second '

Yeah, you indeed can. :) Then it correctly sorts on }krR«'"Σ. PS: I tend to use = (print without popping) for debug purposes sometimes. You can also add --debug-stack as argument, but it's a bit weird in the new 05AB1E version imho.

Ruby, 57 bytes
->s{s.sort_by{|o|%{->s{.ort_by|%}index()9}.index(o)||99}}

Try it online!
Fairly straightforward, assuming I haven't missed a golfing trick. Take in a list of characters and sort by their index in a string consisting of all the uniq characters in the code in order of their appearance. Often their first appearance is in that very string, but that doesn't change the order.

Python 2, 62 bytes
lambda a:sorted(a,key=('lambd :sorted(,ky=\'\\+).fin'+a).find)

Same concept as my C# answer.
Try it online!

\\\' should be \'\\. Nice approach though! Saved 23 bytes in my Java answer.

@KevinCruijssen Fixed

PowerShell, 68 bytes
$p=$args
&($t={$p|sort-object{"`$p=`$args
&(`$t={$t})$_"|% i*f $_}})

Try it online!

sort instead sort-object works too. 2) the variable $b defined out of scope your code. the Standard loopholes requires a complete answer. For Powershell it means: any person can wirte the code to a file as a powershell script and run it in a terminal. Your code does not work from script file. Sorry.

@mazzy, thank you very much. 1) the sort alias does not work in pwsh on Ubuntu 18.04 2) yes, this is my fault, but I corrected myself, and as a result, the code became longer, of course :)

(oO)! I've created sort alias for Powershell. code became longer - this is the challenge :)

awesome $_ at the end of a source code!

Yes, you are right. Each individual character of $p is append to the end of the string with the source code and gets an index equal to $src.Length, but since “their order does not matter and should not be consistent,” it is not matter. In this answer, the entire input string is appended to the end of the string with the source code.

@mazzy, don't standard I/O rules allow you to give a function from the input to the output? I dunno what counts as a function in PowerShell...

@dfeuer, I don't understand your question. Sorry.

Java 10, 129 100 bytes
s->{s.sort(java.util.Comparator.comparing(c->("s->{.ort(javuilCmpcng\"\\+)dexOf;}"+c).indexOf(c)));}

-29 bytes by porting the +c from @EmbodimentOfIgnorance's C# answer.
Try it online.
Explanation:
s->{                 // Method with char-List parameter and no return-type
  s.sort(java.util.Comparator.comparing(c->
    ("s->{.ort(javuilCmpcng\"\\+)dexOf;}"
                     //  Push a String containing the characters in the code
     +c)             //  Append the current character
        .indexOf(c)  //  And get the first index of the current character in the String

NOTE: Usually it's cheaper to use s.sort((a,b)->Long.compare(a,b)) instead of s.sort(java.util.Comparator.comparing(c->c), but in this case it would be 11 bytes longer:
s->{var v="s->{var =\"\\;.ot(,)Lngcmpe+idxOf}";s.sort((a,r)->Long.compare((v+a).indexOf(a),(v+r).indexOf(r)));}

Try it online.

Japt, 18 7 bytes
Takes input as an array of characters
nQi"nQi

Try it

J, 14 bytes
Anonymous tacit prefix function.
]/:']/:''i'i:]

Try it online!
] the argument
…i: last occurrence (non-members get the index beyond end of lookup string) of each character in:
']/:''i' the characters ]/:'i
…/: use that to sort:
] the argument

Are the four leading spaces a result of the echo or the code?

@tjjfvi It is how TIO is configured. Fixed now.

Charcoal, 37 bytes
≔´≔´´´η´Ｆ´Φ´θ´⁼´ι´κ´¬´№ηＦηΦθ⁼ικΦθ¬№ηι

Try it online! Explanation:
≔´≔´´´η´Ｆ´Φ´θ´⁼´ι´κ´¬´№η

There are two ways of quoting characters in Charcoal; ´ quotes any single character while ”y...” quotes any character except ” and also counts as a separate string. It turns out that the overhead in having to deal with ” means that it doesn't end up any golfier.
ＦηΦθ⁼ικ

Loop over the characters in turn, outputting any matching characters from the input. This sorts the input.
Φθ¬№ηι

Output any unmatched characters in the input.

Jelly, 26 bytes (UTF-8*)
“®³nÞṾ©V”Ṿ©VV

Try it online!
Takes input as a Python-formatted string in the 1st command-line argument.
Unique characters:
“®³nÞṾ©V”

*Note: I discovered that this doesn't work when encoded in JELLY, since it sorts the UTF-8 characters instead of its own bytes.

ReRegex, 335 bytes
([^(])\(/($1/([^(])\[/[$1/([^(\[])\^/^$1/([^(\[^])]/]$1/([^(\[^\]])\)/)$1/([^(\[^\])])\\/\\$1/([^(\[^\])\\])\//\/$1/([^(\[^\])\\\/])\$/\$$1/([^(\[^\])\\\/$])1/1$1/([^(\[^\])\\\/$1])\#/\#$1/([^(\[^\])\\\/$1\#])i/i$1/([^(\[^\])\\\/$1\#i])n/n$1/([^(\[^\])\\\/$1\#in])p/p$1/([^(\[^\])\\\/$1\#inp])u/u$1/([^(\[^\])\\\/$1\#inpu])t/t$1/#input

A Naïve solution, bubble sorts characters to the left based on their occurance in the source code, which only consists of the characters ([^])\/$1#input (in order). Unfortunately, it requires a separate regex for each character, which gets progressively longer per index. Seperating the regexes for readability gives:
([^(])\(/($1/
([^(])\[/[$1/
([^(\[])\^/^$1/
([^(\[^])]/]$1/
([^(\[^\]])\)/)$1/
([^(\[^\])])\\/\\$1/
([^(\[^\])\\])\//\/$1/
([^(\[^\])\\\/])\$/\$$1/
([^(\[^\])\\\/$])1/1$1/
([^(\[^\])\\\/$1])\#/\#$1/
([^(\[^\])\\\/$1\#])i/i$1/
([^(\[^\])\\\/$1\#i])n/n$1/
([^(\[^\])\\\/$1\#in])p/p$1/
([^(\[^\])\\\/$1\#inp])u/u$1/
([^(\[^\])\\\/$1\#inpu])t/t$1/
#input

Try it online!

brainfuck, 647 bytes
,[>>>+>,]<<<<[<<<<]>>>>[[->+>+<<]--[>-<++++++]>-<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]-[>-<---]>------<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]----[>-<----]>+<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]--[>-<++++++]><+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]-[>-<---]>--------<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]----[>-<----]>+++<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]--[>-<++++++]>--<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[[->+>+<<]--[>-<++++++]>---<+>[<->[-]]<[>>.>-<<<-]>>[-<<+>>]>>]<<<<[<<<<]>>>>[>>>[<<<.>>>-]>]

This was a mouthful. For each of Brainfuck's 8 command characters (In order of source appearance), compares them to each character of the input and outputs it when they occur. After each character is done, it outputs whatever wasn't found.
Ungolfed
,[>>>+>,]             Load each character of input with some memory padding
<<<<[<<<<]>>>>         Navigate to the start

[                   For each COMMA
    [->+>+<<]           Copy over the next two
    --[>-<++++++]>-     Subtract 44
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each LEFT BRACKET
    [->+>+<<]           Copy over the next two
    -[>-<---]>------    Subtract 91
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each RIGHT ANGLE BRACKET
    [->+>+<<]           Copy over the next two
    ----[>-<----]>+     Subtract 62
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each PLUS
    [->+>+<<]           Copy over the next two
    --[>-<++++++]>      Subtract 43
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each RIGHT BRACKET
    [->+>+<<]           Copy over the next two
    -[>-<---]>--------  Subtract 93
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each LEFT ANGLE BRACKET
    [->+>+<<]           Copy over the next two
    ----[>-<----]>+++   Subtract 60
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each MINUS
    [->+>+<<]           Copy over the next two
    --[>-<++++++]>--    Subtract 45
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[                   For each DOT
    [->+>+<<]           Copy over the next two
    --[>-<++++++]>---   Subtract 46
    <+>[<->[-]]<[       If NOT Zero
        >>.                 Write it
        >-                  Unset the remember flag
        <<<-                And unset the test flag
    ]
    >>[-<<+>>]          Copy Back
    >>                  Next Char
]<<<<[<<<<]>>>>     And Reset

[       For each remaining character
    >>>[    If the remember flag is still set
        <<<.    Write it
        >>>-    Unset the flag
    ]>      Next character
]       Until it is done

Try it online!

Thunno 2 J, 18 bytes
"XÞxṘs+nȮ"XÞxṘs+nȮ

Explanation
"XÞxṘs+nȮ"XÞxṘs+nȮ  # Implicit input
"XÞxṘs+nȮ"          # Push the string "XÞxṘs+nȮ"
          X         # Pop and store in the variable x
           Þ        # Sort the input by the following:
            x       #  Push x, "XÞxṘs+nȮ"
             Ṙ      #  Get its representation (surround by quotes)
              s+    #  Append the current character
                nȮ  #  And get its index in this string
                    # Implicit output, joined by the J flag

Screenshot


text:
Implement a strongly Darboux function
According to Wikipedia, a strongly Darboux function is

one for which the image of every (non-empty) open interval is the whole real line

In other words, a function \$f\$ is strongly Darboux if given 3 arbitrary real numbers \$a\$, \$b\$, and \$y\$, it is always possible to find an \$x\$ between (distinct) \$a\$ and \$b\$ such that \$f(x) = y\$.
For the purposes of this challenge, we will consider strongly Darboux functions over the rationals instead.
Your challenge is to write a program or function that:

gives a rational number as output for every rational number input,
always gives the same output for a given input, and
has the strongly Darboux property.

Input and output may be either of the following:

an arbitrary-precision number type, if your language has one (or has a library for one, e.g. GMP).
a string representation of the number, which you may assume will always contain a decimal point and at least one digit on either side. It may be in any base \$b \geq 2\$, but input and output must be in the same base. You may use any set of characters for the digits and decimal point (but again, they must be consistent between input and output).

The input will always have a terminating base \$b\$ expansion. As for the output, which may have a theoretically non-terminating base \$b\$ expansion depending on your choice of function, you may choose any of the following:

output digits forever.
take an additional integer as input and output at least that many digits.
output at least as many digits as are in the input (which may contain trailing zeroes).

Note that by the nature of this challenge, the convention that numbers may be assumed to be representable by standard number types does not apply, except for the second input described in option 2 above.
To avoid loopholes with functions that are only defined on non-terminating rationals, your submission must be able to produce output arbitrarily close to a desired value in practice. Formally, given rational numbers \$a\$, \$b\$, \$y\$, and \$\varepsilon\$, there must be a rational number \$x\$ that terminates in your chosen base such that \$a<x<b\$ and \$|f(x)-y|<\varepsilon\$.

To give you some ideas, here is a description of the Conway base 13 function:

Convert \$x\$ to base 13 and remove the decimal point.
If the result is of the form \$[x]A[y]C[z]_{13}\$, where \$[y]\$ and \$[z]\$ consist of only digits from 0 to 9, then \$f(x) = [y].[z]\$.
If the result is of the form \$[x]B[y]C[z]_{13}\$, where \$[y]\$ and \$[z]\$ consist of only digits from 0 to 9, then \$f(x) = -[y].[z]\$.
Otherwise, \$f(x) = 0\$.

This function is strongly Darboux. Say, for example, that we want to find some \$x\$ between \$123.456_{13}\$ and \$123.457_{13}\$ such that \$f(x) = 7.89\$. The base-13 value \$123.456A7C89_{13}\$ would satisfy this requirement.
Your submission may be an implementation of this function, although I suspect that there are other strongly Darboux functions that are a lot shorter to implement. :)

Are the numbers assumed to have a terminating base $b$ expansion?

math.stackexchange link and also the original question it's a dupe of for some examples

If we implement the Conway base 13 algorithm, we could take input in base 13 but would then have to output in base 13 also. Since the output of the function is usually in decimal, we will end up with a recurring tridecimal number. How should this be output? Do we output the first $x$ digits, where $x$ is specified in the question (not yet though)? Or do we need to indicate that it’s recurring?

@NickKennedy Thanks, I overlooked that - I've edited the question to clarify.

@Nitrodon (That edit also addresses your comment.)

"The input will always be a terminating base b expansion" - Are we expected to map a subset of the rational numbers to the real numbers?

@BlackOwlKai No - your function should theoretically work for any real input, but I want to allow submissions that read the entire input before producing output, and of course there's no way to do this if the input is irrational or non-terminating.

Hmm, I'm quite sure I can define a strongly Darboux function that is constant or the identity on all terminating inputs...

@SriotchilismO'Zaic You aren't necessarily restricted to taking input in base 10. "It may be in any base b≥2, but input and output must be in the same base."

@mbomb007 Ah yes I see that is correct, it does not effect the content of my answer though.  Regardless of the base the problem persists.

@SriotchilismO'Zaic Good point - I've edited the question in a way that I believe closes this loophole (without invalidating any of the answers).

Looks like it.  I might think through this more carefully in a little bit but I've retracted my close-vote since I think that it is fixed.

Retina 0.8.2, 43 50 bytes
^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5
0(.)
$1

Try it online! I/O is as a binary string. Encode a binary number y close to another binary number a as follows:

If a does not contain a ., suffix one.
If a contains an odd number of digits after the ., suffix a 0.
If y is negative then suffix 11 otherwise suffix 10.
For each digit in y, suffix 0 followed by that digit.
If y contains a ., suffix 11 at that point, otherwise suffix it after all the digits in y.

Explanation:
^.*\.(..)*1(.)((..)+)1.((..)*)$
$2$*-$3.$5

Pair the digits starting at the binary point. If the number is a valid encoding, then decode the last 1x digit pair to a . and the second last to an optional - sign. Digits before that are ignored.
0(.)
$1

This should just leave pairs that begin with 0, so delete the 0s.

I sometimes get outputs such as -.. Do those imply zeroes or are they not supposed to be produced?

@EriktheOutgolfer I guess I could change the *s to +s, that would guarantee at least one digit before and after the .?

Actually I can't guarantee digits after the .. I think I can still guarantee a digit before the . though.

An additional terminal 0 in a number with . doesn't change its value, but such a change in the input of your function changes the output. Maybe you are allowed to fix this by assuming input has no such 0s. Also, if you group pairs from the right, how does this "theoretically work for any real input"?

@ChristianSievers (Sorry I didn't notice my inbox earlier) I based my answer on the description of the base 13 function in the question, which seems also to require a terminating representation. Also you're right that I was assuming that there would be no trailing zeros. (So integers always have to have 11 appended in step 2.)

The base 13 function is not computable, but still well defined, when non-terminating input is allowed. But grouping into pairs from the right just makes no sense unless input is terminating. Also, I saw that for input 0.01111 we get output -..

@ChristianSievers So if I tweak my answer to group into pairs from the decimal point, then that will be OK? Also, I was already intending to make 0.01111 result in 0.1111, but I forgot about the question because Windows decided to reboot to install updates.

Oh, I thought I found another instance of that already reported problem, I missed that there was no edit to the solution. Yes, if the rest works, grouping from the "decimal" point is okay.

@ChristianSievers OK I hope this version addresses all the issues.

That seems to be well defined. Not sure if it's a problem that results like -00. are possible.

Jelly, 71 bytes
L7*©ṛḅ7WµṪ×⁵d®µ⁴‘¤Ð¡ḊṖ
DF7,8ṣṪ¥ƒṣ9ḅ7×ɗÇƭ€j”,
DFf7r9¤ṫ-Ḍ⁼Ɱ“OY‘TịØ+³çƲ0Ẹ?

Try it online!
A full program that takes a base-10 number as input and output and implements the Conway base 13 function but using bases 7 and 10 rather than 10
and 13. Both input and output use comma as a decimal separator. Output will have a leading - for negative numbers.

The example at the TIO link has the digit 9 in the input and the output, so how are these base 7 numbers?

@ChristianSievers sorry meant base 10 for input and output. Base 7 is used in the code, but is converted back to base 10.

Fine, now I can change the input and understand how that affects the output!

Retina, 28 25 26 28 bytes
.*11|22
.
D^`\.
^3
-
4(.)
$1

Try it online!
Explanation
.*11|22     Delete up to the last 11 and prepend a dot. Also change 22 to a dot.
.
D^`\.       Keep only the last dot, if there is one.
^3          Change 3 at the beginning to a minus sign.
-
4(.)        4 is the escape character.
$1

It may output leading and trailing zeros, and numbers without a integer part.
It could be golfed 2 or 3 bytes more if I could use 4+. But I'm not sure how to define the theoretical result if the input has an endless stream of 4s.

I got cursed by a T-shaped thing by posting this answer.


text:
Golf my iteration function
Here is my ungolfed Ruby code for a function I want to try and golf:
Iter =-> k {
    str = ""
    (0..k).map{|m| str += "-> f#{m} {"}
    str += "f#{k}.times{f1 = f0[f1]};f1"
    (2..k).map{|m| str += "[f#{m}]"}
    eval(str + "}" * (k+1))
}

The best I can do to golf this is essentially shortening variable names, removing spaces, and rearranging the code to reduce the amount of loops:
I=->k{s="f#{k}.times{f1=f0[f1]};f1"
(2..k).map{|m|s+="[f#{m}]"}
(0..k).map{|m|s="->f#{k-m}{"+s+?}}
eval s}

Try it online!
This function can be compacted so that it avoids a lot of defining new functions. You can think of it like this:
$$\operatorname{Iter}(k;f_0,f_1,\dots,f_k)=f_0^{f_k}(f_1)(f_2)(f_3)\dots(f_k)$$
where
$$f^n(x)=\underbrace{f(f(\dots f(}_nx)\dots))$$
denotes function iteration. The types of arguments are given as:
$$\operatorname{Iter}(\text{int};\dots,(\text{int}\mapsto\text{int})\mapsto(\text{int}\mapsto\text{int}),\text{int}\mapsto\text{int},\text{int})$$
That is, the last argument is an integer, and each previous argument maps from T to T, where T is the type of the next argument on the right.
It is true that accepting all arguments at once would allow me to golf the above code further:
I=->k,*a{a[-1].times{a[1]=a[0][a[1]]};(2..k).map{|m|a[1]=a[1][a[m]]};a[1]}

However, the issue is that I need to curry this function. This way, I may treat objects such as
$$\operatorname{Iter}(k)(f_0)$$
as their own object, and thus be able to pass this into Iter(k) to get things such as
$$\operatorname{Iter}(k)(\operatorname{Iter}(k)(f_0))$$
As a specific example of what this function does, we have
\begin{align}\operatorname{Iter}(2)(\operatorname{Iter}(1))(x\mapsto x+1)(2)&=\operatorname{Iter}(1)(\operatorname{Iter}(1)(x\mapsto x+1))(2)\\&=\operatorname{Iter}(1)(x\mapsto x+1)(\operatorname{Iter}(1)(x\mapsto x+1)(2))\\&=\operatorname{Iter}(1)(x\mapsto x+1)(2+1+1)\\&=\operatorname{Iter}(1)(x\mapsto x+1)(4)\\&=4+1+1+1+1\\&=8\end{align}

I'm interested in seeing if this can be golfed down further, with the restriction that the arguments must be curried in the order provided.

Mind if anyone explain the "unclear" close vote? I really did try my best to explain everything, so if there's any part that's unclear, just ask.

It's a bit unclear because you have tagged this "tips", but it's written almost like a challenge. I'd remove the tips tag and make it more clearly a challenge. Otherwise, perhaps make it clear that you're looking for golfing tips for this specific program. Your last statement makes us unsure of what you want.

Not sure if this is what you're looking for, but in J >: is the increment function, and your example I[2][I[1]][->x{x+1}][2] can be written >:^:2^:3 (2).  Try it online!.  ^: is the power of conjunction, and iteratively applies the verb on its left the number of times specified by the number on its right, with 1 being normal application f(x), 2 being f(f(x), etc.

@mbomb007 okay, I cleared that part up.

@lirtosiast Thanks and done

@Jonah interesting syntax, though it seems I'm no longer looking for non-Ruby answers. Am still a bit curious as to how you would write something like I[1][I[2][I[1]]][s][2].

Apparently with your golfed code (and my solution that improves on your golfed code) hits an infinite loop when you change the last argument to 3 instead of 2... This shouldn't happen, right? Or am I missing something? Try it online!

@ValueInk that's not an infinite loop. The issue there is the end result is 3 times 2^402653191 (3<<402653191)

That definitely means I missed something lol... I thought the output was going to be something closer to, I don't know, 12.

@ValueInk Let s[n] = n+1. See that I[1][s][n] = 2n and I[1][I[1][s]][n] = n2ⁿ = n<<n. From that point, you can directly compute your example with n = 3; 3.times{n <<= n}...

Erm, miscalculation, it ought to be 3 << 402653211.

Ruby, 87 bytes
I=->k{eval ("->f%d{"*-~k+"f%d.times{f1=f0[f1]};f1"+"[f%d]"*~-k+?}*-~k)%[*0..k,k,*2..k]}

Try it online!

Ruby, 94 96 bytes
Using loops to do concatenations that followed such a simple pattern felt cumbersome, so I utilized the creative use of join instead, further golfed by the fact that array*str is equivalent to array.join(str)
+2 bytes to fix a typo I made that just so happened to return the same result on the test example by chance.
I=->k{eval"->f#{[*0..k]*'{->f'}{f#{k}.times{f1=f0[f1]};f1#{"[f#{[*2..k]*'][f'}]"if k>1}"+?}*-~k}

Try it online!

Oh wow I never knew you could use array*str in Ruby, and like that! So much to learn...