text:
Sharing (characters) is Caring!
Overview
Consider the following task:

Given a positive integer n > 0, output its integer square root. The integer square root of a number n is the largest value of x where x2 ≤ n, usually expressed with the formula floor(sqrt(n)).
Examples: 25 -> 5, 24 -> 4, 40 -> 6, 1 -> 1.

This task is easy enough on its own. However, in this challenge, your task is to solve this in as many languages as possible using a set of only 25 characters.
Example
First, you need to pick a set (no duplicates) of 25 bytes. It may look something like this (note the leading space):
 ()*-.05:=>Mabdhilmnqrst|

Your challenge is then to, using only characters in this set, construct a solution to the problem in as many text based (sorry, Piet) languages as possible. You can use characters as many times as necessary, but you must not use characters outside the set.
The solutions can be either full programs or functions, but not snippets. For example, using this set of characters, I could do:
M -> (int) Math.sqrt(M)    // Java (lambda expression)
M => Math.sqrt(M)|0        // Javascript (unnamed function)
lambda M: int(M**.5)       // Python (lambda function)

As I've used 3 languages, this would give me a score of 3.
Please also include the set of bytes you are using in your answer.
Rules

This is a rosetta-stone challenge - your score is the number of languages your submission includes. The highest score wins. Standard loopholes apply.
For this challenge, a 'language' counts as a distinctly different programming language - multiple versions of the same language (Python 2, Python 3, etc) are banned.
Programs only need to work for inputs within the language's standard integer range.
Programs with the exact same source code (polyglots) are not allowed.
To be more specific, it is a set of bytes, not characters - so you can use the 05AB1E £ and the Jelly ɱ as the same character (because they have the same codepoint).

Please don't feel as though you have to beat all other solutions - if you have an interesting answer, post it!

Can our solution be in Piet if we have the code be the raw ppm? (e.g. P3 10 10 255 ...)

We need another pixel based language so we can have polyglots with poor old piet

Can we count a polyglot of A and B as language A if we provide another solution that only works in B?

Could you clarify "distinctly different"? For example, is Numberwang--using digits instead of []<>.,+--- distinctly different from Brainfuck? What about SNUSP, a 2D Brainfuck derivative? For both of them, the resulting code would not work in Brainfuck.

@WheatWizard you can't have two programs that are exactly the same, but if you modify one to be different then it's allowed. And yes, if you really must, you can use the raw ppm as "text" for Piet  :P

@JungHwanMin the second is definitely distinctly different as it's 2D. I'd also say numberwang is sufficiently different as it has a different character set.

@JungHwan generally, a different language is a different creator, different syntax , etc. However with esoteric languages the line gets blurry. Trivial, "1 new command" modifications of brainfuck aren't really different to bf, but larger derivatives like the 2D one you linked encourages different ways of programming and so counts as a different language.

C, 23 Bytes f(x){return pow(x,.5);} and 20 characters used f(x){retun powx,.5;}

@WadeTyler Not sure why you've commented that, but you should know that you've counted x twice in your character set. Also, if you name the function something like p that's already in the set then you don't have to count f.

@FlipTack I wanted to make it as a post, for others who didn't use C in theirs because of reasons, and talked with someone that it would be a better idea to leave is a comment on your post so others can see it.

20 languages
Using  ()-#*.05;=>^Vefikloqrst (24 characters) so far:
let f l=floor(l**0.5);;       OCaml
let f l=floor(l**0.5)         F#
f(l)=floor(l^.5)              Julia
f(o)=floor(o^.5)              PARI/GP
s^+>5 0>5 0*.5l               Pyth
(* **.5).floor                Perl 6
floor.(**0.5)                 Haskell
flr.(tt ^.5)                  Wonder
l=>l**.5^0                    JavaScript
l->l**.5^0                    Cheddar
.5^5*5f                       Pyke
(isqrt)                       Maple
ri.5#i                        CJam
isqrt                         Common Lisp
0.5^k                         MATL
*.5^0                         Jelly
*.^0                          M
t0^                           05AB1E
q f                           Japt
r#                            Pushy
V-                            gs2

Try adding flr.(tt ^.5) for Wonder (no added chars).

If you would like to add {}[]  you can add Brain-Flak.  Here's the program

If you added ~, you could do sqrt~~ in Stacked; it takes input from the TOS and leaves output on the stack.

julia also has isqrt

isqrt in Julia wouldn't count because polyglots are not allowed.

The Pyth one would be shorter and more readable if you used ttt5 instead of +>5 0>5 0.

C, 23 Bytes f(x){return pow(x,.5);} and 20 characters used f(x){retun powx,.5;} You can replace the curly brackets with round brackets.

Congrats on winning, enjoy the bounty! ^_^

10 languages
Character set of 19 characters (in CP-1252):
,-/12@QUVX^fkmt¬÷␊␍

Where ␊ represents a line feed and the ␍ represents a carriage return.
(Script for checking the characters)

Jelly, 2 bytes
Æ½

Try it online!
05AB1E, 2 bytes
t1X-^

Try it online!
GS2, 2 bytes
V-

Try it online!
Jolf, 3 bytes
mfU

Try it here! (works best on Firefox)
Japt, 2 bytes
¬f

Try it here!
MATL, 3 bytes
X^k

Try it online!
Pyke, 3 bytes
,1f

Try it here!
Pyth, 6 bytes
/@Q2t2

Try it here!
Oasis, 6 bytes
1␊2/m1÷

Try it online!
2sable, 9 bytes
t1X-XX--^

Try it online!

cU also works in Jolf.

@ConorO'Brien Although it's shorter, it would mean to add c to the list of characters. He's already using both m (in the Oasis sub-answer) and f (in the Japt and Pyke sub-answers).

@KevinCruijssen ik, it's just for posterity

5 languages
Gonna add more languages soon.
Character set (22 bytes):
s^Q.5=>*|0√Lrdmlab :/1

Pyth
s^Q.5

Javascript
Q=>Q**.5|0

Actually
√L

CJam
rdmQ

Python
lambda Q:Q**.5//1

You can replace | by ^ in your JavaScript answer to save a byte in your character set.

5 languages
[].,+<>{}()0134879

18 characters.
I'm trying not to use any alphabet characters...
Brainfuck, Brainfuck++, Brainfuck-ng, Braintrust, ...
,[[>++++++[<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++<]>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<+>]<<<[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>>+<<]],]>>>>>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[<<<<<[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+>+<<]>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<+>]<<+[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<+>>>>+<<]>>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<<+>>]<<<<[>>[<+>>>+<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]<[>+<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]>>>>>>>>+<<<<[>>>+<<[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]<<]>>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+<]<[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<+>]<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]>>>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]<<<<<<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<++++++++++>[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++[<+<<]<[+[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>+<]<+<<]>>>>>]<<<[<++++++[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++<]>.[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++]]++++++[+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++<]>.

Doesn't work for over 224 because 256 (= (sqrt(225)+1)^2) overflows.
Replaced all -s with +s to use one less character. (e.g. - -> 255 +s)
Original Program
,[[>++++++[<-------->-]>[->++++++++++<]>[-<+>]<<<[->>+<<]],]>>>>>>>-[<<<<<[->+>+<<]>[-<+>]<<+[-<<+>>>>+<<]>>[-<<+>>]<<<<[>>[<+>>>+<<-]<[>+<-]<-]>>>>>>>>+<<<<[>>>+<<[->+>[-]<<]>>[->+<]<[-<+>]<-<-]>[-]>>>-]<<<<<<-<++++++++++>[-<-[<+<<]<[+[->+<]<+<<]>>>>>]<<<[<++++++[->++++++++<]>.[-]]++++++[->++++++++<]>.

Brain-Flak
({}(())[()])(()){{}((({})({}((({}())))[{}{({})({}[()])}{}]))[({}[{}])])([({}(())[()])]){(({}()({}[(({}[(())]()){(([({}{})]{}))}{})]{}))[({}[{}])])}{}{}}{}{}({}[()])

@WheatWizard's code. Thanks for the permission!
Brain-Flueue
({}())(())(())({}){{}({})({}<(({})<({({})({}[()])}{})>())>)([{}]<({})>({}))({}<({}<([({})]){()<({}())>}{}(<()>){({}[()])([{}]())}{}>)>)({}<({})>)({})({})}{}({}[()()]){}

Another @WheatWizard's code.
Numberwang
[encoded data, 7402 characters]

Spoon
00101100010000100010111111001000110000000000000000000000000100000011010001000000101111111111011001101000100000011101000110110110110010000001001010110110011001100101100011010010010010010010010000001000110110110110110010000001010101011011001101000100000011101000110110111001000000110111010010010010101101100110100100010000001101110100100011011011011011001000100100010001110100100101011011000001101100100010101100000110110000011010010010010010010010010101101101101100100010010010101101100100000010101000100000001101101100110100100010000001010110011011001000000111010001101100001100000110100010000000110100100100000011011011011011011011000011111111111101000100000011000001000111011011001101100100100100000010101100110111011011001101001001001001000110110110110010001111111100100000010111111110110011010001010001000000011001111111100100000010111111110110011010001010

Per meta consensus, this code should be okay, even though no interpreters are currently available.

5 languages
Using ()*/12 dlinpqrstu and newline (18 characters) so far.
Common Lisp
isqrt

A built-in function.
QBasic
input q
print int(sqr(q))

Python 3
print(int(int(input())**(1/2)))

Python 3 used for floating-point division without decimal points.
Pip
q**/2//1

Unnecessarily golfy to show off the unary inversion operator /. Takes input from stdin. Try it online!
tinylisp
(d sqrt (q((n nsqr input) (i (l input nsqr) (s n 1) (sqrt (s n (s 1 2)) (s 2 (s (s (s 1 n) n) nsqr)) input)))))
(q((input)(sqrt 1 1 input)))

sqrt is a helper function whose arguments are: the current guess n, n squared, and the input number. If input is less than nsqr, we've gone too far, so return n minus 1; otherwise, recurse, adding 1 to n and adding n + n + 1 to nsqr. (The math is a bit complicated because tinylisp only has subtraction built in.) The second line defines our actual function, which takes a single input and returns the result of sqrt with n starting at 1.

If you would like to add {}[]  you can add Brain-Flak.  Here's the program

6 languages
Using retun flosq(agm1)\,i and extended codepoints B1 and BC for 22 bytes so far.
GameMaker Language
return floor(sqrt(argument1))

Pyke
,1f

Julia
isqrt

Maple
(isqrt)

Stuck
i\

TI-Basic (hex dump)
B1 BC 72

Note that 0x72 is r in ASCII.

7 languages
24 chars:
limQi->(nt)Mah.sqr_ ?;:\

CJam
limQ
li       e#Read Int
  mQ     e#Integer square root

Java
i->(int)Math.sqrt(i)

Chaincode
q_
q  #sQuare root
 _ #floor

Math++
_sqrt ?

Grin
;q:

Stuck
i\)

Unilinear
iMivMiMs
i            Read input
 Mi          Convert to int
    v        Square root
    Mi       Convert to int
      Ms     Convert to String

R
sqrt

Costs too much bytes
Python
lambda i:int(i**.5)

Can add R: sqrt

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


text:
Solve an Ice Maze
Ice mazes have been one of my favorite staples of Pokémon games since their debut in Pokémon Gold and Silver.  Your task will be to make a program that solves these types of problems.
Ice mazes primarily consist of, as the name suggests, ice.  Once the player moves in a direction on ice they will continue to move in that direction until they collide with some obstacle.  There is also soil which can be moved across freely and will stop any player moving across it.  The last obstacle is stone.  Stone cannot occupy the same space as the player and if the player attempts to move into it they will stop moving before they can.
You will receive a two dimensional container of values, such as an list of lists or a string separated by newlines, containing 3 distinct values for each of the 3 types of flooring (Ice, Soil, and Stone).  You will also receive two pairs (or other equivalent two value containers) that indicate a start and goal coordinate in the maze.  These may be zero or one indexed.
You must output a list of moves (4 distinct values with a bijection onto N,E,S,W) that would cause the player to arrive at the end when carried out.
Input will always have a closed perimeter of stone around the maze so you do not have to worry about the player exiting the maze
This is code-golf so the fewest bytes wins
Test Cases
Here . will represent ice, ~ will represent soil, and O will represent a stone.  Coordinates are 1 indexed.  Each letter in the solution represents the direction beginning with that letter (e.g. N= North)

Input
OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Output
N

Input
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

Start : 15,12
End   : 16,8

Output
N,W,N,E,N,E,S,W,N,W,S,E,S,E,N,E,N

Input
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

Start : 2,2
End   : 14,3

Output
E,S,S,W,N,E,N

Input
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Start : 2,2
End   : 11,11

Output
E,E,E,E,E,S,S,E,N,W,S,E,N,N,N

Will the input always have at least one valid solution?

@Pavel You can assume so.

Are the test cases (row, column) or (column, row)? 1 or 0 indexed? Do the board edges count as walls?

@MistahFiggins 1 indexed

Related

Related

Is it okay to assume that for every accessible cell there is a way to get out of the maze, i.e. it is impossible to permanently trap yourself in the maze?

@busukxuan You can be permanently trapped in the maze (see testcase 1)

Mathematica, 247 bytes
(p=x#[[##&@@x]];m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};e=Flatten[Table[#->c,{c,a@#}]&/@g,1];Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]])&

With line breaks:
(
p=x#[[##&@@x]];
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]
)&

My immediate idea was to represent the ice and soil positions as nodes in a graph with directed edges corresponding to legal moves, then use FindPath. One might think that determining the legal moves would be the easy part and finding the solution would be the hard part. For me, it was the opposite. Open to suggestions on how to compute the edges.
First argument # is a 2D array where 0 represents ice, 1 represents soil, and 2 represents stone.
Second argument #2 and third argument #3 are the starting and ending points, respectively, in the form {row,column}.
 is the 3 byte private use character U+F4A1 representing \[Function].
Explanation
p=x#[[##&@@x]];

Defines a function p which takes a list x of the form {row,column} and outputs #[[row,column]]; i.e., the ice/soil/stone value at that coordinate.
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c]

Defines a function m which takes a starting position c and direction vector v and recursively determines where you would end up. If c+v is ice, then we continue sliding from that point, so it returns m[c+v,v]. If c+v is soil, then we move to c+v and stop. Otherwise (if c+v is stone or out of bounds), you don't move. Note that this is only intended to be called on ice or soil positions.
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];

Defines the list g of ice and soil positions (p value less than 2).
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};

Defines a function a which takes a starting position c and returns the results of moving in the {1,0}, {-1,0}, {0,1}, and {0,-1} directions. There may be some redundancy. Again, this assumes that c corresponds to ice or soil.
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];

Defines the list e of directed edges representing legal moves. For each position # in g, compute the table of edges #->c for each c in a@#. Then since we'll end up with a sublist for each position #, I flatten the first level. There may be some loops and multiple edges.
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]

Graph[e] is the graph where the nodes are the legal positions (ice or soil) and the edges represent legal moves (possibly bumping into a stone and not moving). We then use FindPath to find a path from #2 to #3 represented as a list of nodes. Since FindPath can take additional arguments to find more than one path, the result will actually be a list containing a single path, so I take the first element using [[1]]. Then I take the successive Differences of the coordinates and Normalize them. Thus up is {-1,0}, down is {1,0}, right is {0,1} and left is {0,-1}.
Test cases

JavaScript (ES6) 180 183
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

Using a BFS, like I did to solve this related challenge
Input
The maze map is a multiline string, using O or 0 for stone, 8 for soil and any nonzero digit less than 8 for ice (7 look good).
Start and end position are zero based.
Output
A list of offset, where -1 is W, 1 is E, negative less than -1 is N and a positive greater than 1 is S
Less golfed
(m,[x,y],[t,u])=>{
  o=~m.search`\n`
  s=[[x-y*o,[]]]
  k=[]
  for(i=0; [p,l]=s[i++], k[p]=1, t-u*o != p;)
  {
    [-1,o,1,-o].map(d=>(
      M=p=>+m[p+=d] ? m[p]<8 ? M(p) : p : p-d,
      q=M(p),
      k[q]||s.push([q,[...l,d]])
    ))
  }
  return l
}

Test

Solve=
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

function Go(maze) {
  var map = maze.textContent;
  var [sx,sy, dx,dy] = map.match(/\d+/g)
  --sx, --sy // zero based
  --dx, --dy // zero based
  map = map.split('\n').slice(1).join('\n') // remove first line
  var result = Solve(map.replace(/\./g, 7).replace(/~/g, 8), [sx,sy], [dx,dy])
  S.textContent = result
  Animate(maze, map, result, sx, sy)
}

function Display(maze, map, pos) {
  var row0 = maze.textContent.split('\n')[0]
  map = [...map]
  map[pos] = '☻'
  maze.textContent = row0+'\n'+map.join('')
}

function Animate(maze, map, moves, x, y) {
  console.log('A',moves)
  var offset = map.search('\n')+1
  var curPos = x + offset * y
  var curMove = 0
  var step = _ => {
    Display(maze, map, curPos)
    if (curMove < moves.length)
    {
      curPos += moves[curMove]
      if (map[curPos] == 'O')
      {
        curPos -= moves[curMove]
        ++curMove
      }
      else
      {
        if (map[curPos] == '~') {
          ++curMove
        }
      }
      setTimeout(step, 100)
    }
    else
      setTimeout(_=>Display(maze,map,-1),500)
  }
  step()
}
td {
  border: 1px solid #888;
}
Select maze

<input type=radio name=R onclick='Go(M1)'>

3,3 to 3,2
OOOOO
OO.OO
O...O
OOOOO

<input type=radio name=R onclick='Go(M2)'>

15,12 to 16,8
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

<input type=radio name=R onclick='Go(M3)'>

2,2 to 14,3
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

<input type=radio name=R onclick='Go(M4)'>

2,2 to 11,11
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Python3, 439 bytes
def f(b,s,S,e,E):
 q=[(s,S,[[(s,S)]],'')]
 for x,y,d,p in q:
  if(x,y)==(e,E):return p
  for D,X,Y in[('E',0,1),('W',0,-1),('N',-1,0),('S',1,0)]:
   if'~'==b[x][y]and(T:=[(x+X,y+Y)])not in d and'O'!=b[x+X][y+Y]:q+=[(*T[0],d+[T],p+D)]
   elif'.'==b[x][y]:
    T,Q,W=[],x,y
    while 1:
     if(S:=b[Q+X][W+Y])in'.~':
      T+=[(Q+X,W+Y)];Q+=X;W+=Y
      if'~'==S:break
     else:break
    if(U:=sorted(T))not in d and U:q+=[(Q,W,d+[U],p+D)]

Try it online!

source: Stack Exchange

license: 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/

sort: votes


text:
Zero sum covers
Introduction
Consider a nonempty list L of integers.
A zero-sum slice of L is a contiguous subsequence of L whose sum equals 0.
For example, [1, -3, 2] is a zero-sum slice of [-2, 4, 1, -3, 2, 2, -1, -1], but [2, 2] is not (because it doesn't sum to 0), and neither is [4, -3, -1] (because it's not contiguous).
A collection of zero-sum slices of L is a zero-sum cover of L if every element belongs to at least one of the slices.
For example:
L = [-2, 4, 1, -3, 2, 2, -1, -1]
A = [-2, 4, 1, -3]
B =        [1, -3, 2]
C =                  [2, -1, -1]

The three zero-sum slices A, B and C form a zero-sum cover of L.
Multiple copies of the same slice can appear in a zero-sum cover, like this:
L = [2, -1, -1, -1, 2, -1, -1]
A = [2, -1, -1]
B =        [-1, -1, 2]
C =                [2, -1, -1]

Of course, not all lists have a zero-sum cover; some examples are [2, -1] (every slice has nonzero sum) and [2, 2, -1, -1, 0, 1] (the leftmost 2 is not part of a zero-sum slice).
The task
Your input is a nonempty integer list L, taken in any reasonable format.
Your output shall be a truthy value if L has a zero-sum cover, and a falsy value if not.
You can write a full program or a function, and the lowest byte count wins.
Test cases
[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True

By "every element belongs to one of the slices", are you treating the same value at different indices as distinct?

@ngenisis Yes, they are distinct and each should occur in a slice that contains the corresponding index.

Should not the third falsy example [2,2,-1,-1,0,1] -> False be truthy since both slices [2,-1,-1] and [-1,0,1] add to zero and all their elements are in the original list?

The leftmost 2 is not part of any zero-sum slice. It's a bit unclear, but they have to occur in a slice that "contains their index".

Understood. That makes it harder. :o)

Jelly, 13 12 bytes
JẆịS¥ÐḟċþJḄẠ

Try it online!
How it works
JẆịS¥ÐḟċþJḄẠ  Main link. Argument: A (array)

J             Yield all indices of A.
 Ẇ            Window; yield all slices of indices.
     Ðḟ       Filter; keep slices for which the link to the left returns 0.
    ¥           Combine the two atoms to the left into a dyadic chain.
  ị               Retrieve the elements of A at the slice's indices.
   S              Take the sum.
         J    Yield the indices of A.
       ċþ     Count table; count how many times each index appears in each table.
          Ḅ   Unbinary; convery the array of counts of each index from base 2 to
              integer. This yields 0 iff an index does not appear in any slice.
           Ạ  All; return 1 iff all integers are non-zero.

Mathematica, 66 65 bytes
Saved 1 byte, and hopefully learned a new trick for the future, thanks to ngenisis!
Two equally long alternatives, both of which are unnamed functions taking a list of integers as input and returning True or False:
And@@Table[0==Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

0==Norm@Table[Product[Tr@#[[i;;j]],{i,k},{j,k,l}],{k,l=Tr[1^#]}]&

In both cases, Tr@#[[i;;j]] computes the sum of the slice of the input from position i to position j (1-indexed). Product[...,{i,k},{j,k,l}] multiples together all these slice-sums, as i ranges over indices that are at most k and j ranges over indices that are at least k. (Note that l=Tr[1^#] defines l to be the sum of 1 to all the powers in the input list, which is simply the length of the list.) In other words, this product equals 0 if and only if the kth element belongs to a zero-sum slice.
In the first version, each of those products is compared to 0, and And@@ returns True precisely when every single product equals 0. In the second version, the list of products is acted upon by the function Norm (the length of the l-dimensional vector), which equals 0 if and only if every entry equals 0.

Tr[1^#] saves 1 byte from Length@#.

Would 0^ work instead of 0==? Not sure how Mathematica handles that. (you would return 1/0 instead of true/false)

Cool idea, but Mathematica returns Indeterminate for 0^0. Also, 1/0 aren't actually truthy/falsy in Mathematica—it's too strongly typed to make golfers happy :)

Mathematica, 65 64 bytes
Thanks to ngenisis for saving 1 byte.
Union@@Cases[Subsequences[x=Range@Tr[1^#]],a_/;Tr@#[[a]]==0]==x&

I'd rather find a pure pattern matching solution, but it's proving to be tricky (and things like {___,a__,___} are always super lengthy).

Haskell, 94 bytes
import Data.Lists
g x=(1<$x)==(1<$nub(id=<<[i|(i,0)<-fmap sum.unzip<$>powerslice(zip[1..]x)]))

Usage example: g [-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3]
-> True.
How it works (let's use [-1,1,5,-5] for input):
        zip[1..]x  -- zip each element with its index
                   -- -> [(1,-1),(2,1),(3,5),(4,-5)]
      powerslice   -- make a list of all continuous subsequences
                   -- -> [[],[(1,-1)],[(1,-1),(2,1)],[(1,-1),(2,1),(3,5)],[(1,-1),(2,1),(3,5),(4,-5)],[(2,1)],[(2,1),(3,5)],[(2,1),(3,5),(4,-5)],[(3,5)],[(3,5),(4,-5)],[(4,-5)]]
    <$>            -- for each subsequence
   unzip           --   turn the list of pairs into a pair of lists
                   --   -> [([],[]),([1],[-1]),([1,2],[-1,1]),([1,2,3],[-1,1,5]),([1,2,3,4],[-1,1,5,-5]),([2],[1]),([2,3],[1,5]),([2,3,4],[1,5,-5]),([3],[5]),([3,4],[5,-5]),([4],[-5])]
  fmap sum         --   and sum the second element
                   --   -> [([],0),([1],-1),([1,2],0),([1,2,3],5),([1,2,3,4],0),([2],1),([2,3],6),([2,3,4],1),([3],5),([3,4],0),([4],-5)]
 [i|(i,0)<-    ]   -- take all list of indices where the corresponding sum == 0
                   -- -> [[],[1,2],[1,2,3,4],[3,4]]
 id=<<             -- flatten the list
                   -- -> [1,2,1,2,3,4,3,4]
nub                -- remove duplicates
                   -- -> [1,2,3,4]

(1<$x)==(1<$    )  -- check if the above list has the same length as the input list.

powerslice is such a great function name.

J, 36 35 bytes
#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\

For every subsum I add the element's indexes and I keep the indexes iff subsum is 0 and then check whether every index is present.
Trick: 1-based indexes of a list can be generated with #\ i.e. length of every prefix.
Usage:
   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1 _1 2
1
   (#\*/@e.[:;]({:*0=[:+/{.)@|:\.\@,.#\) 2 _1
0

Try it online here.

I think you can save 2 bytes using the base 1 trick for summation and using a composed flatten #\*/@e.&,]({:*0=1#.{.)@|:\.\@,.#\

APL (Dyalog Unicode), 22 20 bytes
-2 bytes thanks to Bubbler
∧/∨⌿↑0={×\⌽+\⌽⍵}¨,\⎕

Try it online!
Explanation
                 ,\⎕      ⍝ All prefixes of the input
       {       }¨         ⍝ Map each to
          ⌽+\⌽⍵           ⍝ The sum of each postfix
        ×\                ⍝ Scan multiplied, spreading any zero sums to the other elements in the sub-array
     0=                   ⍝ Map zeroes to true
    ↑                     ⍝ Mix the arrays into a 2D matrix
∧/∨⌿                      ⍝ Do all columns have at least one true value?

Please don't use Dyalog Classic unless you really have to.

@Adám Yeah, I've read through the reasons not to and I'm using Unicode for future answers.

A full program saves 2 bytes.

Ruby, 81 bytes
Try it online
Simplistic brute-force solution; for every element of the array, try to find a zero-sum slice that contains it.
->a{(0..l=a.size).all?{|i|(0..i).any?{|j|(i..l).any?{|k|a[j..k].inject(:+)==0}}}}

JavaScript (ES6), 109 bytes
f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)

Test snippet

f=([q,...a],b=[],c=[])=>1/q?f(a,[...b,0].map((x,i)=>x+q||(c=c.map((n,j)=>n|i<=j)),c.push(0)),c):c.every(x=>x)

I.textContent = I.textContent.replace(/.+/g,x=>x+` (${f(eval(x.split(" ")[0]))})`)

[-1] -> False
[2,-1] -> False
[2,2,-1,-1,0,1] -> False
[2,-2,1,2,-2,-2,4] -> False
[3,-5,-2,0,-3,-2,-1,-2,0,-2] -> False
[-2,6,3,-3,-3,-3,1,2,2,-2,-5,1] -> False
[5,-8,2,-1,-7,-4,4,1,-8,2,-1,-3,-3,-3,5,1] -> False
[-8,-8,4,1,3,10,9,-11,4,4,10,-2,-3,4,-10,-3,-5,0,6,9,7,-5,-3,-3] -> False
[10,8,6,-4,-2,-10,1,1,-5,-11,-3,4,11,6,-3,-4,-3,-9,-11,-12,-4,7,-10,-4] -> False
[0] -> True
[4,-2,-2] -> True
[2,2,-3,1,-2,3,1] -> True
[5,-3,-1,-2,1,5,-4] -> True
[2,-1,-1,-1,2,-1,-1] -> True
[-2,4,1,-3,2,2,-1,-1] -> True
[-4,-1,-1,6,3,6,-5,1,-5,-4,5,3] -> True
[-11,8,-2,-6,2,-12,5,3,-7,4,-7,7,12,-1,-1,6,-7,-4,-5,-12,9,5,6,-3] -> True
[4,-9,12,12,-11,-11,9,-4,8,5,-10,-6,2,-9,10,-11,-9,-2,8,4,-11,7,12,-5] -> True

Python, 123 120 bytes
-3 bytes thanks to @Zgarb
Populates a list with the same size as the input with zero-sum slices and overwrites according to indexes, returning its equality to the original at the end.
def f(l):
 s=len(l);n=[0]*s
 for i in range(s):
  for j in range(i,s+1):
   if sum(l[i:j])==0:n[i:j]=l[i:j]
 return n==l

I think you can use 0 as the placeholder instead of None. There won't be false positives, because every 0 in the input is always part or a zero-sum slice.

You are right. I thought about that but ended up concluding that it could incur in false positives.

APL (Dyalog Unicode), 22 bytes
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+\⍵}

Try it online!
Same byte count as Jo King's, but totally different approach.
How it works
≢={≢∪∊↓∘⍳/¨⍸∘.=⍨0,+\⍵}  ⍝ Input: integer vector
  {             0,+\⍵}  ⍝ Cumulative sum and prepend 0
            ∘.=⍨        ⍝ Self outer product by equality
           ⍸            ⍝ Extract coords of ones; (a,b) with a>b is included
                        ⍝ iff the interval [b+1..a] has zero sum
      ↓∘⍳/¨  ⍝ For each coord, [b+1..a] if a>b, empty vector otherwise
   ≢∪∊       ⍝ Count unique values
≢=           ⍝ Is the count same as the length of the original array?

Clojure, 109 bytes
#(=(count %)(count(set(flatten(for[r[(range(count %))]l r p(partition l 1 r):when(=(apply +(map % p))0)]p))))

Generates all partitions which sum to zero, checks that it has "length of input vector" distinct indices.

PHP, 104 bytes
Brute force and still over 99 bytes. :-(
for($p=$r=$c=$argc;$s=--$p;)for($i=$c;$s&&$k=--$i;)for($s=0;$k<$c&&($r-=!$s+=$argv[$k++])&&$s;);echo!$r;

takes input from command line arguments, 1 for truthy, empty for falsy. Run with -r.
breakdown
for($p=$r=$argc;$s=$p--;)   # loop $p from $argc-1 to 0 with dummy value >0 for $s
    for($i=$p;$s&&$k=$i--;)     # loop $i (slice start) from $p to 1, break if sum is 0
        for($s=0;                   # init sum to 0
            $k<$argc                # loop $k (slice end) from $i to $argc-1
            &&($r-=!$s+=$argv[$k++])    # update sum, decrement $r if sum is 0
            &&$s;);                     # break loop if sum is 0
echo!$r;                    # $r = number of elements that are not part of a zero-sum slice

$argv[0] contains the filename; if run with -r, it will be - and evaluate to 0 for numeric ops.

JavaScript (ES6), 102 bytes
a=>(g=f=>a.map((_,i)=>f(i)))(i=>g(j=>jb[k]&=kj),t=0),b=g(_=>1))&&!/1/.test(b)

Computes the partial sums for all the elements i..j inclusive, and resets the relevant elements of b from 1 to 0 when it finds a zero sum, finally checking that there are no 1s left.

Scala, 49 bytes
% =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)

Try it at ideone
Usage:
val f:(Seq[Int]=>Boolean)= % =>(1 to%.size)flatMap(%sliding)exists(_.sum==0)
f(Seq(4, -2, -2)) //returns true

Ungolfed:
array=>(1 to array.size)
  .flatMap(n => array.sliding(n))
  .exists(slice => slice.sum == 0)

Explanation:
% =>            //define a anonymouns function with a parameter called %
  (1 to %.size) //create a range from 1 to the size of %
  flatMap(      //flatMap each number n of the range
    %sliding    //to an iterator with all slices of % with length n
  )exists(      //check whether there's an iterator with a sum of 0
    _.sum==0
  )

I'm not exactly sure how this works, but I think it should fail on some of the truthy test cases.

@Zgarb I added a link to ideone, so you can verify that it's correct. It's basically a brute-force, trying every possible slice.

You can use % as a parameter name? Cool!

@Cyoce You can use pretty much any Unicode char except .,;:()[]{}\"'. Pretty useful for golfing, because they get seperated from letters by the parse, so you can save some whitespace.

I checked the test cases, and it seems to give true for the second falsy case.

@Cyoce In fact, all of the operators in java are simply methods called +, -, *, /, %, < and so on of the Int / Float / Boolean classes.

@Zgarb I updated the ideone link to include the second testcase ([2, -1]). It returns true.

Welp, I meant the second falsy example in the text, which is actually the third falsy test case. Sorry!

Python 3, 99 bytes
lambda a,r=range:len({k for j in r(len(a)+1)for i in r(j)if sum(a[i:j])==0for k in r(i,j)})==len(a)

Try it online!
Creates a set of all indices which are part of a zero sum. Then checks if all indices are present.

Python, 86 Bytes
def f(l):
 r=range(len(l))
 if[i for i in r for j in r if sum(l[j:j+i+1])==0]:return 1

Truthy = 1
Falsy   = None

This incorrectly returns 1 for the third test case.

It actually returns 1 for all test cases except the first two falsy ones.

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


text:
Smallest Multiple to "Palindromize"
Goal:
Given any non-zero natural number a, find the smallest non-zero natural
number b such that a•b is palindromic, e.g. it reads the same forwards and backwards. Input a through any reasonable means (STDIN, function argument, etc.), And output b through any reasonable means (STDOUT, function return value.)
Notes:

Input will not always have a solution (multiples of 10), so you must create an error, or display -1/0

Input validation is not necessary, assume a is a natural number.

Standard loopholes apply (Hardcoding, using a language created after this challenge)

Examples:
a=34, b=8 (272)
a=628, b=78 (48984)
a=15, b=35 (525)
a=33, b=1 (33)
a=20, (Error, -1, or 0)

How do we know if the input has a solution or not? Or is figuring that out part of the challenge?

As far as I can tell, only multiples of 10 do not have solutions.

Do we have to "detect" that there is no solution or can we e.g. go into an infinite loop which will eventually throw an error?

Some are harder to find (powers of 3), I needed some time for 243 and 729, but it seems to work for every n given enough time

Related Math.SE post. Yes, every number that isn't a multiple of 10 has a palindromic multiple.

@JulianLachniet hey, you seems to like a leaderboard on your question, you can just copy the one in Pyramid of broken strings, change the QUESTION_ID and OVERRIDE_USER to this question id (106336) and to your id (well that question is yours too, so you don't need to change this one)

Can someone explain how to contact a moderator about reopening this question?

@JulianLachniet Having a*b=c where a is given and c is a palindrome, your question asks to output 'b', the linked question asks to output 'c'. There is really very little difference...

Pyth, 10 9 bytes
&eQf_I`*Q

Try it online.
Explanation
&eQf_I`*QT    Implicitly append T, and take input in Q.
 eQ           Calculate input mod 10.
&             Logical and, only evaluate the following if result ≠ 0.
   f          Starting from 1, find the first integer T for which...
      `       ...the string representation of...
       *QT    ...input multiplied by T...
    _I        ...is equal to its reverse.

Ruby, 51 bytes
->a{(1..a%10/0.0).find{|b|(c="#{a*b}")==c.reverse}}

Explanation
        a%10/0.0 # -> NaN for multiples of 10, Infinity otherwise

05AB1E, 11 bytes
T%            # input mod 10
  0›          # is greater than 0
    µ         # repeat the following until counter reaches that number (0 or 1)
     ¹N*      # input * iteration
        ÂQ    # is equal to its reverse
          ½   # if true, increase counter
              # implicitly output last iteration (or 0)

Try it online!

C, 108 101 bytes
Thanks to @nmjcman101 for 7 bytes!
m,o;f(n){for(o=0;n;)o=o*10+n%10,n/=10;return o;}g(n){m=-1;if(n%10)for(m=1;n*m!=f(n*m);m++);return m;}

Is C the only language here with no built-in reversing/checking palindrome function?
Try it online!

Could you change the for in g to for(m=1;n*m!=f(n*m));, initialize m=-1; earlier in g and then just return m.  g(n){m=-1;if(n%10)for(m=1;n*m!=f(n*m);m++);return m;} (I think you could throw ++m in the condition, but check that)

@nmjcman101 thanks! I saw your comment before editing, tried ++m in various places, but it didn't work.

Java, 113 bytes
i->{int j=1;for(String a;!new StringBuilder(a=String.valueOf(i*j)).reverse().toString().equals(a);)j++;return j;}

Python 2, 78 66 60 bytes
def f(a):
 b=a%10!=0
 while `a*b`!=`a*b`[::-1]:b+=1
 print b

Try it online

That's a nice answer, you can still golf it down.

Improved it a bit by simplifying the b check.

You can drop that ; and use a single space instead of 4 spaces. Also, use print b by changing it to Python 2. After all this it'll be 66 bytes.

I've written too much c code in my life :) I think I could also simplifiy the str() casts when using python 2.

Yea, I forgot that you can use a instead of str(a) in python 2, that's saves a lot too. Also, what encoding you are using, UTF-8 is fine here, so \n is 1 byte.

Good point, changed my editor byte count to use \n instead of \r\n.

QBIC, 29 bytes
:{c=a*q~!c$=_f!c$||_Xq\q=q+1

Explanation:
:      Get cmd line param as number 'a'
{      DO
c=a*q  multiply 'a' by 'q' and assign to 'c', which is 1 at the start of a QBIC program
~      IF
!c$    'c' cast to string
=      equals
_f!c$| 'c' cast to string, the reversed
|      THEN
_Xq    Quit, printing 'q'
\q=q+1 ELSE increment q and rerun
       DO Loop is auto-closed by QBIC, as is the IF

Eventually, 'q' will overflow and throw an error on an unsolvable 'a'.

Mathematica, 43 bytes
If[10∣#,0,#//.x_/;!PalindromeQ@x:>x+#]/#&

Explanation
If[10∣#,0,...]/#&

If the input is a multiple of 10, return 0 (divided by the input).
#//....

Otherwise, repeatedly apply the following substitution to the input.
x_/;!PalindromeQ@x

Match a value which is not a palindrome.
...:>x+#

And replace that value with itself plus the input. This repeated substitution therefore searches through consecutive multiples of the input until it finds a palindrome.
.../#

Finally, to figure out b we simply divide the result by the input again.

Haskell, 67 66 bytes
f a|a`mod`10==0=0|1>0=[b|b<-[1..],show(a*b)==reverse(show$a*b)]!!0

Returns 0 if a is a multiple of 10. Will check from 1 to infinity for b if the textual reverse of a*b is the same as a*b.

Python 2, 68 bytes
x,y=input(),1
if not x%10:x+''
while `x*y`!=`y*x`[::-1]:y+=1
print y

Outputs an error if input is a multiple of 10.


text:
Obfuscated Integer Notation
Edit: I will be posting a newer version of this question on meta-golf soon. Stay tooned!
Edit #2: I will no longer be updating the challenge, but will leave it open. The meta-golf version is available here: https://codegolf.stackexchange.com/questions/106509/obfuscated-number-golf
Background:
Most numbers can be written with only 6 different symbols:

e (Euler's Constant)
- (Subtraction, Not Negation)
^ (Exponentiation)
(
)
ln (Natural Logarithm)

For example, you could convert the imaginary number i using this equation:
(e-e-e^(e-e))^(e^(e-e-ln(e^(e-e)-(e-e-e^(e-e)))))

Goal:
Given any integer k through any reasonable means, output the shortest representation possible of that number using only those 6 symbols.
Examples:
0 => "e-e"
1 => "ln(e)"
2 => "ln(ee)"
// Since - cannot be used for negation, this is not a valid solution:
// ln(e)-(-ln(e))
-1 => "e-e-ln(e)"

Notes:

Ending parenthesis count towards the total amount of characters.
ln( only counts as 1 character.
Everything else counts as 1 character.
n^0=1
Order of operations apply
Parenthesis multiplying is acceptable, e.g. (2)(8)=16, 2(5)=10, and eln(e)=e.
ln e is not valid, you must do ln(e)

I think that formula (ln(ee...e)) is the best way to portray positives. Edit: no, its not. ln(e^(ln(eeeee)ln(eeee))) is better for 20

@JulianLachniet love the idea, would like to see the first 10-20 terms of the sequence requested though. Maybe put up an example for -10 to 10 for clarification. WheatWizard has already poked a couple holes, with those holes the objective criteria of "shortest possible" is hard to determine without concrete examples.

Not sure about some of the higher ones, especially 20.

Can I output mathematica's symbol for e instead of the ascii character 'e'?

Yes, it's still counted as a byte

This form: ln(ee...e) takes n + 3 characters. This: ln(e^((A1)(A2)...(AK))) takes 6 + combined character count of A1-K where A1 * A2 * ... AK == n

ln(eeee)^ln(ee) is a shorter than ln(eeeeeeeeeeeeeeee) for 16

First of all, this is non-trivial since multiplication can save code. Second, I have not written an optimal program which makes test cases difficult to prove.

Just a word of suggestion.  I think this might be more fun as a [tag:meta-golf] challenge than as a [tag:code-golf] challenge.  Its really hard to demonstrate that some code always produces the optimal result so it might be better to score answers on how well they golf their output.

Meta-golf tag has no questions. Are you sure that's what you mean?

@JulianLachniet no hyphen sorry.  [tag:metagolf]

I'm thinking best solution is brute force it.

ln(eee)^ln(ee) is shorter than ln(eeeeeeeee) by one character (since ln( is one character) making that the lower bound for solutions that are not ln(eee...)

Using prefix is not allowed as it could change the results.

Can this output any valid representation or the shortest one?

No. There is a reason for the notation I chose

Thanks for clarifying. (But I think you mean eln(e)=e.)

Python 3, 402 bytes
from itertools import*
from ast import*
from math import*
v,r=lambda x:'UnaryOp'not in dump(parse(x)),lambda s,a,b:s.replace(a,b)
def l(x,y):
    for s in product('L()e^-',repeat=x):
        f=r(r(r(''.join(s),'L','log('),')(',')*('),'^','**')
        g=r(f,'ee','e*e')
        while g!=f:f,g=g,r(g,'ee','e*e')
        try:
            if eval(g)==y and v(g):return g
        except:0
def b(v):
    i=1
    while 1:
        r=l(i,v)
        if r:return r
        i+=1

Example usage:
>>> b(1)
'log(e)'
>>> b(0)
'e-e'
>>> b(-3)
'e-log(e*e*e)-e'
>>> b(8)
'log(e*e)**log(e*e*e)'

Note that although the output format may not reflect it, the code properly counts all lengths according to the question's specifications.
This is a dumb bruteforce through all the possible lengths of strings. Then I use some replacements so that Python can evaluate it. If it's equal to what we want, I also check to exclude unary negative signs by checking the AST.
I'm not very good at golfing in Python, so here's the semi-ungolfed code if anybody wants to help!
from itertools import*
from ast import*
from math import*

def valid(ev):
    return 'UnaryOp' not in dump(parse(ev))

def to_eval(st):
    f = ''.join(st).replace('L', 'log(').replace(')(', ')*(').replace('^', '**')
    nf = f.replace('ee', 'e*e')
    while nf != f:
        f, nf = nf, nf.replace('ee', 'e*e')
    return nf

def try_length(length, val):
    for st in product('L()e^-', repeat=length):
        ev = to_eval(st)
        try:
            if eval(ev) == val and valid(ev):
                return st
        except:
            pass

def bruteforce(val):
    for i in range(11):
        res = try_length(i, val)
        if res:
            print(i, res)
            return res

Instead of indenting with tabs you can indent with spaces for one level of indent and tabs for 2.


text:
Is it an OVSF code?
Given a list of 1s and -1s, determine whether or not it is a valid OVSF code (by outputting a truthy or falsey value).
OVSF codes are defined as follows:

[1] is an OVSF code.

If X is an OVSF code, then X ++ X and X ++ -X are both OVSF codes.
Here ++ is list concatenation, and - negates every element in the list.

No other lists are valid OVSF codes.

You may assume the input list contains only -1 and 1, but you must handle the empty list correctly, as well as lists whose length is not a power of 2.
Shortest code (in bytes) wins.
Test cases
[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[-1, 1] -> False
[-1, -1] -> False
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True

What does "OVSF" stand for?

Orthogonal variable spreading factor, which refers to the way they are used and also to a useful property they have. This didn’t seem very relevant, but the Wikipedia link explains it all (vaguely).

Should [-1, 1] be an example of False?  My initial solution passed all the given examples but this as well.  Alternatively, it could be allowed if [-1] was a valid seed code.

@doug I added some clarifying test cases. [-1] is not a valid seed code so [-1, 1] → False.

Hmm.. My test is necessary but not sufficient.  Here’s another that passes but shouldn’t: [1, -1, 1, 1, -1, -1, 1, -1]

Jelly, 18 16 14 11 bytes
^2/Eam2µḊ¿Ṭ

Outputs [1] (truthy) for OVSF codes, [] (falsy) otherwise.
Try it online!
Background
Like @LuisMendo's MATL answer and @xnor's Python answer, this submission verifies the input array "from the inside out".
Every (non-overlapping) pair of elements of a OVSF code of length two or higher is essentially a copy of the the first pair, either with the same signs or with both signs swapped. Likewise, every (non-overlapping) 4-tuple of elements of a OVSF code of length four or higher is essentially a copy of the the first 4-tuple, either with the same signs or with both signs swapped. The same is true for 8-tuples, 16-tuples, etc., up to the length of the OVFS code.
One way to verify this is to check all pairs for equality modulo the sign first, then remove the second element of each pair (which is now redundant information). If we repeat this process once more, we're essentially checking all 4-tuples. In the next iteration, we're comparing 8-tuples, etc.
Finally, if all the required 2k-tuples were equal modulo the sign and the array has been reduced to a singleton, it is sufficient to check if the remaining element is a 1.
How it works
^2/Eam2µḊ¿Ṭ  Main link. Argument: A (array of 1's and -1's)

       µḊ¿   While dequeuing A (removing its first element) yields a non-empty
             array, execute the monadic chain to the left, updating A with the
             return value after each iteration.
^2/            Compute the bitwise XOR of each non-overlapping pair of elements of
               A. Note that 1 ^ 1 = 0 = -1 ^ -1 and 1 ^ -1 = -2 = -1 ^ 1.
               For an array of even length that consists of the same pairs modulo
               the sign, this returns either an array of 0's or an array of -2's.
               If the length is odd, it will also contain the last element, which
               is either a 1 or a -1.
   E           Test the elements of the result for equality. This yields 1 if the
               array consists solely of 0's or solely of -2's, 0 otherwise.
    a          Take the logical AND of the previous result and every element of A.
               This returns A if it passed the previous test, but replaces all of
               its elements with 0's otherwise.
     m2        Modulo 2; select every second element of A, starting with the first.
             At this point, the last return value can be:
               • [  ] if the input was empty
               • [ 1] if the input was a valid OVSF code
               • [-1] if the input was the negative of a valid OVSF code.
               • [ 0] in all other cases.
           Ṭ  Untruth; yield an array with 1's at the specified indices.
              Indexing is 1-based in Jelly, so [1] returns [1], the array with a 1
              at index 1. Since the indices -1 and 0 are non-canonical, the arrays
              [-1] and [0] are mapped to []. The empty array remains empty.

Mathematica, 52 47 45 bytes
Byte count assumes CP-1252 encoding and $CharacterEncoding set to WindowsANSI (the default on Windows installations).
±___=!(±1=1>0)
a__±b__/;a!==b!||{a}==-{b}:=±a

This defines a variadic function PlusMinus, which takes the input list as a flat list of arguments and returns a boolean, e.g. PlusMinus[1, -1, -1, 1] gives True. It's theoretically also usable as an operator ±, but that operator is only syntactically valid in unary and binary contexts, so the calling convention would get weird: ±##&[1,-1,-1,1]. It will throw a bunch of warnings that can be ignored.
This will also throw a few warnings which can be ignored.
There might be away to shorten the somewhat annoying a!==b!||{a}==-{b} part, but I'm not finding anything right now. Keywords like SubsetQ and MatrixRank are simply too long. :/
Explanation
The solution basically defers all the tricky things to Mathematica's pattern matcher and is therefore very declarative in style. Apart from some golfitude on the first line, this really just adds three different definitions for the operator ±:
±___=False;
±1=True;
a__±b__/;a!==b!||{a}==-{b}:=±a

The first two rows were shortened by nesting the definitions and expressing True as 1>0.
We should deconstruct this further to show how this actually defines a variadci function PlusMinus by only using unary and binary operator notation. The catch is that all operators are simply syntactic sugar for full expressions. In our case ± corresponds to PlusMinus. The following code is 100% equivalent:
PlusMinus[___]=False;
PlusMinus[1]=True;
PlusMinus[a__,b__]/;a!==b!||{a}==-{b}:=PlusMinus[a]

By using sequences (sort of like splats in other languages) as the operands to ± we can cover an arbitrary number of arguments to PlusMinus, even though ± isn't usable with more than two arguments. The fundamental reason is that syntactic sugar is resolved first, before any of these sequences are expanded.
On to the definitions:
The first definition is simply a fallback (___ matches an arbitrary list of arguments). Anything that isn't matched by the more specific definitions below will give False.
The second definition is the base case for the OVSF, the list containing only 1. We define this to be True.
Finally, the third definition applies only to lists that can be decomposed into X ++ X or X ++ -X, and recursively uses the result for X. The definition is limited to these lists by ensuring they can be split into subsequences a and b with a__±b__ and then attaching the condition (/;) that either {a}=={b} or {a}==-{b}. Defining PlusMinus as a variadic function in this weird way via an operator saves a whopping 5 bytes over defining a unary operator ± on lists.
But wait, there's more. We're using a!==b! instead of {a}=={b}. Clearly, we're doing this because it's two bytes shorter, but the interesting question is why does it work. As I've explained above, all operators are just syntactic sugar for some expression with a head. {a} is List[a]. But a is a sequence (like I said, sort of like a splat in other languages) so if a is 1,-1,1 then we get List[1,-1,1]. Now postfix ! is Factorial. So here, we'd get Factorial[1,-1,1]. But Factorial doesn't know what to do when it has a different number of arguments than one, so this simply remains unevaluated. == doesn't really care if the thing on both sides are lists, it just compares the expressions, and if they are equal it gives True (in this case, it won't actually give False if they aren't, but patterns don't match if the condition returns anything other than True). So that means, the equality check still works if there are at least two elements in the lists. What if there's only one? If a is 1 then a! is still 1. If a is -1 then a! gives ComplexInfinity. Now, comparing 1 to itself still works fine of course. But ComplexInfinity == ComplexInfinity remains unevaluated, and doesn't give true even though a == -1 == b. Luckily, this doesn't matter, because the only situation this shows up in is PlusMinus[-1, -1] which isn't a valid OVSF anyway! (If the condition did return True, the recursive call would report False after all, so it doesn't matter that the check doesn't work out.) We can't use the same trick for {a}==-{b} because the - wouldn't thread over Factorial, it only threads over List.
The pattern matcher will take care of the rest and simply find the correct definition to apply.

Haskell, 57 bytes
q=length
f l=l==until((>=q l).q)(\s->s++map(*l!!q s)s)[1]

Given input list l, grows a OVSF code s by starting from [1] and repeatedly concatenating either s or -s, whichever makes the first element match that of l. Then, checks that the result is l at the end. This is checked once s has length at least that of l.
Some alternatives recursive structures also happened to give 57:
(s%i)l|length l<=i=s==l|j<-2*i=(s++map(*l!!i)s)%j$l
[1]%1

q=length
s%l|q s>=q l=s==l|r<-s++map(*l!!q s)s=r%l
([1]%)

q=length
g s l|q s<q l=g(s++map(*l!!q s)s)l|1>0=s==l
g[1]

MATLAB/Octave, 94 bytes
function a=f(r);n=nnz(r);m=log2(n);a=0;if fix(m)-m==0;for c=hadamard(n);a=a+all(r==c');end;end

This is using a new approach: The allowed OVSF codes of length N appear in the log2(N)-th Walsh-matrix, as they are basically defined by the same recursion:

Walsh matrices are special cases of the Hadamard-matrices of size N x N if N is a power of two. (There are also Hadamard matrices of other sizes.) MATLAB and Octave have a variety of built in functions that generate test matrices to test properties of numerical algorithms, among them is hadamard(). Fortunately for powers of two MATLAB's hadamard() usex exactly the construction of the Welsh-matrices.
So this function first checks whether the inputs length is a power of two, and if it is, it checks whether it is a row of the corresponding size Welsh-matrix.
Try it online!

Python, 64 bytes
f=lambda l:[]<l[1::2]==[x*l[1]for x in l[::2]]*f(l[::2])or[1]==l

Splits the list into even-indexed elements and odd-indexed elements via slices. Checks if the result vectors are either equals or negatives by multiplying one by the sign forced by its first element. Then, does the same recursive check on the even-indexed elements.
For the base case, if the check fails, rejects unless the list is [1]. The empty list is also specifically rejected to avoid an infinite loop.
A different strategy like my Haskell answer gives 66 bytes:
f=lambda l,i=1,s=[1]:l[i:]and f(l,i*2,s+[x*l[i]for x in s])or s==l

><> (Fish), 431 385 bytes

-46 bytes by creating a new stack with l-2 elements so I can remove the 2- from many places.

l[bb01.
>rl2=?vl3=?vl2%?vl2-2,[r0501.
      0v=1:<    0
< <  < <<       /
  1  0
   ?!^  v|.!]@{r/
 v&,2-2l<
 >&:?!v1-&l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@=?!v}]]
 l2-, ~v&,2-2lr                 .c1r8+eer]]}<
^    1<>&:?!v1-&l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@0$-=?!v}]]79.
^         1~<.a10r                       .c1ra+eer]]}<
n;
>&1+&v
     >&:?!v1-&l4-2,[}]l4-[r]l4-2,[{]l4-[r]
       .r~<

Try it
This took me wayyyy to long. Checking if 2 lists are equal is a pain in ><>

This code loops to check if 2 lists are equal:
l2-[l2,[{]rl2,[}]rl2,1+[{$:@$:@=?!v}]]

Basically, what we do is:

l gets the length of the stack
l-2 is the total length of both lists. So you see l2- all over.
(l-2)/2 is the length of one list, so you see l2-2, all over too.
l2-2,[{] moves the top list to a new stack, shifts it left, then pushes it back to the old list. This means a new value is the top one.
To shift the other list, it's a bit more complex. Since there is no command to push the bottom of the stack to a new list. We use l2-[3]l2-2,[}]l2-[r]. Reverse both lists, then shift the top half right, then reverse both lists together again.
Now we need to check if the top of both lists are equal. We now take (l-2)/2+1 elements, so the entire top list but 1 of the bottom list. Then we shift left to 1 item from the bottom list to the top. Now we use the $:@$:@ trick to compare them. In either case we need to shift the list back.

this is copied twice. There is also this:
>&1+&v
     >&:?!v1-&l4-2,[{]l4-[r]l4-2,[{]l4-[r]
       .r~<

Which resets the list after the checking process, only needed if the process was aborted halfway though (they where not equal)

JavaScript (ES6), 85 61 bytes
a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>e==a[j=i&-i]*a[i-j])

Previous version which checked elements to ensure that they were 1 or -1:
a=>(l=a.length)&&!(l&l-1)&a.every((e,i)=>i?(j=i&-i)<i?e==a[j]*a[i-j]:e==1|e==-1:e==1)

Explanation:

The length cannot be zero
The length must be a power of 2
The first element must be 1
Elements in positions that are a power of 2 must be either 1 or -1
Elements in other positions are the product of all the elements in the positions corresponding to the bitmask, e.g. a[22] == a[2] * a[4] * a[16]. Since a[20] == a[4] * a[16] has already been checked, only a[22] == a[2] * a[20] needs to be checked.
The above check gives degenerate results for i not having at least two bits set. In the case of zero bits set, it checks that a[0] == a[0] * a[0], which is false for a[0] == -1, while in the case of one bit set, it checks that a[i] == a[0] * a[i].

You can change (l=a.length)&&!(l&l-1) to (l=a.length)&-l==l to save 4 bytes

@PatrickRoberts Isn't that true for l==0?

Oh, you're right. Well then (l=a.length)&&l&-l==l? to save 1 byte...

Actually nevermind, your function fails for the case [1,1,1,1,-1,-1,-1,-1,1,1,1,1,1,1,1,1] even without my suggestions.

@PatrickRoberts l&-l==l doesn't work because == has higher precedence than &. And the test case doesn't work because of a typo which is going to cost me a byte to fix.

K (ngn/k), 34 bytes
Translation of Jonah's solution.
{~^*((#1_2\#x){(x,x),'x,-x}/,1)?x}

Try it online!

Haskell, 106 91 87 86 bytes
g n|n<1=[[1]]|m<-g(n-1)=foldl(\a b->[b++map(0-)b,b++b]++a)[]m++m
f l=elem l$g$length l

The function g generates the n iteration of lists (relatively inefficiently, since length $ g n == 3^n, however if we'd delete the duplicates, we'd get 2^n), f checks if our list is in any one of them. Thanks to @Zgrab for a few hints!
Try it online!

Running the last 2 test cases didn't yield an output for me.

@obarakon Yep, that is because g is very inefficient and produces a ton of duplicates. (Check the debug section, it is probably due to the time or memory limitations.)

JavaScript (ES6), 130 93 87 85 83 bytes
f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b))

Demo

f=a=>(b=a.slice(0,l=a.length/2),c=a.slice(l)+"",a==1||l&&b==c|b.map(i=>-i)==c&f(b)),[[],[1],[-1],[1,1],[1,-1],[1,1,1,1],[1,1,1,1,1],[1,-1,-1,1,-1,1,1,-1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,1,1,1,1],[1,1,1,1,-1,-1,-1,-1,1,1,1,1,-1,-1,-1,-1]].map(a=>console.log(`[${a}] -> ${!!f(a)}`))

APL, 46 bytes
{0::0⋄⍵≡,1:1⋄⍬≡⍵:0⋄(∇Z↑⍵)∧(∇Y)∨∇-Y←⍵↓⍨Z←.5×⍴⍵}

Fairly straightforward:

Base cases:

0::0: if an error occurs, return 0
⍵≡,1:1: if the input is exactly [1], return 1
⍬≡⍵:0: if the input is the empty list, return 0

Recursive case:

Z←.5×⍴⍵: Z is half the length of the input
Y←⍵↓⍨Z: Y is the last half of the input (this fails if ⍴⍵ is uneven, triggering the exception handler)
(∇Y)∨∇-Y: either the last half of the list, or the negation of the last half of the list, must be an OVSF code
(∇Z↑⍵)∧: and the first half of the list must be an OVSF code.

I don't think it's enough to check OVSF-codeness for the second half; it should be equal to the first half or its negation.

they say BASIC is a high level languish and APL is a high level of anguish :')

they say BASIC is a high level languish and APL is a high level of anguish :')

MATL, 21 20 bytes
`2eZ}yy=&=tn1>hh]1X=

Try it online! Or verify all test cases.
How it works
The code splits the array into two equal-length pieces: the first with the odd-indexed entries, the second with the even-indexed entries. The two pieces are forced to have equal length, with a padding zero in the second if needed. Then the code checks that

The corresponding entries of the two pieces are either all equal or all different;
No entry in the second piece is zero;
The length of the pieces exceeds 1.

If these three conditions are met, the process is applied again on the first piece. If the loop is exited because the length was already 1, the input is an OFSV code. Else it is not.
Condition 1 iterated is an equivalent version of the defining property of OVSF codes. For an array of say length 8, the straightforward approach would be to check that entries 1,2,3,4 are all equal or all different to entries 5,6,7,8 respectively (this is the defining property). But we can equivalently check that entries 1,3,5,7 are all equal or all different to entries 2,4,6,8 respectively; and this turns out to use fewer bytes.
Condition 2 makes sure that the input length is a power of 2: if it's not, a padding zero will be introduced at some stage.
`        % Do...while loop
  2e     %   Reshape as a two-row matrix, with a padding zero if needed
         %   Row 1 contains the original odd-indexed entries, row 2 the
         %   even-indexed
  Z}     %   Split matrix into two vectors, one corresponding to each row
  yy     %   Duplicate those two vectors
  =      %   Check if corresponding entries are equal or not
  &=     %   Matrix of all pairwise comparisons. This will give a matrix
         %   filled with ones if and only if the previous check gave all
         %   true or all false (condition 1)
  tn1>   %   Duplicate and push true if size exceeds 1, or false otherwise
         %   (condition 3)
  hh     %   Concatenate condition 1, condition 3, and the original copy of
         %   the second piece (condition 2). The resulting vector is truthy
         %   if and only if it doesn't contain any zero
]        % End
1X=      % True if top of the stack is a single 1, false otherwise

Haskell, 66 bytes
Yay, infinite lists!
o=[1]:(o>>= \x->[x++map(0-)x,x++x])
f l=l`elem`take(2*2^length l)o

Alternative versions:
o=[1]:(o<**>map(>>=flip(++))[map(0-),id])
f=Data.List.Ordered.hasBy(comparing length)o

Thanks for the (0-) trick, I was stuck with negate or ((-1)*)

J, 31 bytes
e.,.@1(],.~,],.-)^:[~0>.2<.@^.#

Try it online!
We build everything and check if the input is a member.

0>.2<.@^.# Tells us how many iterations to build: Base 2 log of the length of the list.  This will be the exact number of iterations for truthy cases.  To handle non-power-of-2 lengths, we take the floor.  To handle empty lists, we take the max with 0.
,.@1 Seed the iterations with a table containing just 1.
(],.~,],.-) Build the next iteration per the definition: Input zipped with itself ,.~ catted with , the input zipped with its negative ],.-.
e. Is the input a member of that list?

K (ngn/k), 41 bytes
f:{$[2>#x;x~,1;{f[x]&|/x~/:-:\y}.2 0N#x]}

Try it online!

Haskell, 69 68 bytes
g x=any(elem x)$scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]]x

Usage example: g [-1,1] -> False.
Even more inefficient than @flawr's answer. It takes too much time and memory for 4 element lists. To see that the list of OVSF codes (with a lot of duplicates) is actually created, try:
take 10 $ c $ scanr(\_->concat.mapM(\y->[y++y,y++map(0-)y]))[[1]] [1..4]

which returns
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1],
 [1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1],
 [1,-1,-1,1,1,-1,-1,1,1,-1,-1,1,1,-1,-1,1],
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
 [1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1]]

i.e. the list starts with all 16 element lists (4 times concatenated, because of [1..4]), continues with all 8 element lists and so on until it ends with [1].
Edit: @xnor saved a byte. Thanks!

Ah, I totally forgot about scanr!

I think you can cut a byte by doing any(elem x) instead of elem x$c and not defining c.

Python 2, 78 75 bytes
def f(x):l=len(x)/2;return[n*x[l]*f(x[:l])for n in x[l:]]==x[:l]>[]or[1]==x

Try it online!

K (ngn/k), 47 bytes
{$[x~,1;1;(1=#?x*|x)&c=2*(d:-2!c:#x);o(d#x);0]}

Try it online!

More work testing for a power of two than I expected.

>/2\x should work to test if a number is a power of 2

Ugh.  Original tested a necessary condition but need recursion to cover sufficiency.

Vyxal, 11 bytes
⁽y↔≬y*≈MA=h

Try it online! or Test suite. Returns 1 for truthy and 0 for falsy.
Explanation
Essentially compares the odd indices to even indices, then applying it again with even indices, until arriving with an empty list.
⁽y          # a lambda that returns the even indices only
  ↔         # apply to the input until empty, returning a new list containing
            #  the values each time it was applied. Includes the input
   ≬        # a lambda that:
    y       #  uninterleaves (pushes odd indices then even indices)
     *      #  multiplies (vectorises)
            #  - in the case that the length of the input is not a power of two,
            #    it pads a 0 to the shorter list
      ≈     #  then checks if all are equal
       M    # map to each element
        A   # check if all are truthy
         =  # is the number equal to the input? (vectorises)
            # - -1 is always 0
            # - 0 never appears in the input
            # - 1 is 1 if it satisfies OVSF code, otherwise 0
            # - an input of [] returns []
          h # get first element
            # - [] outputs 0
            # - [-1,...] outputs 0
            # - [1,...] outputs 1 if it is valid

JavaScript (ES6), 80
f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

Recursively builds and check each list up to the length of the input list, starting with [1].
Return value is JS truthy or falsey, specifically 1 or true if valid, 0 or false or undefined if not valid.
Test

f=(l,k=[1])=>l+l==k+k||l[k.length]&&f(l,k.concat(k))|f(l,k.concat(k.map(v=>-v)))

test=`[] -> False
[1] -> True
[-1] -> False
[1, 1] -> True
[1, -1] -> True
[1, 1, 1, 1] -> True
[1, 1, 1, 1, 1] -> False
[1, -1, -1, 1, -1, 1, 1, -1] -> True
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, 1, 1, 1, 1] -> False
[1, 1, 1, 1, -1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, -1] -> True`
.split('\n')

test.forEach(r=>{
  input = r.match(/-?1/g)||[]
  check = r.slice(-4) == 'True'
  result = f(input)
  console.log(result, check, '['+input+']')
})

Clojure, 118 bytes
(defn f[C](or(=(count C)1)(let[l(/(count C)2)[a b](split-at l C)](and(> l 0)(=(count b)l)(apply =(map * a b))(f a)))))

Splits input c into two halves a and b and checks if their element-wise products are all identical. If so, checks that the first half is valid sequence.
This one is 142 bytes but I found it more interesting:
#((set(nth(iterate(fn[I](mapcat(fn[i][(concat i i)(concat i(map - i))])I))[[1][-1]])(loop[l(count %)i 0](if(< l 2)i(recur(/ l 2)(inc i))))))%)

loop calculates log_2 of input's length, iterate generates sequences of that many iterations based on the definition. This returns the input argument if it is a valid sequence and nil otherwise.

Rust, 150 bytes
|m|f(m,1);fn f(k:&[i8],u:i8)->bool{let m=k.len()/2;k!=&[]&&(k==&[u]||f(&k[..m],u)&&(&k[..m]==&k[m..]||(f(&k[m..],-u)&&(0..m).all(|i|k[i]==-k[i+m]))))}

Attempt This Online!

Prolog (SWI), 96 75 bytes
+[1].
+L:-append(A,B,L),A\=[],(A=B;A-B),+A.
[]-[].
[A|B]-[C|D]:-C is-A,B-D.

Try it online!
-15 bytes thanks to Steffan!

81 bytes

Haskell, 85 82 bytes
-3 bytes thanks to @Laikoni
f[x]=x<0
f x|n<-length x`div`2,y<-take n x,z<-drop n x=n<1||y/=z&&y/=map(0-)z||f y

Try it online!
Not too short but efficient.

Assignments in a guard are a bit shorter than using where: Try it online!


text:
Sort a string, sort of
If you sort a string you'll typically get something like:
         ':Iaaceeefggghiiiiklllllmnnooooprrssstttttuuyyyy

Yes, that was the first sentence sorted.
As you can see, there are a lot of repeated characters, aa, eee, ttttt, 9 spaces and so on.
If we add 128 to the ASCII-value of the first duplicate, 256 to the second, 384 to the third and so on, sort it again and output the new string (modulus 128 to get the same characters back) we get the string:
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

(Note the single leading space and the 4 trailing spaces).
The string is "sequentially sorted" <space>':I....uy, <space>aeg....uy, <space>egi....ty, <space>iloty, <space>lt, <space>, <space>,<space>, <space>.
It might be easier to visualize this if we use a string with digits in it. The string 111222334 will when "sorted" be: 123412312.
Challenge:
To no surprise, the challenge is to write a code that sorts a string according to the description above.
You can assume that the input string will contain only printable ASCII-characters in the range 32-126 (space to tilde).

Test cases:
**Test cases:**
 *:Tacest*es*s*

If you sort a string you'll typically get something like:
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

Hello, World!
 !,HWdelorlol

#MATLAB, 114 bytes
 #,14ABLMTbesty 1A

f=@(s)[mod(sort(cell2mat(cellfun(@(c)c+128*(0:nnz(c)-1),mat2cell(sort(s),1,histc(s,unique(s))),'un',0))),128),''];
'()*+,-0128:;=@[]acdefhilmnoqrstuz'(),0128@acefilmnorstu'(),12celmnostu'(),12celnstu(),clnst(),cls(),cs(),()()()()

This is code-golf, so the shortest code in each language counted in bytes will winref.

Title is a bit confusing, resulting in me thinking this and ignoring the description:
https://tio.run/nexus/05ab1e#@1@td2jh4ZVe//@rW3kmJqempWdkZufk5uUXFBWXlFYqJKamZ@bk5UM4IHZ@cUmlApACkjklCgoKAA Nice challenge otherwise, I'll work on expanding that to meet the brief.

Can we output a list of characters instead of a string?

If you can input a string, then the output should be a string too. If a list of characters is the normal way of inputting and outputting strings in your languages then it's OK. You can for instance not output {'S', 'g', 'i', 'n', 'r', 't'} in Python, since the "normal" way to do it is "String".

I'll correct my comment above: a string is a list of characters, so a list of characters is accepted output. However, a list of strings is not accepted. This means, if it's possible to add a second character to an element in your list then it's not accepted. As an example: {'a','b'} is not accepted in Matlab since you can add a character to each of the characters like this: {'aa','b'}. Your input and output must be on the same format.

@StewieGriffin When you say sorted according to the description above. Do you mean my sort algorithm must follow the process of modifying ASCII values or it just has to produce the same output as that algorithm?

No, you only need the same result. So far, I think only one answer has used the same algorithm.

Proposed alternate title: ,Safginorst orst ort :P

@DJMcMayhem haha, nice and descriptive title... It's actually possible to pronounce, so it could work :)

It would be funny if someone made an answer that was already sorted |:)

Pyth, 5 bytes
s.T.g

Test suite
Very straightforward: Group and sort, transpose, concatenate.
s.T.g
s.T.gkQ    Implicit variables
   .gkQ    Group the input input lists of elements whose values match when the
           identity function is applied, sorted by the output value.
 .T        Transpose, skipping empty values. This puts all first characters into
           a list, then all second, etc.
s          Concatenate.

Pyth has everything to become new J, it's awesome

@shabunc If you want to see the new J, check out https://github.com/DennisMitchell/jelly

Jelly, 3 bytes
ĠZị

Try it online!
How it works
Oh boy, this challenge was all but made for Jelly.
The group atom (Ġ) takes an array1 as input and groups indices that correspond to identical elements of the array. The array of index groups is sorted with the corresponding elements as keys, which is precisely the order we require for this challenge.
Next, the zip atom (Z) transposes rows and columns of the generated (ragged) matrix of indices. This simply consists of reading the columns of the matrix, skipping elements that are not present in that column. As a result, we get the first index of the character with the lowest code point, followed by the first index of the character with the second lowest code point, … followed by the second index of the character with the lowest code point, etc.
Finally, the unindex atom (ị) retrieves the elements of the input array at all of its indices in the generated order. The result is a 2D character array, which Jelly flattens before printing it.

1 Jelly doesn't have a string type, just arrays of characters.

"Oh boy, this challenge was all but made for Jelly." -> 3 byte answer

As I said, almost made for Jelly. :)

Python 3, 109 105 104 103 99 93 90 88 81 79 69 bytes
2 bytes saved thanks to FlipTack
7 bytes saved because flornquake caught my dumb error
2 bytes saved thanks to xnor
10 bytes saved thanks to Dennis
a=[*input()]
while a:
    for c in sorted({*a}):print(end=c);a.remove(c)

Explanation
We start by converting our string to a list using a splat and storing that list in a variable a.  Then while our a is not the empty list we go through each unique member of a in sorted order, print it and remove a copy of that character from the list.
Each iteration prints thus prints one copy of each character present in a.

Why is sorted even needed here? s=set(a) results in a sorted set of unique characters right? Then shouldn't list(s) also be sorted? (I have tested, so I know it's not, I just don't understand why)

@StewieGriffin set is an unsorted set.

@StewieGriffin when printed they are sorted but not by their ASCII values exactly.  It often appears they are but I believe they are sorted by some type of hash.

I see, I'm reading about it now... :) A bit confusing, since list gets a different order back... Why not keep it consistent at least...

@WheatWizard If the loop body has constructs like if, while, for, etc, then it has to be on a newline. But if it's just a few statements, it can be written all on one line

You can make f a string instead of a list to save a few bytes.

@flornquake Thanks I should have seen that a while ago.

If you take a=list(input()), you can do a.remove(c), which is a net savings.

Switching to Python 3 would save a lot of bytes. https://tio.run/nexus/python3#JY7NTsMwEITP9VMs4uAfDGoikFCqSC0nkOBWiUNVIeNsWgvHDrEDBMSzF5vcdmfnm1ntG4QaKKUnVe@Ecf0YGd@Tz6OxCKoii9YPoME4CH6I2LAfoX551Q/GRYauqTVfqasBO/@BTPNTSiIkMy@ZGZQ7ILvhKQe/UDOd6jhZzDQ/CbHFEEGrgKESgjy0MPnxvwkUhJhsh6xQayFOvdHK2gkOGJOlw3jMZ2vesCL3aK2X8OwH25yR86fN9nFzJ6EoruF1ihhIW69Z4LvONyzHM52AslPz0I6OrdP3@qIobwVbVs59p/Wy4DJZymyZqcBlIY8mRM2CHJ15HzFpnEs6OiqXeUoJaaX71R8

@Dennis Wow.  I tried a while ago and even with the fancy splats I could only save a byte.  Thanks for telling me.

Haskell, 44 bytes
import Data.List
concat.transpose.group.sort

Usage example:
Prelude Data.List> concat.transpose.group.sort $ "If you sort a string you'll typically get something like:"
" ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt    "

Sort, group equal chars to a list of strings (e.g. "aabbc" -> ["aa","bb","c"]), transpose and flatten into a single string, again.

This might be stupid thing to ask but how does this adds 128,256,384.... to the repeated values?

Python 2, 75 bytes
lambda s:`zip(*sorted((s[:i].count(c),c)for i,c in enumerate(s)))[1]`[2::5]

Try it online!

Don't know if it's valid but lambda s:`[sorted((1e9+s[:i].count(c),c)for i,c in enumerate(s))]`[18::21] works for strings with max length 9e9.

@xnor you can drop the [] and change 18 to 17 to save two bytes.  lambda s:\sorted((1e9+s[:i].count(c),c)for i,c in enumerate(s))`[17::21]`

@xnor At the very least, this should be a valid 32-bit Python golf. I tried to get rid off the zip, but I don't think adding 1e9 would have ever occurred to me... Thanks!

@WheatWizard Good eye. Thanks!

This fails if the string has backslashes in it.

@Lynn Right, rollang back. Thanks for catching that.

APL (Dyalog Unicode), 21 20 bytes
t[0~⍨∊⍉(⊂⍋∪t)⌷⊢⌸t←⍞]

Try it online!
t[...] index t (to be defined shortly) with...
 0~⍨ zeros removed from
 ∊ the enlisted (flattened)
 ⍉ transposed
 (⊂…)⌷ reordered using…
  ⍋ the indices which would sort
  ∪ the unique letters of
  t t (to be defined shortly)
 ⊢⌸t keyed* t, which has the value of
  ⍞ prompted text input
TryAPL online!

* ⊢⌸t creates a table where the rows (padded with zeros for a rectangular table) list each unique letters' indices in t.

which of the glyphs are more expensive?

@ren Updated to use new technology that allows counting each glyph as a single byte.

C, 109 106 105 104 102 100 97 98 96 91 Bytes
Back up to 98 Bytes, needed to initialize j to make f(n) re-useable
Down to 96 Bytes using puts in place of strlen B-)
It's strange I had to back to strlen but I got rid of the for(;i++;) loop so now it's down to 91 Bytes.  Apparently the man page for puts reads;
"RETURNS
   If successful, the result is a nonnegative integer; otherwise, the result is `EOF'."

... I was lucky it was working in the first place
char*c,i,j;f(m){for(j=strlen(m);j;++i)for(c=m;*c;c++)if(*c==i){*c=7,putchar(i),j--;break;}}

test code...
main(c,v)char**v;
{
    char test[] = "If you sort a string you'll typically get something like: ";
    char test2[] = "Hello, World!";

    f(test);puts("");
    f(test2);puts("");
}

Here are a few test cases, now it's time to golf this down
C:\eng\golf>a.exe
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt
 !,HWdelorlo

Are the trailing spaces left out in the first test case?

I have three trailing spaces in the first test case...  That's because I didn't include the trailing space on the input string ;-)

Mathematica, 68 60 59 bytes
Split[Characters@#~SortBy~ToCharacterCode]~Flatten~{2}<>""&

Accepts a String. Outputs a String.
If list of characters were allowed (46 bytes):
Split[#~SortBy~ToCharacterCode]~Flatten~{2,1}&

Version using Sort (40 bytes):
Split@Sort@Characters@#~Flatten~{2}<>""&

This version cannot be my answer because Sort cannot be used here; Sort sorts by canonical order, not by character code.

I don't know mathematica so this might be just fine, but did you read this comment?

@StewieGriffin Welp, nope. I can fix that, but doesn't that give an unfair advantage to languages that don't have a String vs Char[] distinction? Related meta discussion

Good point. I made a correction, see the comment below the original. Fair? I'm not sure if this makes your answer valid or not.

@StewieGriffin Mathematica doesn't have a distinction between characters and strings. Even the Characters command technically output  a list of length-1 strings.

@StewieGriffin I think this is also relevant. I think it's better to allow the input in any reasonable format, be it a string, list of length 1 strings, array of characters, array of bytes, etc.

Wow, I had no clue that this usage of Flatten exists.

@MartinEnder This is a good guide.

JavaScript (ES6), 79 bytes

f=s=>s&&(a=[...new Set(s)]).sort().join``+f(a.reduce((s,e)=>s.replace(e,``),s))
<input oninput=o.textContent=f(this.value)>

Works by extracting the set of unique characters, sorting it, removing them from the original string, and recursively calculating the sort of the rest of the string. 81 byte solution that I found interesting:
f=s=>s&&(s=[...s].sort().join``).replace(r=/(.)(\1*)/g,"$1")+f(s.replace(r,"$2"))

Python 2, 77 76 bytes
d={}
def f(c):d[c]=r=d.get(c,c),;return r
print`sorted(input(),key=f)`[2::5]

Takes a quoted string as input from stdin.
Try it online!

I think this isn't allowed because functions have to be re-usable. You could make it a program.

I really like this method, sorting with a function that mutates. The nesting of tuples is clever too.

@xnor Thanks, fixed.

J, 16 15 bytes
/:+/@(={:)\;"0]

This is a verb that takes and returns one string.
Try it online!
Miles saved a byte, thanks!
Explanation
Nothing too fancy here: sort primarily by order of occurrence, secondarily by char value.
/:+/@(={:)\;"0]  Input is y.
          \      Map over prefixes:
  +/              Sum
    @(   )        of
      =           bit-array of equality
       {:         with last element.
                 This gives an array of integers whose i'th element is k
                 if index i is the k'th occurrence of y[i].
           ;     Pair this array
            "0   element-wise
              ]  with y
/:               and sort y using it as key.

I think you can save a byte moving summation to the outside of the parentheses +/@(={:)\

@Miles Oh yeah, because a train has infinite rank. Nice, thanks!

V, 37 36 bytes
Thanks @DJMcMayhem for the byte!
Í./&ò
dd:sor
Íî
òÍ¨.©¨±«©±À!¨.«©/±³²

Try it online!
Not sure I like the regex at the end, but I needed to make the ò break somehow.
Explain
Í./&ò                    #All chars on their own line
dd:sor                   #Delete empty line, sort chars
Íî                       #Join all lines together s/\n//
òÍ¨.©¨±«©±À!¨.«©/±³² #until breaking s/\v(.)(\1+)\1@!(.+)/\3\2\1

Íî (or :%s/\n//g) is shorter than VGgJ

Python 2, 70 bytes
f=lambda s,i=0,c='':s[i>>7:]and(s.count(c)>i>>7)*c+f(s,i+1,chr(i%128))

Try it online
This is very inefficient. The test link changes the i>>7 to i>>5 and sets the recursion limit to 10000. Assumes the inputs only has ASCII values up to 126.
Uses the div-mod trick to iterate through two loops: minimum counts i/128 in the outer loop and ASCII values i%128 in the inner loop. Includes a character c with the given ASCII value if the number of times it appears in the string is at least its minimum count.
The code uses a trick to simulate the assignment c=chr(i%128) so that it can be referenced in the expression (s.count(c)>i>>7)*c. Python lambdas do not allow assignment because they only take expressions. Converting to a def or full program is still a net loss here.
Instead, the function pushes forward the value chr(i%128) to the next recursive call as an optional input. This is off by one because i has been incremented, but doesn't matter as long as the string doesn't contain special character '\x7f' (we could also raise 128 to 256). The initial c='' is harmless.

Brainf*ck, 458 226 bytes
,[>>>>>>,]<<<<<<[[-<<<+<<<]>>>[>>>[>>>>>>]<<<[>>--[<->--]<-<[>->+<[>]>[<+>-]<<[<]>-]>>.[[-]<]<<<[[>>>>>>+<<<<<<-]<<<]>>>>>>]>>>[>>>[>>>>>>]<<<[>>--[<->--]<-<[>->+<[>]>[<+>-]<<[<]>-]>>[-<+<+>>]<[->>+<<]<[<<<<<<]>>>]>>>]]<<<<<<]

Try it online! - BF
Numberwang, 262 226 bytes
8400000087111111442111911170004000400000071114002241202271214020914070419027114170270034427171114400000091111112711170000007000400040000007111400224120227121402091407041902711417027004219190071420091171411111170007000771111117

Try it online! - NW
I put both of these here because they are identical code.

PHP, 83 bytes
for($s=count_chars($argv[1]);$s=array_filter($s);$c%=128)echo$s[++$c]--?chr($c):'';

Unfortunately you can't have unset in a ternary so I need to use the annoyingly long array_filter.
Use like:
php -r "for($s=count_chars($argv[1]);$s=array_filter($s);$c%=128)echo$s[++$c]--?chr($c):'';" "If you sort a string you'll typically get something like:"

Vyxal d, 3 bytes
sĠ∩

Try it Online!
s   # Sort
 Ġ  # Group run lengths
  ∩ # Transpose
    # (d flag) take deep sum

FSharp, 194 190 170 140 133 bytes
let f=Seq.map
let(@)=(>>)
f int@Seq.groupBy id@f(snd@Seq.mapi((*)128@(+)))@Seq.concat@Seq.sort@f((%)@(|>)128@byte)@Array.ofSeq@f char

Using Seq instead of Array saves a couple of bytes
Defining a shorter name, and using another maps to avoid a (fun ->) block
It turns out F# can map a char to an in, so removing the shortened name of System.Text.Encoding.ASCII, and adding in another map saves me 20 bytes!
Returning a char array instead of a string, saves me 30 bytes!
I no longer need to make sure it's a string, saves me 7 bytes

Perl 6, 54 bytes
{[~] flat roundrobin |.comb.classify(~*){*}.sort»[*]}

Explanation:

{  }: A lambda that takes one argument -- e.g. 21211.
.comb: Split the input argument into a list of characters -- e.g. (2,1,2,1,1).
.classify(~*): Group the characters using string comparison as the grouping condition, returning an unordered Hash -- e.g. { 2=>[2,2], 1=>[1,1,1] }.
{*}: Return a list of all values of the Hash -- e.g. [2,2], [1,1,1].
.sort: Sort it -- e.g. [1,1,1], [2,2].
»[*]: Strip the item containers the arrays were wrapped in due to being in the hash, so that they won't be considered as a single item in the following step -- e.g. (1,1,1), (2,2).
roundrobin |: Zip the sub-lists until all are exhausted -- e.g. (1,2), (1,2), (1).
flat: Flatten the result -- e.g. 1, 2, 1, 2, 1.
[~]: Concatenate it to get a string again -- e.g. 12121.

(Credit for the roundrobin approach goes to Sean's answer.)

05AB1E, 15 bytes
{.¡"ä"©¹g×«øJ®K

Try it online!
or as a
Test suite
Explanation
{                # sort input
 .¡              # group by equal elements
   "ä"©          # push "ä" and store a copy in the register
       ¹g×       # repeat the "ä" input-nr times
          «      # concatenate the result to each string in the grouped input
           ø     # zip
            J    # join to string
             ®K  # remove all instances of "ä" in the string

10 of the 15 bytes are for getting around 05AB1E's way of handling zipping strings of different length.

Perl 6, 68 bytes
{my \a=.comb.sort;[~] flat roundrobin |a.squish.map({grep *eq$_,a})}

I was a little surprised to find that there's no built-in way to group like elements in a list.  That's what the squish-map bit does.

I get "This Seq has already been iterated" unless I rename a to @a (+2 bytes). Also, grep *eq$_, can be written grep $_, (-3 bytes) since a string is a valid smart-matcher.

{[~] flat roundrobin |.comb.classify(~*){*}.sort»[*]} -- This variation is only 54 bytes.

@smis I don't see that error.  Maybe we're using different versions?  I'm on rakudo-star-2016.10.  Anyway, your solution puts mine to shame, you should post it as a separate answer.

I'm using a bleeding-edge Rakudo compiled from the main branch of the git repo this week. Anyway, I posted the classify-based solution as a separate answer now.

JavaScript (ES6), 77 75 bytes
s=>(a=[],x={},[...s].sort().map(c=>a[x[c]=n=-~x[c]]=(a[n]||'')+c),a).join``

Stable sorts the lexicographically sorted string by nth occurence

F=s=>(a=[],x={},[...s].sort().map(c=>a[x[c]=n=-~x[c]]=(a[n]||'')+c),a).join``

const update = () => {
  console.clear();
  console.log(F(input.value));
};
input.oninput = update;
update();
#input {
  width: 100%;
  box-sizing: border-box;
}
<input id="input" type="text" value="         ':Iaaceeefggghiiiiklllllmnnooooprrssstttttuuyyyy" length=99/>

1+~~ is the same as -~.

@Neil Awesome thanks -2 bytes

Husk, 4 bytes
ΣTgO

Try it online!
Explanation
ΣTgO
   O Order
  g  group
 T   Transpose
Σ    join

Japt -P, 4 bytes
Input as a character array, output as a string.
ü Õc

Try it
ü Õc     :Implicit input of character array
ü        :Group & sort
  Õ      :Transpose
   c     :Flatten
         :Implicitly join & output

JavaScript (Node.js), 71 bytes
f=x=>x&&[...x].filter(k=c=>k[c]?![h+=c]:k[c]=1,h='').sort().join``+f(h)

Try it online!

Retina, 24 bytes
O`.
O$#`(.)(?=(\1)*)
$#2

Try it online!

Ruby, 59+1 = 60 bytes
Adds one byte for the -n flag. Port of @PatrickRoberts' dictionary solution.
d={};print *$_.chars.sort_by{|c|d[c]||=0;c.ord+128*d[c]+=1}

JavaScript (ES6), 114 bytes
Separated with newline for clarity, not part of byte count:
s=>[...s].map(a=>(m[a]=-~m[a])*128+a.charCodeAt(),m={})
.sort((a,b)=>a-b).map(a=>String.fromCharCode(a%128)).join``

Demo

`**Test cases:**
 *:Tacest*es*s*

If you sort a string you'll typically get something like:
 ':Iacefghiklmnoprstuy aegilnorstuy egilosty iloty lt

Hello, World!
 !,HWdelorlol

#MATLAB, 114 bytes
 #,14ABLMTbesty 1A

f=@(s)[mod(sort(cell2mat(cellfun(@(c)c+128*(0:nnz(c)-1),mat2cell(sort(s),1,histc(s,unique(s))),'un',0))),128),''];
'()*+,-0128:;=@[]acdefhilmnoqrstuz'(),0128@acefilmnorstu'(),12celmnostu'(),12celnstu(),clnst(),cls(),cs(),()()()()`.split`\n\n`.map(s=>(p=s.split`\n`,console.log(`${p[0]}\n\n${r=f(p[0])}\n\nmatch: ${r==p[1]}`)),
f=s=>[...s].map(a=>(m[a]=-~m[a])*128+a.charCodeAt(),m={}).sort((a,b)=>a-b).map(a=>String.fromCharCode(a%128)).join``)

The same bytecount as my Matlab code, and the exact same approach. Haven't attempted to golf mine yet though. I'll probably upvote later if you add an explanation :-) (I've made a principle out of not upvoting answers without explanations, even when I understand it) :-)

Clojure, 79 bytes
#(for[V[(group-by(fn[s]s)%)]i(range 1e9)k(sort(keys V))c[(get(V k)i)]:when c]c)

An anonymous function, returns a sequence of characters. Supports up-to 10^9 repetitions of any characters, which should be plenty.

BQN, 6 bytesSBCS
∾·⊒⊸⊔∧

Run online!
sort, group by occurrence count, join.

Factor + grouping.extras, 48 bytes
[ natural-sort [ ] group-by values round-robin ]

Attempt This Online!

natural-sort Sort the input
[ ] group-by values Group like contiguous elements, e.g. "aabbc" -> { "aa" "bb" "c" }
round-robin One from each group in order, until there are no elements left. e.g. { "aa" "bb" "c" } -> "abcab"