text:
Calculate the n-th iterate of a polynomial for a specific value; fⁿ(x)
Given a polynomial function f (e.g. as a list p of real coefficients in ascending or descending order), a non-negative integer n, and a real value x, return:
   f n(x)
i.e. the value of f (f (f (…f (x)…))) for n applications of f on x.
Use reasonable precision and rounding.
Solutions that take f as a list of coefficients will probably be the most interesting, but if you are able to take f as an actual function (thereby reducing this challenge to the trivial "apply a function n times"), feel free to include it after your non-trivial solution.
Example cases
p =[1,0,0] or f =x^2, n =0, x =3: f 0(3) =3
p =[1,0,0] or f =x^2, n =1, x =3: f 1(3) =9
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =0, x =2.3: f 0(2.3) =2.3
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =1, x =2.3: f 1(2.3) =-8.761
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =2, x =2.3: f 2(2.3) =23.8258
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =3, x =2.3: f 3(2.3) =-2.03244
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =4, x =2.3: f 4(2.3) =1.08768
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =5, x =2.3: f 5(2.3) =-6.38336
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =6, x =2.3: f 6(2.3) =14.7565
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =7, x =2.3: f 7(2.3) =-16.1645
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =8, x =2.3: f 8(2.3) =59.3077
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =9, x =2.3: f 9(2.3) =211.333
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =10, x =2.3: f 10(2.3) =3976.08
p =[0.1,-2.3,-4] or f =0.1x^2-2.3x-4, n =11, x =2.3: f 11(2.3) =1571775
p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =0, x =-1.1: f 0(-1.1) =-1.1
p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =1, x =-1.1: f 1(-1.1) =1.349
p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =2, x =-1.1: f 2(-1.1) =6.92072
p =[-0.1,2.3,4] or f =−0.1x^2+2.3x+4, n =14, x =-1.1: f 14(-1.1) =15.6131
p =[0.02,0,0,0,-0.05] or f =0.02x^4-0.05, n =25, x =0.1: f 25(0.1) =-0.0499999
p =[0.02,0,-0.01,0,-0.05] or f =0.02x^4-0.01x^2-0.05, n =100, x =0.1: f 100(0.1) =-0.0500249

Related

Can my Jelly answer take a Jelly link and consider it a "function", for example?

@EriktheOutgolfer I originally required input as list of coefficients in order to prevent such trivial solutions. However, I relaxed it by request. I suggest that you post the list version, and add the trivial version as a note (or opposite).

I've already posted the list version, but the function version is a lot shorter.

@EriktheOutgolfer Yeah, obviously. See my added note.

Added the Jelly link version, below the list version.

So, in terms of lambda calculus, λf.λn.λx.n f x?

@Zacharý If you say so… I don't speak lambda.

With lambda definition n f n is already a function for this

Octave, 49 bytes
@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)

Try it online!
Or, taking coefficients:
Octave, 75 57 bytes
@(p,x,n)(f=@(f,n){@()polyval(p,f(f,n-1)),x}{~n+1}())(f,n)

Try it online!
A special thanks for Suever over at StackOverflow, for this answer some time ago on a question of mine, proving that a recursive anonymous function is possible.
This defines an anonymous function, which is a wrapper for a recursive anonymous function; something which is not a native Octave concept, and requires some fancy cell array indexing.
As a bonus, the second version is a nice lesson in variable scoping in Octave. All instances of r can legally be replaced by f, which then simply overwrites the existing f in the most local scope (similar for n)
Explanation
@(p,x,n)(f=@(r,m){@()p(r(r,m-1)),x}{~m+1}())(f,n)
@(p,x,n)         .                ..    .  ..   .   % Defines main anonymous function
        (f=@(r,m).                ..    .  ).   .   % Defines recursive anonymous function
                 .                ..    .   .   .   %  r: Handle ('pointer') to recursive function
                 .                ..    .   .   .   %  m: Current recursion depth (counting from n to 0)
                 .                ..    .   (f,n)   % And call it, with
                 .                ..    .           %  r=f (handle to itself)
                 .                ..    .           %  m=n (initial recursion)
                 {                }{    }           % Create and index into cell array
                                    ~m+1            %  Index: for m>0: 1; for m==0: 2.
                                ,x                  %  Index 2: final recursion, just return x.
                  @()                               %  Index 1: define anonymous function, taking no inputs.
                     p(        )                    %   which evaluates the polynomial
                       r(     )                     %    of the recursive function call
                         r,m-1                      %     which is called with r
                                                    %     and recursion depth m-1
                                                    %     (until m=0, see above)
                                         ()         % Evaluate the result of the cell array indexing operation.
                                                    %  which is either the anonymous function
                                                    %  or the constant `x`.

The key to this is that anonymous functions are not evaluated when they are defined. So, the @(), which seems a bit superfluous since it defines an anonymous function which is called with () directly after, is actually strictly necessary. It is not called unless it is selected by the indexing statement.
Octave, 39 bytes (boring way)
function x=f(p,x,n)for i=1:n;o=p(o);end

Just for completeness, the Octave solution with the shortest bytecount.
Yawn..

I'll try rereading this another time, but I still don't quite get it.. As a big Octave fan I can only say, great job +1.

@Michthan l'll try and make a better explanation, but it's by far the most terse Octave I've written - usually, function names are the majority of the byte count. It's almost Lisp.

@Michthan Hopefully, the new explanation makes some sense, looking at it in an 'exploded' view.

Mathematica, 56 47 28 bytes
Nest[x\[Function]x#+#2&~Fold~#,##2]&

\[Function] takes 3 bytes in UTF-8.
Take parameters in order p,x,n.
p (parameter 1) is in increasing order of degree.
Obviously if f can be taken as a function this can be reduced just to Nest.

Do you need to reverse the coefficients?

@Giuseppe That's why there is Reverse in the code.

@user202729 I think you can take the coefficients in whatever order you want, either ascending or descending.

We are allowed to take them in increasing or decreasing order of degree, I believe. (I don't know Mathematica at all)

Yes, you can can take them in desired order: in ascending or descending order

How does \[Function] look?

@Adám Similar to ↦.

Pari/GP, 31 bytes
(p,n,x)->for(i=1,n,x=eval(p));x

Try it online!

Husk, 5 bytes
←↓¡`B

Try it online!
The key idea here is that evaluating a polinomial at a point x is equivalent to performing base conversion from base x.
B when given a base and a list of digits performs base conversion. Here we use its flipped version, in order to take the list of digits first and partially apply this function to it. We obtain then a function which computes the value of the given polynomial at a point, the second part of this solution deals with iterating this function the correct amount of times:
Husk, 3 bytes
←↓¡

¡ is the "iterate" function, it takes a function and a starting point and returns the infinite list of values obtained iterating the function.
↓ takes a number (the third argument of this challenge) and drops that many elements from the start of the list.
← returns the first element of the resulting list.

JavaScript (ES6),  52 49 44  42 bytes
Saved 5 bytes thanks to G B and 2 more bytes thanks to Neil
Takes input in currying syntax as (p)(n)(x), where p is the list of coefficients in descending order.
p=>n=>g=x=>n--?g(p.reduce((s,v)=>s*x+v)):x

Test cases

let f =

p=>n=>g=x=>n--?g(p.reduce((s,v)=>s*x+v)):x

console.log(f([1,0,0])(0)(3))
console.log(f([1,0,0])(1)(3))
console.log(f([0.1,-2.3,-4])(0)(2.3))
console.log(f([0.1,-2.3,-4])(1)(2.3))
console.log(f([0.1,-2.3,-4])(2)(2.3))
console.log(f([0.1,-2.3,-4])(3)(2.3))
console.log(f([0.1,-2.3,-4])(4)(2.3))
console.log(f([0.1,-2.3,-4])(5)(2.3))
console.log(f([0.1,-2.3,-4])(6)(2.3))
console.log(f([0.1,-2.3,-4])(7)(2.3))
console.log(f([0.1,-2.3,-4])(8)(2.3))
console.log(f([0.1,-2.3,-4])(9)(2.3))
console.log(f([0.1,-2.3,-4])(10)(2.3))
console.log(f([0.1,-2.3,-4])(11)(2.3))
console.log(f([-0.1,2.3,4])(0)(-1.1))
console.log(f([-0.1,2.3,4])(1)(-1.1))
console.log(f([-0.1,2.3,4])(2)(-1.1))
console.log(f([-0.1,2.3,4])(14)(-1.1))
console.log(f([0.02,0,0,0,-0.05])(25)(0.1))
console.log(f([0.02,0,-0.01,0,-0.05])(100)(0.1))

If p is in descending order, you can reduce using s*x+v and ignore i.

In that case, can you omit the ,0 from the reduce?

@Neil Good catch. :-)

Ruby, 42 bytes
->c,n,x{n.times{x=c.reduce{|s,r|s*x+r}};x}

C is the list of coefficients in descending order
Trivial version, where f is a lambda function (26 bytes):
->f,n,x{n.times{x=f[x]};x}

# For example:
# g=->f,n,x{n.times{x=f[x]};x}
# p g[->x{0.02*x**4-0.01*x**2-0.05},100,0.1]

Try it online!

R, 96 58 55 52 bytes
f=function(n,p,x)`if`(n,f(n-1,p,x^(seq(p)-1)%*%p),x)

Try it online!
Explanation:
seq(p) generates the list 1, 2, ..., length(p) when p is a vector, so seq(p)-1 is the exponents of the polynomial, hence x^(seq(p)-1) is equivalent to x^0 (always equal to 1), x^1, x^2, ... and computing a dot product %*% with p evaluates the polynomial at x.
Additionally, if P is taken as a function, then this would be 38 bytes:
function(n,P,x)`if`(n,f(n-1,P,P(x)),x)

And we can of course always generate P by P=function(a)function(x)sum(x^(seq(a)-1)*a)

Jelly, 10 bytes
*⁹LḶ¤×⁹Sµ¡

Try it online!
Takes x, coefficients in ascending order, n in this order.
4 bytes
⁹v$¡

Try it online!
Takes x, Jelly link (may need to be quoted/escaped), n in this order.

APL (Dyalog), 20 9 bytes
{⊥∘⍵⍣⎕⊢⍺}

Try it online!
This takes x as the left argument, the coefficients of the function as the right argument, and n from STDIN.
Looking back at this after many a long time, I realised I could simplify the calculation by using base conversion ⊥.

APL (Dyalog), 5 bytes
If we can take the function as a Dyalog APL function, then this can be 5 bytes.
⎕⍣⎕⊢⎕

Takes x, n and then the function as input from STDIN.

05AB1E, 10 9 bytes
-1 byte thanks to Erik the Outgolfer
sF³gÝ¨m*O

Try it online!
Takes x as first argument, n as second and p in ascending order as third.
Explanation
sF³gÝ¨m*O
s         # Forces the top two input arguments to get pushed and swaped on the stack
 F        # Do n times...
  ³        # Push the third input (the coefficients)
   g       # Get the length of that array...
    Ý¨     # and create the range [0 ... length]
      m    # Take the result of the last iteration to these powers (it's just x for the first iteration)
       *   # Multiply the resuling array with the corresponding coefficients
         O # Sum the contents of the array
          # Implicit print

You can remove the second ³.

Also (This is in case n is 0 so x is on the stack) is wrong, you still need the s for non-zero n.

Yeah that's true. I was thinking more along the lines of replacing ¹².with s so it gets the job of pushing x to the stack done in 1 byte without needing to loop at least once. Probably should have worded that better ^^' .Also thanks for the -1!

I meant that you would still need it since 05AB1E uses the last input for implicit input if all inputs have been read.

"sF³gÝ¨m³O" and in the explanation too...

Damn you're fast. Fixed.

J, 15 bytes
0{(p.{.)^:(]{:)

Try it online!
Takes the polynomial as a list of coefficients of ascending powers.
Explanation
0{(p.{.)^:(]{:)  Input: polynomial P (LHS), [x, n] (RHS)
            {:   Tail of [x, n], gets n
           ]     Right identity, passes n
  (    )^:       Repeat n times starting with g = [x, n]
     {.            Head of g
   p.              Evaluate P at that value
                   Return g = [P(head(g))]
0{               Return the value at index 0

Haskell, 15 bytes
((!!).).iterate

Try it online!
Thanks to totallyhuman for 11 bytes off of both solutions
This defines a tacit function that takes a function as its first argument and n as its second argument, and composes that function with itself n times. This can then be called with an argument x to get the final value. Thanks to the magic of currying, this is equivalent to one function taking three arguments.

Taking a list of coefficients instead of a function argument:
Haskell, 53 bytes
((!!).).iterate.(\p x->sum$zipWith(*)p[x^i|i<-[0..]])

Try it online!
This is the same as the above code, but composed with a lambda function that converts a list of coefficients into a polynomial function. The coefficients are taken in reverse order from the examples - as ascending powers of x.

15 bytes.

The TIO of the second one should take a list as argument, not a function ;) Though you can save a handful of bytes by using a fold like this (note that the zero-polynomial can't be [] but must be something like [0] or similar).

Jelly, 4 bytes
⁴ḅ$¡

Try it online!
Full program that takes x p n as command line arguments
How it works
⁴ḅ$¡ - Main link. Takes x and p on the left
  $  - Previous 2 links as a monad f(x):
⁴    -   Yield p
 ḅ   -   Convert p from base x
   ¡ - Apply f(x) to x n times

Python 3, 70 69 bytes
f=lambda p,n,x:n and f(p,n-1,sum(c*x**i for i,c in enumerate(p)))or x

Takes p in ascending order, i.e. if p is [0, 1, 2] then the corresponding polynomial is p(x) = 0 + 1*x + 2*x^2. Simple recursion solution.
Try it online!

C# (.NET Core), 82 bytes
using System.Linq;f=(p,n,x)=>n<1?x:p.Select((c,i)=>c*Math.Pow(f(p,n-1,x),i)).Sum()

Try it online!
Takes a list of coefficients in the opposite order from the test cases (increasing order?) so that their index in the array is equal to the power x should be raised to.
And the trivial version in 30 bytes:
f=(p,n,x)=>n<1?x:f(p,n-1,p(x))

Try it online!
Takes a delegate and applies it recursively n times.

MATL, 11 bytes
ii:"ZQ6Mw]&

Try it online!
Slightly less interesting than my Octave answer, although I think there's some clever juggling of inputs to make sure n=0 works as expected.

Julia 0.6.0 (78 bytes)
using Polynomials;g(a,n,x)=(p=Poly(a);(n>0&&(return g(a,n-1,p(x)))||return x))
Explainations:
The package Polynomials is pretty self explanatory: it creates polynomials. After that it's a pretty basic recursion.
In order to have a polynomial:  -4.0 - 2.3*x + 0.1*x^2 the input a must be like a = [-4, -2.3, 0.1]

Axiom, 91 bytes
f(n,g,x)==(for i in 1..n repeat(v:=1;r:=0;for j in 1..#g repeat(r:=r+v*g.j;v:=v*x);x:=r);x)

indented
fn(n,g,x)==
     for i in 1..n repeat
          v:=1; r:=0
          for j in 1..#g repeat(r:=r+v*g.j;v:=v*x)
          x:=r
     x

the input for polynomy g it is one list of numbers in the reverse of the example of exercise.
for example
[1,2,3,4,5]

it would represent the polinomy
1+2*x+3*x^2+4*x^3+5*x^4

test:
(3) -> f(0,[0,0,1],3)
   (3)  3
                                                    Type: PositiveInteger
(4) -> f(1,[0,0,1],3)
   (4)  9
                                                    Type: PositiveInteger
(5) -> f(0,[-4,-2.30,0.1],2.3)
   (5)  2.3
                                                              Type: Float
(6) -> f(1,[-4,-2.30,0.1],2.3)
   (6)  - 8.7610000000 000000001
                                                              Type: Float
(7) -> f(2,[-4,-2.30,0.1],2.3)
   (7)  23.8258121
                                                              Type: Float
(8) -> f(9,[-4,-2.30,0.1],2.3)
   (8)  211.3326335688 2052491
                                                              Type: Float
(9) -> f(9,[-4,-2.30,0.1,0,0,0,0,1],2.3)
   (9)  0.4224800431 1790652974 E 14531759
                                                              Type: Float
                                   Time: 0.03 (EV) + 0.12 (OT) = 0.15 sec
(10) -> f(2,[-4,-2.30,0.1,0,0,0,0,1],2.3)
   (10)  44199336 8495528344.36
                                                              Type: Float

Röda, 41 bytes
f p,n,x{([0]*n)|x=_+p()|reduce _*x+_;[x]}

Try it online!
A trivial version:
f F,n{([_]..[0]*n)|reduce F(_)+_}

Try it online!
It takes the the value for x from the stream.

C++14, 71 bytes
As generic unnamed lambda, returning via the x Parameter:
[](auto C,int n,auto&x){for(auto t=x;t=0,n--;x=t)for(auto a:C)t=a+x*t;}

Ungolfed and testcase:
#include<iostream>
#include<vector>

using namespace std;

auto f=
[](auto C,int n,auto&x){
 for(
  auto t=x; //init temporary to same type as x
  t=0, n--; //=0 at loop start, also check n
  x=t       //apply the result
  )
  for(auto a:C)
   t=a+x*t; //Horner-Scheme
}
;

int main() {
 vector<double> C = {0.1,-2.3,-4};//{1,0,0};
 for (int i = 0; i < 10; ++i) {
  double x=2.3;
  f(C, i, x);
  cout << i << ": " << x << endl;
 }
}

QBIC, 19 bytes
[:|:=:*c^2+:*c+:}?c

Takes inputs as

Number of iterations
starting value of x
Then the 3 parts of the polynomial

Sample output:
Command line: 8 2.3 0.1 -2.3 -4
 59.30772

Clojure, 66 bytes
#(nth(iterate(fn[v](apply +(map *(iterate(partial * v)1)%3)))%2)%)

Full example:
(def f #(nth(iterate(fn[v](apply +(map *(iterate(partial * v)1)%3)))%2)%))
(f 10 2.3 [-4 -2.3 0.1])
; 3976.0831439050253

Composing a function is 26 bytes:
#(apply comp(repeat % %2))

(def f #(apply comp(repeat % %2)))
((f 10 #(apply + (map * [-4 -2.3 0.1] (iterate (partial * %) 1)))) 2.3)
; 3976.0831439050253

Japt, 18 bytes
Pretty straightforward, does what the challenge says on the tin.
o r_VË*ZpVÊ-EÉÃx}W
o                  // Take `n` and turn it into a range [0,n).
  r_            }W // Reduce over the range with initial value of `x`.
    VË             // On each iteration, map over `p`, yielding the item
      *Z           // times the current reduced value
        pVÊ-EÉ     // to the correct power,
              Ãx   // returning the sum of the results.

Takes inputs in order n, p, x.
Try it online!

Haskell, 39 bytes
p!x=(iterate(\y->foldl1((+).(y*))p)x!!)

Try it online!
(!) takes as input a polynomial p, represented as a list of coefficients, a real number x and an integer n, and returns \$p^n(x)\$.

Factor + math.polynomials, 35 bytes
[ [ [ polyval ] keep ] times drop ]

Try it online!
Takes a value, a list of coefficients (high powers on the right), and the number of times to iterate, in that order. polyval is a builtin word that evaluates a polynomial given a value and a list of coefficients.


text:
A Room Of Mirrors
(This challenge is very similar, but this current challenge has additional complications.)

Imagine a 2-dimensional room, where the walls are plated with flat mirrors.
Suddenly, a beam of light strikes into the room, where a piece of wall is missing! The lightbeam dances around the room, getting reflected by the wall mirrors, and eventually leaving the room again.
The Logic
You are given 5 variables: W, H, X, Y and Z.
Now, what do they mean?
W, H is the size of the room (including the walls), with W being width and H being height.
X, Y is the coordinate that the wall has the hole at. You can assume that this is always located on a wall tile. Coordinates are 0-based, with the X-axis pointing right and the Y-axis pointing down.
Z is a single character, representing the direction that the light falls into the room, either \ or  /.
The room has to be built up of the following characters:

| for horizontal walls
- for vertical walls
+ for corners

Example: (W=7,H=4)
+-----+
|     |
|     |
+-----+

Now that we have a room, lets destroy one of the wall tiles, so a beam of light falls into the room. Beams of light are diagonal lines, represented by \ and / characters.
Let's replace the wall tile at X=2, Y=0 with a \ beam of light.
+-\---+
|     |
|     |
+-----+

The incoming light travels diagonally across the room until it hits a mirror wall. If a wall is hit, the direction inverts along the axis of the wall, and the beam travels on.
+-\---+
|\ \/\|
| \/\/|
+-----+

In this example, the light beam gets to a point where a corner of the wall is hit, which inflicts that the beam gets reversed completely and travels all the way back, eventually leaving the room.
Your Task
Write a program that prints the room and the whole path of the light beam, until it leaves the room again or repeats into an infinite loop.
Input
Input may be received in any reasonable format, but it has to include the 4 integers W, H, X, Y and the character Z, for example [10, 8, 0, 3, \].
You may assume that:

W, H >= 3
X, Y are always located at a wall
Z will only be able to contain the values \ and /.

Output
You can decide if you return a string or directly output to stdout.
It has to include the room's wall and the light beam (defined by the ASCII characters above).
Rules

Standard loopholes are forbidden.
This is code-golf, so the shortest code in bytes, in any language, wins.
All coding languages that were created prior to the publication of this challenge are allowed.

Examples
Input: [5, 4, 2, 0, /]
+-/-+
|/ /|
|\/ |
+---+

Input: [20, 3, 0, 1, \]
+------------------+
\/\/\/\/\/\/\/\/\/\|
+------------------+

Input: [10, 8, 0, 3, \] (Example of an infinite loop that won't leave the room again.)
+--------+
|/\/\/\/\|
|\/\/\/\/|
\/\/\/\/\|
|\/\/\/\/|
|/\/\/\/\|
|\/\/\/\/|
+--------+

Good luck!

Charcoal, 55 bytes
ＢＮＮＪＮＮＰψ↷⎇⁼δ/⎇∧⁻⁻θ¹ζＩε⁷Ｉ3⎇∧ＩζＩε⁵Ｉ1Ｗ¬℅ＫＫ«¹Ｆ³¿∧κ℅ＫＫ«↷κ¶↷κ

Try it online! Link is to verbose version of code. Edit: I don't know why but that code isn't working right now. Here's a tweaked version instead. Explanation of the original code:
ＢＮＮ

Draw the outer box.
ＪＮＮＰψ

Move the cursor to the entry point and make a hole in the box at this point, so this becomes the background.
↷⎇⁼δ/⎇∧⁻⁻θ¹ζＩε⁷Ｉ3⎇∧ＩζＩε⁵Ｉ1Ｐ

Rotate to the appropriate direction to print the initial line segment.
Ｗ¬℅ＫＫ«¹

While the cursor is over a hole, draw the next line segment.
Ｆ³¿∧κ℅ＫＫ«↷κ¶↷κ

Look for a hole in which to draw the next line segment. This works by repeating the same code three times. The first time, nothing happens. The second time, if the cursor is not over a hole, it rotates right 45°, then takes one step to the right, then rotates right 45°. This has the effect of reflecting it in one axis. The third time, if the cursor is still not over a hole, it rotates right 90°, then takes one step to the right, then rotates right 90°. This has the effect of changing the reflection to the other axis. If there still isn't a hole, then a corner or infinite loop has been reached, so the outer loop halts.

In order for people to test your code works, it would help to have a link to the golfed code online, with the verbose version separately.

TIO works just fine with this code for me.

@trichoplax that was easy

@trichoplax The TIO link does actually shows the golfed code in the output, which is where I copy and paste it from...

Yes it all works fine. I was just making the general point that the beauty of TIO is that you can include a link that tests the golfed code, rather than people having to copy and paste. I'm not suggesting that this is essential, or that people aren't capable of copying and pasting - it just saves a little bit of time for each person viewing.

@trichoplax When you use -v -sl then it's actually the translated succinct code as printed that gets executed. This does of course depend on the deverbosifier generating correct succinct code, because if it doesn't, then the generated code fails, even though the original verbose code was technically correct.

Interesting - thanks for explaining. I wasn't familiar with this "deverbosifier".

source: Stack Exchange

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

sort: votes


text:
Stackin' Boards
I have a bunch of boards I need to stack in as small a space as possible.  Unfortunately, the boards fall over if I stack them more than 10 high.  I need a program to tell me how to stack the boards to take as little horizontal space as possible, without stacking boards more than ten high, or having boards hanging out over empty space.
Your Task:
Write a program or function, that when given an array containing the lengths of boards, outputs as ASCII art the way to stack the boards to conserve as much horizontal space as possible, without stacking the boards more than 10 high or having any part of any board hanging out over empty space.  Your ASCII art should show the configuration of the boards, with each one shown using a different character.  There will be a maximum of 20 boards. For example, if the input was [2,2,4,2,2,4,4,4], a possible output is:
dhh
dgg
dff
dee
abc
abc
abc
abc

which is a stable configuration (although this would fall over in ~0.1 seconds in real life).
Input:
An array containing up to 20 integers, showing the lengths of the boards.
Output:
ASCII art showing the configurations of the boards, as outlined above.
Test Cases:
Note that there may be other solutions for the test cases, and the characters shown for each board may be different.
[12,2,2,2,3,4,4,8,8]        -> ffgghhiii
                               ddddeeeeeeee
                               bbbbbbbbcccc
                               aaaaaaaaaaaa

[4,4,4,4,4,4,4,4,4,4,4,4]   -> llll
                               aaaa
                               cfghk
                               cfghk
                               cfghk
                               cfghk
                               debij
                               debij
                               debij
                               debij

[4,4,4,4,4,4,3,3,3,2,2,2,1] -> jjml
                               iiil
                               hhhk
                               gggk
                               ffff
                               eeee
                               dddd
                               cccc
                               bbbb
                               aaaa

Scoring:
This is code-golf, lowest score in bytes wins

Python 3, 513 512 511 509 499 497 485 465 459 458 444 bytes
Incredibly bad runtime, will finish at some point

e,j,c=enumerate,len,range
def f(n,p=[],o=97):
    r,l,m=lambda x:min(b,f(n[:i]+n[i+1:],x,o+1),key=j),chr(o),j(p)
    b=[p,l*(sum(n)*2+m)][n>[]]
    for i,a in e(n):
        for h,d in e(p):
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
            if(j(d)<10)*all(j(x)==j(d)for x in p[h:h+a])*(a<=m-h):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
        if a<11:b=r(p+[l*a])
        b=r(p+[l]*a)
    return["\n".join("".join(9-u<j(x)and x[9-u]or" "for x in b)for u in c(10)),b][o>97]

Try it online!
Edit: -2 -8 bytes thanks to @Mr. Xcoder
Edit: -8 bytes thanks to @notjagan
Explanation
e,j,c=enumerate,len,range
         # These built-ins are used a lot
def f(n,p=[],o=97):
         # n is the remaining blocks
         # p is the current stack
         # o is the ASCI code for the next letter to use
    r,l,m=lambda x:min(b,f(n[:i]+n[i+1:],x,o+1),key=j),chr(o),j(p)
         # r is the recursive call, that also selects the smallest stack found
         # l is the letter to use next
         # m is the length of the current stack
    b=[p,l*(sum(n)*2+m)][n>[]]
         # Sets the current best, if there are no remaining blocks, select the found stack, else we set it to be worse than the possible worst case
    for i,a in e(n):
         # Loop through all the remaining blocks
        for h,d in e(p):
         # Loop through all the columns in the current stack
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
         # If we can place the current block vertically in the current column, try it
            if(j(d)<10)*all(j(x)==j(d)for x in p[h:h+a])*(a<=m-h):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
         # If we can place the current block horizontally starting in the current column, try it
        if a<11:b=r(p+[l*a])
         # If the current block is lower than 10, try place it vertically to the right of the current stack
        b=r(p+[l]*a)
         # Try to place the current horizontally to the right of the current stack
    return["\n".join("".join(9-u<j(x)and x[9-u]or" "for x in b)for u in c(10)),b][o>97]
         # Return the best choice if we aren't in the first call to the function, that is the next letter is a. Else return the found best option formatted as a string

Python 3, 587 bytes
Actually runnable on TIO for some of the test cases
e,j,c=enumerate,len,range
def f(n,p=[],o=97,b=[]):
    if(not n):return p
    if not b:b="a"*sum(n)*2
    r,q,s,l,m=lambda x:q(f(n[:i]+n[i+1:],x,o+1,b)),lambda x:[b,x][j(b)>j(x)],b,chr(o),j(p)
    if j(b)<=m:return b
    for i,a in e(n):
        for h,d in e(p):
            if a<11-j(d):b=r([p[f]+l*a*(f==h)for f in c(m)])
            if j(d)<10 and a<=m-h and all(map(lambda x:j(x)==j(d),p[h:h+a])):b=r([p[f]+l*(h<=f<h+a)for f in c(m)])
        if s==b:
            if a<11and m+1<j(b):b=r(p[:]+[l*a])
            if m+a<j(b):b=r(p[:]+[l for r in c(a)])
    return["\n".join("".join(map(lambda x:" "if u>=j(x)else x[u],b))for u in c(9,-1,-1)),b][o>97]

Try it online!
Both solutions could probably be golfed quite a bit.

483 bytes

583 bytes for the second one

Mr. Xcoder, the second one can be reduced by near 50 bytes, I just havn't applied the changes for the first one to the second one

I know the second one can be golfed a lot, but the changes to the first one should be helpful.

They were, I also found a way to reduce it by 18 more bytes as well

462 bytes (-3 bytes), since p[:] is essentially just p.

You earned my upvote, for some great code with a wonderful explanation, that shows lots of effort and thought. Congrats  and welcome to PPCG!

-8 bytes.

442 bytes, and I think I can golf it even more.

418 (-26). You used if a<11:b=r(p+[l*a]), but it had no effect, since you were doing b=r(p+[l]*a) right after that anyway. Hope it helps!

411

@Mr.Xcoder I don't think that's removable, looks like he just forgot an else?

:| i don't even know if that leads to non-optimal solutions

Python3, 1081 bytes
Rather long, but crunches every test case, including several additional ones, in ~0.184 seconds
E=enumerate
R=range
from itertools import*
G=lambda l:[[j for j,_ in b]for a,b in groupby(E(l),key=lambda x:x[1]=='')if a]
def C(l,L,H):
 q=[([a],[i])for i,a in E(l)if a<=L]
 while q:
  A,I=q.pop(0)
  if sum(A)<=L and(H==0 or sum(A)==L):yield(tuple(A),I)
  for i,a in E(l[max(I)+1:],max(I)+1):
   if sum(T:=A+[a])<=L:q+=[(T,I+[i])]
def P(b,l,Q,t):
 for i,a in E(b):
  if''in a:
   F=0
   B,Y=eval(str(b)),[]
   for g in G(a):
    if(O:=[*C(l,len(g),t)]):
     F,d=1,{}
     for J,K in O:d[J]=K
     O=[*d.items()]
     M=max(sum(A)for A,_ in O)
     V,I=min([(o,p)for o,p in O if sum(o)==M],key=lambda x:len(x[0]));Y+=I
     for v in V:
      Q+=1
      for _ in R(v):B[i][g.pop(0)]=chr(Q)
   if F or t:return(B,[y for x,y in E(l)if x not in Y],Q)
def f(l):
 I,Q=1 if max(l)<11 else max(l),96
 while I:
  q,S=[(B:=[[''for _ in R(I)]for _ in R(10)],[*l],96)],[B]
  while q:
   b,L,Q=q.pop(0)
   if[]==L:return b
   if(C:=P(b,L,Q,1))and C not in S:q+=[C];S+=[C]
   if(C:=P([*map(list,zip(*b))],L,Q,0)):
    B,L,Q=C;
    if(B:=[*map(list,zip(*B))])not in S:q+=[(B,L,Q)];S+=[B]
  I+=1

Try it online!

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

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


text:
DropSort it like it's hot
As described in this question:

Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only some of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

To use one of their test cases, an input of {1, 2, 5, 4, 3, 7} yields {1, 2, 5, 7}, as 4 and 3 are both dropped for being smaller than the previously "sorted" value, 5.
We don't want "sorting" algorithms, we want them to be the real deal. Therefore, I want you to write a program that, given a list of numbers, outputs a list of DropSorted lists (to be a complete sorting algorithm, we would need to merge these lists, but
merging two sorted lists has been done before, and asking you to do it again is pretty much asking two questions, so this question is specifically the "splitting" step of our complete DropSort).
The arrangement and content of our lists is crucial, however. The output of your program must be equivalent to the output of a DropSort, followed by a DropSort of the discarded values, and so on until you have only have a list of sorted chains. Again, borrowing the existing test suite (and adding two more):
Input                  -> Output
{1, 2, 5, 4, 3, 7}     -> {{1, 2, 5, 7}, {4}, {3}}
{10, -1, 12}           -> {{10, 12}, {-1}}
{-7, -8, -5, 0, -1, 1} -> {{-7, -5, 0, 1}, {-8, -1}}
{9, 8, 7, 6, 5}        -> {{9}, {8}, {7}, {6}, {5}}
{10, 13, 17, 21}       -> {{10, 13, 17, 21}}
{10, 10, 10, 9, 10}    -> {{10, 10, 10, 10}, {9}}  //Note equivalent values aren't dropped
{5, 4, 3, 8, 7, 6}     -> {{5, 8}, {4, 7}, {3, 6}}
{0, 2, 5, 4, 0, 7}     -> {{0, 2, 5, 7}, {4}, {0}}

You may assume the input is non-empty.
This is code-golf, so standard rules apply!

Can we output like [5, 4, 3, 8, 7, 6] -> [5, 8], [4,3,7,6]?

@Xcoder, well I don't mind the syntax, but you still have to sort the second list (and split it in this case). Knowing when to stop is part of the challenge ;). And Stewie, I don't really know what to tell you. I saw the DropSort challenge and thought this sounded fun. Any chance you used your time machine to jump ahead and see this question? Just don't use it to see the best answer!

Note that adding the sorting of the left-overs takes the solutions out of linear time.

Should {3,4,5,3,4,5,3,4,5} result in {{3,4,5,5,5},{3,4,4},{3}}?

@QBrute I think that's right.

MATL, 15 10 9 bytes
5 bytes off using @beaker's idea of cumulative maximum
t"ttY>=&)

Input is a numeric row vector, in the format [1, 2, 5, 4, 3, 7] (commas are optional). The output contains lists separated by newlines, with the numbers in each list separated by spaces.
Try it online! Or verify all test cases.
Explanation
Given an array, the code picks from it every entry that equals the cumulative maximum up to that entry.
For example, given
1 2 5 4 3 7

the code picks the first, second, third and sixth entries:
1 2 5     7

Then the process is repeated on the subarray formed by the remaining entries (in the original order):
      4 3

This needs to be done until the subarray of remaining entries is empty. An upper bound on the required number of iterations is the input size. The last iterations may not be needed. In that case they operate on an empty array, producing additional empty arrays.
At the end, the stack contains the required arrays and possibly several empty arrays, which are not displayed at all.
t        % Implicit input. Duplicate
"        % Do as many times as the input size
  tt     %   Duplicate twice
  Y>     %   Cumulative maximum
  =      %   Compare for equality. Will be used as logical index
  &)     %   Two-output indexing: pushes indexed subarray, and then
         %   a subarray with the remaining entries
         % End (implicit)
         % Display stack (implicit). Empty arrays are not displayed

Haskell, 67 59 58 bytes
(q:r)!x|x<last q=q:r!x|1<2=(q++[x]):r
_!x=[[x]]
foldl(!)[]

Explanation: Given a list of lists (that are already sorted) and a value x, the ! operator will place x at the end of the first list whose last element is less than or equal to x. If no such list exists, the list [x] is placed at the end.
Try it online.

This is an incredibly clever solution. I honestly expected most people to just DropSort over and over until there was nothing left, but I hoped someone would think of a more creative way.

Husk, 10 bytes
hUmü<¡Ṡ-ü<

Try it online!
This is a combination of my other Husk answer and xnor's Haskell answer.
The duplicate ü< feels clunky, but I don't know how to get rid of it...
Explanation
The function ü< translates to nubBy(>) in Haskell.
It traverses a list from left to right, keeping those elements for which no previously kept element is strictly greater.
In other words, it performs dropsort.
The leftover elements are obtained by taking list difference of the original list and the result of ü<.
hUmü<¡Ṡ-ü<  Implicit input, say x = [2,3,5,4,4,2,7].
     ¡      Iterate
      Ṡ-    list difference between argument
        ü<  and its dropsort: [[2,3,5,4,4,2,7],[4,4,2],[2],[],[],[],...
  m         Map
   ü<       dropsort: [[2,3,5,7],[4,4],[2],[],[],[],...
 U          Prefix of unique elements: [[2,3,5,7],[4,4],[2],[]]
h           Drop last element: [[2,3,5,7],[4,4],[2]]

Outgolfs top answer by 33% "I dunno, it feels clunky"

Haskell, 50 bytes
import Data.List
f[]=[]
f l|r<-nubBy(>)l=r:f(l\\r)

Try it online!

I nearly had this, just didn't know the \\  function : (

Oh that is indeed a very handy function! Very nice solution=)

Husk, 16 bytes
hUm₁≤¡₁>
ṠfSz⁰G▲

Try it online!
Explanation
This first line is the main function, and the second is a higher order helper function (it takes a function as argument and returns a new function).
It's accessed by the subscript ₁.
The idea is that ₁≤ performs dropsort and ₁> gives the leftover elements.
ṠfSz⁰G▲  Helper function, takes binary function p (as ⁰) and list x (implicit).
         For example, p = (≤) and x = [2,4,3,4,5,2].
     G▲  Left scan on x with maximum: [2,4,4,4,5,5].
  Sz     Zip with x
    ⁰    using the function p: [1,1,0,1,1,0].
Ṡf       Keep elements of x at truthy indices: [2,4,4,5].

In the main function, we iterate the leftovers function ₁> and apply the dropsort function ₁≤ to the results.
hUm₁≤¡₁>  Main function, implicit list argument, say x = [2,4,3,4,5,2].
     ¡    Iterate
      ₁>  the leftovers function: [[2,4,3,4,5,2],[3,2],[2],[],[],[],...
  m       Map
   ₁≤     the dropsort function: [[2,4,4,5],[3],[2],[],[],[],...
 U        Prefix of unique elements: [[2,4,4,5],[3],[2],[]]
h         Drop last element (an empty list): [[2,4,4,5],[3],[2]]

Husk is the new Jelly...

@EriktheOutgolfer Beaten by MATL. :/

Python 3, 131 112 103 95 bytes
Thanks a lot @Mr. Xcoder for a smashing 19 bytes!!
Thanks a lot @ovs for an amazing 17 bytes!
def f(x):
 a,*x=x or[0];m=[a];d=[]
 for i in x:[m,d][i<m[-1]]+=i,
 return[m]+(x and(d>[])*f(d))

Try it online!
Explanation:
def f(x):               #recursive function taking list, returns list of lists
 if len(x)<2:return[x]  #for a single element return [element]
 m=[x[0]];d=[]          #initialize main and dropped lists
 for i in x[1:]:[m,d][i<m[-1]]+=[i]  #append elements from the argument list accordingly into main and dropped list
 return[m]+(d>[])*list(f(d)) #add main-list along with further evaluated dropped-list(recursived) into a list of lists

116 bytes. The if-else can be collapsed into [m,d][i<m[-1]]+=[i].

Woah , Thanks a lot... I was tryng that [m,d] thing but it was not working somehow....

113 bytes. (len(d)>0) is bool(d), because empty lists are falsy in Python. +1, Nice solution!

@Mr.Xcoder d>[] found it.. Thanks to your help... :)

Nice trick... Indeed, I missed that.

95 bytes

@ovs, Woah, Thanks a ton!!! I don't even know how that works!! The comma thing??

i, is just a short for (i,), which is a tuple containing a. a,*x = x or [0] is python3's extended unpacking. Here is an helpful SO post on this topic with some examples.

Haskell, 113 107 102 92 bytes
import Data.List
a!(b:c)|b<last a=a!c|1>0=a++[b]!c
a!b=a
g x@(b:c)|i<-[b]!c=i:g(x\\i)
g x=[]

Try it online!
This feels really long.
Explanation
! performs the drop sort on a list, while # collects the trimmings.  g then repeatedly applies # until the list is empty recording the results in a list.

Replacing head a with a!!0 saves a byte.

APL, 27 bytes
{⍵≡⍬:⍬⋄(⊂X/⍵),∇⍵/⍨~X←⍵≥⌈\⍵}

Explanation:

⍵≡⍬:⍬: if the input is empty, return the empty list
X←⍵≥⌈\⍵: all numbers greater or equal to the running maximum
(⊂X/⍵): the list of those numbers,
∇⍵/⍨~X: followed by the result of running this function on the remaining numbers

Save a byte with {⍵≡⍬:⍬⋄(⊂⍵~r),∇r←⍵/⍨⍵<⌈\⍵}. Morten is getting worried by the lack of response to his emails. Is everything alright?

Oh dear. I'm happy to here that you managed. See you next week.

JavaScript (ES6), 64 bytes
f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

Ungolfed:
f=(a,l,r=[])=>
  a+a&&                                    //any elements left?
  [a.filter(                               //filter elements that are in order,
    e=>e<l?!r.push(e):(l=e,1)              //push unsorted elements to r
   ),                                      //push() returns the new length of the array,
                                           //... so !push() will always return false
   ...f(r)                                 //recurse on r
  ]

f=(a,l,r=[])=>a+a&&[a.filter(e=>e<l?!r.push(e):(l=e,1)),...f(r)]

console.log(JSON.stringify(f([1, 2, 5, 4, 3, 7])));     // [1, 2, 5, 7][4][3]
console.log(JSON.stringify(f([10, -1, 12])));           // [10, 12][-1]
console.log(JSON.stringify(f([-7, -8, -5, 0, -1, 1]))); // [-7, -5, 0, 1][-8, -1]
console.log(JSON.stringify(f([9, 8, 7, 6, 5])));        // [9][8][7][6][5]
console.log(JSON.stringify(f([10, 13, 17, 21])));       // [10, 13, 17, 21]
console.log(JSON.stringify(f([10, 10, 10, 9, 10])));    // [10, 10, 10, 10][9]
console.log(JSON.stringify(f([5, 4, 3, 8, 7, 6])));     // [5, 8][4, 7][3, 6]
console.log(JSON.stringify(f([0, 2, 5, 4, 0, 7])));     // [0,2,5,7],[4],[0]

For a split second there I thought ?! was some fancy new operator...

Ha, yeah, I should have included an explanation.  Now added.

@Neil ?!

(i,n,o=[])=>[i.filter(a=>(n||a)<=a?(n=a,1):!o.push([a])),...o]
Apparently, great minds think (kind of) alike. Unfortunately I can't seem to shave off any more bytes... Just noting, you can remove f= in your code, and maybe my code might give you some ideas on how to golf yours even more.

Thanks, @DavidArchibald.  I can't remove f= from my code, because it's recursive.  Yours is an interesting approach, but it doesn't seem to work for a couple of the test cases.  For example, it returns [[5,8],[4],[3],[7],[6]]  for the next-to-last case.

I feel silly now that I missed both of those. I'll blame it on burnout. I really shouldn't codegolf after coding for hours. I even realized that it was recursive with the f(r) part. Funny that we both came up with !x.push() I haven't seen that anywhere.

I can relate to burnout.  An earlier version of my code had (r.push(e),0), which I soon realized could be shortened to !r.push(e).  Don't think I've seen that before either.

Java 8, 182 179 177 bytes
import java.util.*;l->{List r=new Stack(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Stack()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;}

-3 bytes thanks to @Nevay.
-2 bytes by using Stack instead of Vector.
Explanation:
Try it here.
import java.util.*;            // Required import for List and Vector
l->{                           // Method with ArrayList<Integer> parameter and List return-type
  List r=new Stack(),          //  Return-List
       t;                      //  Temp-List
  for(int p,i,x;               //  Some temp integers
      l.size()>0;)             //  Loop (1) as long as there are still items left in the list
    for(p=l.get(0),            //   Set `p` to the first item of the list
        r.add(t=new Stack()),  //   Add a new inner List to the result-List
        i=0;i<l.size();        //   Inner loop (2) from 0 to the size of the list (exclusive)
         p=x)                  //     After every iteration, save the previous value in `p`
      if((x=l.get(i++))>=p)    //    If the current item is equal or larger than the previous:
        t.add(l.remove(--i));  //     Add it to the temp-List, and remove it from the input-List
                               //   End of inner loop (2) (implicit / single-line body)
                               //  End of loop (1) (implicit / single-line body)
  return r;                    //  Return result-List
}                              // End of method

Can you use try{}catch{} instead of checking against l.size() to save some?

You can start the inner loop at 0 and remove the brackets of the outer for-loop l->{List r=new Vector(),t;for(int p,i,x;l.size()>0;)for(p=l.get(0),r.add(t=new Vector()),i=0;i<l.size();p=x)if((x=l.get(i++))>=p)t.add(l.remove(--i));return r;} (-3 bytes).

R, 61 bytes
f=function(x)if(sum(x|1)){print(x[b<-x==cummax(x)]);f(x[!b])}

Try it online!
Recursive function. sum(x|1) is shorthand for length(x), so this recursion will run untill x is empty. cummax takes the cumulative maximum of x, which is then compared to x again. This produces a boolean vector of length x, where all the TRUEs correspond to sorted values. We use that to take a subset of x and print it. The function is then called again on the remainder of x.

C#, 188 203 bytes
int[][]f(int[]a){int[]t=a.Where((n,i)=>i<1||n>=a[i-1]).ToArray(),m=a.Where((n,i)=>i>0&&n<a[i-1]).ToArray();var s=new int[][]{t}.ToList();if(m.Any())s.AddRange(f(m));return s.ToArray();}

The byte count includes +18 for:
using System.Linq;

Try it online!

@RickHitchcock Fixed at the cost of 15 bytes! Nice spot.

Good job : ) +1

C++14, 118 108 bytes
Using the algorithm from w0lf's Haskell answer.
As unnamed generic lambda. First parameter is a container of the values to dropsort (like vector<int>) and second parameter requires a compatible empty container of containers (like vector<vector<int>>) for the return value via reference.
In the first version of the program, there was R.clear;() as first statement, so that the container of containers didnt need to be empty.
Peter Cordes thought this could into the specification, so dropping 10 byte for that.
[](auto A,auto&R){for(auto x:A){for(auto&D:R)if(D.back()<x){D.push_back(x);goto F;}R.emplace_back(1,x);F:;}}

Try it online!
Ungolfed:
[](auto A,auto&R){
 for(auto x:A){       //foreach item
  for(auto&D:R)       //foreach result list
   if(D.back()<x){    //x bigger than last element
    D.push_back(x);   //add x
    goto F;           //break and jump over the emplace
   }
  R.emplace_back(1,x);//create new list with this element
  F:;
 }
}

You can probably get away with omitting the R.clear(), and just require the caller to start with an empty container.

@PeterCordes good idea, i might respec my other C++ answers which featured return via reference parameter.

Python 2, 88 bytes
-4 bytes thanks to Arnold Palmer
b,r=input(),[]
for i in b:
 for l in r:
	if l[-1]<=i:l+=[i];break
 else:r+=[[i]]
print r

Try it online!
Solution similar to @w0lf's haskell [answer][1]
Rare use case for for-else construction
Iterate through sorted lists for l in r (empty at start).
If element(from input) i is larger than last element of list l[-1], add element to list l+=[i], break.
If no list was accepted, add new list with this elemens r+=[[i]]

88 bytes by just taking it out of its function.

C (gcc), 176 175 173 bytes
#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;main(a){while(scanf("%d",*l+w)>0)++w;while(i=w){P(l[a=!a][w=0])for(j=1;j<i;++j){x=l[a][j];x<t?l[!a][w++]=x:P(x)}puts("");}}

Try it online!
Somewhat readable version:
#define P(x)printf("%d ",t=x);
l[2][99];t;x;i;j;w;
main(a)
{
    while(scanf("%d",*l+w)>0)++w;
    while(i=w)
    {
        P(l[a=!a][w=0])
        for(j=1;j<i;++j)
        {
            x=l[a][j];
            x<t?l[!a][w++]=x:P(x)
        }
        puts("");
    }
}

175 bytes.

Uhh, of course, how stupid -- thanks!

JavaScript (ES6), 71 70 68 bytes
a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o

Pretty simple, just iterates the array, looks for the first inner array whose last value is <= to the next value to drop, if none exists, append a new inner array with the next value to the output, otherwise append the next value to the first found inner array that matches the condition.
Updates
Thanks to Neil, saved three bytes converting (...,o) to ...&&o and re-organizing the callback to map() to be more compact.

f=a=>a.map(n=>(o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n),o=[])&&o;[[1,2,5,4,3,7],[10,-1,12],[-7,-8,-5,0,-1,1],[9,8,7,6,5],[10,13,17,21],[10,10,10,9,10],[5,4,3,8,7,6],[0,2,5,4,0,7]].map(f).map(JSON.stringify).map(v=>console.log(v))
.as-console-wrapper{max-height:100%!important}

&&o is a byte shorter than (,o).

@Neil gah! Great catch, thank you

I like your [...b].pop(), but I think (o.find(b=>[...b].pop()<=n)||(n=[n],o)).push(n) saves you a byte or two.

At this rate, I'll feel obligated to mark this as a community post... damn

Just because of a couple of tweaks? It's still basically the same code...

@Neil That second one was a pretty hefty rewrite. I don't think I would have figured that out myself, and that was the core of the algorithm. Sure it's still doing the same thing and you only saved 2 bytes, but it was pretty ingenious.

Not really, all I did was to move the [n] around a bit (the revision history shows that it wasn't that much of a change).

Nice job for a non-recursive approach.

Japt, 29 bytes
@lOpP)<1}a@=f_<VªOoV=Z+S}V=Ug

Test it online!

PHP, 102 bytes, 98 bytes
<?php function s($i){static$s;foreach($i as$v)${$v<max($l)?f:l}[]=$v;$s[]=$l;!$f?:s($f);return$s;}

Try it online!
-4 bytes, thanks to @Umbrella
Explanation
<?php

The function takes the input list as an array.
function s($i) {

$s, which will become the finally returned list of lists, is declared static. This
extends its scope to all calls of this function, allowing the function to be called
recursively without having to pass this result list as an argument or to return it.
    static $s;

Loop through each value in the list.
    foreach ($i as $v)

Is it less than the biggest current list member?
        $v < max($l) ?

Yes, put it on list $f for further sorting.
                        $f[] = $v :

No, put it on list $l.
                        $l[] = $v;

Push list $l onto the list of lists.
    $s[] = $l;

If there's anything in list $f, send it round again for further sorting.
    !$f ?: s($f);

Return the list of lists.
    return $s;
}

Accounting for the 31 chars I left out as <?php function d($a){return$r;}, you heartily crushed me.  Aside, I just realized we both forgot to output.

I've been golfing my solution down to try to beat yours without using yours and I found a way yours can be improved: I think you can save four characters by replacing $v<max($l)?$f[]=$v:$l[]=$v; with ${$v<max($l)?f:l}[]=$v; -- at least, it works in my tests.

@Umbrella, isn't returning, outputting??? And thanks for those 4 bytes. I never think of working like that, using code to evaluate the variable name. I must remember to consider that in future challenges…

Found it, consensus seems to accept returning as output: https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/2456#2456

PHP, 91 103 96 85 bytes
(Edited to add 12 chars of print_r($r); to meet requirement to output)
(Edited to remove 7 bytes when allowing PHP Errors)
(Edited to remove 11 bytes when golfing the assignment further)
while($a){$b=$d=[];foreach($a as$i)${max($b)>$i?d:b}[]=$i;$a=$d;$r[]=$b;}print_r($r);

Given input $a, it produces result $r
Pretty:
while ($a) {
    $b = $d = [];
    foreach ($a as $i) {
        ${max($b) > $i ? d : b}[] = $i;
    }
    $a   = $d;
    $r[] = $b;
}

The pseudo-recursive outer loop initializes the keep $b and discard $d arrays to empty, then does a basic drop sort loop, finally setting the discards as the new input and adding the keeps to the result $r

Sage, 102 bytes
def f(w,a=[]):
 for x in w:
  q,c=exists(a,lambda b:b[-1]<=x)
  if q:c+=[x]
  else:a+=[[x]]
 return a

Very similar to @Dead Possum's answer.
Appends each member x of w to the first list in a {list of lists} with x greater than it's last element.
if none, appends [x] to a.
I would really like it if exists returned a if nothing was found! Also trying to apply @officialaimm's one-line idea ...
Question: If I removed my code from the function, I'd have to assign w to input right? So would it save bytes?

APL, 100 88 83 79 78 57 56 77 76 bytes
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)}

-0 bytes thanks to Kritixi Lithos...
Try it online!
There's got to be some better way to do this (There is). Any tips are very greatly appreciated and welcome.
How?
(Note, some of this explanation might be wrong, as I forgot how this worked)
{⍵≡X←⍵/⍨~V←⍵≠⌈\⍵:⍵⋄X(∇V/⍵)} - separate the argument into nested drop-sorts
{⍵≡(S←¯1↓⍵),⊃⊃⌽⍵:⍵⋄∇S,⊃⌽⍵}  - un-nesting (passed the result of the above)
{(E/⍵),⊂⍵/⍨~E←(⍬≢⍴)¨⍵}∘     - fixing array mishaps (passed the result of the above)

{⍬≢⍴⍵} can become (⍬≢⍴)

ALready did that without seeing your comment,

What is the purpose of {(⍵/⍨~E),⊂⍵/⍨E←(⍬≡⍴)¨⍵}? It seems to be separated from everything else

Without it, the first test case would be something like [[1,2,5,7],[4],3], instead of the required [[1,2,5,7],[4],[3]].

You might be able to shorten that dfn to just (,¨)

I think ,¨∘ works, and thank you so much Kritixi! (It sounds more like a name, I'm sticking with that)

Never mind. Nope. Nope. Nope. Nope. Nope. Fails on (10 ¯1 12 0 1).

Jelly, 26 bytes
<»\¬x@ðW;µ⁸Ñ
<»\x@µÑ
1Ŀ¹L?

This is the same method as marinus' APL answer.
Try it online!.

Ocaml, 69 62 bytes
let rec d=function h::i::t when h>i->d(h::t)|h::t->h::d t|x->x

Explanation:
let rec d = function (* Implicitly take an list as a parameter *)
    (* If the list starts with two elements h and i and h is greater than i, drop i and sort the list starting with h and the rest t *)
    | h::i::t when h > i -> d (h::t)
    (* If h is not greater than i, make a new list starting with h and a tail containing the drop sorted rest *)
    | h::t -> h::d t
    (* If none of the cases apply, the list is empty. *)
    | x -> x

JavaScript (Node.js), 125 109 106 bytes
-16 18 bytes from Zacharý
-1 by removing { and } by changing the incrementer to include the "set last to the current"
m=x=>{z=[[],[]];l=NaN;for(i=0;i<x.length;l=x[i++])if(l>x[i])z[1].push(x[i]);else z[0].push(x[i]);return z}

Basically, asks is the current item greater than the last item, add to the first list. Otherwise, add to the second.
Found out during this that comparing any number to NaN will always result false. Interesting!
Explanation:
m = x => {                         // Create function
  z = [[], []];                      // Initialize dropsort output
  l = NaN;                           // Initialize last element
  for (i = 0; i < x.length; l=x[i++])// For each item in input...
    if (l > x[i])                    // If current item is greater than previous
      z[1].push(x[i]);               // Then add it to the first part of output
    else                             // Elsewise
      z[0].push(x[i]);               // Add it to the nonordered part of the dropsort
                                     // Set last item to current item
  }                                  // Repeat
  return z                           // Return finished dropsort
}                                    // End function

Try it online!

Do you have to use var?

@Zacharý, let me check!

The parens aren't needed around x.


text:
Approximate the Dottie number to arbitrary precision
The Dottie number is the fixed point of the cosine function, or the solution to the equation cos(x)=x.1
Your task will be to make code that approximates this constant.  Your code should represent a function that takes an integer as input and outputs a real number.  The limit of your function as the input grows should be the Dottie number.
You may output as a fraction, a decimal, or an algebraic representation of a number.  Your output should be capable of being arbitrarily precise, floats and doubles are not sufficient for this challenge.  If your language is not capable of arbitrary precision numbers, then you must either implement them or choose a new language.
This is a code-golf question so answers will be scored in bytes, with fewer bytes being better.
Tips
One way of calculating the constant is to take any number and repeatedly apply the cosine to it.  As the number of applications tends towards infinity the result tends towards the fixed point of cosine.
Here is a fairly accurate approximation of the number.
0.739085133215161

1: Here we will take cosine in radians

So, if we are using Python, we must implement our own type or import Decimal?

How accurate must our submissions be?

Goes to Jelly tutorial to steal ÆẠȷ¡ realizes it's invalid. Tries Brachylog; oh no Brachylog doesn't even do floats.

@Mr.Xcoder They must only be asymptotically accurate.

I feel like the "arbitrarily precise" requirement is a bit too stringent.  Why not consider an answer valid once x=cos(x)?

@kamoroso94 Because then answers can output the value without calculation.  The arbitrarily precise requirement requires that answers actually be calculated as opposed to simply stored in the source.

Ah I see, that is quite an unfortunate loophole.  Thanks for explaining.

Possible duplicate of Approximate the plastic number (instead of x^3-1=x we have cos(x)=x)

@Sanchises I don't believe this is a duplicate.  In some languages, those with equation solvers, the two tasks are very similar.  However the majority of languages don't have these.  The most common algorithm for solving here simply doesn't work on the other question.

For a computer "arbitrary precise" is it too much, because each number use memory, and memory is limited. Perhaps better  "arbitrary precise until one upper bound", for example digits until 10^4 or until memory of PC allow that calculation

I would like to see this in Haskell, APL, and some Lisp flavor.

Can you please judge on whether my answer is valid or not? I claim that I am returning an arbitrarily precise algebraic representation of the number, as per the definition of the number itself.

@MarkC Better late than never. There are now two APL answers here.

... one of which was deleted as invalid.

MATL, 34 30 19 bytes
11 bytes off thanks to Sanchises!
48i:"'cos('wh41hGY$

The last decimal figures in the output may be off. However, the number of correct figures starting from the left increases with the input, and the result converges to the actual constant.
Try it online!
Explanation
For input n, and starting at x=1, this applies the function
              x ↦ cos(x)
with n-digit variable-precision arithmetic n times.
48         % Push 48, which is ASCII for '1': initial value for x as a string
i:"        % Do n times, where n is the input
  'cos('   %   Push this string
  w        %   Swap. Moves current string x onto the top of the stack
  h        %   Concatenate
  41       %   Push 41, which is ASCII for ')'
  h        %   Concatenate. This gives the string 'cos(x)', where x is the
           %   current number
  GY$      %   Evaluate with variable-prevision arithmetic using n digits
           %   The result is a string, which represents the new x
           % End (implicit). Display (implicit). The stack contains the last x

Why not just apply it n times at n digits precision? This seems overly complicated.

This is incredible. I want to see it in APL.

dzaima/APL, 55 bytes
⎕←⊃{⍵,⍨-/P,((P÷⍨×)/¨(2×⍳N)⍴¨⊃⍵)÷!2L×⍳N}⍣{⍵≢∪⍵}P←10L*N←⎕

Using big integer (no big decimals!) arithmetic (where \$10^N\$ is the equivalent of a 1), iterate the first \$N\$ terms of the Taylor series (an overestimate, but that's fine) until a duplicate has been encountered. May be off by a bit due to lost precision in the end, but, as with other answers, those differences will disappear with higher \$N\$.
 No TIO link as TIO's dzaima/APL hasn't been updated to support bigintegers.
Example I/O:
1
9L

10
7390851332L

100
7390851332151606416553120876738734040134117589007574649656806357732846548835475945993761069317665318L

200
73908513321516064165531208767387340401341175890075746496568063577328465488354759459937610693176653184980124664398716302771490369130842031578044057462077868852490389153928943884509523480133563127677224L

Python 3, 58 bytes
lambda n:S('cos('*n+'0'+')'*n).evalf(n)
from sympy import*

Try it online!

A version in Python 2 that doesn't memory error as quickly.

No evalf in M :o

GNU bc -l, 30
Score includes +1 for -l flag to bc.
for(a=1;a/A-b/A;b=c(a))a=b
a

The final newline is significant and necessary.
Try it online.
-l does 2 things:

enable the "math" library, including c() for cos(x)
sets precision (scale) to 20 decimal places (bc has arbitrary precision calculation)

I'm not really clear on the precision requirement.  As it is, this program calculates to 20 decimal places.  If a different precision is required, then scale=n; needs to be inserted at the start of the program, where n is the number of decimal places.  I don't know if I should add this to my score or not.
Note also that for some numbers of decimal places (e.g. 21, but not 20), the calculation oscillates either side of the solution in the last digit.  Thus in the comparison of current and previous iterations, I divide both sides by 10 (A) to erase the last digit.

According to current consensus on scoring flags, the score of this answer is now 29.

Wolfram Language (Mathematica), 19 bytes
Nest[Cos,0,9#]~N~#&

Try it online!
-3 bytes from @alephalpha

-3 bytes: Cos@#& -> Cos

@alephalpha yes, sure. old times...

R (+Rmpfr), 55 bytes
function(n,b=Rmpfr::mpfr(1,n)){for(i in 1:n)b=cos(b);b}

Dennis has now added Rmpfr to TIO so this will work; added some test cases.
Explanation:
Takes the code I wrote from this challenge to evaluate cos n times starting at 1, but first I specify the precision I want the values to be in by creating an object b of class mpfr with value 1 and precision n, n>=2, so we get more precision as we go along.
Try it online!

Try again. :) In the future, if anything is missing from TIO, don't hesitate to drop a message in http://talk.tryitonline.net.

@Dennis Thank you! I'll keep that in mind in the future!

Octave, 42 bytes
@(n)digits(n)*0+vpasolve(sym('cos(x)-x'));

Try it online!
Pretty much a duplicate of my answer to Approximate the Plastic Number, but somewhat shorter due to more relaxed requirements.

Mathics or Mathematica, 46 bytes
{$MaxPrecision=#}~Block~Cos~FixedPoint~N[1,#]&

Try it online!

PHP, 50 bytes
$a=$argv[1];$i=$j=0;while($i<$a){$j=cos($j);$i++;}

Try it online!

Welcome to the site! :)

I believe that for($a=$argv[1];$a--;)$j=cos($j);echo$j; (40 bytes) is enough.

Pyth, 57 54 bytes
u_.tG1lX$globals()$"neg"$__import__("decimal").Decimal

This would be much shorter if we didn't need the Decimal to be up to spec, but it is what it is.
Edit 1: -3 bytes because we need a number anyways, so we can use Xs returned copy of globals() length as our starting value, moving it to the end and removing a $ and some whitespace.
Try it online!

JavaScript (Node.js), 84 bytes
n=>"0."+(F=(J,Z=c=0n)=>J?F(J*-I*I/++c/++c/B/B,Z+J):I-Z>>2n?(I=Z,F(B)):I)(B=I=10n**n)

Try it online!
Has a precision of roughly n-1 digits. BigInt is used and cos(x) is calculated using its Taylor expansion. The I-Z>>2n part is used only to prevent looping forever (with a cost of 4 bytes and some precision). Although theoretical applicable for arbitrary precision, practical range is n<63 because of stack overflow.
Shorter (82 bytes), no worries about stack overflow, but far fewer precision
n=>"0."+eval("for(I=B=10n**n;n--;I=Z)for(Z=J=B,c=0n;J;)Z+=(J=J*-I*I/++c/++c/B/B)")

Much shorter (80 bytes), larger range until stack overflow (n<172), but same precision as the 82-byte.
n=>"0."+(F=(J,Z=c=0n)=>J?F(J*-I*I/++c/++c/B/B,Z+J):n--?(I=Z,F(B)):I)(B=I=10n**n)

If arbitrary precision is not the main point, then 25 bytes:
F=n=>n?Math.cos(F(n-1)):1

82 detect precision

Factor + math.polynomials math.factorials, 66 bytes
[| x | 1 x [ sq neg x [0,b) [ 2 * n! recip ] map polyval ] times ]

Try it online!
Factor has rational numbers, but no arbitrary-precision decimals. This answer tries to exploit it as much as possible: iterate the evaluation of the fist n terms of Taylor series (more precisely, Maclaurin series) n times, with the starting value of 1. The output is given as a rational number; the floating-point representation is also shown on TIO to check the value in human-readable form.
The function is very slow to calculate and very slow to converge, but in theory it must converge to the Dottie number as n increases, since the iterated function approaches the cosine function, the iteration count increases to infinity, and the whole computation is done in rationals (and therefore exact).
How it works
Given a positive integer \$n\$, the code approximates the Dottie number as follows:
$$
\cos{x} = \sum_{i=0}^{\infty}{\frac{(-1)^i}{(2i)!}x^{2i}}
\approx \sum_{i=0}^{n-1}{\frac{(-x^2)^i}{(2i)!}} \\
\text{Dottie number } = \cos{x} \text{ iterated } \infty \text{ times on } 1 \\
\approx \sum_{i=0}^{n-1}{\frac{(-x^2)^i}{(2i)!}} \text{ iterated } n \text{ times on } 1
$$
[| x |  ! an anonymous function that takes one arg `x` as a local variable
  1 x [ ... ] times  ! repeat the inner function x times on the value 1...
    sq neg           !   val -> -val^2
    x [0,b)          !   0..x-1
    [ 2 * n! recip ] map  ! convert each number `i` to 1/(2i)!
    polyval          !   evaluate the array as polynomial at the value of -val^2
]

64 bytes

Julia 1.0, 42 bytes
!n=big(n<2||setprecision(()->cos(!~-n),n))

Try it online!
sets the precision of BigFloats to n bits and computes \$cos^{n-1}(1)\$ recursively

Perl 5, 41 Bytes
use bignum;sub f{$_[0]?cos(f($_[0]-1)):0}

Bignum is required for the arbitrary precision. Defines a function f that recursively applies cosine to 0 N times.
TIO doesn't seem to have bignum so no link :(

Mathematica 44 Bytes
FindRoot[Cos@x-x,{x,0},WorkingPrecision->#]&

FindRoot uses Newton's method by default.

Axiom, 174 bytes
f(n:PI):Complex Float==(n>10^4=>%i;m:=digits(n+10);e:=10^(-n-7);a:=0;repeat(b:=a+(cos(a)-a)/(sin(a)+1.);if a~=0 and a-b<e then break;a:=b);a:=floor(b*10^n)/10.^n;digits(m);a)

ungolfed and commented
-- Input: n:PI numero di cifre
-- Output la soluzione x a cos(x)=x con n cifre significative dopo la virgola
-- Usa il metodo di Newton a_0:=a  a_(n+1)=a_n-f(a_n)/f'(a_n)
fo(n:PI):Complex Float==
  n>10^4=>%i
  m:=digits(n+10)
  e:=10^(-n-7)
  a:=0     -- Punto iniziale
  repeat
     b:=a+(cos(a)-a)/(sin(a)+1.)
     if a~=0 and a-b<e then break
     a:=b
  a:=floor(b*10^n)/10.^n
  digits(m)
  a

results:
(3) -> for i in 1..10 repeat output[i,f(i)]
   [1.0,0.7]
   [2.0,0.73]
   [3.0,0.739]
   [4.0,0.739]
   [5.0,0.73908]
   [6.0,0.739085]
   [7.0,0.7390851]
   [8.0,0.73908513]
   [9.0,0.739085133]
   [10.0,0.7390851332]
                                                               Type: Void
           Time: 0.12 (IN) + 0.10 (EV) + 0.12 (OT) + 0.02 (GC) = 0.35 sec
(4) -> f 300
   (4)
  0.7390851332 1516064165 5312087673 8734040134 1175890075 7464965680 635773284
  6 5488354759 4599376106 9317665318 4980124664 3987163027 7149036913 084203157
  8 0440574620 7786885249 0389153928 9438845095 2348013356 3127677223 158095635
  3 7765724512 0437341993 6433512538 4097800343 4064670047 9402143478 080271801
  8 8377113613 8204206631
                                                      Type: Complex Float
                                   Time: 0.03 (IN) + 0.07 (OT) = 0.10 sec

I would use the Newton method because it would be faster
than 'repeated cos(x) method'
 800   92x
1000  153x
2000  379x

where in the first column there is the number of digit
and in the second column there is how much Newton method
is faster than use repeated cos(x) method, here.
Good Morning

PowerShell Core, 35 bytes
1.."$args"|%{$x=[Math]::Cos($x)}
$x

Try it online!

Vyxal, 6 bytes
(∆c)$Ḟ

Try it Online!
Uses sympy's arbitrary-precision cosine function. Since decimals are outputted to a fixed precision (although stored as arbitrary-precision) it has to be taken to n decimal places.
(  )   # n times
 ∆c    # cosine
    $Ḟ # result to n decimal places

Maxima, 93 bytes
A port of @MarcMush's Julia 1.0 answer in Maxima.
93 bytes, it can be golfed much more.

Golfed version. Try it online!
b(n):=block([o],o:fpprec,fpprec:n,r:if n<2 then bfloat(n)else bfloat(cos(b(n-1))),fpprec:o,r)

Ungolfed version. Try it online!
/* Define the recursive function with dynamic precision */
b(n) := block(
    [old_prec],
    /* Save the old precision */
    old_prec: fpprec,
    /* Set the precision relative to n */
    fpprec: n,
    /* Perform the calculation with the new precision */
    result: if n < 2 then bfloat(n) else bfloat(cos(b(n-1))),
    /* Restore the old precision */
    fpprec: old_prec,
    /* Return the result */
    result
);

/* Print the results from 1 to 1000 */
for i:1 thru 1000 do (
    print(b(i))
);

Pari/GP, 47 bytes
f(n)=if(n,subst(Pol(cos(x+O(x^n))),x,f(n-1)),1)

Try it online!

Haskell, 267 bytes
f d=(iterate(\(b,e)->r(\(x,y)(z,w)->(x*10^(2*d-y)+z*10^(2*d-w),2*d))(0,0)$takeWhile((/=0).fst)[r(\(x,y)(z,w)->(x*z,y+w))((-1)^n,0)[let z=2*e*n;s=max(z-d)0in(b^(2*n)`div`10^s,z-s),(10^d`div`product[2..2*n],d)]|n<-[0..]])(7,1))#[];(h:t)#v|h`elem`v=h|0<1=t#(h:v);r=foldr

Try it online!

J-uby, 33 bytes
Takes the desired precision as an argument.
~:!~%(:& &~(:cos&BigMath))&0.to_d

Attempt This Online!

Go, 71 bytes
import."math"
func f(n int)(k float64){for;n>=0;n--{k=Cos(k)}
return k}

Attempt This Online!
Input is the number of times to apply cos. Limited to 64-bit floating point precision.

APL(NARS), 219 chars
R←{⍵=0:⍵⋄10≥m←(⍺-⍨⌊10⍟d←∣1∧÷⍵×1x)⌊⍺-⍨⌊10⍟n←∣1∧⍵×1x:⍵⋄(×⍵)×(⌊n÷q)÷⌊d÷q←{(10∘×⍣⍵)1x}m-5}

r←p C w;d;e;v;m
r←d←1⋄e←1÷10x*p⋄v←¯1,0⋄m←w×w×¯1
r+←d×←m÷×/v+←2⋄→2×⍳e<∣d⋄r←p R r

r←D w;e;v
e←1÷10x*w⋄v←1x
r←w C v⋄→0×⍳e>∣v-r⋄v←r⋄→2

C is the cos function, has as parameters p the precision (or the number of digits afther the decimal point)
and w the rational number (here represented using r as in 23r4 for 23/4) and return a rational. If the argument
of that function is a int or a float, it return one float. For 3 significative digits we have
      3 C 1
0.5403028025
      3 C 1x
4357r8064
      2○1
0.5403023059

D is the function that would return the number in question that has argument the digit of precision.
How appear one fractional result?
      D 3
117407r158925

So there is need one function that traslate the fractional result in a decimal string we can read
r2fs: input ⍺ the precision ⍵ one rational number
r2fs←{⎕ct←0⋄k←≢b←⍕⌊⍵×10x*a←⍺⋄k-←s←'¯'=↑b⋄c←{s:'¯'⋄''}⋄m←s↓b⋄0≥k-⍺:c,'0.',((⍺-k)⍴'0'),m⋄c,((k-⍺)↑m),'.',(k-⍺)↓m}

One has to note as ⎕ct is a local varible in r2fs and its value in use out of that function is different.
So all could be more clear
      8 r2fs¨ D¨ 1 2 3 4 5 6 7 8
 0.70224186 0.73556389 0.73875727 0.73905483 0.73908230 0.73908552 0.73908517 0.73908513
      19 r2fs D 20
0.7390851332151606416
      40 r2fs D 39
0.7390851332151606416553120876738734040131
      39 r2fs D 40
0.739085133215160641655312087673873404013

For the C function sometime the result is not ok for float input
     10 C 45
55.65114514
      2○45
0.5253219888
      10 C 45
55.65114514
      2○45
0.5253219888

but the fraction input it seems converge right for cos
      49 r2fs 50 C 45x
0.5253219888177296960474644048235629188973106884573

One other problem one has to solve here it seems to me that the function D can converge to that number but its fraction in r
is so big that consume all resources so have to be cut in some way... I would say one could reduce the size of the fraction in memory
cuting the final parts of the numerator and denomicator (save all the digits of both until precision number),
something as function R make (for me R has to be used inside the cos).

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


text:
Cardinal Code Challenge
Task
You're in charge of making a compass, of sorts.
Imagine your source code as the compass "needle" where running at different orientations produces distinct output.
Supported source code orientations are North, East, South, and West.
Example
Let's say you have source code:
ABCD
 J K
WXYZ

We'll consider this the North orientation, rotating 90 degrees clockwise points us to the East:
W A
XJB
Y C
ZKD

rotating again points South:
ZYXW
K J
DCBA

and finally, the last rotation to the West:
DKZ
C Y
BJX
A W

When ran, each of the above code examples should output a single, distinct printable ASCII character of your choosing.
Notes
Your code shall take no input.
Empty spaces or new lines do not collapse/disappear when rotating.
Leading/trailing new lines are okay in output.
Answers may be whole programs or functions, thus output to STDOUT or return the function result.
Standard code-golf rules apply; shortest answer in bytes wins!

May we output more than 1 character?

Does a newline count as a printable character? (I don't think so, just asking for clarification.)

Do we have to pad the code with spaces so it's a perfect rectangle (and count those spaces in our score)? For example, would code shaped like this be valid, given the first one is the submission?

Apart from the output spec, I think this is a duplicate

@Mr.Xcoder Output should be a single character.  I originally wanted only N, E, S, W, as output but thought perhaps that was too difficult or unnecessarily constraining.

@BusinessCat You do not have to pad your code to make a rectangle - that example you provided would be valid.

@ETHproductions New lines aren't printable ASCII to my knowledge.

@CzarMatt What if our source is 0 or 1 byte(s) long? Is a program like Z acceptable?

@Mr.Xcoder Um, how could 4 identical programs print 4 different ASCII chars?

@DigitalTrauma Darn, and here I was searching for examples with "compass" in the q/a.  :)  Also, I was hoping putting this in the sandbox would surface any potential dupes.

@DigitalTrauma The comment rules make a big difference in the two.

What about trailing whitespace in output, is that ok? Specifically I'm wondering about a single trailing space.

@CzarMatt Would the score of your example be 13 or 14 bytes if the space on South can be omitted? (i.e. do we count the smallest or the largest rotation?)

Jelly, 2 bytes
*2

Try it online!
Note that the main entry for a Jelly program is its last link, where any newline character will split links), neither of the two-line programs actually access their top link.
The four full programs, all of which implicitly print their result, are:
North:
*2   -> (implicit) zero raised to the power of 2 = 0

East:
*
2    -> literal 2 = 2

South:
2*   -> two raised to the power of (implicit) 2 = 4

West:
2
*    -> (implicit) zero raised to the power of (implicit) zero = 1

This is the final answer. Well done.

Japt, 3 2 bytes
gy

Somehow, somehow, I found an extremely hacky 2-byte solution...

North outputs 0:
gy

Since there's no implicit input, it defaults to 0. g on a number returns the sign of the number regardless of its arguments ("y" in this case).

East outputs 2:
g
y

In a multi-line program, the first line sets the input to its result. This is basically a no-op, since g on 0 is 0. Then y returns the GCD of 0 and... since it's missing an argument, it defaults to 2 (thanks, @Oliver!). This gives 2 as the output.

South outputs g:
yg

y, as before, is GCD. Since gcd(0, x) is x for any value, y on 0 takes the liberty of just returning its argument. In this case, the argument is "g", which is the result.

West outputs 1:
y
g

y on 0, as before, returns 2. This is then passed to g, which (as already discussed) is the sign function on numbers. Therefore, the result is 1.

Java (OpenJDK 8), 7309 4421 855 bytes
-2888 bytes thanks to Leaky Nun
-3566 bytes thanks to Wheat Wizard
//i/////////////////////////////////////////////////////////////
//n//////////////////////////////////////////////////////////////////
interface M{static void main(String[]a){System.out.println(0);}}/////
//e//}};)2(nltnirp.tuo.metsyS{)a][gnirtS(niam diov citats{M ecafretni
//r//////////////////////////////////////////////////////////////////
//f}/////////////////////////////////////////////////////////////////
//a}//
//c;//
//e)//
// 3//
//M(//
//{n//
//sl//
//tt//
//an//
//ti//
//ir//
//cp//
// .//
//vt//
//ou//
//io//
//d.//
// m//
//me//
//at//
//is//
//ny//
//(S//
//S{//
//t)//
//ra//
//i]//
//n[//
//gg//
//[n//
//]i//
//ar//
//)t//
//{S//
//S(//
//yn//
//si//
//ta//
//em//
//m //
//.d//
//oi//
//uo//
//tv//
//. //
//pc//
//ri//
//it//
//na//
//tt//
//ls//
//n{//
//(M//
//1 //
//)e//
//;c//
//}a//
//}f//
///r//
///e//
 //t//
 //n//
 //i//

Try it online!
Old version
Straightforward aproach with comments wrapping the code^2 square, this can be done in pretty much any language.
a (more readable) example in python

##p#####
# r  2 #
print 1#
# n  t #
# t  n #
#4 tnirp
# 3  r #
#####p##

Great general appraoch, now I just need to figure out how to do it! :)

You can use interface M{static void main(String[]a){System.out.println(0);}} instead to save some bytes.

Would this be work? Its way shorter

"straightforward", he says. I'd hate to do that by hand.

@MagicOctopusUrn it wasn't done by hand c;

@MagicOctopusUrn nah, I made this answer to show this algorithm, the language is irrelevant :3

Ahhh... after sorting oldest you WERE the first to do this, nice.

Brain-Flak, 33 bytes
##)(##))()()  ((
((  ))##    ()##

Try it online!
Brain-Flak, 33 bytes
##)     ## #
(( ))#)())()
  # ( (

Try it online!
Brain-Flak, 36 bytes
#)##     ## #
  (())#)())()
 #   ( (

Try it online!
Brain-Flak, 38 bytes
######  (#
(()()())#))((
       #(  ##

Try it online!
Brain-Flak, 41 bytes
##(#####(#
(()()())#
##))()((
####((#)#)#

Try it online!

Holy crap! I was working on one, but I couldn't get anywhere. I thought it would take atleast 30-40 minutes of work to figure something out. This is amazing!

This is very cool!

Trying to golf you :P so far have 3 of them working

Alice, 17 bytes
1/ 3<
vPo</
5} @<

Outputs 1. Try it online!
5v1
}P/
 o
@<3
</<

Outputs x. Try it online!
<@ }5
/<oPv
<3 /1

Outputs 5. Try it online!
</<
3<@
 o
/P}
1v5

Outputs 3. Try it online!

05AB1E, 5 3 bytes
Y'X

North, East, South, West

Impressive, that was quick!

@MagicOctopusUrn I think Y'X will work, but I have to try it still.

@Riley it does, also it works forward and backwards, Y'X is also valid. Still looking for a 2-byte though; none of the 'dot commands' work for it, so I'm doubtful it exists.

@MagicOctopusUrn I don't think there is a 2 byte solution with the way newlines work. It wouldn't be hard to brute Force though.

10 would've worked if they allowed multiple characters for an output ;P.*

@MagicOctopusUrn That was my first thought too.

Brute-Forcer v0.3

Befunge, 17 13 bytes
I thought Befunge would be fun for a geometrical problem. There is a trivial 4x4 solution akin to others here (I need 3 commands) but I managed a bit better.
Edit: forgot about newlines
Edit 2: realized I could create a cat
Edit 3: the cat is dead
2v3
@.v
.
1@.

RIP kitty :<
1.@ 2
^._.^
3 @.4

Lost, 45 bytes
v////v1//v(((
\(((%>2@0>%(((\
  (((v//3v////v

Try it online!
To recap the gimmick of lost from the esolangs wiki:

Lost is a 2-Dimensional language where the instruction pointer starts at a random location, moving in a random direction. Despite this, Lost is still capable of creating completely deterministic programs.

So at first glace, Lost is perhaps not the ideal language for this challenge because of its incredible fragility.

C (gcc), 283 279 209 bytes
/////////)pm//
/////////;ua//
main(){//}ti//
puts("N"//sn//
);}///////((//
//////////")//
///"//////W{//
///E//////"///
//)"//////////
//((///////};)
//ns//"S"(stup
//it}//{)(niam
//au;/////////
//mp)/////////

Try it online!
Same old comment trick here, but at least, in C this doesn't get huuuge ;)

-4, thanks to ETHproductions!
fixed W direction and -70 (!) bytes thanks to comments by ETHproductions

Do you need any of the four slashes on the right edge right above the gap?

Hey .. uhm ... I guess, actually ... no. Good catch, thanks :)

I think you can pack it together quite a bit more tightly by moving each );} to the line below, like so (I haven't tested the rotations though)

Oh, the W program in your current setup currently fails because there's an extra sn after the actual code. Apparently you can fix this by changing the slash right before the pm on the top line to a semicolon.

uhh ... probably time to delete this and start over :o (first version was a square of slashes, but I thought I'd do a "clever" thing saving some bytes ... dammit)

@ETHproductions I fixed/improved it using your very nice idea (don't know why I didn't see it as I did experiment with line breaks ...) If you want to post it yourself, that would be fair and I'll delete it.

It's your answer, I'm just helping you golf it ;-) You can shave off a few more bytes by making the actual code a 3x6 rectangle: Try it online!

Just a nitpick but it looks like you've got two "W"s

Starry, 34 bytes
  zz
  +
   .
    +

Or with spaces shown as hyphens so you can see them:
--zz--
--+---
---.--
----+-
------

Try it online!
The commands in Starry are +, . and some other things, and what they do is determined by how many spaces there are before them: a + with n spaces pushes n−5 to the stack, and . with an even number of spaces prints it. The zs and newlines are ignored entirely.
There are 6 spaces before the first + so it pushes 6−5 = 1, and the . prints it.
And the rotations:
-----
-----
---+z
--.-z
-+---
-----

Try it online! This prints "8".
------
-+----
--.---
---+--
--zz--

Try it online! This prints "2".
-----
---+-
z-.--
z+---
-----
-----

Try it online! And this prints "3".

What a neat language. Also, I never said you have to pad with whitespace to form a rectangle.  But if your source relies on the spaces then I suppose you have to count them.

@CzarMatt, thanks for the clarification! I've updated the post.

Labyrinth, 9 bytes
!
2@2
 !)

Prints 0. Try it online!
 2)
 @!
!2

Prints 3. Try it online!
)!
2@2
  !

Prints 1. Try it online!
 2!
!@
)2

Prints 2. Try it online!
Explanation
Each program starts at the first non-space in reading order (i.e. either the top left or top centre character), moving east. For the first program:
!   Print an implicit zero.
    The IP can't move east, so it moves south instead.
2   Push a 2.
    The IP can't keep going south, so it turns east instead.
@   Terminate the program.

For the second program:
2   Push a 2.
)   Increment it to 3.
    The IP can't keep going east, so it turns south instead.
!   Print the 3.
    The IP can't keep going south, so it turns west instead.
@   Terminate the program.

For the third program:
)   Increment an implicit zero to 1.
!   Print the 1.
    The IP can't keep going east, so it turns south instead.
@   Terminate the program.

For the fourth program:
2   Push a 2.
!   Print the 2.
    The IP can't keep going east, so it turns back around to move west.
2   Push another 2.
    The IP can't keep going west, so it turns south instead.
@   Terminate the program.

Wumpus, 7 bytes
O@$
)))

Prints 0. Try it online!
)O
)@
)$

Prints 1. Try it online!
)))
$@O

Prints 3. Try it online!
$)
@)
O)

Prints 2. Try it online!
Explanation
The first program is easy enough: O prints an implicit zero and @ terminates the program.
Starting at the second program, we need to look at the triangular grid layout to understand the control flow:

)   Increment an implicit zero to 1.
O   Print the 1.
))  Two irrelevant increments.
@   Terminate the program.

For the third program:

))) Increment an implicit zero to 3.
O   Print the 3.
@   Terminate the program.

The fourth one is where it gets really funky. Dashed lines indicate cells that aren't executed because they are skipped by the $:

$   Skip the ).
$   Skip the @.
))  Increment an implicit zero to 2.
O   Print the 2.
))  Two irrelevant increments.
@   Terminate the program.

Super cool, great diagrams, too.

PowerShell, 20 11 bytes
#4#
1#3
#2#

Abuses comments (#) like crazy, and the fact that a single number placed onto the pipeline gets output as-is. The above prints 1. Try it online!
From here, you can easily see that each rotation yields only one number that's on the "left" of the comments, and so there's only one number that will be output per rotation.
Saved 9 bytes thanks to Wheat Wizard!

Don't know powershell, but wouldn't this work?

@WheatWizard Yes, indeed. Thanks!

Cardinal, 20 17 12 11 bytes
.$
Z%"
+$v

Try it online!
All this time and no-one answered in Cardinal? This first one outputs 0.
East
 +Z.
 $%$
 v"

Try it online!
Outputs 1.
South

v$+
"%Z
 $.

Try it online!
Outputs a space.
West
 "v
$%$
.Z+

Try it online!
Outputs v.

dc, 9 bytes
 1
2p3
 4

Try it online!
I think its obviousness is part of the charm.

Batch, 90 bytes
 :: :::@:
:&s ohce@
:e   : c:
      :h:
:o     o:
:h:
:c :   w:
@echo n&:
:@::: ::

Batch doesn't really have a comment character. For whole-line comments, : works, as it introduces a label, but I still need something to terminate the echo command while being a no-op when reversed. &: seems to work, which is all I need here, but it really confuses Batch, erroring out if I don't put a : before the @ on the next line, and also somehow forgetting to print a newline.

JavaScript (ES6), 86 bytes
Outputs 0 for North, 1 for East, 2 for South, and 3 for West.
////  _//
////  =//
_=>0//>//
  ////1//
  // //
//3////
//>//2>=_
//=  ////
//_  ////

const source =
`////  _//
////  =//
_=>0//>//
  ////3//
  // //
//1////
//>//2>=_
//=  ////
//_  ////`;

function rotateTextCW(text) {
  const lines = text.split("\n");
  const maxLineLength = lines
    .map(line => line.length)
    .reduce((max, len) => Math.max(len, max), 0);
  const paddedLines = lines.map(line => line.padEnd(maxLineLength));
  const charGrid = paddedLines.map(line => line.split(""));
  const rotatedGrid = [...new Array(maxLineLength)]
    .map(v => new Array(charGrid.length));

  for (let i = 0; i < charGrid.length; i++) {
    for (let j = 0; j < charGrid[i].length; j++) {
      rotatedGrid[j][charGrid.length - i - 1] = charGrid[i][j];
    }
  }

  return rotatedGrid
    .map(chars => chars.join("").trimRight())
    .join("\n");
}

const orientations = ["North", "East", "South", "West"];
let rotatedSource = source;
let markup = "";

orientations.forEach(orientation => {
  const code = `<pre>${rotatedSource}</pre>`;
  const result = `<code>${eval(rotatedSource)()}</code>`;
  const row = `
    ${orientation}
    ${code}
    ${result}	`;
  markup += `<tr>${row}</tr>`;
  rotatedSource = rotateTextCW(rotatedSource);
});

document.querySelector("table tr:first-child")
  .parentNode
  .innerHTML += markup;
<link href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css" rel="stylesheet" />

      Orientation
      Source
      Result

MATLAB, 29 17 5 11 bytes
Having realised that the question called for single ASCII characters not just a distinct output, here is a MATLAB approach which will do just that:
%4%
1%3
%2%

This will implicitly print 1, 2, 3, or 4 depending on the rotation.

Come to think of it, this would work in MATL as well. Same byte count as mine, though.

SOGL V0.12, 4 bytes
5H
I

Outputs 1, Try it Here!
I5
 H

Outputs H, Try it Here!
 I
H5

Outputs 5, Try it Here!
H
5I

Outputs 6, Try it Here!

If it contains a space, it is 5 bytes.

@Mr.Xcoder OP in comments said that you don't need to pad it

MATL, 11 bytes
HxI
xFx
TxK

Try it online!
Let's get this started in MATL. The main challenge is that MATL just fails if a function requires input if the stack is empty. Perhaps something clever with modifiers like X, Y, Z and & could make for something shorter, but I couldn't find a suitable combination.
Explanation: all characters push a single integer on the stack, and x removes all of them but the last.

Perl, 49 bytes
48 bytes code + 1 for -p.
Assumes empty input which TIO doesn't support, so a newline is added in its place and not used. Prints N, E, S, W.
# ####
#S= _$
#; W#
 $_=N#
#_ _#
#= $#
#E#
 ## #

Try it online!

C (gcc), 120 bytes
I had hoped for more synergy between the variants.
//}=)f8 ///
// c{(7 ///
   ;rr; //}
        ;c=
78; /// r{)
f(r /// r(f
){r /// ;38
=c;
}// ;rr;
/// 9({c //
/// 6f)=}//

North
East
South
West

MathGolf, 11 bytes
Þ2Þ
3 1
Þ0Þ

A bit boring, but since MathGolf implicitly outputs the entire stack joined together, I'm not sure if something shorter is possible here..
Default; rotated once clockwise; rotated two times clockwise; rotated three times clockwise.
Explanation:

0123: These push the digit to the stack
 : This pushes a space character to the stack
Þ: This empties the stack except for the top value

And in the end the entire stack joined together is output implicitly as result.

brainfuck, 72 bytes
++
+++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++
+

Try it online!
Try it rotated once!
Try it rotated twice!
Try it rotated thrice!

Nice idea. <33 copies of +>.<35 copies of +><newline>+ to save a newline, and I think it's the shortest possible that prints those 4 chars.

JavaScript (Node.js), 69 bytes
 _=>0//
/*    *_
/      =
1      >
>      3
=      /
_*    */
 //2>=_

Try it online!
This approach should work for any language with C-style comments.

MAWP, 5 bytes
North: 3
2M:
2

Try it!
East: 4
22
 M
 :

Try it!
South: 2
  2
:M2

Try it!
West: 1
:
M
22

Try it!
The existing 1 in the stack is very convenient here.

Python 2, 71 bytes
##p#####
# r  2 #
print 1#
# n  t #
# t  n #
#4 tnirp
# 3  r #
#####p##

Try it online!
Big thanks to this answer!
Note I did not copy it directly, but actually had a program in mind and golfed it with this.