text:
Multiply Two Integer Polynomials
Your task is to take two single-variable integer polynomial expressions and multiply them into their unsimplified first-term-major left-to-right expansion (A.K.A. FOIL in the case of binomials). Do not combine like terms or reorder the result. To be more explicit about the expansion, multiply the first term in the first expression by each term in the second, in order, and continue in the first expression until all terms have been multiplied by all other terms. Expressions will be given in a simplified LaTeX variant.
Each expression will be a sequence of terms separated by + (with exactly one space on each side) Each term will conform to the following regular expression: (PCRE notation)
-?\d+x\^\d+

In plain English, the term is an optional leading - followed by one or more digits followed by x and a nonnegative integer power (with ^)
An example of a full expression:
6x^3 + 1337x^2 + -4x^1 + 2x^0

When plugged into LaTeX, you get \$6x^3 + 1337x^2 + -4x^1 + 2x^0\$
The output should also conform to this format.
Since brackets do not surround exponents in this format, LaTeX will actually render multi-digit exponents incorrectly. (e.g. 4x^3 + -2x^14 + 54x^28 + -4x^5 renders as \$4x^3 + -2x^14 + 54x^28 + -4x^5\$) You do not need to account for this and you should not include the brackets in your output.
Example Test Cases
5x^4
3x^23

15x^27

6x^2 + 7x^1 + -2x^0
1x^2 + -2x^3

6x^4 + -12x^5 + 7x^3 + -14x^4 + -2x^2 + 4x^3

3x^1 + 5x^2 + 2x^4 + 3x^0
3x^0

9x^1 + 15x^2 + 6x^4 + 9x^0

4x^3 + -2x^14 + 54x^28 + -4x^5
-0x^7

0x^10 + 0x^21 + 0x^35 + 0x^12

4x^3 + -2x^4 + 0x^255 + -4x^5
-3x^4 + 2x^2

-12x^7 + 8x^5 + 6x^8 + -4x^6 + 0x^259 + 0x^257 + 12x^9 + -8x^7

Rules and Assumptions

You may assume that all inputs conform to this exact format. Behavior for any other format is undefined for the purposes of this challenge.

It should be noted that any method of taking in the two polynomials is valid, provided that both are read in as strings conforming to the above format.

The order of the polynomials matters due to the expected order of the product expansion.
You must support input coefficients between \$-128\$ and \$127\$ and input exponents up to \$255\$.

Output coefficents between \$-16,256\$ and \$16,384\$ and exponents up to \$510\$ must therefore be supported.

You may assume each input polynomial contains no more than 16 terms

Therefore you must (at minimum) support up to 256 terms in the output

Terms with zero coefficients should be left as is, with exponents being properly combined
Negative zero is allowed in the input, but is indistinguishable from positive zero semantically. Always output positive zero. Do not omit zero terms.

Happy Golfing! Good luck!

related

@LuisfelipeDejesusMunoz I imagine not. Parsing is an integral part of the challenge and the OP says -- "It should be noted that any method of taking in the two polynomials is valid, provided that both are read in as strings conforming to the above format." (emphasis added)

R, 159 153 148 bytes
function(P,Q,a=h(P),b=h(Q))paste0(b[1,]%o%a[1,],"x^",outer(b,a,"+")[2,,2,],collapse=" + ")
h=function(s,`/`=strsplit)sapply(el(s/" . ")/"x.",strtoi)

Try it online!
I really wanted to use outer, so there's almost surely a more efficient approach.

Haskell, 131 122 bytes
(%)=drop
f s=do(a,t)<-reads s;(i,u)<-reads$2%t;(a,i):f(3%u)
p!q=3%do(a,i)<-f p;(b,j)<-f q;" + "++shows(a*b)"x^"++show(i+j)

Try it online!
f parses a polynomial from a string, ! multiplies two of them and formats the result.
H.PWiz saved 9 bytes. Thanks!
Ungolfed
type Monomial = (Int, Int) -- a^i
type Polynomial = [Monomial]

parse :: String -> Polynomial
parse s = do (a, s')  <- reads s
             (i, s'') <- reads (drop 2 s')
             (a, i) : parse (drop 3 s'')

(!) :: String -> String -> String
p!q = drop 3 (concat terms)
  where terms    = [term (a*b) (i+j) | (a,i) <- p', (b,j) <- q']
        term a i = concat [" + ", show a, "x^", show i]
        p'       = parse p
        q'       = parse q

129 bytes

even better

Ruby, 102 100 98 bytes
->a,b{a.scan(w=/(.*?)x.(\d+)/).map{|x|b.scan(w).map{|y|(eval"[%s*(z=%s;%s),z+%s]"%y+=x)*"x^"}}*?+}

Try it online!
How?
First step: get all the numbers from both polynomials: scan returns the numbers as an array of pairs of strings.
Then, do a cartesian product of the 2 lists. Now we have all the numbers where we need them, but still in the wrong order.
Example: if we multiply 3x^4 by -5x^2, we get the numbers as [["3","4"],["-5","2"]], the first idea was to zip and flatten this list, and then put the numbers into an expression to be evaluated as [3*-5, 4+2]. Actually, we don't need to reorder the numbers, we could do it inside the expression by using a temporary variable: the expression becomes [3*(z=4,-5),z+2].
After evaluating these expressions, we get the coefficient and exponent, we need to join them using "x^", and then join all the tems using "+".

Haskell, 124 121 bytes
import Data.Lists
f!x=map f.splitOn x
z=read!"x^"!"+"
a#b=drop 3$do[u,v]<-z a;[p,q]<-z b;" + "++shows(u*p)"x^"++show(v+q)

Note: TIO lacks Data.Lists, so I import Data.Lists.Split and Data.List: Try it online!
Edit: -3 bytes thanks to @Lynn.

This is actually 123 bytes! f!x=map f.splitOn x and then z=read!"x^"!"+" saves a byte; for the last line drop 3$do[u,v]<-z a;[p,q]<-z b;" + "++shows(u*p)"x^"++show(v+q) saves two more. 120 bytes

@Lynn: the TIO version imports Data.List instead of Data.Lists, so it's +1 byte.

Pyth - 39 bytes
LmsMcdK"x^"%2cb)j" + "m++*FhdKsedCM*FyM

Try it online.

JavaScript (Babel Node), 118 bytes
Takes input as (a)(b).
a=>b=>(g=s=>[...s.matchAll(/(-?\d+)x.(\d+)/g)])(a).flatMap(([_,x,p])=>g(b).map(([_,X,P])=>x*X+'x^'+-(-p-P))).join` + `

Try it online!

SNOBOL4 (CSNOBOL4),  192 176 bytes
	P =INPUT
	Q =INPUT
	D =SPAN(-1234567890)
P	P D . K ARB D . W REM . P	:F(O)
	B =Q
B	B D . C ARB D . E REM . B	:F(P)
	O =O ' + ' K * C 'x^' W + E	:(B)
O	O ' + ' REM . OUTPUT
END

Try it online!
	P =INPUT				;* read P
	Q =INPUT				;* read Q
	D =SPAN(-1234567890)			;* save PATTERN for Digits (or a - sign); equivalent to [0-9\\-]+
P	P D . K ARB D . W REM . P	:F(O)	;* save the Koefficient and the poWer, saving the REMainder as P, or if no match, goto O
	B =Q					;* set B = Q
B	B D . C ARB D . E REM . B	:F(P)	;* save the Coefficient and the powEr, saving the REMainder as B, or if no match, goto P
	O =O ' + ' K * C 'x^' W + E	:(B)	;* accumulate the output
O	O ' + ' REM . OUTPUT			;* match ' + ' and OUTPUT the REMainder
END

JavaScript, 112 110 bytes
I found two alternatives with the same length. Call with currying syntax: f(A)(B)
A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(a=>P(B).map(b=>a[0]*b[0]+'x^'+(a[1]- -b[1]))).join` + `

f=
A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(a=>P(B).map(b=>a[0]*b[0]+'x^'+(a[1]- -b[1]))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(([c,e])=>P(B).map(([C,E])=>c*C+'x^'+(e- -E))).join` + `

f=
A=>B=>(P=x=>x.split`+`.map(x=>x.split`x^`))(A).flatMap(([c,e])=>P(B).map(([C,E])=>c*C+'x^'+(e- -E))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

-2 bytes (Luis): Remove spaces around split delimiter.

JavaScript, 112 bytes
Using String.prototype.matchAll.
A=>B=>(P=x=>[...x.matchAll(/(\S+)x.(\S+)/g)])(A).flatMap(a=>P(B).map(b=>a[1]*b[1]+'x^'+(a[2]- -b[2]))).join` + `

f=
A=>B=>(P=x=>[...x.matchAll(/(\S+)x.(\S+)/g)])(A).flatMap(a=>P(B).map(b=>a[1]*b[1]+'x^'+(a[2]- -b[2]))).join` + `

console.log( f('5x^4')('3x^23') )
console.log( f('6x^2 + 7x^1 + -2x^0')('1x^2 + -2x^3') )
console.log( f('3x^1 + 5x^2 + 2x^4 + 3x^0')('3x^0') )
console.log( f('4x^3 + -2x^14 + 54x^28 + -4x^5')('-0x^7') )
console.log( f('4x^3 + -2x^4 + 0x^255 + -4x^5')('-3x^4 + 2x^2') )

split' + ' => split'+' to save 2 bytes

@Arnauld Seems fine without them

@EmbodimentofIgnorance My bad, I misread Luis' comment. I thought it was about the join.

Python 2, 193 bytes
import re
f=re.finditer
lambda a,b:' + '.join(' + '.join(`int(m.group(1))*int(n.group(1))`+'x^'+`int(m.group(2))+int(n.group(2))`for n in f('(-?\d+)x\^(\d+)',b))for m in f('(-?\d+)x\^(\d+)',a))

Try it online!
Side note: First time doing a code golf challenge, so sorry if the attempt sucks haha

Welcome to PPCG! I'm not much of a python programmer, but there's probably some room for improvement. Perhaps you can find help at Tips for Golfing in Python or Tips for Golfing in ! Hope you enjoy the time you spend here :-)

save 12 bytes

Some quick golfing for 161 bytes. Though looking at the other python answers, re.finditer might not be the shortest approach

Retina, 110 bytes
\S\S+(?=.*\n(.+))
 $1#$&
|" + "L$v` (-?)(\d+)x.(\d+).*?#(-?)(\d+)x.(\d+)
$1$4$.($2*$5*)x^$.($3*_$6*
--|-(0)
$1

Try it online! Explanation:
\S\S+(?=.*\n(.+))
 $1#$&

Prefix each term in the first input with a #, a copy of the second input, and a space. This means that all of the terms in copies of the second input are preceded by a space and none of the terms from the first input are.
|" + "L$v` (-?)(\d+)x.(\d+).*?#(-?)(\d+)x.(\d+)
$1$4$.($2*$5*)x^$.($3*_$6*

Match all of the copies of terms in the second input and their corresponding term from the first input. Concatenate any - signs, multiply the coefficients, and add the indices. Finally join all of the resulting substitutions with the string  + .
--|-(0)
$1

Delete any pairs of -s and convert -0 to 0.

Jelly, 28 bytes
ṣ”+ṣ”xV$€)p/ZPSƭ€j⁾x^Ʋ€j“ +

Try it online!
Full program. Takes the two polynomials as a list of two strings.
Explanation (expanded form)
ṣ”+ṣ”xV$€µ€p/ZPSƭ€j⁾x^Ʋ€j“ + ” Arguments: x
         µ                     Monadic chain.
          €                    Map the monadic link over the argument.
                               Note that this will "pop" the previous chain, so
                               it will really act as a link rather than a
                               sub-chain.
ṣ”+                             ṣ, right = '+'.
                                Split the left argument on each occurrence of
                                the right.
                                Note that strings in Jelly are lists of
                                single-character Python strings.
        €                       Map the monadic link over the argument.
       $                         Make a non-niladic monadic chain of at least
                                 two links.
   ṣ”x                            ṣ, right = 'x'.
                                  Split the left argument on each occurrence of
                                  the right.
      V                           Evaluate the argument as a niladic link.
            /                  Reduce the dyadic link over the argument.
           p                    Cartesian product of left and right arguments.
                       €       Map the monadic link over the argument.
                      Ʋ         Make a non-niladic monadic chain of at least
                                four links.
             Z                   Transpose the argument.
                 €               Map the monadic link over the argument.
                ƭ                 At the first call, call the first link. At the
                                  second call, call the second link. Rinse and
                                  repeat.
              P                    Product: ;1×/$
               S                   Sum: ;0+/$
                  j⁾x^           j, right = "x^".
                                 Put the right argument between the left one's
                                 elements and concatenate the result.
                        j“ + ” j, right = " + ".
                               Put the right argument between the left one's
                               elements and concatenate the result.

Aliasing
) is the same as µ€.
A trailing ” is implied and can be omitted.
Algorithm
Let's say we have this input:
["6x^2 + 7x^1 + -2x^0", "1x^2 + -2x^3"]

The first procedure is the Parsing, applied to each of the two polynomials. Let's handle the first one, "6x^2 + 7x^1 + -2x^0":
The first step is to split the string by '+', so as to separate the terms. This results in:
["6x^2 ", " 7x^1 ", " -2x^0"]

The next step is to split each string by 'x', to separate the coefficient from the exponent. The result is this:
[["6", "^2 "], [" 7", "^1 "], [" -2", "^0"]]

Currently, it looks like there's a lot of trash in these strings, but that trash is actually unimportant. These strings are all going to be evaluated as niladic Jelly links. Trivially, the spaces are unimportant, as they are not between the digits of the numbers. So we could as well evaluate the below and still get the same result:
[["6", "^2"], ["7", "^1"], ["-2", "^0"]]

The ^s look a bit more disturbing, but they actually don't do anything either! Well, ^ is the bitwise XOR atom, however niladic chains act like monadic links, except that the first link actually becomes the argument, instead of taking an argument, if it's niladic. If it's not, then the link will have an argument of 0. The exponents have the ^s as their first char, and ^ isn't niladic, so the argument is assumed to be 0. The rest of the string, i.e. the number, is the right argument of ^. So, for example, ^2 is \$0\text{ XOR }2=2\$. Obviously, \$0\text{ XOR }n=n\$. All the exponents are integer, so we are fine. Therefore, evaluating this instead of the above won't change the result:
[["6", "2"], ["7", "1"], ["-2", "0"]]

Here we go:
[[6, 2], [7, 1], [-2, 0]]

This step will also convert "-0" to 0.
Since we're parsing both inputs, the result after the Parsing is going to be this:
[[[6, 2], [7, 1], [-2, 0]], [[1, 2], [-2, 3]]]

The Parsing is now complete. The next procedure is the Multiplication.
We first take the Cartesian product of these two lists:
[[[6, 2], [1, 2]], [[6, 2], [-2, 3]], [[7, 1], [1, 2]], [[7, 1], [-2, 3]], [[-2, 0], [1, 2]], [[-2, 0], [-2, 3]]]

Many pairs are made, each with one element from the left list and one from the right, in order. This also happens to be the intended order of the output. This challenge really asks us to apply multiplicative distributivity, as we're asked not to further process the result after that.
The pairs in each pair represent terms we want to multiply, with the first element being the coefficient and the second being the exponent. To multiply the terms, we multiply the coefficients and add the exponents together (\$ax^cbx^d=abx^cx^d=ab(x^cx^d)=(ab)x^{c+d}\$). How do we do that? Let's handle the second pair, [[6, 2], [-2, 3]].
We first transpose the pair:
[[6, -2], [2, 3]]

We then take the product of the first pair, and the sum of the second:
[-12, 5]

The relevant part of the code, PSƭ€, doesn't actually reset its counter for each pair of terms, but, since they're pairs, it doesn't need to.
Handling all pairs of terms, we have:
[[6, 4], [-12, 5], [7, 3], [-14, 4], [-2, 2], [4, 3]]

Here, the Multiplication is done, as we don't have to combine like terms. The final procedure is the Prettyfying.
We first join each pair with "x^":
[[6, 'x', '^', 4], [-12, 'x', '^', 5], [7, 'x', '^', 3], [-14, 'x', '^', 4], [-2, 'x', '^', 2], [4, 'x', '^', 3]]

Then we join the list with " + ":
[6, 'x', '^', 4, ' ', '+', ' ', -12, 'x', '^', 5, ' ', '+', ' ', 7, 'x', '^', 3, ' ', '+', ' ', -14, 'x', '^', 4, ' ', '+', ' ', -2, 'x', '^', 2, ' ', '+', ' ', 4, 'x', '^', 3]

Notice how we've still got numbers in the list, so it's not really a string. However, Jelly has a process called "stringification", ran right at the end of execution of a program to print the result out. For a list of depth 1, it really just converts each element to its string representation and concatenates the strings together, so we get the desired output:
6x^4 + -12x^5 + 7x^3 + -14x^4 + -2x^2 + 4x^3

C# (Visual C# Interactive Compiler), 192 190 bytes
n=>m=>string.Join(g=" + ",from a in n.Split(g)from b in m.Split(g)select f(a.Split(p="x^")[0])*f(b.Split(p)[0])+p+(f(a.Split(p)[1])+f(b.Split(p)[1])));Func<string,int>f=int.Parse;string p,g;

Query syntax seems to be a byte shorter than method syntax.
Try it online!

Each expression will be a sequence of terms separated by + (with exactly one space on each side) 190 bytes

Perl 6, 114 bytes
{my&g=*.match(/(\-?\d+)x\^(\d+)/,:g)».caps».Map;join " + ",map {"{[*] $_»{0}}x^{[+] $_»{1}}"},(g($^a)X g $^b)}

Try it online!

86 bytes

Python 2, 130 bytes
lambda a,b:' + '.join([`v*V`+'x^'+`k+K`for V,K in g(a)for v,k in g(b)])
g=lambda s:[map(int,t.split('x^'))for t in s.split(' + ')]

Try it online!


text:
Match Roman Numerals
Challenge
Given some input string, return a truthy value if it represents a correct roman numeral between 1 (=I) and 3999 (=MMMCMXCIX), and a falsey value otherwise.
Details

The input is a non-empty string that only comprises the characters IVXLCDM.
The roman numerals (that we use here in this challenge) are defined as follows:

We use only following symbols:
Symbol  I   V   X   L   C   D    M
Value   1   5  10  50 100 500 1000

To define which strings are actually valid roman numerals, it is probably easiest to provide the rule of conversation: To write a decimal number a3 a2 a1 a0 (where each ai represents one digit. So for example to represent 792 we have a3=0, a2=7, a1=9, a0=2.) as a roman numeral, we decompose it into the power of tens. The different powers of ten can be written as follows:
      1-9: I, II, III, IV, V, VI, VII, VIII, IX
    10-90: X, XX, XXX, XL, L, LX, LXX, LXXX, XC
  100-900: C, CC, CCC, CD, D, DC, DCC, DCCC, CM
1000-3000: M, MM, MMM

Beginning at the left side with the most significant digit of the, we can convert the number that each digit represents separately and concatenate them. So for the example from above this would look like so:
Digit        a3    a2   a1   a0
Decimal       0     7    9    2
Roman             DCC   XC   II

Therefore the roman numeral for 792 is DCCXCII. Here is a full list of all roman numerals that are relevant for this challenge: OEIS a006968.txt
Examples
Truthy
MCCXXXIV (1234)
CMLXXXVIII (988)
DXIV (514)
CI (101)

Falsey
MMIXVIII
IVX
IXV
MMMM
XXXVX
IVI
VIV

Subset of this conversion challenge.

I still don't think this qualifies as a "subset" as the set of invalid inputs is larger. This challenge here only refers to the "well"-defined numbers that are used in OEIS A006968

Why is MMMM invalid? Is there a letter for 5000 that should be used instead for M?

Check out the specs, there is no such letter. The only symbols used are I,V,X,L,C,D,M.

Verbose, 1362 bytes
GET A ROMAN NUMERAL TYPED IN BY THE CURRENT PERSON USING THIS PROGRAM AND PUT IT ONTO THE TOP OF THE PROGRAM STACK
PUT THE NUMBER MMMM ONTO THE TOP OF THE PROGRAM STACK
MOVE THE FIRST ELEMENT OF THE PROGRAM STACK TO THE SECOND ELEMENT'S PLACE AND THE SECOND ELEMENT OF THE STACK TO THE FIRST ELEMENT'S PLACE
DIVIDE THE FIRST ELEMENT OF THE PROGRAM STACK BY THE SECOND ELEMENT OF THE PROGRAM STACK AND PUT THE RESULT ONTO THE TOP OF THE PROGRAM STACK
PUT THE NUMBER V ONTO THE TOP OF THE PROGRAM STACK
GET THE FIRST ELEMENT OF THE PROGRAM STACK AND THE SECOND ELEMENT OF THE PROGRAM STACK AND IF THE SECOND ELEMENT OF THE PROGRAM STACK IS NOT ZERO JUMP TO THE INSTRUCTION THAT IS THE CURRENT INSTRUCTION NUMBER AND THE FIRST ELEMENT ADDED TOGETHER'S RESULT
PUT THE NUMBER I ONTO THE TOP OF THE PROGRAM STACK
GET THE TOP ELEMENT OF THE STACK AND OUTPUT IT FOR THE CURRENT PERSON USING THIS PROGRAM TO SEE
PUT THE NUMBER III ONTO THE TOP OF THE PROGRAM STACK
GET THE FIRST ELEMENT OF THE PROGRAM STACK AND THE SECOND ELEMENT OF THE PROGRAM STACK AND IF THE SECOND ELEMENT OF THE PROGRAM STACK IS NOT ZERO JUMP TO THE INSTRUCTION THAT IS THE CURRENT INSTRUCTION NUMBER AND THE FIRST ELEMENT ADDED TOGETHER'S RESULT
PUT THE NUMBER NULLA ONTO THE TOP OF THE PROGRAM STACK
GET THE TOP ELEMENT OF THE STACK AND OUTPUT IT FOR THE CURRENT PERSON USING THIS PROGRAM TO SEE

Outputs I for valid roman numerals in the range I-MMMCMXCIX and NULLA (0) or informs user input is not a valid roman numeral otherwise.

I can't decide if this is the right tool for the job or not.

Is this the right tool for any job?

C# (Visual C# Interactive Compiler), 79 109 bytes
This seems like a Regex challenge, I'm sure a shorter solution can be found...
s=>System.Text.RegularExpressions.Regex.IsMatch(s,"^M{0,3}(C[MD]|D?C{0,3})(X[CL]|L?X{0,3})(I[XV]|V?I{0,3})$")

Try it online!

Couldn't you shorten {0,3} to {,3}?

@flawr doesn't seem to capture anything then

Ah sorry, only things like {5,} work, but not {,5}.

Should actually be 109 bytes

@ExpiredData well this still confuses me since I see some answers not include dependencies while others do. I will keep it in mind for future answers.

You can add it as compiler flag instead, so it's 72 bytes and the language should be changed to C# (Visual C# Interactive Compiler) with flag /u:System.Text.RegularExpressions.Regex, like this answer :)

In general however, required imports should always be counted in the byte-count. In the C# (Visual C# Interactive Compiler) however it's possible to add most imports as compiler flags. The compiler flags used to count towards the byte-count in the past, but this is no longer the case. They're now counted as a different language instead.

@KevinCruijssen And this, this, this, and this. :)

@EmbodimentofIgnorance Yeah, I know you use them more often, but was looking for an example with the regex in particular. :) But I see your last this-link is with regex as well. :)

Alternate regex: ^M?M?M?(C[MD]|D?C?C?C?)(X[CL]|L?X?X?X?)(I[XV]|V?I?I?I?)$. Same length, but looks weirder (which is the goal, right?)

@KevinCruijssen thank you for the clarification :)

Wolfram Language (Mathematica), 35 bytes
Check[FromRomanNumeral@#<3999,1<0]&

Try it online!
5 bytes saved, thanks to @attinat
the limitation [1,3999] unfortunateley costs 7 bytes...
 here is the code for any roman number
Wolfram Language (Mathematica), 28 bytes
Check[FromRomanNumeral@#,F]&

Try it online!
the above code works for any number, not just [1,3999]

@ExpiredData "The input is a non-empty string that only comprises the characters IVXLCDM."

35 bytes. Boole is also shorter (by one byte) than using If in that way.

Java 8, 70 bytes
s->s.matches("M{0,3}(C[MD]|D?C{0,3})(X[CL]|L?X{0,3})(I[XV]|V?I{0,3})")

Port of @Innat3's C# answer, so make sure to upvote him!
Try it online.
Explanation:
s->                // Method with String parameter and boolean return-type
  s.matches("...") //  Check if the string matches the regex fully
                   //  (which implicitly adds a leading "^" and trailing "$")

M{0,3}             // No, 1, 2, or 3 adjacent "M"
(     |        )   // Followed by either:
 C[MD]             //  A "C" with an "M" or "D" after it
      |            // or:
       D?          //  An optional "D"
         C{0,3}    //  Followed by no, 1, 2, or 3 adjacent "C"
(     |        )   // Followed by either:
 X[CL]             //  An "X" with a "C" or "L" after it
      |            // or:
       L?          //  An optional "L"
         X{0,3}    //  Followed by no, 1, 2, or 3 adjacent "X"
(     |        )   // Followed by either:
 I[XV]             //  An "I" with an "X" or "V" after it
      |            // or:
       V?          //  An optional "V"
         I{0,3}    //  Followed by no, 1, 2, or 3 adjacent "I"

CP-1610 assembly (Intellivision),  52 ... 48  47 DECLEs1 = 59 bytes
Let's try this on a system that predates Perl by a good 7 years. :-)
Takes a pointer to a null-terminated string in R4. Sets the Zero flag if the input is a valid Roman numeral, or clears it otherwise.
                ROMW    10              ; use 10-bit ROM width
                ORG     $4800           ; map this program at $4800

                ;; ------------------------------------------------------------- ;;
                ;;  test code                                                    ;;
                ;; ------------------------------------------------------------- ;;
4800            EIS                     ; enable interrupts

4801            SDBD                    ; R5 = pointer into test case index
4802            MVII    #ndx,     R5
4805            MVII    #$214,    R3    ; R3 = backtab pointer
4807            MVII    #11,      R0    ; R0 = number of test cases

4809  loop      SDBD                    ; R4 = pointer to next test case
480A            MVI@    R5,       R4
480B            PSHR    R0              ; save R0, R3, R5 onto the stack
480C            PSHR    R3
480D            PSHR    R5
480E            CALL    isRoman         ; invoke our routine
4811            PULR    R5              ; restore R5 and R3
4812            PULR    R3

4813            MVII    #$1A7,    R0    ; use a white 'T' by default
4815            BEQ     disp

4817            MVII    #$137,    R0    ; or a white 'F' is the Z flag was cleared

4819  disp      MVO@    R0,       R3    ; draw it
481A            INCR    R3              ; increment the backtab pointer

481B            PULR    R0              ; restore R0
481C            DECR    R0              ; and advance to the next test case, if any
481D            BNEQ    loop

481F            DECR    R7              ; loop forever

                ;; ------------------------------------------------------------- ;;
                ;;  test cases                                                   ;;
                ;; ------------------------------------------------------------- ;;
4820  ndx       BIDECLE test0, test1, test2, test3
4828            BIDECLE test4, test5, test6, test7, test8, test9, test10

                ; truthy
4836  test0     STRING  "MCCXXXIV", 0
483F  test1     STRING  "CMLXXXVIII", 0
484A  test2     STRING  "DXIV", 0
484F  test3     STRING  "CI", 0

                ; falsy
4852  test4     STRING  "MMIXVIII", 0
485B  test5     STRING  "IVX", 0
485F  test6     STRING  "IXV", 0
4863  test7     STRING  "MMMM", 0
4868  test8     STRING  "XXXVX", 0
486E  test9     STRING  "IVI", 0
4872  test10    STRING  "VIV", 0

                ;; ------------------------------------------------------------- ;;
                ;;  routine                                                      ;;
                ;; ------------------------------------------------------------- ;;
      isRoman   PROC

4876            PSHR    R5              ; push the return address

4877            MOVR    R7,       R2    ; R2 = dummy 1st suffix
4878            MOVR    R2,       R5    ; R5 = pointer into table
4879            ADDI    #@tbl-$+1,R5

487B  @loop     MVI@    R5,       R1    ; R1 = main digit (M, C, X, I)
487C            MVI@    R5,       R3    ; R3 = prefix or 2nd suffix (-, D, L, V)

487D            MVI@    R4,       R0    ; R0 = next digit

487E            CMPR    R0,       R3    ; if this is the prefix ...
487F            BNEQ    @main

4881            COMR    R2              ; ... disable the suffixes
4882            COMR    R3              ; by setting them to invalid values
4883            MVI@    R4,       R0    ; and read R0 again

4884  @main     CMPR    R0,       R1    ; if R0 is not equal to the main digit,
4885            BNEQ    @back           ; assume that this part is over

4887            MVI@    R4,       R0    ; R0 = next digit
4888            CMPR    R0,       R1    ; if this is a 2nd occurrence
4889            BNEQ    @suffix         ; of the main digit ...

488B            CMP@    R4,       R1    ; ... it may be followed by a 3rd occurrence
488C            BNEQ    @back

488E            MOVR    R2,       R0    ; if so, force the test below to succeed

488F  @suffix   CMPR    R0,       R2    ; otherwise, it may be either the 1st suffix
4890            BEQ     @next
4892            CMPR    R0,       R3    ; or the 2nd suffix (these tests always fail
4893            BEQ     @next           ; if the suffixes were disabled above)

4895  @back     DECR    R4              ; the last digit either belongs to the next
                                        ; iteration or is invalid

4896  @next     MOVR    R1,       R2    ; use the current main digit
                                        ; as the next 1st suffix

4897            SUBI    #'I',     R1    ; was it the last iteration? ...
4899            BNEQ    @loop

489B            CMP@    R4,       R1    ; ... yes: make sure that we've also reached
                                        ; the end of the input

489C            PULR    R7              ; return

489D  @tbl      DECLE   'M', '-'        ; table format: main digit, 2nd suffix
489F            DECLE   'C', 'D'
48A1            DECLE   'X', 'L'
48A3            DECLE   'I', 'V'

                ENDP

How?
The regular expression can be rewritten as 4 groups with the same structure, provided that # is any invalid character that is guaranteed not be present in the input string.
                 +-------+---> main digit
                 |       |
(M[##]|#?M{0,3})(C[MD]|D?C{0,3})(X[CL]|L?X{0,3})(I[XV]|V?I{0,3})
                   ||  |
                   |+--+-----> prefix or second suffix
                   |
                   +---------> first suffix

The first suffix of the group \$N\$ is the main digit of the group \$N-1\$. Therefore, we can store the patterns with the pair \$(\text{main_digit}, \text{second_suffix})\$ alone.
Our routine attempts to parse the input string character by character according to these patterns and eventually checks whether the end of the string is reached.
Output

screenshot of jzIntv

1. A CP-1610 opcode is encoded with a 10-bit value, known as a 'DECLE'. This routine is 47 DECLEs long, starting at $4876 and ending at $48A4 (included).

wouldn't this be one of the few places where fractional bytes are valid

@ASCII-only I used to think so, but I don't know for sure. See the comments of this answer for some insight about this.

@ASCII-only Also, I've just found this post in meta that tends to confirm it's probably best to round to whole bytes.

ah, so it's only 10 bits when it's in RAM?

The program is never stored in RAM, only in ROM. So it depends on the memory chips used in the cartridge. The CPU is designed to access either 10-bit or 16-bit ROM. The "ROMW 10" directive forces the compiler to generate code in 10-bit format.

R, 74 71 56 bytes
Thanks to @RobinRyder, @Giuseppe, & @MickyT for their suggestions how to use grep effectively with R's built in as.roman.
sub("^M(.+)","\\1",scan(,""))%in%paste(as.roman(1:2999))

Try it online!

as.roman won't work anyway, since it only works up to 3899 for some reason.

I really should read the documentation better, Probably because 4000 doesn't have a definite representation in Roman, so how'd one do 3900. This is similar to 390 and now I just found an issue with my grep where I'd have to anchor the pattern.

@Giuseppe, addressed, using the same regex as the other answers.

I wonder if there's a way to use .romans here...probably not.

@Giuseppe I thought about it but didn't explore very far.

66 bytes using as.roman: first strip the initial M if there is one, then check whether the result is in as.roman(1:2999). This requires special handling of the case where the input is M.

@RobinRyder 56 bytes using paste to coerce to character and tweaking the regex.

@Giuseppe change the regex to ^M(.+) to handle the special M case

@MickyT ah, of course, I never get * versus + right on the first try...

@Giuseppe for me it is trying to remember if it's ? or +

My last question is, who the heck decided that romans would be a useful thing to put into R??? It was added in 2.5.0 (April 2007)...

Is the + necessary at all? I think you can just as well use ^M(.) and save a byte, the rest of the string then doesn't get matched and subsequently isn't replaced.

of course + could be used elsewhere for 53 bytes Try it online!

or different approach for 50 (this one might need some checking but seems to work alright) Try it online!

If anyone is interested I asked StackOverflow a question about the mismatched regex from an earlier edit. You can view it here https://stackoverflow.com/questions/55642649/why-do-upper-bounded-braces-in-r-grepl-function-find-one-more-of-the-repeated-to/55643992#comment97999239_55643992

Wolfram Language (Mathematica), 32 bytes
RomanNumeral@Range@3999~Count~#&

Try it online!

Jelly,  48 47 46  44 bytes
-1 thanks to Nick Kennedy
5Żo7;“ÆæC‘ð“IVXLCDM”ṃ@3Ƥm2”MẋⱮ3¤ṭŻ€ṚŒpF€ḟ€0ċ

A monadic Link accepting a non-empty list of characters consisting only of IVXLCDM which yields either 1 (when it's a valid Roman numeral between \$1\$ and \$3999\$) or 0 (if not).
Try it online! Or see the test-suite.
How?
5Żo7;“ÆæC‘ð“IVXLCDM”ṃ@3Ƥm2”MẋⱮ3¤ṭŻ€ṚŒpF€ḟ€0ċ  - Main Link: list of characters S

5Żo7;“ÆæC‘  - chain 1: f(S) -> X
5Ż          - zero range of five = [0,1,2,3,4,5]
  o7        - OR seven             [7,1,2,3,4,5]
     “ÆæC‘  - list of code-page indices        [13,22,67]
    ;       - concatenate          [7,1,2,3,4,5,13,22,67]

          ð - start a new dyadic chain...

“IVXLCDM”ṃ@3Ƥm2”MẋⱮ3¤ṭŻ€ṚŒpF€ḟ€0ċ - chain 2: f(X,S) -> isValid
“IVXLCDM”                         - list of characters, IVXLCDM
           3Ƥ                     - for infixes of length three:
                                  - (i.e. IVX VXL XLC LCD CDM)
         ṃ@                       -   base decompression with swapped arguments
                                  -   (i.e. use characters as base-3 digits of X's values)
                                  -   (e.g. IVX -> VI I V IX II IV III VII VIII)
             m2                   - modulo two slice (results for IVX XLC and CDM only)
                    ¤             - nilad followed by link(s) as a nilad:
               ”M                 -   character 'M'
                  Ɱ3              -   map across [1,2,3] with:
                 ẋ                -     repeat -> M MM MMM
                     ṭ            - tack
                      Ż€          - prepend a zero to each
                        Ṛ         - reverse
                                  -   -- now we have the table:
                                  -    0 M MM MMM
                                  -    0 DC C D CM CC CD CCC DCC DCCC
                                  -    0 LX X L XC XX XL XXX LXX LXXX
                                  -    0 VI I V IX II IV III VII VIII
                         Œp       - Cartesian product   [[0,0,0,0],...,["M","CM",0,"IV"],...]
                           F€     - flatten €ach  [[0,0,0,0],...,['M','C','M',0,'I','V'],...]
                             ḟ€0  - filter out the zeros from €ach       ["",...,"MCMIV",...]
                                ċ - count occurrences of S

There seems to be a redundant space on the first line. Another byte. Another byte can be saved by using a simpler first line. Try it online!

Thanks, I've saved one more from it.

Perl 5 (-p), 57 bytes
$_=/^M*(C[MD]|D?C*)(X[CL]|L?X*)(I[XV]|V?I*)$/&!/(.)\1{3}/

TIO

uses almost the same regular expression except {0,3} quantifier was changed by *
&!/(.)\1{3}/ to ensure the same character can't occur 4 times in a row.
can't be golfed with -/(.)\1{3}/ because would give-1 for IIIIVI for example

05AB1E, 61 9 8 bytes
ŽF¯L.XIå

Whopping \$\color{green}{\textrm{-52 bytes}}\$ thanks to @Adnan, because apparently 05AB1E's Roman Number builtin wasn't documented, haha.. xD
Try it online or verify all test cases.
Explanation:
ŽF¯       # Push comressed integer 3999
   L      # Create a list in the range [1,3999]
    .X    # Convert each integer in this list to a roman number string
      Iå  # Check if the input is in this list
          # (and output the result implicitly)

See this 05AB1E tip of mine (section How to compress large integers?) to understand why ŽF¯ is 3999.

Original 61 bytes answer:
•1∞Γ'иÛnuÞ\₂…•Ž8вв€SÐ)v.•6#&‘нδ•u3ôNèyè}'M3L×)Rεõš}`3Fâ}€˜JIå

Try it online or verify all test cases.
Explanation:
•1∞Γ'иÛnuÞ\₂…•             '# Push compressed integer 397940501547566186191992778
              Ž8в           # Push compressed integer 2112
                 в          # Convert the integer to Base-2112 as list:
                            #  [1,11,111,12,2,21,211,2111,10]
€S                          # Convert each number to a list of digits
  Ð                         # Triplicate this list
   )                        # And wrap it into a list of lists (of lists)
    v                       # Loop `y` over each these three lists:
     .•6#&‘нδ•              #  Push compressed string "xivcxlmcd"
              u             #  Uppercased
               3ô           #  And split into parts of size 3: ["XIV","CXL","MCD"]
     Nè                     #  Use the loop index to get the current part
       yè                   #  And index the list of lists of digits into this string
    }'M                    '# After the loop: push "M"
       3L                   # Push list [1,2,3]
         ×                  # Repeat the "M" that many times: ["M","MM","MMM"]
          )                 # Wrap all lists on the stack into a list:
                            # [[["I"],["I","I"],["I","I","I"],["I","V"],["V"],["V","I"],["V","I","I"],["V","I","I","I"],["I","X"]],[["X"],["X","X"],["X","X","X"],["X","L"],["L"],["L","X"],["L","X","X"],["L","X","X","X"],["X","C"]],[["C"],["C","C"],["C","C","C"],["C","D"],["D"],["D","C"],["D","C","C"],["D","C","C","C"],["C","M"]],["M","MM","MMM"]]
           R                # Reverse this list
            εõš}            # Prepend an empty string "" before each inner list
                `           # Push the four lists onto the stack
                 3F         # Loop 3 times:
                   â        #  Take the cartesian product of the two top lists
                    }€˜     # After the loop: flatten each inner list
                       J    # Join each inner list together to a single string
                        Iå  # And check if the input is in this list
                            # (after which the result is output implicitly)

See this 05AB1E tip of mine (sections How to compress strings not part of the dictionary?, How to compress large integers?, and How to compress integer lists?) to understand why:

•1∞Γ'иÛnuÞ\₂…• is 397940501547566186191992778
Ž8в is 2112
•1∞Γ'иÛnuÞ\₂…•Ž8вв is [1,11,111,12,2,21,211,2111,10]
.•6#&‘нδ• is "xivcxlmcd"

I'm not sure why .X is not documented, but I think this should work: 3999L.XQO

@Adnan Haha, -52 bytes right there. Completely forgot you indeed told us about adding a Roman Number builtin. Will ask @Mr.Xcoder in chat to add it to the docs. Are any other commands missing? ;) PS: Saved another byte by compressing 3999. :)

Python 2, 81 bytes
import re
re.compile('M{,3}(D?C{,3}|C[DM])(L?X{,3}|X[LC])(V?I{,3}|I[VX])$').match

Try it online!
Let's look at the last part of the regex, which matching the Roman numerals up to 9 (including the empty string)
V?I{,3}|I[VX]

This has two alternatives separated by |:

V?I{,3}: An optional V followed by up to 3 I's. This matches the empty string I,II,III, V, VI,VII,VIII.
I[VX]: An I followed by a V or X. This matches IV and IX.

The same things with X,L,C matching the tens, with C,D,M matches the hundreds, and finally ^M{,3} allows up to 3 M's (thousands) at the start.
I tried generating the template for each trio of characters rather than writing it 3 times, but this was a lot longer.

No need for the ^ anchor at the beginning; match already implies it matches at the beginning of the string.

@ShadowRanger Thanks, I removed the ^.

Although I think you messed up the count in the edit; should be 83, not 81.

@ShadowRanger The count is 81 because the f= isn't included in the code since anonynomous functions are allowed. It's just for TIO.

Ah, makes sense. Annoying there's no way to organize it to hide that in the header or footer, but yeah, unassigned lambdas are legal, so unassigned bound methods of compiled regex should be good too.

well, unassigned lambdas are legal, but only because they're a valid expression that can be used as a function, but imports are used all the time. it's either just something the community has implicitly (?) agreed on, or i must have missed the meta post

Retina, 56 51 bytes
(.)\1{3}
0
^M*(C[MD]|D?C*)(X[CL]|L?X*)(I[XV]|V?I*)$

Port of @NahuelFouilleul's Perl 5 answer, so make sure to upvote him!
Try it online or verify all test cases.
Explanation:
(.)\1{3}        # If four adjacent characters can be found which are the same
0               # Replace it with a 0

^...$           # Then check if the string matches the following fully:
 M*             #  No or any amount of adjacent "M"
 (     |    )   #  Followed by either:
  C[MD]         #   A "C" with an "M" or "D" after it
       |        #  or:
        D?      #   An optional "D"
          C*    #   Followed by no or any amount of adjacent "C"
 (     |    )   #  Followed by either:
  X[CL]         #   An "X" with a "C" or "L" after it
       |        #  or:
        L?      #   An optional "L"
          X*    #   Followed by no or any amount of adjacent "X"
 (     |    )   #  Followed by either:
  I[XV]         #   An "I" with an "X" or "V" after it
       |        #  or:
        V?      #   An optional "V"
          I*    #   Followed by no or any amount of adjacent "I"

Python 3, 116 113 109 107 105 106 bytes
import re
lambda n:re.match(r'(M{,3}(C(M|CC?|D)?|DC{,3}))(X(C|XX?|L)?|(LX{,3}))?(I(X|II?|V)?|VI{,3})?$',n)

Try it online!
-1 byte thanks to ShadowRanger

As I mentioned on the Py2 answer, the leading ^  is unnecessary since match only matches at the beginning of a string already.

@ShadowRanger added anchors while debugging and then didn't try again without them. I'll remember that now - thanks! :)

Well, just to be clear, the trailing $ is necessary (only fullmatch implies anchors on both ends, and obviously that would cost more than a $).

@ShadowRanger Ah! That explains why I needed anchors! Didn't realize I only needed to anchor the end. Thanks again.

perl -MRegexp::Common -pe, 34 bytes
$_=/^$RE{num}{roman}$/&!/(.)\1{3}/

The &!/(.)\1{3}/ part is necessary, because Regexp::Common allows four (but not five) of the same characters in a row. That way, it matches roman numbers used on clock faces, where IIII is often used for 4.

Ruby, (-n) 56 bytes
p~/^M{,3}(D?C{,3}|CM|CD)(L?X{,3}|XC|XL)(V?I{,3}|IV|IX)$/

Try it online!
Outputs 0 (truthy) or nil (falsy).

source: Stack Exchange

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

sort: votes


text:
Can a neural network recognize primes?
Background
Recognizing primality seems like a poor fit for (artificial) neural networks.  However, the universal approximation theorem states that neural networks can approximate any continuous function, so in particular it should be possible to represent any finitely-supported function one desires.  So let's try to recognize all the primes among the first million numbers.
More precisely, because this is a programming website, let's go up to 2^20 = 1,048,576.  The number of primes below this threshold is 82,025 or roughly 8%.
Challenge
How small of a neural network can you find that correctly classifies all 20-bit integers as prime or not prime?
For the purposes of this challenge, the size of a neural network is the total number of weights and biases required to represent it.
Details
The goal is to minimize the size of a single, explicit neural network.
The input to your network will be a vector of length 20 containing the individual bits of an integer, represented either with 0s and 1s or alternatively with -1s and +1s.  The ordering of these can be most-significant-bit first or least-significant-bit first.
The output of your network should be a single number, such that above some cutoff the input is recognized as prime and below the same cutoff the input is recognized as not prime.  For example, positive might mean prime (and negative not prime), or alternatively greater than 0.5 might mean prime (and less than 0.5 not prime).
The network must be 100% accurate on all 2^20 = 1,048,576 possible inputs.  As mentioned above, note that there are 82,025 primes in this range.  (It follows that always outputting "not prime" would be 92% accurate.)
In terms of standard neural network terminology, this would likely be called overfitting.  In other words, your goal is to perfectly overfit the primes.  Other words one might use are that the "training set" and the "test set" are the same.
This challenge does not consider the number of "trainable" or "learnable" parameters.  Indeed, your network is likely to contain hard-coded weights, and the example below is entirely hard-coded.  Instead, all weights and biases are considered parameters and are counted.
The length of the code necessary to train or generate your neural network is not relevant to your score, but posting the relevant code is certainly appreciated.
Baseline
As a baseline, it is possible to "memorize" all 82,025 primes with 1,804,551 total weights and biases.
Note that this code that follows includes many things: a working example, working test code, a working definition of neural network using a known neural network library, a "hard-coded" (or at least, not "trained") neural network, and a working measurement of score.
import numpy as np

bits = 20

from keras.models import Sequential
from keras.layers import Dense

from sympy import isprime

# Hardcode some weights
weights = []
biases  = []
for n in xrange(1<<bits):
    if not isprime(n):
        continue
    bit_list = [(n / (1 << i))%2 for i in xrange(bits)]
    weight = [2*bit - 1 for bit in bit_list]
    bias   = - (sum(bit_list) - 1)
    weights.append(weight)
    biases .append(bias)
nprimes = len(biases)
weights1 = np.transpose(np.array(weights))
biases1  = np.array(biases )
weights2 = np.full( (nprimes,1), 1 )
biases2  = np.array( [0] )

model = Sequential()
model.add(Dense(units=nprimes, activation='relu', input_dim=bits, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
print "Total weights and biases: {}".format( np.size(weights1) + np.size(weights2) + np.size(biases1) + np.size(biases2) )

# Evaluate performance
x = []
y = []
for n in xrange(1<<bits):
    row = [(n / (1 << i))%2 for i in xrange(bits)]
    x.append( row )
    col = 0
    if isprime(n):
        col = 1
    y.append( col )
x = np.array(x)
y = np.array(y)

model.compile(loss='binary_crossentropy', optimizer='sgd', metrics=['accuracy'])

loss, accuracy = model.evaluate(x, y, batch_size=256)
if accuracy == 1.0:
    print "Perfect fit."
else:
    print "Made at least one mistake."

What is a neural network?
For the purposes of this challenge, we can write down a narrow but precise definition of an (artificial) neural network.  For some external reading, I suggest Wikipedia on artificial neural network, feedforward neural network, multilayer perceptron, and activation function.
A feedforward neural network is a collection of layers of neurons.  The number of neurons per layer varies, with 20 neurons in the input layer, some number of neurons in one or more hidden layers, and 1 neuron in the output layer.  (There must be at least one hidden layer because primes and not-primes are not linearly separable according to their bit patterns.)  In the baseline example above, the sizes of the layers are [20, 82025, 1].
The values of the input neurons are determined by the input.  As described above, this will either be 0s and 1s corresponding to the bits of a number between 0 and 2^20, or -1s and +1s similarly.
The values of the neurons of each following layer, including the output layer, are determined from the layer beforehand.  First a linear function is applied, in a fully-connected or dense fashion.  One method of representing such a function is using a weights matrix.  For example, the transitions between the first two layers of the baseline can be represented with a 82025 x 20 matrix.  The number of weights is the number of entries in this matrix, eg 1640500.  Then each entry has a (separate) bias term added.  This can be represented by a vector, eg a 82025 x 1 matrix in our case.  The number of biases is the number of entries, eg 82025.  (Note that the weights and biases together describe an affine linear function.)
A weight or bias is counted even if it is zero.  For the purposes of this narrow definition, biases count as weights even if they are all zero.  Note that in the baseline example, only two distinct weights (+1 and -1) are used (and only slightly more distinct biases); nonetheless, the size is more than a million, because the repetition does not help with the score in any way.
Finally, a nonlinear function called the activation function is applied entry-wise to the result of this affine linear function.  For the purposes of this narrow definition, the allowed activation functions are ReLU, tanh, and sigmoid.  The entire layer must use the same activation function.
In the baseline example, the number of weights is 20 * 82025 + 82025 * 1 = 1722525 and the number of biases is 82025 + 1 = 82026, for a total score of 1722525 + 82026 = 1804551.  As a symbolic example, if there were one more layer and the layer sizes were instead [20, a, b, 1], then the number of weights would be 20 * a + a * b + b * 1 and the number of biases would be a + b + 1.
This definition of neural network is well-supported by many frameworks, including Keras, scikit-learn, and Tensorflow.  Keras is used in the baseline example above, with code essentially as follows:
from keras.models import Sequential
model = Sequential()
from keras.layers import Dense
model.add(Dense(units=82025, activation='relu', input_dim=20, weights=[weights1, biases1]))
model.add(Dense(units=1, activation='relu', weights=[weights2, biases2]))
score = numpy.size(weights1) + numpy.size(biases1) + numpy.size(weights2) + numpy.size(biases2)

If the weights and bias matrices are numpy arrays, then numpy.size will directly tell you the number of entries.
Are there other kinds of neural networks?
If you want a single, precise definition of neural network and score for the purposes of this challenge, then please use the definition in the previous section.  If you think that "any function" looked at the right way is a neural network with no parameters, then please use the definition in the previous section.
If you are a more free spirit, then I encourage you to explore further.  Perhaps your answer will not count toward the narrow challenge, but maybe you'll have more fun.  Some other ideas you may try include more exotic activation functions, recurrent neural networks (reading one bit at a time), convolutional neural networks, more exotic architectures, softmax, and LSTMs (!).  You may use any standard activation function and any standard architecture.  A liberal definition of "standard" neural network features could include anything posted on the arxiv prior to the posting of this question.

What sort of types are these weights?  Usually people use floats can we use other numeric types? e.g. types of less, more or unlimited precision.

@SriotchilismO'Zaic: For the purposes of the narrow definition, I think it makes sense to restrict to float and double (IEEE single- and double-precision floating point real numbers) for all of the weights and intermediate values.  (Although note that some implementations may use other amounts of precision -- eg 80-bit -- during evaluation.)

I love this question but am disappointed there isn't a much smaller neural network to be find with enough training time.

Trial division: score 59407, 6243 layers, 16478 neurons in total
Given as a Python program which generates and validates the net. See the comments in trial_division for an explanation of how it works. The validation is quite slow (as in, running time measured in hours): I recommend using PyPy or Cython.
All layers use ReLU (\$\alpha \to \max(0, \alpha)\$) as the activation function.
The threshold is 1: anything above that is prime, anything below is composite or zero, and the only input which gives an output of 1 is 1 itself.
#!/usr/bin/python3

import math

def primes_to(n):
    ps = []
    for i in range(2, n):
        is_composite = False
        for p in ps:
            if i % p == 0:
                is_composite = True
                break
            if p * p > i:
                break
        if not is_composite:
            ps.append(i)
    return ps

def eval_net(net, inputs):
    for layer in net:
        inputs.append(1)
        n = len(inputs)
        inputs = [max(0, sum(inputs[i] * neuron[i] for i in range(n))) for neuron in layer]
    return inputs

def cost(net):
    return sum(len(layer) * len(layer[0]) for layer in net)

def trial_division(num_bits):
    # Overview: we convert the bits to a single number x and perform trial division.
    # x is also our "is prime" flag: whenever we prove that x is composite, we clear it to 0
    # At the end x will be non-zero only if it's a unit or a prime, and greater than 1 only if it's a prime.
    # We calculate x % p as
    #     rem = x - (x >= (p << a) ? 1 : 0) * (p << a)
    #     rem -= (rem >= (p << (a-1)) ? 1) : 0) * (p << (a-1))
    #     ...
    #     rem -= (rem >= p ? 1 : 0) * p
    #
    # If x % p == 0 and x > p then x is a composite multiple of p and we want to set it to 0

    N = 1 << num_bits
    primes = primes_to(1 + int(2.0 ** (num_bits / 2)))

    # As a micro-optimisation we exploit 2 == -1 (mod 3) to skip a number of shifts for p=3.
    # We need to bias by a multiple of 3 which is at least num_bits // 2 so that we don't get a negative intermediate value.
    bias3 = num_bits // 2
    bias3 += (3 - (bias3 % 3)) % 3

    # inputs: [bit0, ..., bit19]
    yield [[1 << i for i in range(num_bits)] + [0],
           [-1] + [0] * (num_bits - 1) + [1],
           [0] * 2 + [-1] * (num_bits - 2) + [1],
           [(-1) ** i for i in range(num_bits)] + [bias3]]

    for p in primes[1:]:
        # As a keyhole optimisation we overlap the cases slightly.
        if p == 3:
            # [x, x_is_even, x_lt_4, x_reduced_mod_3]
            max_shift = int(math.log((bias3 + (num_bits + 1) // 2) // p, 2))
            yield [[1, 0, 0, 0, 0], [0, 1, -1, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, -1, p << max_shift]]
            yield [[1, -N, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << max_shift, 0]]
        else:
            # [x, x % old_p]
            max_shift = int(num_bits - math.log(p, 2))
            yield [[1, 0, 0], [1, -N, -p_old], [-1, 0, p << max_shift]]
            yield [[1, -N, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0], [1, -p << max_shift, 0]]

        for shift in range(max_shift - 1, -1, -1):
            # [x, rem]
            yield [[1, 0, 0], [0, 1, 0], [0, -1, p << shift]]
            yield [[1, 0, 0, 0], [0, 1, 0, 0], [0, 0, -1, 1]]
            yield [[1, 0, 0, 0], [0, 1, -p << shift, 0]]
        # [x, x % p]
        p_old = p

    yield [[1, 0, 0], [1, -N, -p]]
    yield [[1, -N, 0]]

def validate_primality_tester(primality_tester, threshold):
    num_bits = len(primality_tester[0][0]) - 1
    primes = set(primes_to(1 << num_bits))
    errors = 0
    for i in range(1 << num_bits):
        expected = i in primes
        observed = eval_net(primality_tester, [(i >> shift) & 1 for shift in range(num_bits)])[-1] > threshold
        if expected != observed:
            errors += 1
            print("Failed test case", i)
        if (i & 0xff) == 0:
            print("Progress", i)

    if errors > 0:
        raise Exception("Failed " + str(errors) + " test case(s)")

if __name__ == "__main__":
    n = 20

    trial_div = list(trial_division(n))
    print("Cost", cost(trial_div))
    validate_primality_tester(trial_div, 1)

As an aside, re

the universal approximation theorem states that neural networks can approximate any continuous function

it's easy to show that a neural network using ReLU is Turing complete. The easiest logic gate to implement robustly is NOR: an n-input NOR gate is \$\max\left(0, 1 - \sum a_i\right)\$. I say robustly because this gate accepts inputs greater than 1 but (provided the inputs are not between 0 and 1) only ever outputs 0 or 1. A single-layer AND gate is \$\max\left(0, 1 + \sum(a_i - 1)\right)\$ but only works correctly if its inputs are guaranteed to be 0 or 1, and may output larger integers. Various other gates are possible in one layer, but NOR by itself is Turing-complete so there's no need to go into detail.

As a further aside, I started work on an Euler test before I tried trial division, because I thought it would be more efficient, but raising a number (7 was the best candidate) to a power of (x-(x mod 2)) would require 38 multiplications followed by reduction mod x, and the best network I found for multiplying 20-bit numbers costs 1135, so it's not going to be competitive.

Score 984314, 82027 layers, 246076 neurons in total
We can keep things entirely in the integers if we use activation function ReLU, which simplifies the analysis.
Given an input \$x\$ which is known to be an integer, we can test whether \$x = a\$ with two layers and three neurons:

First layer: outputs \$\textrm{ge}_a = (x - a)^+\$ and \$\textrm{le}_a = (-x + a)^+\$
Second layer: outputs \$\textrm{eq}_a = (-\textrm{ge}_a - \textrm{le}_a + 1)^+\$. \$\textrm{eq}_{a}\$ will be \$1\$ if \$x = a\$ and \$0\$ otherwise.

Layer 1: reduce the 20 inputs to one value \$x\$ with weights 1, 2, 4, ... and bias 0. Cost: (20 + 1) * 1 = 21.
Layer 2: outputs \$\textrm{ge}_2 = (x - 2)^+\$, \$\textrm{le}_2 = (-x + 2)^+\$. Cost (1 + 1) * 2 = 4.
Layer 3: outputs \$\textrm{accum}_2 = (-\textrm{ge}_2 - \textrm{le}_2 + 1)^+\$, \$\textrm{ge}_3 = (\textrm{ge}_2 - (3-2))^+\$, \$\textrm{le}_3 = (-\textrm{ge}_2 + (3-2))^+\$. Cost (2 + 1) * 3 = 9.
Layer 4: outputs \$\textrm{accum}_3 = (2^{21} \textrm{accum}_2 -\textrm{ge}_3 - \textrm{le}_3 + 1)^+\$, \$\textrm{ge}_5 = (\textrm{ge}_3 - (5-3))^+\$, \$\textrm{le}_5 = (-\textrm{ge}_3 + (5-3))^+\$. Cost (3 + 1) * 3 = 12.
Layer 5: outputs \$\textrm{accum}_5 = (2^{21} \textrm{accum}_3 -\textrm{ge}_5 - \textrm{le}_5 + 1)^+\$, \$\textrm{ge}_7 = (\textrm{ge}_5 - (7-5))^+\$, \$\textrm{le}_7 = (-\textrm{ge}_5 + (7-5))^+\$. Cost (3 + 1) * 3 = 12.
...
Layer 82026: outputs \$\textrm{accum}_{1048571} = (2^{21} \textrm{accum}_{1048559} -\textrm{ge}_{1048571} - \textrm{le}_{1048571} + 1)^+\$, \$\textrm{ge}_{1048573} = (\textrm{ge}_{1048571} - ({1048573}-{1048571}))^+\$, \$\textrm{le}_{1048573} = (-\textrm{ge}_{1048571} + ({1048573}-{1048571}))^+\$. Cost (3 + 1) * 3 = 12.
Layer 82027: outputs \$\textrm{accum}_{1048573} = (2^{21} \textrm{accum}_{1048571} -\textrm{ge}_{1048573} - \textrm{le}_{1048573} + 1)^+\$. Cost (3 + 1) * 1 = 4.
The threshold is 0. If working with doubles, overflow to \$+\infty\$ is quite possible, but that seems to be perfectly in accordance with the rules.
Score is (82026 - 3) * 12 + 21 + 4 + 9 + 4.

Cool. As I understand, this also "memorizes" the primes, but it tests for equality "sequentially" rather than in "parallel". (Alternatively, it's like a transpose of the baseline.) The first step is to immediately move away from the bit pattern and just work with the actual integer itself. As a result, there isn't a 20-fold penalty in the equality check. Thanks for your submission

What is superscript plus?

@feersum, that's notation from the Wikipedia page on ReLU linked in the question. $x^+ = \max(0, x)$

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


text:
Make it rain characters
Inspired by this chat mini-challenge.
Given a string as input (ASCII printable characters only), output the string with the letters "raining" down. Each letter must be a random number of lines downward (random between 0 and the length of the string, each having non-zero probability), and only one character per column. All possible outputs must again have a non-zero probability of occurring.
That's maybe a little confusing, so here's an example (taken from that CMC):
Hello World

          d
H
       o
  llo

         l
      W
 e
        r

Note how the H is one space down, the d is zero down, and the llo all happen to line up. The r is the farthest down, at 9, but is still less than the string length away from the top. This is just one example, there are dozens of other possibilities for input Hello World.
Other examples could be:
test

t
 e
  s
   t

PP&CG

  & G
 P

P  C

Input and output can be given by any convenient method.
The input is guaranteed non-empty (i.e., you'll never receive "" as input).
You can print it to STDOUT or return it as a function result.
Either a full program or a function are acceptable.
Any amount of extraneous whitespace is acceptable, so long as the characters line up appropriately (e.g., feel free to pad as a rectangle).
Standard loopholes are forbidden.
This is code-golf so all usual golfing rules apply, and the shortest code (in bytes) wins.

Thought this was going to involve animation when I read the title. Have we had an animated version of this?

@Shaggy Not that I've seen or been able to find.

"Any amount of extraneous whitespace is acceptable" - does that include a leading line of whitespace?

I know we have had one based on the Matrix code, but good luck finding it with those 2 keywords! Do you mind if I Sandbox the idea?

What is the maximum input size answers need to implement? I'm seeing many people use random functions that use "pseudo-random" in the backendground, and certain input words are larger than the size of the seed used in those generators, and they will fail the " All possible outputs must again have a non-zero probability of occurring."  constraint you have specified

@JonathanAllan Leading whitespace is fine.

@Shaggy Go for it!

@Ferrybig One of the standards of the site is you can assume your language doesn't have limitations (e.g., an unlimited-memory computer), in order to implement your designed algorithm. Same should apply here with regard to the size of the PRNG (e.g., 64-bit), so long as the algorithm presented isn't based on that limitation. So far, I've not seen anything wrong with any of the submissions.

R, 104 bytes
function(s){m=matrix(" ",l<-nchar(s),l)
m[cbind(1:l,sample(l,l,T))]=el(strsplit(s,""))
write(m,1,l,,"")}

Try it online!
Input as a string; writes to stdout.

You can save a byte by using scan(,'') and nesting a bunch of calls but honestly I vastly prefer the function approach, this other one is hideous for minimal gain. Might spark some ideas, though. Try it online!

I think sample(l,,T) suffices instead of sample(l,l,T) (-1 byte).

JavaScript (ES6), 72 bytes
Takes input as a list of characters. Returns a matrix of characters.
a=>a.map((_,y)=>a.map((c,x)=>Math.random()<.5|!a[y+1]?(a[x]=' ',c):' '))

Try it online!

I think you could save one byte by not negating the ternary expression.

@orthoplex That wouldn't work because (0|'A') === (0|undefined) and the remaining letters would not be guaranteed anymore to appear on the last row. (So, basically, it's just like |!a[y+1] was removed altogether.)

Google says that Math.random() returns a number in [0, 1), so couldn't Math.random()<.5 become Math.random()>0?

@nedla2004 In theory, yes. In practice, I think it's very likely that the implementation(s) of the PRNG can't possibly return exactly $0$ (let alone close enough $0$'s so that all configurations actually have a chance to occur). Because we define a language by its implementation, I personally think it's therefore invalid.

For what platform did you make your javascript for? Since the challenge has a uniqueness requirement, and does not specify a max input, this really matters, as most platforms are using a math.random() implementation that has an internal state, and thus cannot generate unique output.

@Arnauld That makes sense, I agree that defining the language by what it does makes this dubious at best.

@Arnauld Not just in theory. It is possible to get 0. Extremely small chance, but still positive. I wrote a post about it: https://dev.to/targumon/how-does-math-random-work-1526

Pyth - 9 bytes
Outputs list of lines.
.tm+*;OlQ

 .t                       Transpose, padding with spaces
  m      (Q implicit)     Map over input
   +    (d implicit)      Concatenate to loop var
    *                     String repeat
     ;                    This refers to the var replaced by loop var, which is d=" "
     O                    Random number less than
      lQ                  Length of input

Try it online.

Japt, 8 bytes
-1 byte from @Shaggy
y_iUÊö ç

y_iUÊö ç        Full Program. Implicit input U
y_              transpose and map each row in U (Call it X)
  i             Insert at the beginning of X:
       ç        " " repeated ↓ many times
   UÊö          random integer in [0, length of U]
                implicit transpose back and output

Try it online!

8 bytes

lol @Shaggy I got the same answer a while ago, i was just adding an explanation. Thanks anyway c:

J, 30 19 bytes
|:@,.]{.~"+_2-#?@##

Try it online!

0|:]{.~"+_1-#?# for 15 bytes

@GalenIvanov I love this idea but since the dyad deal takes without repetition, the range of outputs won't span the full range of possibilities.  eg, it won't be possible for 2 letters to have randomly dropped to the same height.

@Conor, You can do 0|:]{.~"+_2-#?@## for 17 bytes without changing the behavior of your answer.

@Jonah Yes, right. I realized that and had another 17-byte solution.

0|:]({.~_2-?)"0# for 16 bytes

APL (Dyalog Unicode), 16 bytesSBCS
Anonymous tacit prefix function
⍉∘↑⊢↑¨⍨∘-∘?≢⍴1+≢

≢ length of string
1+ one added to that
≢⍴ "length" copies of that
∘? random integers in range 1…those, and then…
∘- negate, and then…
⊢↑¨⍨ take than many elements from each character, padding on the left with spaces
∘↑ mix list of strings into matrix, padding with spaces on the right
⍉ transpose
Try it online!

Julia, 69 bytes
f(s)=(n=length(s);z=fill(' ',n,n);for i=1:n z[rand(1:n),i]=s[i]end;z)

This defines a function f that accepts a String or Vector{Char} and returns a Matrix{Char}.
Ungolfed:
function f(s)
    n = length(s)
    z = fill(' ', n, n)  # an n×n matrix of spaces
    for i = 1:n
        # set a random entry in the ith column to the ith character in s
        z[rand(1:n),i] = s[i]
    end
    z
end

Example:
julia> f("test")
4×4 Array{Char,2}:
 't'  ' '  ' '  ' '
 ' '  ' '  ' '  ' '
 ' '  'e'  ' '  't'
 ' '  ' '  's'  ' '

This could surely be better; my golfing skills are pretty rusty.
Try it online!

Ruby, 59 57 55 bytes
->a{a.map{|c|s=[' ']*z=a.size;s[rand z]=c;s}.transpose}

Try it online!
Inputs 1D, outputs 2D array of characters.

Japt, 8 bytes
yÈùUÊö Ä

Try it
yÈùUÊö Ä     :Implicit input of string U
y            :Transpose
 È           :Pass each column through the following function and transpose back
  ù          :  Left pad with spaces to length
   UÊ        :    Length of U
     ö       :    Random number in the range [0,UÊ)
       Ä     :    Plus 1

Jelly, 10 bytes
³LŻX⁶x;)z⁶

Try it online!
      )    | For each input character
³L         | Length of original input
  Ż        | 0..length
   X       | Random number from that list
    ⁶x     | That number of spaces
       ;   | Concatenate to the character
        z⁶ | Finally transpose with space as filler

We can output a leading line of spaces, so 9 bytes (although I feel like there may be an 8...)

@JonathanAllan wouldn’t that be equivalent to the range 0..(length - 1)? The question specifies between 0 and the string length. Or am I missing something?

Oh yes, I forgot about the inclusive-ness - when I asked three days ago about leading whitespace I'm pretty sure I had a 9, and I think it wasnt what I suggested above... hmm

PHP, 88 bytes
for($o='';$i<$l=strlen($argn);$o[$i+$l*rand(0,$l)]=$argn[$i++]);echo chunk_split($o,$l);

Try it online!
Or 94 bytes using PHP's cryptographic random integers function.
for($o='';$i<$l=strlen($argn);$o[$i+$l*random_int(0,$l)]=$argn[$i++]);echo chunk_split($o,$l);

Try it online!
Input from STDIN, output to STDOUT. Run as:
$ echo Hello World|php -nF rain.php
   l  W
  l

 e      r d

H      o

         l

    o

-1 byte (empty string instead of space) and +1 byte (err on side of rules) thx to @ASCII-only!

wonder if this is allowed, since you don't include the <?php that the ?> closes. also seems like it's fine if $o is the empty string

@ASCII-only, you're right, empty string will also work (with a little more complaining). I'm not sure the ruling on using closing and re-opening tags, I'll update it though to stay on the up and up. Thx!

Note that the rules for this challenge say "All possible outputs must again have a non-zero probability of occurring", this is not possible with the PHP rand function, as you can have an input text that requires more random than the size of the internal seed rand uses, so technically your answer fails to satisfy this condition in all situations

@Ferrybig I agree that the legacy PHP/libc rand is not useful for much, however all supported/production versions of PHP (7.1+) use Mersenne Twister RND (mt_rand) internally for a random number generation. Is your concern that this is not sufficiently random for this challenge?

mt_rand also uses an pseudo random number system internally, and also has the limitations. Assuming that PHP is compiled with 64 bit numbers (and that the seed, used for rand or mt_rand accepts this full range) would generate unique outputs for words upto the length of 13 characters or shorter. Pretty limiting if you ask me

Charcoal, 10 9 bytes
↑Ｅθ◧ι⊕‽Ｌθ

Try it online! Link is to verbose version of code. Edit: Saved 1 byte thanks to @ASCII-only. Explanation:
  θ         Input string
 Ｅ          Map over characters
        θ   Input string
       Ｌ    Length
      ‽     Random value
     ⊕      Incremented
    ι       Current character
   ◧        Padded to length
↑           Print rotated

As ASCII-only points out, you can move the letters randomly up instead of down for the same effect (except that there might be extra white space at the bottom rather than the top). Printing an array of characters upwards is equivalent to printing a string normally, so the padding then just offsets each character vertically by a random amount.

wonder if printing up instead would work?

05AB1E (legacy), 9 bytes
εIgÝΩú}ζ»

Input as a string or list of characters (either is fine).
Try it online.
Much slower 9-bytes alternative:
gDÝsãΩúζ»

Input as a list of characters.
Try it online.
Both use the legacy version of 05AB1E, since the new version requires an explicit €S before the ζ..
Explanation:
ε       # Map each character in the (implicit) input to:
 Ig     #  Take the length of the input
   Ý    #  Create a list in the range [0, input-length]
    Ω   #  Pop and push a random integer from this list
     ú  #  Pad the current character with that many leading spaces
}ζ      # After the map: zip/transpose; swapping rows/columns (with space as default filler)
  »     # Then join all strings by newlines (and it output implicitly as result)

g          # Get the length of the (implicit) input-list
 D         # Duplicate this length
  Ý        # Create a list in the range [0, input-length]
   sã      # Take the cartesian product of this list that many times
     Ω     # Pop and push a random list from this list of lists of integers
      ú    # Pad the characters in the (implicit) input-list with that many spaces
       ζ   # Zip/transpose; swapping rows/columns (with space as default filler)
        »  # Then join all strings by newlines (and it output implicitly as result)

Was thinking along the lines of gD¸s∍ÝδΩ but it's longer... and ooo... this doesn't even work in the new 05AB1E ;).

K (oK), 20 bytes
Solution:
+c$(-1-c?c:#x)$++x:

Try it online!
Explanation:
+c$(-1-c?c:#x)$++x: / the solution
                 x: / store input as x
                +   / flip (enlist)
               +    / flip again (break into chars)
              $     / pad (each) character
   (         )      / do this together
           #x       / length of x
         c:         / save as c
      -c?           / choose (?) c times from c
    -1              / subtract from -1
 c$                 / pad to length of x
+                   / flip

Perl 5 -F, 50 49 bytes
-1 by @DomHastings
map$;[rand@F][$i++]=$_,@F;say map$_||' ',@$_ for@

Try it online!

Nice, actually works! :P You can save a couple of bytes with map$_||$",@$_ too!

PowerShell, 108 102 98 bytes
-4 bytes thanks to mazzy
$a=1..($z=($y=$args|% t*y).count)|%{random $z}
1..$z|%{-join($y|%{" $_"[$a[$i++%$z]-eq+$r]});$r++}

Try it online!
Basically iterates 1..length of the string twice, once to get random line locations for each character, and a second time to actually build each line using those indices. Figuring out how to do it in one sweep is where the big byte savings are.

Try it online!?

C (gcc), 131 125 bytes
-6 bytes thanks to ceilingcat
f(char*s){int l=strlen(s),R[l],i=l,j;for(srand(&l);i--;)R[i]=rand()%l;for(;++i<l*l;printf("\n%c"+!!j,i/l^R[j=i%l]?32:s[j]));}

Try it online!

@ceilingcat Cheers!

AWK, 120 118 bytes
{while(i++<NF)r[i]=int(rand()*NF)+1;for(;l++<NF;j=k=0){while(k++<NF)if(r[k]==l){printf"%*c",k-j,$k;j=k}print FS}}

Try it online!
I've included the 5 bytes in the score for the necessary -F '' switch, but I had to use the BEGIN{FS=""} directive for the TIO link since it doesn't process the command-line switch properly.

Python - 92 bytes
import random
lambda s:map(None,*[(random.randrange(len(s))*' '+c).ljust(len(s))for c in s])

You have to include the import random

@MilkyWay90 d'oh

You can save 1 byte by using from random import* instead.

I think map(None,... doesn't work in Python 3, so you should specify Python 2 in your title.

SmileBASIC 3, 62 bytes
LINPUT T$L=LEN(T$)CLS
FOR I=0TO L-1LOCATE,RND(L+1)?T$[I];
NEXT

Red, 84 bytes
func[s][foreach n random collect[repeat n length? s[keep n]][print pad/left s/:n n]]

Try it online!

Python 3, 140 131 bytes
from random import*
def f(s):
	e=range(len(s))
	p=[choice(e)for t in s]
	for r in e:print(''.join((r-p[i]and' 'or s[i]for i in e)))

Try it online!

Python 3, 208 bytes
import random as r;x=input();R=range(len(x));c=[r.choice(R) for i in R];y=[' '*c[i]+x[i]+' '*(len(x)-c[i]) for i in R];R=range(len(y));print('\n'.join([''.join(r) for r in [[y[i][j] for i in R] for j in R]]))

Creates a list of random choices, then makes a list of columns with blank space everywhere except at the index specified by each random choice. The columns are transposed into rows and printed out with newlines between them.
Try it online!