text:
Output the Arecibo Message

The Arecibo message is a 1974 interstellar radio message carrying basic information about humanity and Earth sent to globular star cluster M13 in the hope that extraterrestrial intelligence might receive and decipher it... The message consisted of 1,679 binary digits, approximately 210 bytes...
The number 1,679 was chosen because it is a semiprime (the product of two prime numbers), to be arranged rectangularly as 73 rows by 23 columns. The alternative arrangement, 23 rows by 73 columns, produces an unintelligible set of characters (as do all other X/Y formats).

This is the message with color added to highlight its separate parts. The actual binary transmission carried no color information.

Source: Wikipedia

Your task is to output the Arecibo Message in the exact 23x73 arrangement shown in the image. Any of these output formats is acceptable:

Text, using one character for ones and another for zeros (using the usual rules for row separation)
A 2D array of two distinct values
A 23x73 image with two distinct colors
Aan uninterrupted stream of 1679 items of two distinct values (i.e. any of the above formats, but flat.)
A 1679-bit integer. Indicate bit and byte order (endianness) in your solution.

For your convenience, here is a copy-pastable version (also an example output in text format):
00000010101010000000000
00101000001010000000100
10001000100010010110010
10101010101010100100100
00000000000000000000000
00000000000011000000000
00000000001101000000000
00000000001101000000000
00000000010101000000000
00000000011111000000000
00000000000000000000000
11000011100011000011000
10000000000000110010000
11010001100011000011010
11111011111011111011111
00000000000000000000000
00010000000000000000010
00000000000000000000000
00001000000000000000001
11111000000000000011111
00000000000000000000000
11000011000011100011000
10000000100000000010000
11010000110001110011010
11111011111011111011111
00000000000000000000000
00010000001100000000010
00000000001100000000000
00001000001100000000001
11111000001100000011111
00000000001100000000000
00100000000100000000100
00010000001100000001000
00001100001100000010000
00000011000100001100000
00000000001100110000000
00000011000100001100000
00001100001100000010000
00010000001000000001000
00100000001100000000100
01000000001100000000100
01000000000100000001000
00100000001000000010000
00010000000000001100000
00001100000000110000000
00100011101011000000000
00100000001000000000000
00100000111110000000000
00100001011101001011011
00000010011100100111111
10111000011100000110111
00000000010100000111011
00100000010100000111111
00100000010100000110000
00100000110110000000000
00000000000000000000000
00111000001000000000000
00111010100010101010101
00111000000000101010100
00000000000000101000000
00000000111110000000000
00000011111111100000000
00001110000000111000000
00011000000000001100000
00110100000000010110000
01100110000000110011000
01000101000001010001000
01000100100010010001000
00000100010100010000000
00000100001000010000000
00000100000000010000000
00000001001010000000000
01111001111101001111000

If your language, for some reason, has a builtin for the Arecibo Message, you may not use that builtin.
Good Luck!
UPDATE: I accepted the 05AB1E answer since it was the first one to be shorter than the original message. Don't let that dissuade you from new solutions.
UPDATE 2019-09-09: Accepted answer moved to a new 05AB1E answer, as it obsoletes the previous 05AB1E answer. Same point goes as previous update; new solutions still welcome.

If a language has a built in for Arecibo message, I can tell, with all certainty, that I've seen everything in this world c:

Mathematica (IIRC) has an image builtin for Lena, so it wouldn't surprise me if it also has an Aricebo message as well.

@RobertS. no because there are other valid formats besides text.

In the spirit of the original format, a flat result/output should be allowed. The whole point of 1679 bits is exactly that the proper number of rows and columns can be inferred from the signal length.

Are we allowed go return an array of strings, that do not represent lines?

@EmbodimentofIgnorance, how else would you represent it?

So is my solution here valid?

@EmbodimentofIgnorance unless it either outputs lines of 23 characters or an uninterrupted stream of 1679 values, no.

@LuisfelipeDejesusMunoz Mathematica has a builtin to determine goats in a picture, so an Arecibo message builtin wouldn't really surprise me either.. That language is built on builtins of the universe.. >.>

As far as I know, they didn't even bother repeating the message. It was sent only once. As mentioned on Wikipedia, it was really just a (fun) technological demonstration.

05AB1E, 182 bytes
•sv¯ö¨₁ÿ.ÛïžôΔ¨γ_Ígv…=Bм„Ð.(Ü¦i´…ε±G½0^/₃öRÛž¼¤"āêL!ˆ6‘GāÜ‡ðв₁÷Ã7€₂δ¬‚Cć¨g¾†@÷[_-68¯a∍iG*6ÆîÆ;>éjζãÎÂ+ºžnî¼ć'(ÝÞΔ‹∞Ã‰Ý¹Õ5λ₆*a|§oÄmôæ¨;Â—:hž¥ð¢ocË'¨%¡4Ćáß©ìća;FÁ?iˆèεƒʒ•Ž6–FD4‰`3ÊD?i-

Try it online! (uses 1 for 0 and 0 for 1, as allowed by the question).
Try it online! (5 bytes longer, 0 for 0 and 1 for 1, added newlines for readability).
Most of the code is a base-255 integer constant N, the rest is an Asymmetric Numeral System decoder, using hardcoded probabilities of 75% / 25% (the actual frequency of 0 is 76.35%, which is so close to 75% that it would only save 1.2 bits in the payload, while the nice and round 75% lets us save several bytes in the decoder).
Ž6–F                  # repeat the following 1679 times:
    D                 #  duplicate N
     4‰`              #  divmod 4: pushes N / 4, N % 4 on the stack
        3Ê            #  is N % 4 != 3 ? (boolean 1 or 0)
          D?          #  print a copy
            i-        #  if it's 1, subtract: N = N - (N / 4)
                      #  (otherwise, N = N / 4, since that's the top of the stack)

Here's the ANS encoder that generated the constant: Try it online!
Î                          # start from N = 0
 Rv         ]              # for each bit in the reversed input:
   4*                      #  N *= 4
     yi                    #  if the bit is 1:
       3+                  #   N += 3
         ë                 #  else:
          3÷               #   N /= 3 (integer division)
             ₅B'•.ø        # compress N as base-255

Good work at obsoleting the previous 05AB1E answer!

05AB1E, 215 210 200 bytes
Saved 15 bytes thanks to Magic Octopus Urn
•cOž¤4é57ñΛ\Ö₃BαöĀíL½₅üBdoÙRθLγ¨G×Tćú$G(˜ƒ¦!€R»SDrµCnJ†d∊ζ·<8‡T@|‹ï=BζćósxG\ÙÎ$¿o₁5/ÔŸÇBûXé-”a::Ž]°∊y;ζ]MÜβ‘иL”β{üÃÇíäc€÷›ÎU=}¨иaŸdY`»¾ÚUβ:ô©¦β†₅DGŠβ3Jêθ,äá!ícqšVÖ›lÈΣ¯pε €êÊƒDpÙ/¬Žλ8:ãÿ3=€.Þć•3BY¾4×:

Try it online!
or with Additional formatting
Base-255 encoded trinary string with occurrences of 0000 replaced by 2.

@MagicOctopusUrn: Thanks! That makes it 210 even :)

It's actually even better if you replace 0000 with 2 by 9 more bytes. - https://pastebin.com/aZ6tHxjx for 201

@MagicOctopusUrn: Yes, I found that as well and was just about to post it :)

Cool!  Since the Arecibo messages is 210 bytes (23 * 73 / 8 = 209.875), your solution (currently at 200 bytes) is shorter than the message itself!

I went ahead and made this the accepted answer since it was the first one to be shorter than the message itself.

Java, 688 678 590 379 361 bytes
Returns a string.
n->new java.math.BigInteger("in95mzupnpa2r0khpoepyql6ioqyn413avucdtfay6indx4wh9dehe3sn18klobtf4z9g9q17umqmwpegr2khb5eqinn7azl4jpfp2a8eui0xfrx5qwrou6gd65jh4ge3ls14k5lu7qrvmg6942ms29u5rb8fa6yrdhfoh5zoi9bdi7uh5ig0u0ff9kounth8sh357x7qox4m3oqviqsbrvakonbka4ahp21bgzi5v1akzzuqoncszhpabbru9q1uo2g11zr73iuyiqr5ikr69zn7cdv7e1lhd6ese9",36).toString(3).replace("2","0000")

-10 bytes by returning the raw stream (old answer)
-88 bytes by using base 10 numerics (thanks @ceilingcat!)
-211 bytes (I knew it could be golfed!) by using a base-36 encoded BigInteger (thanks @JollyJoker!)
-18 bytes by using a different encoded integer (thanks again @JollyJoker)

Try it online!

Explanation:
n->new java.math.BigInteger("base36 string",36) // Decode the base-36 integer.
   .toString(3)                                 // Re-encode as ternary
   .replace("2","0000")                         // Replace 2 with "0000"
                                                // Implicit return

Comments are not for extended discussion; this conversation has been moved to chat.

Jelly, 213 bytes
“H²ɓ¶Ṡḷ€ẹ]ƒf*ḳḢ&ƁṇOḥ{ḄṫwỊ+oLạʋß¢H9¢¹÷ỴɗÇ⁶ƲƙæḊẋ3³=1!VƇƁ'D⁺3Ỵɱ©⁵%fȯez#ƈjƒżṆo.ZF⁶ċṢ⁶ọṛb9Ȯƒd?ƁUĠt4ẇ,ḞġƒµƭfʠƁP§÷øȤŻPɲẋ(¢ß¢(⁽3¶ṙėɗy@ṁYȮL~e⁷ƤĊ§nỊṅµṠ°@7ẠB>Ġ⁻İ}uy¡½:esOpḢt}qS©HÞṬĖṛṇḣ9÷;ESḢ,Ẉ^ṙpƲ©tṃwçnẒṆ¡⁻Jıƒị£-&Ɱ*ẋʂżoȯÑḢɼ’

Try it online!
I played around with Huffman coding, but the improvements in data size were outweighed by the extra code. As such, this is simply a base-250 encoded version of the desired output. Output consists of an integer that when decoded as bijective base 2 will yield the 1D list of 1s and 2s. Thanks @Emigna for pointing out the change in rules.
Try it online - with further decoding to demonstrate output!
If a more conventional binary encoding is preferred, here is one that encodes an integer representation of the inverted binary message. The most significant bit of the integer represents the beginning of the message.

Brainfuck, 2360 2008 1938 1902 bytes
-[>+<-----]>---......+.-.+.-.+.-.+.-............>++[-<+.-.+.-.....>]<..+.-.>++[-<.+.-...+.-..>]<+.-.+..-..>+++[-<+.-.+.-.+.-.>]<.+.-..+.-.>+++[-<............>]<+..-..................>++[-<.+..-.+.-..................>]<+.-.+.-.+.-..................+.....-..>+++[-<..........>]<+..-....+...-...+..-....+..-...+.-.............+..-..+.-....+..-.+.-...+..-...+..-....+..-.+.-.>++[-<+.....-.+.....-.>]++[-<............>]<.+.-......>++[-<...........+.-.................>]<+......-.............+.....-.>++[-<...........>]<+..-....+..-....+...-...+..-...>++[-<+.-.......>]<..>++[-<+.-....+..-.>]<..+...-..+..-.+.-.>++[-<+.....-.+.....-.>]++[-<............>]<.+.-......+..-.........+.-...........+..-...............+.-.....+..-..........+......-.....+..-......+.....-..........+..-..........>+++[-<...+.-.....>]<+.-......+..>++[-<-.......+.>]<.-....+..-......+.-..........+..-...+.-....+..-...............+..-..+..-.............+..-...+.-....+..-.........+..-....+..-..>++[-<....+.-...>]++[-<...+.-.....>]<+.-.......>++[-<+..-........+.-...+.-........>]<.+.-.......+.-.....>++++[-<+.-.......>]++[-<.....+..-....>]<....+..-.........+.-...+...-.+.-.+..-...........>++[-<+.-.......>]<.......+.-.....+.....-............+.-....+.-.+...-.+.-..+.-.+..-.+..-......+.-..+...-..+.-..+.......-.+...-....+...-.....+..-.+...-.........+.-.+.-.....+...-.+..-..+.-......+.-.+.-.....+......-..+.-......+.-.+.-.....+..-......+.-.....+..-.+..-..>+++[-<...........>]<+...-.....+.-..............+...-.+.-.+.-...>++[-<+.-.+.-.+.-.>]<.+...-.........+.-.+.-.+.-.+.-................+.-.+.-..............+.....-................+.........-..........>++[-<..+...-.....>]++[-<....+..-.......>]<+..-.+.-.........+.-.+..-..>++[-<...+..-..+..-....>]<+.-.>++[-<..+.-.+.-...>]<+.-....>+++[-<+.-...+.-..>]<......>++[-<+.-...+.-.>]<...........+.-....+.-.>++[-<...+.-.........>]<+.-..............+.-..+.-.+.-...........+....-..+.....-.+.-..+....-...

Try it online!
My idea was to first generate a simple solution consisting of setting up an ASCII 0 followed only by +-. instructions to produce the output. Repeating sections can then be shortened using loops.
Choosing the optimal set of non-overlapping sections for looping basically comes down to solving a maximum-weight independent set problem. Currently, I just use a greedy algorithm which takes the section that can be optimized the most and then removes all conflicting sections. This is then repeated until no sections are left.
Using a more sophisticated algorithm one can surely achieve better results.

Piet, 1763 codels
Outputs a stream of 0s and 1s (no line breaks).
Codel size 1:

Codel size 4, for easier viewing:

Explanation

First, push a sentinel value of -1 onto the stack.
Then push the Arecibo message, in reverse order (because it's a stack), using run-length encoding.
Finally, alternate between two loops, one printing zeroes and the other printing ones.

The loop counter is the current stack value, decremented until it hits zero, at which point it is discarded and we switch to the other loop.
Between the zeroes-loop and the ones-loop, check for the sentinel value, exiting if it is found.

Notes
The program follows a spiral path, clockwise from top left into the centre. The scattered black blocks that roughly follow the diagonals are the flow control. Here's the trace from NPiet.
I've been working on this since the day this challenge went up, but it took a little bit of time to get the message "written" into the picture! I wrote the final loops and the sentinel value first, and then built up the message from the centre outwards. (Since Piet always starts execution from the top left, I expected to have to shuffle and rotate the image around to avoid excess whitespace, but it fit perfectly!)
Fun fact: Run-length encoding in Piet doesn't (by itself) save any space. It takes n codels of one colour to push the value n onto the stack, or n codels of different colours to push that many 1s onto the stack. So it's the same number of codels either way. But the bigger numbers that RLE gives you mean you can use arithmetic tricks (e.g. instead of pushing 9, you can push 3, duplicate, and multiply) to reduce the number of codels, and funny-shaped blocks to fill in available whitespace.
I wasn't sure about how to count score for Piet entries. I found some that seem to count all codels, and others that explicitly only count those actively used. I just counted them all; ignoring white codels (even those that the program never moves through) seems akin to ignoring whitespace in a more typical programming language.
Oh, and I've just now (two hours after posting) realised that I wasted the last bit of time working on this. I wanted to trim off the almost-completely-white last row and column, so I shuffled things around... including the black flow-control blocks. But the edges of the image work the same as black! If I'd just remembered that, I wouldn't have needed to spend so much time puzzling over the intricacies of DPs and CCs...

C# (Visual C# Interactive Compiler), 366 332 329 319 bytes
int i;foreach(var g in"*ЀʂЄ࢈ҲપԤ␀␀␀؀ȀȀȀ؀␀␀సؘࠀƐഘؚ྾ߟ␀␀Ā␀␀ྀ␀␀రܘࠈഌΚ྾ߟ␀␀ă␀ྃ␀ȁăÃ1`ƀ1`ÃĂȃЃЁȂĀ`ÀƀȺ؀Ȃ␀ȏЀȗɛ'Ŀஇ7;ȅ?ȅ0ȍЀ␀␀΂␀ΨՕ΀Ŕ␀ŀЀ?܀àǀƀ`̀°٠Ƙѐʈш҈EB@Ѐޟɸ")Write(Convert.ToString(g,2).PadLeft(12-i++%2,'0'));

Replace all instances of ␀ with \0 to test.
Try it online!
C# (Visual C# Interactive Compiler), 305 bytes, 210 chars
_=>"*ЀʂЄ࢈ҲપԤ␀␀␀؀ȀȀȀ؀␀␀సؘࠀƐഘؚ྾ߟ␀␀Ā␀␀ྀ␀␀రܘࠈഌΚ྾ߟ␀␀ă␀ྃ␀ȁăÃ1`ƀ1`ÃĂȃЃЁȂĀ`ÀƀȺ؀Ȃ␀ȏЀȗɛ'Ŀஇ7;ȅ?ȅ0ȍЀ␀␀΂␀ΨՕ΀Ŕ␀ŀЀ?܀àǀƀ`̀°٠Ƙѐʈш҈EB@Ѐޟɸ".Select((g,i)=>Convert.ToString(g,2).PadLeft(12-i%2,'0'))

Same with above, replace with ␀ with \0 to test. Output as IEnumerable<string>.
Try it online!(Courtesy of Jo King)

TIO link with NUL bytes

I believe the ++ in 12-i++%2 is a nop (at least, it worked for me when I removed it)

@someone They are a copy-paste from the old answer I forgot to remove

Your 319 byte version with actual NUL characters: Try it online!

 [Python 2], 345 bytes
s=''
for c in")pG/K(K*j$h%kk$ppjGE&I6S6S5[5eCv~vw0x&z$wgqcde$e=G4G?G4eG0e:vv~w*G,gn$wy$uuuuG=G)I,G.I2G(I-eG(I)e-I0G+G+G(G)I*G*vI)G-w'I2y0w'I,vI)G*G)G+G(G*I+W+I+W,G*G(G*G*G*G/I,I+I,iq.G*G1G(e/g$c%sG)m%md~$M(},K(cO)K(eO)K(I)G(aE$M(G1c$hpoI,pG3K1e3eU/M*M,I.I*S,Q(y*y'hG(ng&j$j$G+hW/g'G/G,G1k.d$e$mN":c=ord(c)-35;s+=[bin(c-35)[2:],'0'*c][c<35]
print s

I encoded the length of strings of 0s as a byte starting at chr(31). Then I encoded the remaining 10101 as binary numbers starting at chr(70) up to chr(126). Binary strings that didn't fit were split up into smaller chunks.
Edit: Reduced to 326 bytes. Thanks Jo King
Edit: Fixed a bug in the code generator program
Edit: Final Edit

You don't need to save the big string in o to a variable.

Bubblegum, 275 236 bytes
00000000: e006 8e00 e45d 0018 6988 6507 a228 f86f  .....]..i.e..(.o
00000010: f042 c62f d4d7 b99e 38bc 56c4 52e8 2630  .B./....8.V.R.&0
00000020: 8aaa 7252 d47d 5ef4 c96a 511f 6842 423f  ..rR.}^..jQ.hBB?
00000030: 4532 ca9f 22d3 1633 e0c4 665a d5dc 4e68  E2.."..3..fZ..Nh
00000040: 7b09 76ae 3c7e f9d4 fa4a 05e0 4163 c580  {.v.<~...J..Ac..
00000050: c585 a383 2396 4ca9 1f48 a4b9 744e 37c8  ....#.L..H..tN7.
00000060: 68c5 af23 645d 59a7 542a e6d1 23b9 3aba  h..#d]Y.T*..#.:.
00000070: f0e6 2738 dfd5 b0a3 c6a3 60bf c5b6 5ae6  ..'8......`...Z.
00000080: 7893 30a8 ae04 edf9 298b b777 4d56 285b  x.0.....)..wMV([
00000090: cb74 07cc 7a7b a399 3dc7 c6e7 b693 e715  .t..z{..=.......
000000a0: d908 876e 001f 7408 3c6a 5fcd 37cb 02c4  ...n..t.<j_.7...
000000b0: 93de 33c2 a11e 5bac cd12 d99a fac3 e0fa  ..3...[.........
000000c0: 5268 94f7 d640 0f73 cede f79d 821f 39d1  Rh...@.s......9.
000000d0: dc49 ff06 6962 6c31 dc29 a077 01c3 7690  .I..ibl1.).w..v.
000000e0: 85ef bbec 31d7 5c7f f9fc 8c00            ....1.\.....

Try it online!

Node.js, 333 bytes
Returns a binary string of 1,679 characters.
_=>Buffer(")SI)=.);1K?>>>2333A3,93/I3>3)g33)AEAAI)5JQZJTddda3)*3*33+3,e)*e3)//0/1+)1C/7Cgggg3395)9)A3IY)h*IH),39+)995*)AA-)59Y)*O3Z,)//*)91**)A*-)Y+1)I11+)I1)/)5)Y*0?)+)I)-0Y)1@;_*7<gaE/a)Q7[*9HM+IY16I33)a1)*^.><I+S3.38I)*hY)7)a)Y)A,9*A5Y/A:9=9K:1I-=9)19I)9*329)GH<").map(x=>s+=(x-51&&x-41).toString(2).padStart(x-51?6:12,0),s='')&&s

Try it online! (with formatted output)

JavaScript (ES8), 413 bytes
Returns a binary string of 1,679 characters.
_=>atob('AsKoAFBQEiIlwpVVUk!!ABwo!DQ!Gg!V!Aw7g!!GHGHCi!yGjHChsK+w7vDr8K!!Q!Q!!g!/DgAHDs!AGGHDhiAgCGhjwprDu8Ovwr4!ABAw4AQAcK!MKDAD8GB8OAD!QCAQQMBAYYEAMQwABwpgAMQwBwoYEBAgEEBgEQDAIwoAgIMKAwoDCgMKABgDDgDAEdcKACAgAEHwAIXTCtgTDpMO+w6HDgcK4AsKDwrIFB8OkCgwINg!!A4IAB1FVTDoArCo!U!/CgAB/w4ADwoDDoAwAYDQBYMOMBmEUFEIkSMKARR!woQgAQB!MKUAHnDtA'.split`!`.join`AA`).replace(/[\s\S]/g,c=>c.charCodeAt().toString(2).padStart(8,0))

Try it online! (with formatted output)

Perl 6, 368 bytes
.say for :36('FJXOE0PDDNF5Y5EHGB8M9SWMXQOXIKIT9F6ZKWWDEACHCBGXL1N2H60CN0CJ4EMKF7D6MODSKYJVNR4SFTDR6NSM421LQ67B6MWF0G5BQATFOJJJBQ0UFQM64T0MWSQN41C4S5D1QR5KJM2L9UTYMMKUBBQWY45YCMRGO8ZRGTQH7LXMZBUASLCTKX30IH0AYKYEPHO8HFHX8GAY5WM38YOSUX0HABYSH2PPBLRDRZIN5ANAQ3V8PLOZ6EHC0UI95EVJVYD1820T6J14HGX85NWFQET2NWOMSNUT0JW4LHMY90X094TEE9KXJXSNN6YPERFQW').base(2).substr(1).comb(23)

Try it online!
The long string is the message as a single base-36 number (with a single prefixed 1 bit to preserve the leading zeroes) which is then converted back to binary and printed 23 bits at a time.

You can use >>.say and &{S/.//} to save bytes. Have you thought about using a different base instead?

Yes, I tried using base 65536/Unicode, but the message runs into some forbidden surrogate codepoints.  I was able to avoid that by adding a fixed offset to each codepoint, but astonishingly, some of the generated strings crashed Emacs a few times.  Resolving the issues started taking more time than I could afford to commit.  I'll probably revisit the problem later.

There's no point going into multiple byte characters, since that increases your byte count. 289 bytes by implementing my tips from above  and using base 122 (to avoid carriage returns)

Wolfram Language (Mathematica), 383 bytes
StringPartition[Uncompress@"1:eJylVNsRwjAM44s92KBaBTZgAUZhZXqtHUuOWrgjfSRRHFlO4tyer/vjfb1clq0gHirZLRjby986hppcT5p+L3BmgJ3t4Ul4GsNyG++7YbaXLh0ZTPhXa4Sn+X/s9Qfk3Hx2cOaSIuNYaVu5laschvgzSqAjHeZBhilKgKBDEhw0upJRg+HOK4MyNC29sfbc3RV0VPDqeLiRTsG1ulExq1IitpunOa7asnYM9siDZ6eidUCkEzBOUbCkGIig4aTyUGBYWAX6W6aXIWGGI/HlhmsqzSU0QTZjkMVpaX5sBsm1OGKVg1qdjKP0EdyqZBRLhukn8DLBQav6kccgz8OKfgBzjj6Z",23]

Try it online!

bash + GNU tools, 351 bytes
base64 -d<<<H4sIAPnNrVwCA6WUCRLDIAwDv8T+/3NNG4wvkTBTcisGSyA8xrcxj9Ds02F+Z7yuf3hnPyz0vYEGz+FG3IKBs+x3oL2PSh0TM/PnaGamft9nPUCew3uCp5RBWdRKGz+qNJn8qRKkkNaTBgeVIFXWOdi8VCaIeUnsfHo6TXpaFa3H5olf6J5MuIHLoEi0uKcRFCvEXG4xseglKzZg7kpYJSLMA3M7wXKR+/L2WiK0kvg+TDASLp6Co1KEVIlVmFzhCktRhBBDdSZYU1xKHrmDUllcWpNR/YNW2QNcHtF0rSySb0MXk/SDUgEwG5gfLvQDxuEdDo8GAAA=|gunzip

TIO

didn't see your bash post before I posted mine - so much smaller!

MathGolf, 223 220 bytes
'06*"x·<×J× Ç×►B×ê\"@$↕!◙è0♥f░×→0×♠p└☺α?×└•×◙×P♣p¬è:×►∟××××←♦♠♣≥â☻┘A☺▄αp⌂r☻[║►×>◘×♦♦└:☻↑`×♥@@@@►►@♦↑ ☻♀◘☻♦☻☻├×å↑×╠×Ç!♠ 0♀◘↑◘☻♦◘×♠α♥â▼ÇA×└×◘` ×××▀≈}═14♦►►π0♀××°×α•×►×××☻×◘××└≈}_├↑♪↓×─0♫♥×××|××*××♪×Ç♠×└×××× ⌐¬╩↕◄○((×T☺"$à+

Try it online!
Explanation
'0                push single character "0"
  6*              repeat 6 times
    "..."         push the magic string
         $        convert to ordinal
          à       convert to binary string
           +      pop a, b : push(a+b) (add the 6 zeroes)
                  below is the footer
            L/    divide into groups of 23 characters
              n   join array with newlines into string

You can move the L/n to the footer, so it's actually 220 bytes. Can more bytes be saved by porting the 05AB1E / Java answers (using this compressed integer, convert it to base-3, and replace all 2s with 0000s)?

@KevinCruijssen nice catch! I wish I had more string replacement functions, but that's not part of MathGolf right now.

How about a map per digit, which maps 2 to ♫░╞? EDIT: Never mind. I see you don't have a Base Conversion builtin (except for binary/hexadecimal) to convert to base-3?

@KevinCruijssen I have thought a bit on how I should change the base conversion. I certainly don't need one command for converting binary string to decimal, and another for converting a binary array to decimal. That way, I can fit another base conversion command in (and the idea has always been to have general base conversion in the language).

Surely you can move the + to the footer as well

Python 3, 331 bytes
exit(''.join(bin(i)[3:]for i in b'`UP@JB`IDQKJjjd`@@@@@L@@Ah@@CP@@J`@@_@@@@@LNLLP@FPtXpu}}}|@@@@`@@`@@@A@@A~@@~@@@CCCcDA@DMCGM____@@@@HF@H@L@@PX@_`pO`A`@HA@HHF@`LLB@FHX@@s@@Xa`CC@`HD@``L@b@XAD@PDDA@PD@C@F@X@ck@A@P@BCx@DKi[@gI\x7f\\NC\\@TGY@hOrAPXDFp@@@@@\\D@@zbjipAU@@B`@Gp@@\x7fx@G@\\@X@LAh@lFXCLHhJHQHdPBJH@DHP@H@`@Dh@OOix')[1:])

Try it online!

Perl 5, 460 bytes
printf"%023b",oct"0x$_"for qw/15400 141404 4444b2 555524 0 600 1a00 1a00 2a00 3e00 0 61c618 400190 68c61a 7df7df 0 80002 0 40001 7c001f 0 618718 404010 68639a 7df7df 0 81802 1800 41801 7c181f 1800 100804 81808 61810 18860 1980 18860 61810 81008 101804 201804 200808 101010 80060 60180 11d600 101000 107c00 10ba5b 1393f 5c3837 283b 10283f 102830 106c00 0 1c1000 1d4555 1c0154 140 7c00 1ff00 701c0 c0060 1a00b0 330198 228288 224488 22880 21080 20080 9400 3cfa78/

Try it online!

Python 2, 336 bytes
print bin(int('gVQAKCgJERLKqqkgAAAAAMAABoAADQAAKgAAfAAAAAMOMMQAGQ0Yw19998AAAAgAAgAAABAAB+AA+AAADDDjEBAENDHNffffAAAAIGAIAMAAQYAfgwPgBgAIBAIIGAgMMCAGIYAAzAAYhgDDAgIEAggMAiAYBEAQEEBAQEADAGAYAjrABAQACD4AELpbAnJ/cODcAUHZAoPyBQYEGwAAAAAcEAA6iqpwBVAACgAHwAA/4AHAcAYAMBoAsGYDMIoKIRIkQCKIAEIQAIAgAEoAPPp4'.decode('base64').encode('hex'),16))[3:]

Try it online!
Prints a string of bytes

Zsh (+coreutils), 320 577 bytes
It runs on my Mac, but try it online doesn't work because TIO doesn't have basenc :( It's a one-line program, I've added newlines here for readability. Data compressed to z85 encoding (similar to Ascii85).
basenc -d --z85<<<'0&M8}p.B@#L#QZE00001Fb*2U02+?qq#={[000069asT6g8.)4ZwEwH00
0Mg1onA4aoh}/0Q{6?7?7Abap8T<N!#M/0000:ZZ{J%0d$no1{.{L01Yzs5hjUju{Cb/00eC!f:[
8q1oX#k5eUKnfBigKaB[#)FcD1?fA=JG2NyzwD&LsiWGLW<&LA29Gr+T=<o=q3huiZS05#83BRN)
l3zmwk01TOWF4#ep&0YP[gY.1d24nhWll]9LmgYDLaoqEc0f^Fe]ZR$Y'|basenc --base2msbf
 -w0|cut -c-1679

Encoding steps
. Convert Arecibo message to a digestible format → bitstr.8
. Convert bitstr.8 into binary, using script demo16.sh** → bits.16.again
. Convert binary to z85 → basenc --z85 bits.16.again >bits.85
. Use the z85-encoded string in bits.85 for a much shorter code golf!
Decoding steps -- i.e. what the main script does
. basenc -d --z85<<< decodes the z85 string to binary
. |basenc --base2msbf -w0 decodes binary to Ascii 1s and 0s
. |cut -c-1679 trims extra data

Original 577-byte solution
try it online!!
S=fxxxxibxxdxxfyzzzyx1yxxxxxxxxyyywl2ij1xxhj1xxhixxxhi5iw2d3c2d2cxl2bxc2az2c2d2ax4x4x4x5wcxpxwdxp15m5w2d2d3c2cxfxhxc1xxc2c2y1xx4x4x4x5wc1f2ixj2kd1e2j15e2f5j2kb1h1hyc1f2gzd2d2fzaf2c1d2ej2b2gf2c1d2ed2d2f1dc1f1hzb1g2hya1h2hya1i1gzb1g1g1dc1l2ed2h2gbz2xx2ibzd1lbzb5jb1dx2xyx1x2fy2yy6x3d3e2a3ixxd2x2b1fxxd6b1fxxd2db1e2a2jwb3e1lb2xxzxxxxx1b3ixxxynxxeh5jf9hd3g3fc2k2eb2a1ix2da2b2g2b2cazxxdxzzazyzyzzezxz1ge1d1d1ge1i1ggyxxia3y4xy3z
for X in ${(s::)S};{case $X in
[a-w])V=$[##$X-96];printf 0%.s {1..$V};;[1-9])V=$[##$X-48];printf 1%.s {1..$V};;[x-z])V=$[##$X-119];printf $[10**$V];;esac}

Used custom encoding logic. The string S is 421 characters, could possibly be compressed a bit more. Letters a-w represent repeated 0s. Numbers 1-9 represent repeated 1s. Letters x y z represent 10 100 1000 respectively.
Maybe I should have tried byte-pair encoding or Ascii85 --> Done. ✅

Bash, 702 697 bytes
xxd -r -p<<X|xz -dc
fd377a585a000004e6d6b4460200210116000000742fe5a3e006d7010c5d
0018698865079cf6752c9e9a501a87a798b4844f9fcfdaaf87733b9d8239
48c816d860a938767f6cb81299f3e8a638effe3068c0e096a8949c81d706
7dff3ec44e5df185b3a48e5b5857724386e8c37cfbd5c856b12614ee78ec
c41df4db3aea71fd3a8fa474905609f78eb3fd66e246557965e4ab6dfd67
efbd9202f542ded9cf98a6401ee2d23afb2f544bd2442c6f428fd612397c
f2c6ec50847ddccc5832185e487712e5a7676b97058d7e485d5a3536166a
44ab3c689c93073cdda73b5306a83c4cd268e79db238bfa2d08ac912a578
75020bc7828342d5a62ce367aff7fd89290336128d119fa4272da2b2a79f
5973c71935af054f2d91c1bd3ea4847a3502d6dc8c975114dacf8a4de600
622d80986dbb0cd00001a802d80d00001b16e2a7b1c467fb020000000004
595a
X

Try it online!

Ruby, 362 bytes
puts"5r0afnfm8wyke8tfy1pwt7xnuaxyh3wodfp7bhsdufyw0xbdp1pumrz2xir652tuc0ss9oec8yad9vefivd66j126wybhefgk2lv38uqqiur11u26q275jk3h2ucithd59awpaenqpqi1pszh52179zw0ddqtbrvo6kyrrgv8c34pqrp83j8estjp63v29t4hqp9yg2hhzjlq1e9zqx6gh20n9lsttimz3nbq060ritrphxaru7quwmv3oujhd9xjddpbacq4bnpf270znhgto59yn0980itylf95pxw9x7rvkvi7mfql1sx46puo8rg4dq0".to_i(36).to_s(2).rjust(1679,?0)

Integer written in base 36. There's surely a more efficient way to compress the integer, e.g. with zlib or base64.
Try it online!

350 bytes if you: (1) use "%b" for formatting instead of to_s, (2) prepend ?0*6 instead of calling rjust

[C++ (VC++)(but tested with gcc as well)], 585 bytes
#define l(x,y)for(int x=0;x<y;x++)
void f(){const char*a="02A800505012Y595Y240U180YD0Y1A0Y540YF80V61C618800321A3186BEFBEF80X10Y40W20YFC001F0X1861C620200868639AFBEFBE0W40C0100180Z83003F0607C00C001008041030101860400C430Z19800310C018604040804101804403008802020808080800600C030047580080800107C002174B604E4FEE1C1B80283B20507E40A0C08360U3820Z751554E00AA0Z140ZF80Z7FC00380E00C0060340160CC06611414422448804510Z8420010040Z940079F4F0";int x=1679;l(i,365){int d=a[i],c=0;d-=(d>47&d<58)?48:((d>64&d<71)?55:0);if(d>70&d<91)c=91-d,d=a[i-1];for(c;c>=0;c--)l(j,4){if(x--)cout<<(int)((d&(8>>j))>0);}}}

Try it online!
ungolfed Version (lacks the break after the 1679th element though and goes until the 1680th):
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
    const char arecibo[]="02A800505012Y595Y240U180YD0Y1A0Y540YF80V61C618800321A3186BEFBEF80X10Y40W20YFC001F0X1861C620200868639AFBEFBE0W40C0100180Z83003F0607C00C001008041030101860400C430Z19800310C018604040804101804403008802020808080800600C030047580080800107C002174B604E4FEE1C1B80283B20507E40A0C08360U3820Z751554E00AA0Z140ZF80Z7FC00380E00C0060340160CC06611414422448804510Z8420010040Z940079F4F0";
    int i = 0,j;
    while (i<sizeof(arecibo)-1)
    {
        char digit = arecibo[i];
        int count=0;
        if (digit >= '0' & digit <= '9')
        {
            digit -= '0';
        }
        else if (digit>='A'& digit<='F')
        {
            digit -=  'A'-10;
        }
        else if (digit > 'F'&digit<='Z')
        {
            //digit does not contain any valid hex digit in this case
            count = 'Z' - digit+1; //digit = Z means repeat 2 more times...
            digit = arecibo[i - 1];
        }
        for (count; count >= 0; count--)
        {
            for (j = 0; j<4; j++)
            {
                cout << (int)(((digit)&(8 >> j))>0);
            }
        }
        i++;
    }
    return 0;
}

as an Explanation: i concatenated the 73 lines of sample output given to one long line.
i encoded them in hexadecimal where the bit order is msbfirst (using this program https://github.com/Marc-Bender/longBinaryStreamToHex/releases/download/addedErrorCode-4/longBinaryStreamToHex.exe)
i shortened the Output of that by about 70 hexadecimal Digits by using the letters 'G'-'Z' as a sign to repeat the last Digit for a certain amount of times (Z = 2more times, Y = 3more times …)
the rest should be relatively self explainatory for Code-Golfers. abusing the preprocessor to shorten loops, abusing the , Operator and the like.
Output Format is uninterrupted stream of 1679 0/1-values.

before anybody asks the const is for compatibility with VC++ (what the main development work was done with)

@ceilingcat i think you can even short that more by pitting your include in the header section...

554 bytes

Perl 6, 348 bytes
{"000000"~:36<5r0afnfm8wyke8tfy1pwt7xnuaxyh3wodfp7bhsdufyw0xbdp1pumrz2xir652tuc0ss9oec8yad9vefivd66j126wybhefgk2lv38uqqiur11u26q275jk3h2ucithd59awpaenqpqi1pszh52179zw0ddqtbrvo6kyrrgv8c34pqrp83j8estjp63v29t4hqp9yg2hhzjlq1e9zqx6gh20n9lsttimz3nbq060ritrphxaru7quwmv3oujhd9xjddpbacq4bnpf270znhgto59yn0980itylf95pxw9x7rvkvi7mfql1sx46puo8rg4dq0>.base(2)}

Based on Benjamin Urquhart's Java solution.
Uses a straight stream of 0 and 1 characters. The link below has some code to prettify the output.
Try it online!

C++ (with Gnu multi-precision library), 359 bytes
This outputs the string as one line. It uses '1' for 0, and '0' for 1 :/
It simply reads the embedded string as base 62, and prints it as base 2.
Use g++ -g arecibo.cpp -lgmp -lgmpxx to compile and link
#include<gmpxx.h>
main(){mpz_out_str(stdout,2,class_mpz("vuXXKBYAu1hPsJPbFSf49akyFd0bjJbMIV3upYndU8kYFPsXcpRUK6c9qnzLfORxkxGL7ZfoSwgSxFbCrydjHL603QcxexopAzoYAcAyEiENJJU2vQA2zM8NDbeY6nHgL8rfFoPJaclwxx6TeKeOEknEQHzp7C4la3o8xijBQLOVweFZ1CI9dXy2VQhgnuwF5FeW5mQ909pRMxhn6G3RJ1QEtkS7oGMZYHM03fh4fj391IoYLGVv3iUVuTrV2ghz9CUa9hfGYrdhGoVE2w1inYalYl",62).get_mpz_t());}

I couldn't get this to work until I replaced class_mpz with mpz_class

Perl 6, 276 bytes
:122[q{3tD!gLF['u#.K>'uCG8cvJZ[on1Z<D!	`Fhqq-_V'"qQn+n0h\:b,vXjo&1TMFaW;wvX;eUS
(ueelNSu,y93\kjGI&?UU/38 :ndi4Y5cyC+ME\g7LWaS;QLjtD^L+aVd(XW%gy\8'Eqk-+f72S5J?(r5!m^5px T[Z'3&jd0lZ'/x%#(}.ords].base(2)~~S/.//.say

Try it online!
Outputs as a series of 1679 0s and 1s. You can have it on different lines by adding .comb(23)>> before the say.
Explanation:
:122["...".ords]                     # Convert the string from base 122
                .base(2)             # To base 2
                        ~~S/.//      # Remove the leading 1
                               .say  # And print

I can probably save bytes by using the output as a 1679 bit integer instead, or reversing the bit representation.

Tcl, 366 bytes
binary scan [binary decode base64 QBUACgpIRKSpqkoCAAAAgAEAsAAAWAAAKgAAHwAAAGA4hhEATFiMYX3f9wEAAAgAIAAAAAQA8AOADwAAGIZjBAQQFsZZ3/d9AAAAAgMIgAEAwQD8YOADMAAIECAIDAgYBgIwwgCAGQCMMIBhICAQIAgYIAIMEAEEBAEBAQFgAAMMIK4BEBAACD4AhC5tICd/h4MdQMFNoOAnUDAQbAAAAAAcBACuqCoHUAUAKADwAQD+A8ABBzAABiyABjNghigoQiQSAaIIACEEgAACACkAni8P] b* z
puts [join [regexp -all -inline .{23} $z] \n]

Try it online!

C++ (gcc), 748 bytes
#define l(X,Y)if(z[i]==#X[0])z.replace(i,1,#Y);
void f(){std::string z = {"ab1eeedala1ebeeheal1mmma1fa1g1eeeeeeea1a1alddhgdbcdgdacedgdacedgdeeedgdndgddhgqiafbcag1dbfa1blceafafbcegcinnnlddhgmddegddhgb1ddelcidbnlddhgqqiafag1hedeblcebcaf1acegcinnnlddhgmhcdegdacdagb1bfda1lcibfhcildacdaga1d1d1almhcheagbqch1blhcmbqgdacachghcmbqgbqch1blmh1d1aga1hfd1aledcd1aledeheaga1heheblmdbqgbcdchga1af1efdga1hedbla1bndala1b1f1ea1fflh1aia1acccl1f1bibff1ldeebf1fla1h1ebfccla1h1ebfbla1bffdalddhgaibedblaieemeeeeelaideeeealdh1ehldcidalhcccidlbihf1hlafdafbgacedefblfachfacagemebeemagema1ma1magbememhgbeb1b1hgbedehghea1edalfcacieacca0"};for(int i=0;i<1751;i++){l(q,cb)l(n,fi)l(m,ae)l(i,c1)l(h,ba)l(g,0l)l(f,0c)l(e,01)l(d,bb)l(c,11)l(b,aa)l(a,00)l(l,\n)printf("%c",z[i]);}}

Try it online!
By replacing the most used substring with a new character until it's not worth it anymore

735 bytes


text:
Roll the carpet
This question is inspired by Kevin Cruijssen's question.
Now that the carpet is laid out, we want to roll it. Your task is to write a program that takes a string and returns a spiral made from this string (representing a rolled carpet viewed from the side).
The procedure for one step of rolling the carpet is the following. There is an example to illustrate what I mean. Notice that the example starts with a partially rolled carpet for better understanding:
ac
rpet

separate the "head" from the "tail" of the carpet: the head is what has been rolled so far, the tail is what remains to be rolled.

Head: ac   Tail:
      rp          et

Rotate the head 90°, clockwise.

Rotated head: ra   Tail (unchanged):
              pc                       et

if the width of the new head (here 2) is less or equal than the length of the tail (here 2)

then, put it on top of the tail
else, the carpet (as it was at the begining of the step) was rolled

New carpet: ra
            pc
            et

Repeat the procedure as many times as needed.

Two examples showing all steps of the carpet rolling:
carpet

 c
 arpet

  ac
  rpet

    ra
    pc
    et

0123456789

 0
 123456789

  10
  23456789

    21
    30
    456789

      432
      501
      6789

Some precisions:

You don't need to show all intermediate steps, only the rolled carpet (e.g. if you find a non-iterative way to compute the result, it's perfect). Also, you don't need to print any leading whitespace, in the examples above, I only show them to align stuff.
Input is a String, a list/array of char
Output is printed to stdout or to a file.
Input is nice: the length is at least 1 char, and at most a constant sufficiently small so that it doesn't cause problems, but you can't use that constant in your program; the content of the string is only nice characters ([a-zA-Z0-9]), encoding at your preference.
This is code-golf, so shortest answer in bytes wins. Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
Default Loopholes are forbidden.
If possible, please add a link with a test for your code.
Also, add an explanation for your answer if you think it is needed.

Closely related

Also this one: https://codegolf.stackexchange.com/questions/125966/wind-me-a-number-snake, but none include the termination check.

Suggested test case: ProgrammingPuzzlesAndCodeGolf - the final tail length greater than 1 tripped me up.

Where is the head on the second carpet example, where nothing is rolled up?

@EmbodimentofIgnorance During the first step (carpet still flat), the first head is just the first letter of the string (and if you have a one letter string, it is triviallly rolled up).

I think you've swapped the words "head" and "tail" here: "if the width of the new head [...] is greater or equal than the length of the tail [...]".

@EriktheOutgolfer I messed up greater and less. Of course, we should continue to roll if the new head is smaller than the tail. Thanks.

Is output not allowed as function output?

@ASCII-only I'd prefer output to be printed. However, if your language is not capable of printing, returning is fine. I know the default I/O methods ( https://codegolf.meta.stackexchange.com/questions/2447/default-for-code-golf-input-output-methods/ ) informally say that returning is fine, but I prefer when printed. If returning instead of printing shows a great improvment or a nice trick, post an answer (and explicit that you are returning, not printing) :-)

Downvoted because of overly restrictive input/output rules; I deleted my Python 2 answer since one cannot use print inside a lambda.

Related: https://oeis.org/A002620

Charcoal, 15 bytes
ＦＳ«Ｆ¬℅§ＫＶ⁰⟲⁶→Ｐι

Try it online! Link is to verbose version of code. Explanation:
ＦＳ«

Loop over the carpet.
Ｆ¬℅§ＫＶ⁰

Check whether there's anything above the cursor.
⟲⁶

If not then roll the carpet.
→Ｐι

Move right and output the current character.
Example: For the input 0123456789, the following actions occur:
0

0 is printed.
01

The cursor moves right and 1 is printed.
0
1

Since there is nothing above the 1, the canvas is rotated.
0
12

The cursor moves right and the 2 is printed.
10
2

Since there is nothing above the 2, the canvas is rotated.
10
23

The cursor moves right and the 3 is printed.
10
234

The cursor moves right and the 4 is printed.
21
30
4

Since there is nothing above the 4, the canvas is rotated.
21
30
45

The cursor moves right and the 5 is printed.
21
30
456

The cursor moves right and the 6 is printed.
432
501
6

Since there is nothing above the 6, the canvas is rotated.
432
501
67

The cursor moves right and the 7 is printed.
432
501
678

The cursor moves right and the 8 is printed.
432
501
6789

The cursor moves right and the 9 is printed.

That's awesome.  So basically Charcoal has a builtin "roll" operator in ⟲?

@Jonah Well, it won't roll for me as it goes, but by outputting the string character-by-character I can roll as I go, yes.

Pyth, 37 bytes
.U+j;bZ.WgleHJlhH,+_MChZ<eZJ>eZJ,]hQt

Try it online here, or verify all the test cases at once here.
.U+j;bZ.WgleHJlhH,+_MChZ<eZJ>eZJ,]hQtQ   Implicit: Q=eval(input())
                                         Trailing Q inferred
                                 ]hQ     First character of Q, wrapped in an array
                                    tQ   All but the first character of Q
                                ,        2-element array of the two previous results
                                           This yields array with rolled carpet (as array of strings) followed by the tail
       .W                                While condition function is truthy, execute inner function, with initial value of the above:
         gleHJlhH                          Condition function, input H
             JlhH                            Number of layers in the current rolled carpet, store in J
          leH                                Lenth of the tail
         g   J                               Is the above greater than or equal to J?
                 ,+_MChZ<eZJ>eZJ           Inner function, input Z
                   _MChZ                     Rotate the current rolled carpet (transpose, then reverse each row)
                  +     <eZJ                 Append the first J characters of the tail as a new row
                 ,                           Pair the above with...
                            >eZJ             ... all but the first J characters of the tail - this is the new tail
.U+j;bZ                                  Join the carpet roll on newlines and append the tail, implicit print

Husk, 24 bytes
►S=ÖLmFȯ:T↔ø§z:oΘḣĠ+CṘ2N

Try it online!
Explanation
Implicit input, say s="carpets"

CṘ2N  Break s into chunks:
   N   Natural numbers: [1,2,3,4,..
 Ṙ2    Repeat each twice: [1,1,2,2,3,3,4,4,..
C      Break s into chunks of these lengths: ["c","a","rp","et","s"]
       The last chunk is shorter if we run out of characters.

§z:oΘḣĠ+  Attempt to merge suffix of chunks:
      Ġ    Cumulative reduce chunk list from right
       +   by concatenation: ["carpets","arpets","rpets","ets","s"]
   oΘḣ     Prefixes of chunk list (empty and nonempty): [[],["c"],..,["c","a","rp","et","s"]]
§z         Zip these by
  :        appending: [["carpets"],["c","arpets"],..,["c","a","rp","et","s"]]
           These are all versions of the chunk list where some suffix has been merged.

mFȯ:T↔ø  Roll each list:
m         Map
 F        reduce from left
      ø   starting from empty character matrix
  ȯ:T↔    by this function:
    T↔     Reverse and transpose (rotating by 90 degrees)
  ȯ:       then append next chunk as new row.
         Result: [["carpets"],["c","arpets"],..,["epr","tca","s"]]

►S=ÖL  Select the matrix rolled by the correct amount:
►       Find element that maximizes
 S=     being equal to
   ÖL   sort by length.
        This selects a matrix whose rows have non-decreasing lengths.
        Ties are broken by choosing the rightmost one.
       Result: ["ra","pc","ets"]

Implicitly print each row separated by newlines.

J, 69 bytes
-3 bytes thanks to FrownyFrog
[:(}:@[,{:@[,])&>/[:((|:@|.@[,#@[$]);#@[}.])&>/^:(<:&#&>/)^:_,.@{.;}.

Try it online!
explanation
[: (}:@[ , {:@[ , ])&>/ [: ((|:@|.@[ , #@[ {. ]) ; #@[ }. ])&>/^:(<:&#&>/)^:_ }. ;~ 1 1 $ {.

The algorithm is straightforward despite being a bit verbose for J.
Overall Strategy: Reduce the input to a square table, with a (possibly empty)
leftover piece.
As we reduce, we'll use a 2 element list of boxes.  Our "result so far" will be
the first box, and "items remaining to be processed" will be the 2nd box.  The
first box will be initialized to the head of the input (but converted to a table):
1 1 $ {.

and "items remaining to be processed" will be the input's tail:
}. ;~

Now we have:
┌─┬─────┐
│c│arpet│
└─┴─────┘

where the 'c' is actually a 1x1 table.
We reduce that down using a J Do... While loop:
^:(...)^:_

Where the part in parenthesis is the "keep going" condition:
<:&#&>/

which says "keep going while the length of the right box is greater than or
equal to the length of the left box (ie, the side length of the square matrix)
What does "keep going" mean?  That's defined in the verb to the left of the
first ^:, which tells us how to take the current result and produce the
next iteration.  That verb is:
((|:@|.@[ , #@[ {. ]) ; #@[ }. ])&>/

Let's break it down:
((|:@|.@[ , #@[ {. ]) ; #@[ }. ])&>/
(  verb in parens               )&>/ NB. put the verb in parens
                                     NB. between the two items
                                     NB. of our list, and unbox
                                     NB. them into left / right
                                     NB. args ([ / ]) for the verb
 (|:@|.@[ , #@[ {. ]) ; #@[ }. ]     NB. breaking down verb in
                                     NB. parens...
                      ; ....         NB. new "remaining items":
                            }. ]     NB. remove from remaining
                        #@[          NB. the size of a side of
                                     NB. the result matrix
                ....  ;              NB. new "result":
  |:@|.@[                            NB. rotate existing result
          ,                          NB. and put it on top of
            #@[ {. ]                 NB. the items we removed
                                     NB. from remaining items

That is, this is just algorithm described in the OP translated literally into J.
Finally we deal with the (possibly 0) leftover items, the tail of our carpet roll:
(}:@[ , {:@[ , ])&>/

This says "take all but the last elm of the result":
}:@[

and append it to , the last items of the result {:@[ with the remaining
items appended to that last item , ]

Ah, J... letters are for noobs

,. can do what 1 1$] does and $ can be used as {..

@FrownyFrog ty.  I got it to 70 bytes with your first suggestion but wasn't sure if I understood $ can be used as {. -- can you clarify?

The last line of the explanation, you use {. to truncate, that one can be a $ as far as I understand.

Also you can replace the right [: with a @

R, 146 132 bytes
function(s){m=F[F]
while({m=rbind(t(m)[,F:0],s[1:F])
s=s[-1:-F]
length(s)>sum(F<-dim(m))})0
write(m[F:1,],1,F[1],,"")
cat(s,sep="")}

Try it online!
Implements the carpet-rolling procedure. Takes input as a list of characters and prints to stdout.
Saved 14 bytes by finding a way to use a do-while loop and initializing using F.
function(s){
m=F[F]					# logical(0); create an empty array (this gets automatically promoted to character(0) later
while(					# do-while loop
      {m=rbind(t(m)[,F:0],s[1:F])	# rotate m counterclockwise and add the first F characters of s to the bottom
       s=s[-1:-F]			# remove those characters
       length(s)>sum(F<-dim(m))})0	# while the number of characters remaining is greater than the sum of m's dimensions
write(m[F:1,],1,F[1],,"")		# write the rolled portion write writes down the columns, we reverse each column
cat(s,sep="")				# and write the remaining characters
}

Jelly, 30 bytes
Seems overly long...
ḢW,ðZU;Ls@¥©ḢWɗ,®Ẏ¤ð/ẈṢƑ$¿ḢY;Ɗ

Try it online!
How?
ḢW,ðZU;Ls@¥©ḢWɗ,®Ẏ¤ð/ẈṢƑ$¿ḢY;Ɗ - Main Link: list of characters
Ḣ                              - pop and yield head
 W                             - wrap in a list
  ,                            - pair with (the remaining list after Ḣ)
                         ¿     - while...
                        $      - ...condition: last two links as a monad:
                     Ẉ         -   length of each
                       Ƒ       -   is invariant under:
                      Ṣ        -     sort
                    /          - ...do: reduce by:
   ð               ð           -   the enclosed dyadic chain -- i.e. f(head, tail):
    Z                          -     transpose
     U                         -     reverse each (giving a rotated head)
              ɗ                -     last three links as a dyad:
          ¥                    -       last two links as a dyad:
       L                       -         length (i.e. number of rows in current roll)
         @                     -         with swapped arguments:
        s                      -           split (the tail) into chunks of that length
           ©                   -       (copy to register for later)
            Ḣ                  -       pop and yield head (Note register "copy" is altered too)
             W                 -       wrap in a list
      ;                        -     concatenate (the rotated head with the first chunk of the tail)
                  ¤            -     nilad followed by link(s) as a nilad:
                ®              -       recall from register (other chunks of tail, or an empty list)
                 Ẏ             -       tighten (the chunks to a flat list)
               ,               -     pair (the concatenate result with the tightened chunks)
                             Ɗ - last three links as a monad:
                          Ḣ    -   pop and yield head
                           Y   -   join with newline characters
                            ;  -   concatenate (the remaining tail)
                               - when running as a full program implicitly prints

05AB1E, 41 bytes
g©L¦€DD2šηO®>‹Ï©IŽ8OS®g4α._.ΛðÜI®O®g->.$«

Way too long, but I wanted to use the Canvas.. Which was probably a bad choice now that I've finished it and it turned out to be this long..
Try it online. (No test suite, because there seems to be a weird issue with the .Λ builtin..)
Explanation:
Let me start by giving a general explanation of the Canvas and what I wanted my code to accomplish. More detailed information can be found in this relevant 05AB1E tip of mine, but for this challenge I wanted to have do the following:
The Canvas builtin takes three parameters:

\$a\$: The size(s) of the line(s). For this challenge, this would be a list [2,2,3,3,4,4,5,5,...].
\$b\$: The character(s) we want to display. For this challenge, this would simply be the input-string.
\$c\$: The direction in which we want to draw these character-lines. For this challenge this would be the directions \$[2,0,6,4]\$ (\$[→,↑,←,↓]\$) rotated \$n\$ amount of times depending on the input-string to have a different starting direction (i.e. input carpet is \$[0,6,4,2]\$ instead and input 0123456789ABCDEFGHI is \$[6,4,2,0]\$ instead).

As for the code:
g                # Get the length of the (implicit) input-string
 ©               # Store it in the register (without popping)
  L              # Create a list in the range [1,length]
   ¦             # Remove the first item to make the range [2,length]
    €D           # Duplicate each to get the list [2,2,3,3,4,4,5,5,...]
      D2š        # Create a copy and prepend a 2: [2,2,2,3,3,4,4,5,5,...]
         η       # Get the prefixes: [[2],[2,2],[2,2,2],[2,2,2,3],...]
          O      # Sum each prefix: [2,4,6,9,12,16,20,...]
           ®     # Push the length from the register again
            >‹   # Check for each summed prefix if it's <= length
              Ï  # And only leave the truthy values
               © # And store this in the register (without popping)
                 # (This is our `a` for the Canvas builtin)
I                # Push the input-string
                 # (This is our `b` for the Canvas builtin)
Ž8O              # Push compressed integer 2064
   S             # Converted to a list of digits: [2,0,6,4]
    ®g           # Push the list from the register, and get its length
      4α         # Get the absolute difference with 4
        ._       # And rotate the [2,0,6,4] that many times towards the left
                 # (This is our `c` for the Canvas builtin)
.Λ               # Now use the Canvas builtin, without printing it yet
  ðÜ             # Remove any trailing spaces (since the Canvas implicitly makes a rectangle)
     ®O          # Push the sum of the list from the register
       ®g-       # Subtract the length of the list from the register
          >      # And add 1
    I      .$    # Remove that many leading characters from the input-string
             «   # And append it at the end of the roll created by the Canvas
                 # (after which the result is output implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž8O is 2064.

MATLAB / Octave, 154 bytes
Not the shortest one, but to golf in MATLAB/Octave is always fun :)
function h=r(t,h);n=fliplr(h');s=size(n,2);q=numel(t);if s<=q h=r(t(max(s,1)+1:end),[n; t(1:max(s,1))]);elseif q>0 h(:,end+q)=' ';h(end,end-q+1:end)=t;end

Try it online!

sadly, op says you have to print

@ASCII-only as explained here (https://it.mathworks.com/matlabcentral/answers/95761-what-do-the-terms-stdin-stdout-and-stderr-mean-with-respect-to-file-i-o-in-matlab-as-used-in-the-ma), stdout in Matlab world refers to the command window. Given that the result of the evaluation of every command is automatically printed to the command window, I think that this answer could be considered consistent with the requirements of the question.

might wanna make that clearer then

@ASCII-only I do not get what do you mean, really. It is a function, you call it, the result will be automatically printed on the command window (i.e. stdout). What's wrong with this? Even the R answer works like this...

Right now you disp it, I'd say you should remove the disp to let people that don't know R that it does write to STDOUT by default

@ASCII-only my bad, you're right: it was an error. I've corrected it now; good catch, thanks :)

Python 3, 112 bytes
r=lambda t,h=[[]]:len(h)>len(t)and h[:-1]+[h[-1]+list(t)]or r(t[len(h):],list(zip(*h[::-1]))+[list(t)[:len(h)]])

In this case, the output is the value of the function.
Try it online!
If you prefer, here another (longer, 129 bytes) solution that prints directly the rolled input:
r=lambda t,h=['']:len(h)>len(t)and set(map(print,h[:-1]+[h[-1]+t]))or r(t[len(h):],list(map(''.join,zip(*h[::-1])))+[t[:len(h)]])

Try it online!

need to print it

@ASCII-only: Quoting the author of the question: "If returning instead of printing shows a great improvment or a nice trick, post an answer (and explicit that you are returning, not printing)". So I think it's okay.

source: Stack Exchange

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

sort: votes


text:
Solve Subset-Sum in polynomial time (...if P = NP)
Shocking news: Dr. Mad J Scientist has released a proof of P = NP to the world. But the proof is nonconstructive, and she's keeping the algorithm to herself.
Worry not. Without even looking at her proof, we can still (almost) write a computer program that solves NP-complete problems in polynomial time.
The Problem
Input a list of integers, such as [-10, -4, 1, 1, 2, 6, 8]. Output a nonempty sublist that sums to 0, such as [-10, 1, 1, 2, 6]. The output list can be in any order. Ignore any integer overflow issues in your language.
If P = NP, your program must provably run in polynomial time on solvable inputs. Your program may act arbitrarily on inputs with no solution. This is code-golf; shortest code wins.
Yes, this challenge is possible. One approach is as follows:

Enumerate all possible computer programs \$P_0, P_1, P_2, \dots\$
  Repeat as \$i\$ goes from 0 to \$\infty\$:
  ----- Run the first \$i\$ programs on the input list, for \$i\$ steps each.
  ----- For each output you get, check whether it's a valid subset sum solution. If so, return it.

This works because, if P = NP, then some program \$P_m\$ solves subset-sum in some polynomial time \$O(n^k)\$. Therefore, the above algorithm will output a solution on the \$\max(m, O(n^k))\$th iteration of the loop, if not before. Therefore, the above algorithm runs in polynomial time on solvable inputs.
Note: A proof that P ≠ NP would allow a 0-byte solution to this problem. Good luck with that :)
Notes
Before you start evaling all strings in a language like Python, let me point out that some of those strings will reformat your hard drive.
This challenge does not run afoul of the no famous open questions rule, because although it is related to P vs NP, this challenge is solvable.

@EmbodimentofIgnorance Why do you think this a duplicate?  There is a restriction here that makes pretty much none of the answers on the other question valid here.

If someone claims she has an algorithm (i.e. constructive proof) and publishes a non-constructive proof instead, no one will believe her

@Lopsy Only if 5 people vote for it to be reopened. I don't think this is a duplicate, but I don't think it's a particularly well-formed prompt. There are glaring issues with it that I think required more time in the Sandbox.

I hammered this open. This isn't at all a dupe of the general subset sum challenge since the complexity restriction means none of the answers on the other question come even close to working, nor can they possibly unless P=NP. Answers to this will be very very different.

Python 3.8 (on Unix), 429 bytes
Since nobody else has posted an answer yet, I thought I'd have a go, though I not 100% certain I haven't missed something important (and I am 100% certain the code could be shrunk down significantly).
As noted in the question, evaluating arbitrary Python strings is dangerous. Fortunately, it's easy to come up with a safe subset of strings whose evaluation is still Turing complete, by embedding the Turing complete While Programming Language, summarised below:

This can be embedded into Python using only strings that match the following regex:
^([0-9 \n():_=+-]|while)+$

To reduce the number of necessary characters, we use a few embedding hacks:

variable names are built only of underscores
if B then C1 else C2 is emulated using while loops (and temporary variables x and y, which hang around afterwards but that's ok):

x=B;y=not x
while x:C1;x=False
while y:C2;y=False

skip is emulated using any constant expression, e.g. 0
true is emulated using e.g. 0==0
false is emulated using e.g. 0==1
B & C is emulated using a pre-evaluated if-then-else (and another temporary variable x):

if B then x=C else x=False

¬ B is emulated using 1-B

To make our life easier, we also allow [ and ], as this permits direct operations on lists (including slicing and concatenation) which avoids having to translate the problem from one on lists into one on integers.
Update: as noted by @ØrjanJohansen, it's also necessary to include < to ensure basic arithmetic remains polynomial.
I claim that any program with just those characters will either execute, or (far more likely) fail to execute, or raise an exception, but will not crash the interpreter or change any global state. Please correct me if I'm wrong.
The rest of the solution is now similar to the prototype presented in the question. We generate all strings of increasing lengths n and execute them, prepopulating the input in variable _ and checking and validating any output from the same variable. We catch any raised exceptions and continue.
The main tricky bit is ensuring polynomial complexity (and termination). We do this by breaking out of each execution after n seconds, using Unix signals and a handler that raises an exception (which the string executions themselves have no way of catching). Since every program will appear repeatedly (eg with trailing whitespace), we don't need to worry about breaking out too soon from a correct program. One tricky bit here is to make sure that the program doesn't crash if the signal is received after the execution completed (successfully or not) but before the signal has been reset; this explains the nested try-catch.
from itertools import*
from re import*
from signal import*
I=eval(input())
signal(SIGALRM,0)
for n in count():
 for p in product(*[set(map(chr,range(128)))]*n):
  if match("([0-9 \n()[\]:_=<+-]|while)+$",(s:="".join(p))):
   try:
    try:
     g={'_':I[::]};alarm(n);exec(s,g);h=g['_']
     if h and all(h.count(x)<=I.count(x)for x in h)and sum(h)==0:
      print(h);n=-1;break
    except:0
    alarm(0)
   except:0
 if n<0:break

Try it online! (though don't expect an actual result; it may be P but it's obscenely slow)

This looks like a great effort.  Now..... is it correct? :)

@Anush The three things to be convinced of are (1) it doesn't crash (2) it eventually finds a polynomial time program (3) it does so in polynomial time. I'm pretty sure 2 is right since While is Turing complete; I'm fairly sure 1 is right, since I can't see how to do anything bad without . or alphabetic characters (apart from while); and I'm mostly sure 3 is right, as I can't imagine anything I've used in the program being non-polynomial. Still, for a formal proof you'd need to prove the CPython implementation of the parser and various built ins!

I think While alone is not enough. The problem is that the language has so primitive arithmetic that although it is Turing-complete, it requires exponential time to do stuff, e.g. testing A < B requires something like brute force incrementing until you find the smallest number. However, I think your Python fragment works, because you also have efficient mutable lists.

You may have to change the input encoding, though. I don't see a way for the fragment to decode large input numbers in polynomial time. (Then again, I'm not a Python expert.)

Actually, I think adding < to the fragment might fix that, assuming that doesn't make it unsafe. (I think that's also generally enough to make While not exponentially-blowing-up.)

@ØrjanJohansen Good points I hadn't thought of. I'll add <, which doesn't make it unsafe as far as I can see. Presumably this also makes multiplication polynomial, via repeated doubling?

Yeah I think everything is polynomial that should be. My reasoning is a bit quirky: using < and repeated doubling you can search for the largest bit in a number, or a difference of numbers. Repeat until you have all the bits. And repeated doubling allows you to turn a list of bits back into a number.

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


text:
To string or not to string
Given an input string, output at random the unique combinations with repetition of the characters in the input string, from length 1 up to the length of the input string, with an equal chance of each one occurring.
Example: given the input abcd (or any combination thereof of the four characters a,b,c,d) , there is an equal chance of outputting:
a b c d aa ab ac ad ba bb bc bd ca cb cc cd da db dc dd aaa aab aac aad aba abb abc abd aca acb acc acd ada adb adc add baa bab bac bad bba bbb bbc bbd bca bcb bcc bcd bda bdb bdc bdd caa cab cac cad cba cbb cbc cbd cca ccb ccc ccd cda cdb cdc cdd daa dab dac dad dba dbb dbc dbd dca dcb dcc dcd dda ddb ddc ddd aaaa aaab aaac aaad aaba aabb aabc aabd aaca aacb aacc aacd aada aadb aadc aadd abaa abab abac abad abba abbb abbc abbd abca abcb abcc abcd abda abdb abdc abdd acaa acab acac acad acba acbb acbc acbd acca accb accc accd acda acdb acdc acdd adaa adab adac adad adba adbb adbc adbd adca adcb adcc adcd adda addb addc addd baaa baab baac baad baba babb babc babd baca bacb bacc bacd bada badb badc badd bbaa bbab bbac bbad bbba bbbb bbbc bbbd bbca bbcb bbcc bbcd bbda bbdb bbdc bbdd bcaa bcab bcac bcad bcba bcbb bcbc bcbd bcca bccb bccc bccd bcda bcdb bcdc bcdd bdaa bdab bdac bdad bdba bdbb bdbc bdbd bdca bdcb bdcc bdcd bdda bddb bddc bddd caaa caab caac caad caba cabb cabc cabd caca cacb cacc cacd cada cadb cadc cadd cbaa cbab cbac cbad cbba cbbb cbbc cbbd cbca cbcb cbcc cbcd cbda cbdb cbdc cbdd ccaa ccab ccac ccad ccba ccbb ccbc ccbd ccca cccb cccc cccd ccda ccdb ccdc ccdd cdaa cdab cdac cdad cdba cdbb cdbc cdbd cdca cdcb cdcc cdcd cdda cddb cddc cddd daaa daab daac daad daba dabb dabc dabd daca dacb dacc dacd dada dadb dadc dadd dbaa dbab dbac dbad dbba dbbb dbbc dbbd dbca dbcb dbcc dbcd dbda dbdb dbdc dbdd dcaa dcab dcac dcad dcba dcbb dcbc dcbd dcca dccb dccc dccd dcda dcdb dcdc dcdd ddaa ddab ddac ddad ddba ddbb ddbc ddbd ddca ddcb ddcc ddcd ddda dddb dddc dddd

Example: given the input efgh (or any combination thereof of the four characters e,f,g,h), there is an equal chance of outputting:
e f g h ee ef eg eh fe ff fg fh ge gf gg gh he hf hg hh eee eef eeg eeh efe eff efg efh ege egf egg egh ehe ehf ehg ehh fee fef feg feh ffe fff ffg ffh fge fgf fgg fgh fhe fhf fhg fhh gee gef geg geh gfe gff gfg gfh gge ggf ggg ggh ghe ghf ghg ghh hee hef heg heh hfe hff hfg hfh hge hgf hgg hgh hhe hhf hhg hhh eeee eeef eeeg eeeh eefe eeff eefg eefh eege eegf eegg eegh eehe eehf eehg eehh efee efef efeg efeh effe efff effg effh efge efgf efgg efgh efhe efhf efhg efhh egee egef egeg egeh egfe egff egfg egfh egge eggf eggg eggh eghe eghf eghg eghh ehee ehef eheg eheh ehfe ehff ehfg ehfh ehge ehgf ehgg ehgh ehhe ehhf ehhg ehhh feee feef feeg feeh fefe feff fefg fefh fege fegf fegg fegh fehe fehf fehg fehh ffee ffef ffeg ffeh fffe ffff fffg fffh ffge ffgf ffgg ffgh ffhe ffhf ffhg ffhh fgee fgef fgeg fgeh fgfe fgff fgfg fgfh fgge fggf fggg fggh fghe fghf fghg fghh fhee fhef fheg fheh fhfe fhff fhfg fhfh fhge fhgf fhgg fhgh fhhe fhhf fhhg fhhh geee geef geeg geeh gefe geff gefg gefh gege gegf gegg gegh gehe gehf gehg gehh gfee gfef gfeg gfeh gffe gfff gffg gffh gfge gfgf gfgg gfgh gfhe gfhf gfhg gfhh ggee ggef ggeg ggeh ggfe ggff ggfg ggfh ggge gggf gggg gggh gghe gghf gghg gghh ghee ghef gheg gheh ghfe ghff ghfg ghfh ghge ghgf ghgg ghgh ghhe ghhf ghhg ghhh heee heef heeg heeh hefe heff hefg hefh hege hegf hegg hegh hehe hehf hehg hehh hfee hfef hfeg hfeh hffe hfff hffg hffh hfge hfgf hfgg hfgh hfhe hfhf hfhg hfhh hgee hgef hgeg hgeh hgfe hgff hgfg hgfh hgge hggf hggg hggh hghe hghf hghg hghh hhee hhef hheg hheh hhfe hhff hhfg hhfh hhge hhgf hhgg hhgh hhhe hhhf hhhg hhhh

Example: given the input ijkl (or any combination thereof of the four characters i,j,k,l), there is an equal chance of outputting:
i j k l ii ij ik il ji jj jk jl ki kj kk kl li lj lk ll iii iij iik iil iji ijj ijk ijl iki ikj ikk ikl ili ilj ilk ill jii jij jik jil jji jjj jjk jjl jki jkj jkk jkl jli jlj jlk jll kii kij kik kil kji kjj kjk kjl kki kkj kkk kkl kli klj klk kll lii lij lik lil lji ljj ljk ljl lki lkj lkk lkl lli llj llk lll iiii iiij iiik iiil iiji iijj iijk iijl iiki iikj iikk iikl iili iilj iilk iill ijii ijij ijik ijil ijji ijjj ijjk ijjl ijki ijkj ijkk ijkl ijli ijlj ijlk ijll ikii ikij ikik ikil ikji ikjj ikjk ikjl ikki ikkj ikkk ikkl ikli iklj iklk ikll ilii ilij ilik ilil ilji iljj iljk iljl ilki ilkj ilkk ilkl illi illj illk illl jiii jiij jiik jiil jiji jijj jijk jijl jiki jikj jikk jikl jili jilj jilk jill jjii jjij jjik jjil jjji jjjj jjjk jjjl jjki jjkj jjkk jjkl jjli jjlj jjlk jjll jkii jkij jkik jkil jkji jkjj jkjk jkjl jkki jkkj jkkk jkkl jkli jklj jklk jkll jlii jlij jlik jlil jlji jljj jljk jljl jlki jlkj jlkk jlkl jlli jllj jllk jlll kiii kiij kiik kiil kiji kijj kijk kijl kiki kikj kikk kikl kili kilj kilk kill kjii kjij kjik kjil kjji kjjj kjjk kjjl kjki kjkj kjkk kjkl kjli kjlj kjlk kjll kkii kkij kkik kkil kkji kkjj kkjk kkjl kkki kkkj kkkk kkkl kkli kklj kklk kkll klii klij klik klil klji kljj kljk kljl klki klkj klkk klkl klli kllj kllk klll liii liij liik liil liji lijj lijk lijl liki likj likk likl lili lilj lilk lill ljii ljij ljik ljil ljji ljjj ljjk ljjl ljki ljkj ljkk ljkl ljli ljlj ljlk ljll lkii lkij lkik lkil lkji lkjj lkjk lkjl lkki lkkj lkkk lkkl lkli lklj lklk lkll llii llij llik llil llji lljj lljk lljl llki llkj llkk llkl llli lllj lllk llll

This by definition also means that every indiviual character within the string too has equal probability. All characters in the input are distinct.

Comments are not for extended discussion; this conversation has been moved to chat.

@EmbodimentofIgnorance Thanks, fixed.

Is the input guaranteed to have at least two distinct characters?

@Neil Yes, indeed.

A terminology issue (because terminology is important here): 'aaa' is not a subset/subsection/substring/subsequence of any permutation of 'abcd'. Every permutation of 'abcd' has exactly 1 'a' in it.

@ChasBrown Ha. Not sure how to phrase it in an exact sense then.

@Flog Edoc: Jo King's approach is pretty to close to what you want to say, I think.

(1) Is the empty string a required valid output? (2) Can we assume that there are no repeated characters in the input?  (3) Can we take the input as a set / list of characters, as opposed to a string? (For future reference, these are all the sorts of questions we usually try to resolve in the Sandbox!)

@ChasBrown 1) No. (see "from length 1") 2) Yes. (last line) 3) No. (considering the tag [tag:string] as well)

@Flog Edoc: (2) There is a real difference between 'will contain at least two distinct characters' and 'all characters will be distinct'. Which do you intend?

i think the keyword here is "ordered samples with replacement" http://mathworld.wolfram.com/BallPicking.html

This challenge seems to have been significantly changed from what was initially posted, making it a completely different challenge and invalidating the existing solutions. That's an automatic -1 from me and the reason I've VTCed as unclear.

The whole part about each character in the string having equal probability of occurring is redundant.  Since each combo has equal probability each character has equal probability.

@Shaggy As it stands now, many edge cases have in fact been resolved, so it is far from unclear as compared to where it started. Right now, I think it's pretty understandable what the requirements are. Other than exact formulaic assumptions (which may affect existing answers and may as well be a different question entirely), I'm not sure what you're looking to do.

Your three examples are all essentially the same. I suggest showing the expected output for: the empty string (if applicable — I suggest you rule it out), input x, input xy, input xxy, input zzz.

@Lynn The question has been changed so that input is composed of only distinct characters (which has made a lot of answers non-optimal). I mentioned the example thing a while ago in a comment now deleted, so the OP probably won't change it :(

@JoKing Making the input distinct characters was supposed to relax the rules a bit. I don't intend to have every esoteric input under the sun listed and dealt with. The only way I can see making this question even more clear and removing every bit of possibility that there is some issue, would be to exactly define in a mathematical sense a formal meaning of the term 'random', and go on and do this for each and every requirement. That is far from necessary and if it were, I wouldn't wish to be the outlier, rather it then be applied to every other question as well. Who wants this!?

@FlogEdoc The problem most people have is that you keep changing the question. We only wanted clarification on whether the input could have multiple of the same character, since you kept implying it but never stating it outright, nor giving a specific example. No-one asked you to change input specs, nor to specify how to take input. I won't vote to close (since the challenge is clear now), but I have downvoted because of the repeated changes invalidating answers or making them less optimal. Just in the future, use the Sandbox to make sure your question is fully clear before posting it.

Jelly,  10  5 bytes
ṗJẎQX

A monadic Link accepting a list of characters which yields a list of characters.
Try it online!
How?
ṗJẎQX - Link list of characters    e.g.  aabc
 J    - range of length                  [1,2,3,4]
ṗ     - Cartesian power (vectorises)     [[a,a,b,c],[aa,aa,ab,ac,aa,aa,ab,ac,ba,ba,bb,bc,ca,ca,cb,cc],[aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,baa,baa,bab,bac,baa,baa,bab,bac,bba,bba,bbb,bbc,bca,bca,bcb,bcc,caa,caa,cab,cac,caa,caa,cab,cac,cba,cba,cbb,cbc,cca,cca,ccb,ccc],[aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,bbaa,bbaa,bbab,bbac,bbaa,bbaa,bbab,bbac,bbba,bbba,bbbb,bbbc,bbca,bbca,bbcb,bbcc,bcaa,bcaa,bcab,bcac,bcaa,bcaa,bcab,bcac,bcba,bcba,bcbb,bcbc,bcca,bcca,bccb,bccc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,cbaa,cbaa,cbab,cbac,cbaa,cbaa,cbab,cbac,cbba,cbba,cbbb,cbbc,cbca,cbca,cbcb,cbcc,ccaa,ccaa,ccab,ccac,ccaa,ccaa,ccab,ccac,ccba,ccba,ccbb,ccbc,ccca,ccca,cccb,cccc]
  Ẏ   - tighten                          [a,a,b,c,aa,aa,ab,ac,aa,aa,ab,ac,ba,ba,bb,bc,ca,ca,cb,cc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,baa,baa,bab,bac,baa,baa,bab,bac,bba,bba,bbb,bbc,bca,bca,bcb,bcc,caa,caa,cab,cac,caa,caa,cab,cac,cba,cba,cbb,cbc,cca,cca,ccb,ccc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,bbaa,bbaa,bbab,bbac,bbaa,bbaa,bbab,bbac,bbba,bbba,bbbb,bbbc,bbca,bbca,bbcb,bbcc,bcaa,bcaa,bcab,bcac,bcaa,bcaa,bcab,bcac,bcba,bcba,bcbb,bcbc,bcca,bcca,bccb,bccc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,cbaa,cbaa,cbab,cbac,cbaa,cbaa,cbab,cbac,cbba,cbba,cbbb,cbbc,cbca,cbca,cbcb,cbcc,ccaa,ccaa,ccab,ccac,ccaa,ccaa,ccab,ccac,ccba,ccba,ccbb,ccbc,ccca,ccca,cccb,cccc]
   Q  - de-duplicate                     [a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc,aaaa,aaab,aaac,aaba,aabb,aabc,aaca,aacb,aacc,abaa,abab,abac,abba,abbb,abbc,abca,abcb,abcc,acaa,acab,acac,acba,acbb,acbc,acca,accb,accc,baaa,baab,baac,baba,babb,babc,baca,bacb,bacc,bbaa,bbab,bbac,bbba,bbbb,bbbc,bbca,bbcb,bbcc,bcaa,bcab,bcac,bcba,bcbb,bcbc,bcca,bccb,bccc,caaa,caab,caac,caba,cabb,cabc,caca,cacb,cacc,cbaa,cbab,cbac,cbba,cbbb,cbbc,cbca,cbcb,cbcc,ccaa,ccab,ccac,ccba,ccbb,ccbc,ccca,cccb,cccc]
    X - uniform random choice

05AB1E, 6 bytes
ā€ã˜ÙΩ

Try it online!
Explanation
ā       # push [1 ... len(input)]
 €ã     # apply repeated cartesian product on each and input
   ˜    # flatten
    Ù   # remove duplicates
     Ω  # pick random string

Perl 6, 35 33 28 bytes
-2 bytes thanks to nwellnhof
{[~] roll .rand+1,$_}o*.comb

Try it online!
This challenge keeps changing a lot.
Explanation:
{                   }o*.comb  # Anonymous code block turning input into chars
                  $_          # From the input
          .rand+1,              # Take a random number from 1 to length of list
     roll                       # Of characters
 [~]                          # And join them into a string

Brachylog, 8 bytes
⊇ᶠbṛ;?ṛw

Try it online!
Prints output directly instead of constraining the output variable, because for some reason this actually fails without the w at the end. Originally this used ≠ and the ∈& backtracking hack I used to implement bogosort, but I realized that it would be far saner to just use b instead.
       w    Print
      ṛ     a random one of
     ?      the input
    ;       or
   ṛ        a random element of
 ᶠ          every
⊇           sublist of
            the input
  b         except the first one (which would be the input).

Python 2, 111 121 bytes
lambda s:choice(g(list(set(s)),len(s)))
from random import *
g=lambda s,n:s+(n>1and[c+k for k in g(s,n-1)for c in s]or[])

Try it online!
Takes any iterable (list, set, string, etc.) of either distinct characters or non-distinct characters as input. Outputs a non-empty string with the required distribution.
g is a recursive function to generate a list of compliant strings.

R, 72 64 bytes
-8 bytes thanks to Giuseppe.
S=sample;S(t<-unique(s<-scan(,"")),S(n<-seq(s),p=length(t)^n),T)

Try it online!
Input and output are vectors of characters. All possible outputs have equal probability.
Explanation (ungolfed version):
s<-scan(,"")                         # takes input as vector of characters
n<-length(s)
t<-unique(s)
sample(t,                           # sample uniformly at random from the list of unique characters
       sample(n,p=length(t)^(1:n)), # with length k in 1..n chosen randomly such that P[k] is proportional to length(t)^k
       T)                           # the sampling is with replacement

64 bytes

Wolfram Language (Mathematica), 41 bytes
""<>#&@*RandomChoice@*Subsets@*Characters

Try it online!

Wha is this part? ""<>#&@

@Jonah <> is StringJoin; ""<>#& is an anonymous function that joins "" with its argument (and is much shorter than StringJoin). @* composes functions.

Java 131 bytes
void k(String a){a.chars().forEach(v->{int z=(int)(Math.random()*(a.length()+1));if(z<a.length())System.out.print(a.charAt(z));});}

Nice approach! Since you're using a Java 8+ stream, why not change void k(String a){a.chars()..;} to a->a.chars().. as well? Also, int z=(int)(Math.random()*(a.length()+1));if(z<a.length()) can be int l=a.length(),z=l+1;z*=Math.random();if(z<l) to save some more bytes. In total it then becomes 104 bytes

Pyth - 7 bytes
Os^LQSl

O                         Random choice
 s                        Collapse list
  ^L                      Map cartesian power
   Q                      Input
   S                      1-indexed range
    l                     Length
     (Q implicit)         Input

Try it online.
Try it online without random pick to see all possible options.

Haskell,  143 126 bytes
-7 bytes thanks to @Laiconi, additional improvement (which I need to fully understand first) in the comments
import Control.Monad
import System.Random
f a|c<-concat[replicateM x a|x<-[1..length a]]=randomRIO(0,length c-1)>>=print.(c!!)

Try it online!

Original

Instead of where you can use a binding in a guard. The do can be desugared, and there was a bit of extraneous whitespace: Try it online!

The list comprehension can be rewritten as concatMap(`replicateM`a)[1..length a] and then shortened to (`replicateM`a)=<<[1..length a].

Though a shorter way to get all strings is mapM(\_->a)=<<scanr(:)[]a, as it does not need the import. This list includes the empty string at the end, so we need to subtract 2 in randomRIO(0,length c-2) to avoid it: Try it online!

Thanks for the feedback, I'm relatively new to haskell (and totally new to golfing), so it's always nice to get some tips from more experiences users :)

seems like it'd be easier generating all possible lists (of every length) and nub-ing to filter out duplicates

C (gcc), 68 65 bytes
f(s,i)char*s;{for(;i<strlen(s);i++)rand()&1?putc(s[i],stdout):0;}

Try it online!

I don't think this is correct anymore

If the op changed the rules that's a pity.

T-SQL, 222 bytes
This creates all combinations of each unique character with recursive sql, then picks a random row from the distinct combinations.
DECLARE @ varchar(max)='T-SQL';

WITH C as(SELECT DISTINCT substring(@,number+1,1)x
FROM spt_values
WHERE'P'=type and len(@)>number),D
as(SELECT x y
FROM c UNION ALL
SELECT y+x
FROM C JOIN D
ON len(y)<len(@))SELECT top 1*FROM D
GROUP BY y
ORDER BY newid()

Note the online version will always give the same result unlike MS-SQL Studio Management. This is because newid() always returns the same value in the online testing. This should work in Studio Management.
Try it online ungolfed version

Charcoal, 34 bytes
≔Φθ⁼κ⌕θιη≔⊕‽ΣＥθＸＬη⊕κζＷζ«§ηζ≔÷⊖ζＬηζ

Try it online! Link is to verbose version of code. Explanation:
≔Φθ⁼κ⌕θιη

Extract the unique characters of the input. Let's call the number of unique characters n.
≔⊕‽ΣＥθＸＬη⊕κζ

Calculate the number of combinations for each possible length and take the sum. Then, pick a random number between 1 and this number (inclusive). This ensures that all combinations are equally likely (within the accuracy of the random number generator).
Ｗζ«§ηζ≔÷⊖ζＬηζ

Convert the number into bijective base n, using the unique characters as the digits.

MATLAB / Octave, 110 bytes
Choose a random permutation of a subset of the input letters (with repetitions), whose random length is based on the probability of generating a word with that length.
@(a)a(randi(numel(a),[find(cumsum(numel(a).^[1:numel(a)])>=randi(sum(numel(a).^[1:numel(a)])),1,'first'),1]));

Try it online!

J, 27 bytes
[:(?@#{])@;[:,@{&.>#\<@#"{<

Try it online!
standard formatting
[: (?@# { ])@; [: ,@{&.> #\ <@#"1 _ <

explanation
Eg, for the string 'abc' we first use #\<@#"{< to create:
┌─────┬─────────┬─────────────┐
│┌───┐│┌───┬───┐│┌───┬───┬───┐│
││abc│││abc│abc│││abc│abc│abc││
│└───┘│└───┴───┘│└───┴───┴───┘│
└─────┴─────────┴─────────────┘

We then take the cartesian product of each of these {, flatten the results, and finally remove the outer boxing ;.
(?@#{])@ takes a random result from that list.

TIO will return the same result every time, but in a normal J REPL it will be random. sounds like a bug to report, random works for Python 3 TIO...

J will start each session with the same seed for its RNG.  If you keep running the same verb in a single session, you'll get different answers.  But if you start your session over, the same sequence will occur.  TIO is like a fresh J session.  So it's not exactly a bug -- at least I wouldn't call it one.

Bug, maybe not. Improvable feature, quite possibly. As someone who's never used J, I'll leave it up to you to report the bug if you wish to.

@ArtemisFowl I figured out how to fix it.  The TIO now works, returning a fresh result each time.

The program now seems to output a list of values...

i’m running it a bunch of times

Oh, right. Like I say, I know nothing about J.

Python 2, 124 bytes
lambda s:g(list(set(s)),len(s))
from random import*
g=lambda s,n:choice(s)+(random()*~-len(s)**(n)>~-len(s)and g(s,n-1)or'')

Try it online!
A different approach: instead of first constructing a list of all compliant strings and choosing one at random, this approach randomly decides to continue extending the string or stopping.
This again has to deal with the exacting input requirements, at a cost of 31 bytes; but the function of interest g takes a list s of characters to be used, and an integer n which is the maximum length of the returned string.
As an example, consider the set of characters ['a','b'] and suppose we want to generate random strings of length 1, 2, or 3.
Then if we randomly choose 'a' as the starting character, the possible strings which could be returned are:
a
 aa
  aaa
  aab
 ab
  aba
  abb

shown above in 'tree' form, which is a total of 1 + 2 + 2*2 = 2^0 + 2^1 + 2^2 = 7 strings. So if we generate a string a; then 1/7 of the time we should stop and return 'a', and 6/7 of the time we should add further to the string - then the distribution will be uniform in the way desired.
More generally, if n is maximum length of the string and x is the number of characters in the set, then the number of strings starting with some given character is going to be:
$$h(n)=\sum_{i=0}^{n-1} x^i$$
$$h(n)=1+x+x^2+x^3...+x^{n-1}$$
For x>1 (guaranteed by OP's rule 'at least two distinct...'), we have:
$$h(n)(x-1)=(1+x+x^2+x^3...+x^{n-1})(x-1)=x^n-1$$
$$h(n)=\frac{x^n-1}{x-1}$$
So to decide whether we should continue extending our string, let p be a random number in [0,1); then we should recurse only if any of these equivalent statements are true:
$$p>\frac{1}{h(n)}$$
$$p>\frac{x-1}{x^n-1}$$
$$p(x^n-1)>x-1$$
of which g is the golfed implementation.

C# (Visual C# Interactive Compiler), 126 bytes
a=>{var s=new Random();int d=a.Length;return Enumerable.Range(1,s.Next(1,d)).Select(x=>a.Distinct().ToList()[s.Next(0,d-1)]);}

Try it online!

Forth (gforth), 68 bytes
include random.fs
: f dup random 1+ 0 do 2dup random + 1 type loop ;

Try it online!
Explanation

Get a random number between 1 and string-length
Loop that many times
For each iteration

Get a random number between 0 and string length - 1
Add that to string starting address and output the character at that address

Code Explanation
include random.fs          \ include the library file needed to generate random numbers
: f                        \ start a new word definition
  dup                      \ duplicate the string-length
  random 1+                \ get the length of the new string, make sure it starts from 1
  0 do                     \ start a loop of that length
    2dup                   \ duplicate the starting address and string length
    random +               \ get a number from 0 to string-length and add it to the address
    1 type                 \ output the character at that address
  loop                     \ end the loop
;                          \ end the word definition


text:
String Manipulation Interpreter
Summary
A new string manipulation language has been made, using only the characters $+#-!*|@>! Your task is to implement an interpreter for it in as few bytes as possible.
Input
A string, which is a single line of this language. This can be taken in any reasonable way (stdin, function parameter, command line argument etc.), or as a predefined variable. If the program asks for user input, accept all user input it asks for from stdin and nothing more, see below. You may assume it is a valid program.
Output
Whatever the language would output, specifications below. You must output a string, in any reasonable way (stdout, function output, etc.), or a variable value. When the language outputs explicitly, this must go to stdout. Standard loopholes are banned.
Language Specifications
Processing and Syntax
The language has a very simple form of processing as it does only string manipulation: it starts with an empty string (""), and changes it with each term. A term is made up of one or two parts: a function (below) followed by possibly a parameter(below), which edits its behaviour. Terms are separated by pipes (|). You may assume it will not be an empty program, and no term will be empty. You should output the value at the end of the program.
Functions
The language has just 6 functions, as shown below. Each function either accepts one or zero parameters.

+ concatenate strings (takes one string parameter, concatenates it to the current value)
! reverse the character order of the current value (no parameter)
* repeat the string (takes one integer parameter, repeats the current value that many times)
- removes all occurrences of a value (takes one string parameter, removes all occurrences of it from the current value)
$ [pseudo-]randomly shuffles the current value (no parameter)
< output the current value to stdout (no parameters)

Values
These are the values that may be passed to functions, represented by regex that would match them:

@[^|]* a string literal, including any character other than pipes. It may be empty.
#[0-9]+ an integer literal
> the next line of stdin. If used with *, convert to integer.

Test Cases
╔════════════════════════╤═════════════╤══════════════╗
║code                    │input        │output        ║
╟────────────────────────┼─────────────┼──────────────╢
║+>|!|+@hello|*>         │13           │31hello31hello║
║                        │2            │              ║
╟────────────────────────┼─────────────┼──────────────╢
║+>|+@abcdefg|$          │hello        │hcloeebafdlg  ║
╟────────────────────────┼─────────────┼──────────────╢
║+@how areyou|-@o|->     │w            │h areyu       ║
╟────────────────────────┼─────────────┼──────────────╢
║+@out|<|*#3             │             │out           ║
║                        │             │outoutout     ║
╟────────────────────────┼─────────────┼──────────────╢
║+>                      │what ever 345│what ever 345 ║
╟────────────────────────┼─────────────┼──────────────╢
║+@$pe<i@l|<|-@$pe<i@l|+>│A|$o $pe<!@| │$pe<i@l       ║
║                        │             │A|$o $pe<!@|  ║
╟────────────────────────┼─────────────┼──────────────╢
║<|+>|!|<                │input text   |              ║
║                        │             │txet tupni    ║
║                        │             │txet tupni    ║
╟────────────────────────┼─────────────┼──────────────╢
║+@>#                    │             |>#            ║
╚════════════════════════╧═════════════╧══════════════╝

Note that test case 2 is random, so any permutation of the characters in it is valid. Also, the outputs in the table are seperated by newlines, but your program doesn't have to do the same. The last value in each case the the final output.
Example (Un-golfed) python interpreter
Try it online! IMO better if you run it through IDLE or whatever you use. (I golfed it down to 424 bytes after, but I'm sure you lot can do better).

Allowing input to already be in a variable is non-standard, as is allowing output to be in one.

Your examples seem to print a newline everytime < is encountered. Is this mandatory?

Will the program have newlines in it? Because if it can, it invalidates Chas Brown's answer

For your future questions, please consider avoiding cumbersome I/O formats. Limiting input to stdin costs extra bytes in some languages and doesn't bring much to the challenge.

@EmbodimentofIgnorance No

@ArtemisFowl FYI, the minimum recommended time to Sandbox a challenge for is 7 days.

@Shaggy Thought I read 72 hrs somewhere. Oh well.

Suggested test case : +@foo>

@ArtemisFowl: because > can be either an input command (but always following another command like +) or inside a literal; while < can be inside a literal but when indended as command it will be alone in between pipes. I suggested this example because I had problem managing this difference ;)

@digEmAll How's the one I just added, +@>#? I used # aswell.

@ArtemisFowl: yep, perfect !

Ruby -palF\|, 146 142 bytes
r='';$F.map{|i|x=i[1]!=?>?i[2..-1]:gets.chomp;eval %w[r.reverse! r*=x.to_i 0 $><<r r=r.chars.shuffle*'' r.gsub!x,'' r+=x][i[0].ord*5%11]};$_=r

Try it online!
Port of Chas Brown's Python answer. Does not print newlines after output.
As usual, Ruby 2.6 version will be 2 bytes shorter with endless range indexing (i[2..]).

R, 287 286 273 269 bytes
function(C,x='',`[`=gsub,`!`=intToUtf8,`?`=utf8ToInt){for(k in el(strsplit(C,'\\|'))){B=eval(parse(t='^.'['','(?<=.)>$'['readLines(,1)','[@#](.+)'['"\\1"',k],,T]]));x=switch((?substr(k,1,1))%%13-2,strrep(x,B),paste0(x,B),,B['',x,f=T],!rev(?x),print(x),,!sample(?x))};x}

Try it online!

-1 thanks to @Kirill L.
-4 thanks to @Giuseppe

Unrolled code and explanation :
function(C){                                      # C is the string manipulation expression
  x = ''                                          # initialize x = ''
  tokens = el(strsplit(C,'\\|'))                  # split C by pipe '|'
  for(k in tokens){                               # for each token k
    arg2 = k
    arg2 = gsub('[@#](.+)','"\\1"',k)             # replace @X or #X with "X" (in quotes)
    arg2 = gsub('(?<=.)>$','"readLines(,1)"',
                 arg2,perl=T)                     # replace > with readLines(,1)
    arg2 = gsub('^.','',arg2)                     # remove the first character
    B = eval(parse(t=arg2))                       # evaluate the string : this will be our
                                                  # second argument B
    A = substr(k,1,1)                             # take the first character :
                                                  # i.e. the main command (+,-,! etc)
    x = switch(A,                                 # switch on the main command, execute the
            '+'=paste0(x,B),                      # corresponding expression and
            '!'=intToUtf8(rev(utf8ToInt(x))),     # store the result into x
            '*'=strrep(x,B),                      # Note: in the actual code we switch on
            '-'=B['',x,f=T],                      # the utf8 value MOD 13-2 of the command
            '$'=intToUtf8(sample(utf8ToInt(x))),
            '<'=print(x)
        )
    }
    x                                             # return x (and print it implicitly)
}

Python 2, 215 219 209 208 bytes
from random import*
I=raw_input;o=''
for t in I().split('|'):p=t[1:]=='>'and I()or t[2:];exec"o=o[::-1] o*=int(p) 0 print(o) o=''.join(sample(o,len(o))) o=o.replace(p,'') o+=p".split()[ord(t[0])*5%11]
print o

Try it online!
-4 because raw_input is required.
9 bytes thanks to Embodiment of Ignorance;
1 byte from Ascii-only.

Input other than the program must be from stdin, as specified in the question.

I use Python 3, but as far as I was aware, that usage of input requires raw_input. Correct me if I am wrong..

According to Py 2.7 docs: input([prompt])
Equivalent to eval(raw_input(prompt)).
This function does not catch user errors. If the input is not syntactically valid, a SyntaxError will be raised.

So, the issue you're raising is something like here, where the input strings would need to be quoted - rather than unquoted as in a 'true' stdin situation. Again, usually the I/O rules are a bit lax; but I will modify.

Thanks for changing. You could save a few bytes by changing to Python 3 and using your old code + 3 bytes for brackets, but... +1 anyways

This, as a standalone program, does not seem to be able to handle multiline programs, because by using stdin, you don't know when the program part ends and the input part starts

@Embodiment of Ignorance: See OP's TIO Implementation. Uses the same approach: program is the first line of input.

208

C# (Visual C# Interactive Compiler), 305 bytes
a=>{string s="",d,g;foreach(var c in a.Split('|')){g=$"{c,2}";d=g[1]==62?ReadLine():g.Substring(2);var z=c[0]%14;s=z<1?string.Concat(Enumerable.Repeat(s,int.Parse(d))):z<2?s+d:z<4?s.Replace(d,""):z<5?s:z<6?string.Concat(s.Reverse()):string.Concat(s.OrderBy(_=>Guid.NewGuid()));Write(z==4?s:"");}return s;}

Try it online!

Javascript, 292 267 bytes
f=(p)=>{c='';p.split`|`.map(l=>{v=l.substr(2);v=l[1]=='#'?parseInt(v):l[1]=='>'?prompt():v;c={'+':_=>c+v,'-':_=>c.split(v).join``,'*':_=>c.repeat(v),'$':_=>[...c].sort(_=>.5-Math.random()).join``,'!':_=>[...c].reverse().join``,'<':_=>alert(c)||c}[l[0]]();});return c}

JSFiddle

Test case 6 doesn't quite work...

@ArtemisFowl, Thanks, the regex was not working correctly and switching to split..join saved a couple of bytes.

Perl 5 -MList::Util=shuffle -pF/\|/, 220 217 210 183 bytes
map{$,=s/..//r;$\=reverse$\if/^!/;$,ne""||chomp($,=<>),$\=~s/\Q$,//g if/^-/;say$\if/^</;$\=join"",shuffle$\=~/./g if/^\$/;$\.=$,eq""?<>=~s/\n//r:$,if/^\+/;$\x=$,eq""?<>:$,if/^\*/}@F}{

Try it online!