text:
Regex in reverse - decompose regular expressions
The Problem
I have a bunch of regular expressions that I need to use in some code, but I'm using a programming language that doesn't support regex! Luckily, I know that the test string will have a maximum length and will be composed of printable ASCII only.
The Challenge
You must input a regex and a number n, and output every string composed of printable ASCII (ASCII codes 32 to 126 inclusive,  to ~, no tabs or newlines) of length less than or equal to n that matches that regex. You may not use built-in regular expressions or regex matching functions in your code at all. Regular expressions will be limited to the following:

Literal characters (and escapes, which force a character to be literal, so \. is a literal ., \n is a literal n (equivalent to just n), and \w is equivalent to w. You do not need to support escape sequences.)
. - wildcard (any character)
Character classes, [abc] means "a or b or c" and [d-f] means anything from d to f (so, d or e or f). The only characters that have special meaning in a character class are [ and ] (which will always be escaped, so don't worry about those), \ (the escape character, of course), ^ at the beginning of the character class (which is a negation), and - (which is a range).
| - the OR operator, alternation. foo|bar means either foo or bar, and (ab|cd)e matches either abe or cde.
* - match the previous token repeated zero or more times, greedy (it tries to repeat as many times as possible)
+ - repeated one or more times, greedy
? - zero or one times
Grouping with parentheses, to group tokens for |, *. +, or ?

The input regex will always be valid (i.e., you do not have to handle input like ?abc or (foo or any invalid input). You may output the strings in any order you would like, but each string must appear only once (don't output any duplicates).
The Test Cases
Input: .*, 1
Output: (empty string), , !, ", ..., }, ~
Input: w\w+, 3
Output: ww, www
Input: [abx-z][^ -}][\\], 3
Output: a~\, b~\, x~\, y~\, z~\
Input: ab*a|c[de]*, 3
Output: c, cd, ce, aa, cde, ced, cdd, cee, aba
Input: (foo)+(bar)?!?, 6
Output: foo, foo!, foofoo, foobar
Input: (a+|b*c)d, 4
Output: ad, cd, aad, bcd, aaad, bbcd
Input: p+cg, 4
Output: pcg, ppcg
Input: a{3}, 4
Output: a{3}
The Winner
This is code-golf, so the shortest code in bytes will win!

Are we allowed to support escape sequences? Then this is trivial.

@JanDvorak No, you are not, as specified in the challenge and as demonstrated in one of the test cases.

@JanDvorak Actually, I thought I had a rule against built-in regex functions, but apparently not. Edited it in now

Your explanation of | makes very little sense. It doesn't seem to handle nested groups or a|b|c. What's wrong with using the standard explanations in terms of how strongly concatenation and alternation bind? (And you have no excuse for not using the sandbox)

@PeterTaylor Because I have no idea what those standard explanations are? ;) You could edit my post with the "standard" terms, or just link me to a resource on this so I can do it myself.

@PeterTaylor Actually, he has an excuse: http://meta.codegolf.stackexchange.com/q/1305/9498

http://www.regular-expressions.info/quickstart.html

@PeterTaylor Ok, edited to just say "alternation"

I like this Regex Debugger

Judging by your examplesthe pattern has to match the entire string? (As opposed to a substring)

@m.buettner Yes, it does.

@Doorknob You should probably put the {\d,\d} quantifier in the The Challenge section if you're going to have it in the The Test Cases section

@Mouq Why is that? It's a test case, not a rule.

@Doorknob It's contradictory if your rules don't say you need it but the test cases say you do

@Mouq "need it"? Need what? I suppose you could say it falls under the first category ("Literal characters"), but I don't see the need to clarify.

I wasn't trying to nit-pick; I just don't see how "Literal characters" covers "a{3}"

@Mouq Umm... a is a literal character, { is a literal character, .... What would you suggest I add to the post? Sorry, I don't see your point.

Hmm. Puzzles like this make me think I ought to learn regular expressions.

@KyleKanos It's a shame real world problems don't make you think you ought to learn regular expressions. :P But they are not as inaccessible as they might seem: http://www.regular-expressions.info/tutorial.html

Noticed a wee typo in the rules, going over them to check my entry: '...of length less than n'. You meant less than or equal to, going by the examples, and both entries work that way.

@bazzargh Thanks; fixed

What about abcd, 2? Do we have to handle cases like that?

How come ab*a|c[de]* matches the empty string? Is this a bug in the test cases?

Are we required to only output each matched string once? May we output ["aa","a","aa"] for aa|a+?

@JanDvorak Yep, I'm assuming that empty string was a mistake. There cannot be duplicate outputs; edited.

Anybody been able to do this with R?

Haskell 757 705 700 692 679 667
import Data.List
data R=L Char|A R R|T R R|E
h=[' '..'~']
k(']':s)a=(a,s)
k('^':s)_=l$k[]s
k('-':c:s)(a:b)=k([a..c]++b)s
k('\\':c:s)a=k s$c:a
k(c:s)a=k s$c:a
l(a,b)=(h\\a,b)
c#E=L c
c#r=A(L c)r
o(a,b)=(foldr(#)E a,b)
t%0=E
t%n=A(t%(n-1))$T t$t%(n-1)
d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s$m r a;r s=w$e s E;w(u,'|':v)=(\(a,b)->(A u a,b))$r v;w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f$b s;e[]t=(t,[]);g t(u,v)=e v$T t u;f(t,'*':s)=(t%n,s);f(t,'+':s)=(T t$t%n,s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o$k s[];b(s:t)=(L s,t)}

output:
ghci> d ".*" 1
[""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"]
ghci> d "w\\w+" 3
["ww","www"]
ghci> d "[abx-z][^ -}][\\\\]" 3
["x~\\","y~\\","z~\\","b~\\","a~\\"]
ghci> d "ab*a|c[de]*" 3
["aa","aba","c","ce","cd","cee","cde","ced","cdd"]
ghci> d "(foo)+(bar)?!?" 6
["foo!","foobar","foo","foofoo"]
ghci> d "(a+|b*c)d" 4
["ad","aad","aaad","cd","bcd","bbcd"]
ghci> d "p+cg" 4
["pcg","ppcg"]
ghci> d "a{3}" 4
["a{3}"]

Explanation: this one's a textbook regex implementation. R is the regex type, with constructors A (alternate), L (literal), T (then) and E (empty/epsilon). The usual 'Star' doesn't appear because I inline it as alternates during the parse (see '%'). 'm' runs the simulation. The parser (start at 'r s=....') is just recursive descent; 'k' parses ranges. The function '#' expands ranges into alternations.

Python v2.7 1069 1036 950 925 897 884 871 833 822
This answer seems rather long for a code golf, but there are a lot operators that need to be handled and I know what purpose each byte in this answer does. Since there is no existing answer I submit this as a target for other users to beat. See if you can make a shorter answer :).
The two main functions are f which parses the regex starting at the ith character, and d which generates the matching strings, using r the sub-regexes we can recursed into, 'a' the array representing the part of the current sub-regex not yet processed, and a string suffix s which represents the part of the string generated so far.
Also check out the sample output and a test harness.
import sys;V=sys.argv;n=int(V[2]);r=V[1];S=len;R=range;C=R(32,127)
Z=[];z=-1;D='d(r,p,';F='for j in '
def f(i,a):
 if i>=S(r):return a,i
 c=r[i];x=0;I="|)]".find(c)
 if c in"([|":x,i=f(i+1,Z)
 if I+1:return([c,a,x],[a],[c,a])[I],i
 if'\\'==c:i+=1;x=c+r[i]
 return f(i+1,a+[x or c])
def d(r,a,s):
 if S(s)>n:return
 while a==Z:
        if r==Z:print s;return
        a=r[z];r=r[:z]
 e=a[z];p=a[0:z]
 if'|'==a[0]:d(r,a[1],s);d(r,a[2],s)
 elif']'==a[0]:
        g=a[1];N=g[0]=='^';g=(g,g[1:])[N];B=[0]*127;O=[ord(c[z])for c in g]
        for i in R(0,S(g)):
         if'-'==g[i]:exec F+'R(O[i-1],O[i+1]):B[j]=1'
         else:B[O[i]]=1
        for c in C:N^B[c]<1or d(r,Z,chr(c)+s)
 elif' '>e:d(r+[p],e,s)
 else:c=p[:z];exec{'.':F+'C:'+D+'chr(j)+s)','?':D+'s);d(r,p[:z],s)','*':F+'R(0,n+1):d(r,c,s);c+=[p[z]]','+':"d(r,p+['*',p[z]],s)"}.get(e,D+'e[z]+s)')
d(Z,f(0,Z)[0],"")

Note that tabs in the original solution have been expanded. To count the number of characters in the original use unexpand < regex.py | wc.

I've never seen python look that horrible.

Can't you change def E(a,b):c=a[:];c.extend(b);return c to E=lambda a,b:a[:].extend(b) , ditto for A

Apparently not, as .extend(b) does not return anything.

How about E=lambda a,b:a[:]+b?

For the elif isinstance(e,str):, I believe you could change the code inside to: exec{'.':'for c in C:d(r,p,s+chr(c))','?':'d(r,p,s);d(r,p[:z],s)','*':'''c=p[:z]#newline for i in R(0,n+1):d(r,c,s);c+=[p[z]]''','+':"d(r,p+['*',p[z]],s)",'\\':'d(r,p,e[1]+s)'}.get(e,'d(r,p,e+s)')(note that the #newline is a newline) (source: http://stackoverflow.com/a/103081/1896169)

If you could find more places to use the exec trick, we could easily change your code into unreadable code :-)

Prolog (SWI), 586 bytes
The built in backtracking ability of Prolog makes it an awesome choice for this challenge. By taking advantage of backtracking, generating strings for a regex becomes exactly the same task as testing if a string is matched by a regex. Unfortunately, much of my golfing effort went into writing a shorter regex parsers. The actual task of decomposing a regular expression we easily golfed.
R-L-S:-R*A,-(B,A,[]),setof(Z,(0/L/M,length(C,M),C+B+[],Z*C),S).
-R-->e+S,S-R.
R-T-->{R=T};"|",e+S,u+R+S-T.
Z+Y-->(".",{setof(C,32/126/C,R)};"[^",!,\E,"]",{setof(C,(32/126/C,\+C^E),R)};"[",\R,"]";"(",-R,")";{R=[C]},([C],{\+C^`\\.[|+?*(`};[92,C])),("*",{S=k*R};"+",{S=c+R+k*R};"?",{S=u+e+R};{S=R}),({Y=c+Z+S};c+Z+S+Y).
\C-->{C=[H|T]},+H,\T;{C=[]};+A,"-",+B,\T,{setof(C,A/B/C,H),append(H,T,C)}.
+C-->[92,C];[C],{\+C^`\\]-`}.
S+e+S.
[C|S]+D+S:-C^D.
S+(B+L+R)+T:-B=c,!,S+L+U,U+R+T;S+L+T;S+R+T.
S+k*K+U:-S=U;S+K+T,S\=T,T+k*K+U.
A/B/C:-between(A,B,C).
A^B:-member(A,B).
A*B:-string_codes(A,B).

Try it online!
Ungolfed Code
generate_string(R, L, S) :-
    % parse regex
    string_codes(R, RC),
    regex_union(RE, RC, []),

    % bound string length
    between(0, L, M),
    length(SC, M),

    % find string
    match(SC, RE, []),

    string_codes(S, SC).

% Parsers
%%%%%%%%%

regex_union(R) -->regex_concat(S), regex_union1(S, R).

regex_union1(R,T) --> [124], regex_concat(S), regex_union1(regex_union(R,S), T).
regex_union1(R, R) --> [].

regex_concat(R) --> regex_op(S), regex_concat1(S, R).

regex_concat1(R, T) --> regex_op(S), regex_concat1(regex_concat(R,S), T).
regex_concat1(R, R) --> [].

regex_op(regex_kleene(R)) --> regex_lit(R), [42].
regex_op(regex_concat(R,regex_kleene(R))) --> regex_lit(R), [43].
regex_op(regex_union(regex_empty,R)) --> regex_lit(R), [63].
regex_op(R) --> regex_lit(R).

regex_lit(regex_char([C])) --> [C], {\+ regex_ctrl(C)}.
regex_lit(regex_char([C])) --> [92], [C].

regex_lit(regex_char(CS)) --> [46], {findall(C, between(32,126, C), CS)}.

regex_lit(regex_char(DS)) -->
    [91], [94], !, class_body(CS), [93],
    {findall(C, (between(32, 126, C), \+ member(C, CS)), DS)}.
regex_lit(regex_char(CS)) --> [91], class_body(CS), [93].

regex_lit(R) --> [40], regex_union(R), [41].

class_body([C|T]) --> class_lit(C),class_body(T).
class_body(CS) -->
    class_lit(C0), [45], class_lit(C1), class_body(T),
    {findall(C, between(C0, C1, C), H), append(H,T,CS)}.
class_body([]) --> [].

class_lit(C) --> [C], {\+ class_ctrl(C)}.
class_lit(C) --> [92], [C].

class_ctrl(C) :- string_codes("\\[]-", CS), member(C, CS).
regex_ctrl(C) :- string_codes("\\.[]|+?*()", CS), member(C, CS).

% Regex Engine
%%%%%%%%%%%%%%

% The regex empty matches any string without consuming any characters.
match(S, regex_empty, S).

% A regex consisting of a single character matches any string starting with
% that character. The chanter is consumed.
match([C|S], regex_char(CS), S) :- member(C, CS).

% A union of two regex only needs to satisify one of the branches.
match(S, regex_union(L,R), T) :- match(S, L, T); match(S, R, T).

% A concat of two regex must satisfy the left and then the right.
match(S, regex_concat(L, R), U) :- match(S, L, T), match(T, R, U).

% The kleene closure of a regex can match the regex 0 times or it can the regex
% once before matching the kleene closure again.
match(S, regex_kleene(_), S).
match(S, regex_kleene(K), U) :- match(S, K, T), S \= T, match(T, regex_kleene(K), U).

I am not familiar with Prolog DCGs, how does regex_union(RE, RC, []) match against regex_union(R) -->...?

@KritixiLithos DCG predicates have two implicit parameters that are supplied automatically when called from within a DCG or as part of phrase\2. The first is the string the DCG is applied to and the second is some suffix of the string that remains after satisfying the DCG predicate. An equivalent construct would be phrase(regex_union(RE), RC).

By the way, you might be interested in solving https://codegolf.stackexchange.com/q/161108/, the challenge asks for a simpler regex, so parsing would be easier, and this sounds like something prolog can do nicely

@KritixiLithos yeah, regex complement is definitely an interesting task. I've implemeneted the regex->nfa->dfa->complement->regex pipeline and it's not exactly short. I want to look into some more terse implementations before posting.

I have been trying to go about it using brute-force; I have an algorithm in mind, but implementing the brute-force part in prolog hasn't been successful so far. Hm, it would be nice if there is a reversible predicate to convert regex <=> dfa. Interesting to see what comes of both our solutions

source: Stack Exchange

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

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

sort: votes


text:
Roll Dungeons and Dragons dice
I want to play Dungeons and Dragons, but I don't have any dice! Your challenge is to roll some D&D dice.
The input format specification in Backus-Naur form is:
<valid-input>  ::= <opt-integer> "d" <integer> <opt-modifier>
<opt-integer>  ::= | <integer>
<opt-modifier> ::= | "+" <integer>
<integer>      ::= "0" | "1" | "2" | "3" | "4" | "5" |
                   "6" | "7" | "8" | "9" | <integer> <integer>

The optional integer before the d is the number of dice to roll; it must be at least 1, and defaults to 1 if not supplied.
The required integer immediately after the d is the number of sides each die has; it must be at least 1. The sides of each die are distinct consecutive positive integers starting at 1.
The optional modifier may be +0, and it defaults to +0 if not specified.
For example, for the input 2d10+5, you generate two random numbers from 1 to 10 inclusive, add them together, and add 5. Then you will output the result.
If you receive invalid input, such as 2d, d20+, 0d4, 2d5+1+2, 2+2, or anything else that doesn't fit this format, you must output "Invalid input". Otherwise, you must output only a single random integer, weighted according to the input. For example, 3d6 should produce more 10s than 4s.
Test cases
Input      Minimum possible output    Maximum possible output
d1         1                          1
d6         1                          6
d1+3       4                          4
d20+3      4                          23
2d1        2                          2
2d6+2      4                          14
d01        1                          1
d01+0      1                          1
01d01+01   2                          2
3d20+10    13                         70

d          Invalid input
d0         Invalid input
d+0        Invalid input
d0+0       Invalid input
0d1        Invalid input
0d1+1      Invalid input
d1+        Invalid input
1d         Invalid input
1d1+       Invalid input
1d+1       Invalid input
2d+2d      Invalid input
d2+d2      Invalid input
d2+2+2     Invalid input
d2-1       Invalid input
-d2        Invalid input
-2d2       Invalid input
4*3        Invalid input
4*d2       Invalid input

This is code-golf, so the shortest code in bytes will win!

Is 2d10-5 a valid input? -- Oops, I missed the part where you said p is 0 or more. Nevermind.

Is 02d05+073 a valid input?

Can you throw a 13 sided die? Or a 17 sided die?

The hard part about this question is validating the input, but the paragraph which describes the validation rules is self-contradictory. It describes n and p as optional, but input which choose not to include them (d20+) as invalid.

@PeterTaylor: I think the + sign should only be added if the modifier p is provided.

@MT0 Yes; 02 is a number >= 1.

@Averroes Of course, why not?

@PeterTaylor Edited post to clarify ("...and preceded by a + sign.")

@Doorknob, Well, because d13 and d17 aren't dice used in D&D. D&D uses d4, d6, d8, d10, d12, and d20. Also, there are certainly cases where a roll would include different types of dice (eg, 1d4+1d6 for a Rogue sneak attacking with a dagger) or having a negative p (eg, 1d20-1 for a skill check with no ranks/training and a negative ability modifier).

@BrianS well you also sometimes see the odd d3 which is done using a normal die and dividing by 2 (rounding up). I'm not entirely sure but I may have seen d2 as well which is just flipping a coin (or using a similar method as above). But yes d13 and d17 are a bit unusual.

@m.buettner, I think 3.5/PF might use d2/d3 for whips, but the standard is to simulate those with d4/d6 (particularly when considering a "standard set" available at hobby shops). 4e doesn't have dice below d4, although it does have things like Weakened condition/half damage.

You're going to play dnd without the usecase of 2d8 + 1d6 + 4? You're gonna have a bad time

2d6+2      4                          12 is wrong; max should be 14.

@CeesTimmerman, concur. Fixed.

Similar to Halloween Golf: The 2spooky4me Challenge! and the Universal Spooky Meme Translator

Perl, 109 95 93 96 89 bytes
s/^d/1d/;/^(\d+)d(\d+)(\+\d+)?$/;$d+=1+rand$2|0for
1..$1;$_=$1*$2?$d+$3:'Invalid input'

Requires the -p switch, which accounts for two of the bytes. Try it online on Ideone.
How it works

Because of the -p switch, a line is read from STDIN and stored in $_.
The command s/^d/1d/ prepends a 1 to $_ if it begins with a d, i. e., if the number of dice has not been specified.
The regular expression /^(\d+)d(\d+)(\+\d+)?/ checks if the line consists of a number, a literal d, another number and, optionally, a third number preceded by a + sign.
If there is a match, the numbers will be saved in $1, $2 and $3.
In this case, the input will be valid if and only if $1 and $2 are both positive.
$d += 1 + rand $2 | 0 adds a pseudo-randomly chosen integer from 1 to the specified number of sides to $d (initially treated as zero).
for 1 .. $1 does the above once for every integer between 1 and the number of dice.
The command $_ = $1 * $2 ? $d + $3 : 'Invalid input' does the following:

If $1 * $2 is zero, it sets $_ to Invalid input.
Otherwise, the input is valid and it sets $_ to the sum of the dice rolls and the modifier.

Because of the -p switch, Perl prints the contents of $_.
Since there a no further input lines, the script exits.

I believe that, in general, extra command line parameters are considered to be worth a byte each but the hyphen is free. In this case, -p would only cost you one, making this a 108 byte solution.

You can use 1..$1||1 instead of 1..$1?$1:1, 2 chars shorter

Can be made 96 chars, /^([1-9]\d*)?d([1-9]\d*)(\+\d+)?$/||die"Invalid input$/";$a+=1+int rand$2for(1..$1||1);$_=$a+$3

@undergroundmonorail: I've seen people counting a single command-line switch as one, two and even three (counting the whitespace) bytes. I'd rather count it as one, but two bytes seems fair to me.

@Hasturkun: Thanks. Parentheses and curly brackets... Not sure what I was thinking. This is Perl!

Your count is too high: the current program is only 87 chars. I assume you've counted a Windows newline and an EOF.

@PeterTaylor: I've counted the -p switch as two bytes.

I assume you haven't tested this.  |0 is not the same as ||0.

@Vynce I assume you haven't either. I use |0 to cast to int, since rand returns a pseudo-randomly chosen float.

Actually, you're right -- but for the wrong reason. ( : I noticed that rand gave floats, and was trying to test the program, and was wondering how you were getting around it; i'm trying to run it and getting lots of syntax errors on the command line.
ETA: ah.  I'm used to perl golfing a -e and this has to be actually a file to work as written

@Vynce I've added a permalink to the question (http://ideone.com/gLJfhO). -e would be problematic here, unless you replace the single quotes with double quotes.

Fortran: 145
character(1)a;read(*,*)s,a,j,a,k;n=0;if(k<0.or.a=="-")then;print*,"error k<0";stop;endif;do l=1,int(s);n=n+int(s*rand(0)+1);enddo;print*,n+k;end;

Abuses implicit typing (i-n are all integers, everything else a real). Minor caveat: input must be space separated, so 2d10+5 must be entered as 2 d 10 + 5, otherwise you'll get an input conversion error.

The basic logic is cool, but this does not handle d 1 correctly (nor several other inputs), nor is the output random. Also no need for ; at the end. Examples

Ruby, 116
Alternative Ruby version.  I was trying to find a way to do it without the regular expressions, but the validation you have to do is a lot harder without them.
gets=~/^(\d+)?d(\d+)(\+\d+)?$/
a=$1||?1
puts$~&&a>?0?eval("r=#{$3||0};#{a}.times{r+=rand(#$2)+1};r"):'Invalid input'

This one is 112, using Dennis' clever Perl algorithm:
$p='(\d*[1-9]\d*)'
puts~/^#$p?d#$p(\+\d+)?$/?eval("r=#{$3||0};#{$1||1}.times{r+=rand(#$2)+1};r"):'Invalid input'

@m.buettner Thanks!  I don't know why I thought it had to be >0.

GolfScript (120 106 bytes)
.100?!1`*\+.43?)!'+0'*+.10,'d+':^*-!*.10,''*-^=*^1/{/n*}/~].,3=*3,or:x~;*{x~\{rand)+}+@*}'Invalid input'if

This is not only shorter than the first version, but also more elegant. The part which actually does the die rolling is
\{rand)+}+@*

The rest is mainly input validation, and a few characters for parsing.
# Start by converting valid inputs into valid inputs with all optional bits.
# Prepend a '1' if the string starts with 'd'.
.100?!1`*\+
# Append '+0' if there's no '+' in the string.
.43?)!'+0'*+
# Now we start knocking out the invalid inputs.
# If it contains a character other than [0-9d+], replace the string with ''.
.10,'d+':^*-!*
# If it doesn't contain exactly one 'd', exactly one '+', and the 'd' before the '+',
# replace the string with ''.
.10,''*-^=*
# Now we either have a valid string, an empty string, or a string which is almost valid
# but has some empty substrings which should be integers, or a forbidden 0 integer value.
# Replace the 'd' and '+' with newlines, eval the result, and gather into an array.
^1/{/n*}/~]
# If we had any empty parts, we'll have fewer than 3 items on the stack.
# In that case, replace with integer values which will fail the final validation step.
.,3=*3,or
# Final validation: number of dice * number of sides per die != 0.
:x~;*
# If we pass, do the actual die rolling. Otherwise give the error message.
{x~\{rand)+}+@*}'Invalid input'if

Online demo with test framework

I'm wondering why you don't use n./? Maybe also 10,n* for one character less.

@Howard, to the first, because it was a last minute hack to pass some test cases and I didn't think about golfing it. To the second, that would make it accept some invalid input.

Java, 378
Just wanted to try a solution with Java far from the best solution. But hey: Java isn't a golfing language in any case!
It gets the input from command line. First parameter args[0] is the input value.
class A{public static void main(String[]s){System.out.print(s[0].matches(
"(0+\\d+|[1-9]\\d*|)d(0+\\d+|[1-9]\\d*)(\\+\\d+)?")?z(s[0]):"Invalid input");}static int
z(String s){String[]a=s.split("d");String[]b=a[1].split("\\+");int c=a[0].isEmpty()?1:Byte.
decode(a[0]);int d=b.length<2?0:Byte.decode(b[1]);while(c-->0)d+=new java.util.Random().
nextInt(Byte.decode(b[0]))+1;return d;}}

Did you know, that decode is shorter than valueOf?

J - 130 (45?) char
This challenge seems to be a little biased towards regular expressions, especially with having to differentiate invalid input. J has a POSIX regex library, so it's not that bad, but it's not integrated as it is with Perl, so J fares no better than other languages.
+/@,`(1+?@#~)/`('Invalid input'"_)@.(0 e.$)0 1 1>.".>|.}.((,'?d','(\+[0-9]+)?$',~}.)'^([0-9]*[1-9][0-9]*)')(rxmatch rxfrom])1!:1]1

If you're just implementing the logic for valid expressions, like the Python/PHP solutions appear to, it's the more reasonable 45 chars:
+/,(1+[:?@#/1>.".;._2@,&'d')`".;._1'+',1!:1]1

Notable bits:

1!:1]1 is the input, and (rxmatch rxfrom]) is the logic that returns the subexpression matches.
Whether or not the input was legal is handled by the regex matching, so we can set the defaults for n and p with 0 1 1>.. It looks backwards (n is 1 by default and p is 0) because we had to reverse (|.) the list earlier, so that the logic at the end executes in the right order.
@. is the Agenda conjunction, essentially a J-ish switch statement. If the matches are empty (if 0 is an e.lement of the $hape: 0 e.$), we emit the error message, else we go through with rolling the dice: #~ to set out the dice, 1+? to roll, and +/@, to add the modifier p and sum.

Does that work for 01d01+01?

@CeesTimmerman My bad. It does now.

TinyMUSH, 239
@dig/t +
@op d=+
@lo d=d
@fail d=Invalid input
@cr .
@set .=com
&d .=$*:\ifelse(regmatch(%0,^(\\\\d+)?d(\\\\d+)(\\\\+\\\\d+)?$,0 1 2 3),ifzero(and(or(not(strlen(%q1)),%q1),%q2),Invalid input,add(die(usetrue(%q1,1),%q2),%q3)),Invalid input)

The first four lines deal with the fact that "d" is an alias for the universal "down" exit with a built-in failure message when it doesn't exist; exits are scanned before user-defined commands.  The remaining lines create an object with a user-defined command making use of the built-in die() function.

PHP, 129
<?eval(preg_filter(~Ð¡×£›ÔÖÀ›×£›Ö×£Ô£›ÔÖÀÛÐ,~ÛžÂÝÛÎÝÀÅÎÄ™×ÄÛ–ÔÔÃÛžÄÛŒÔÂž‘›×ÎÓÛÍÖÖÄšœ—ÛŒÛÌÄ,$_GET[0])?:~šœ—Ý¶‘‰ž“–›ß–‘Š‹ÝÄ);

Uses a regex to create a expression which PHP then evaluates.
Input is fed in via url: ?0=argument. Make sure you urlencode the + to %2b.
Here's what it looks like in a more readable form:
eval(preg_filter('/^(\\d)?d(\\d)(\\+\\d)?$/','$a="$1"?:1;for(;$i++<$a;$s+=rand(1,$2));echo$s$3;',$_GET[0])?:'echo"Invalid input";');

Bitwise inverting the strings using ~ not only saves a character because you don't need quotes (PHP assumes they are strings) but also saves characters because you don't have to escape the backslashes in the regular expression.
The ?: operator is a special form of the ternary operator. $foo = $a ? $a : $b is the same as $foo = $a ?: $b.

Python 3, 184 bytes
import random,re
try:a,b,c=re.findall("^(\d*)d(\d+)(\+\d+)?$",input())[0];t=int(c or 0)+(sum(random.randint(1,int(b))for i in range(int(a or 1)))or q)
except:t="Invalid input"
print(t)

Passes all tests. If zero dice were allowed, it would be 6 bytes shorter by leaving out (or q).

I misunderstood the BNF, though. This page helps.

For the benefit of anyone else who wonders why the regex is anchored at one end but not the other: Python's re.match implicitly anchors at the start but not at the end. I'm not aware of any other regex library which does that.

There's a small saving by initialising t=int(c or 0); and it might be possible to combine your answer with the existing Python one (which uses less whitespace) to save a couple more.

Ruby, 167 147
/^(\d+)?d(\d+)(\+\d+)?$/.match gets
abort'Invalid input'if !$~||$1==?0||!$2||$2==?0
p eval(([0]*($1||1).to_i).map{rand($2.to_i)+1}*?+)+($3||0).to_i

Uses a regexp to do all the work. Since I'm using \d+, the only things I need to check for invalid input are that there was a match, that neither n nor m were 0, and that there was an m. If any of those are found, it aborts with a message ('Invalid input'). Then it just prints the result, since it would have aborted by now if the input was invalid.
The result-printing isn't that interesting, but...
([0]*($1||1).to_i)    # create an array of n elements (1 if there is no n)
.map{rand($2.to_i)+1} # fill it up with random numbers, where the number x is 1 < x < m+1
.inject(:+)           # add them all up
+($3||0).to_i         # and finally add the modifier (0 if there is none)

I later changed .inject(:+) to eval(...*?+), but the idea is the same.

Vyxal V, 89 bytes
h\d=[1p|]⁽±Ḋ→a⟨←aL5=|←a⌊±T⟨0|2|4⟩=|←a1i\d=|←a3i\+=⟩A[←a0i⌊ʁ(←a2i⌊℅⅛)¾∑←a4i⌊+,|«¢q⁰∷Ṗ-←¥«,

Try it Online!
Ties Perl
h\d=[1p|]         # Checks if the first character is a d, and prepends a 1
        ⁽±Ḋ→a     # Splits the string on non-numeric values, so consecutive digits stay grouped, then casts the list to variable "a"

     ⟨←aL5=|           # is it Length 5 (3 numbers, the "+" and the "d")
       ←a⌊±T⟨0|2|4⟩=|  # convert the numbers-as-strings to numbers and check if the numbers are in positions 1 3 and 5 (0 indexed)
         ←a1i\d=|     # is the second item in the list  "d"
           ←a3i\+=⟩    # is the fourth item "+"
                A     # are all of these checks true?

  [←a0i⌊ʁ               # If all the checks are true, create a range from 0-a[0]
        (←a2i⌊℅⅛)       #  for i in said range, generate a random number 0-a[2] and push to global array
             ¾∑←a4i⌊+,  # push global array, sum the values, and add a[4]

            |«¢q⁰∷Ṗ-←¥«, # If any of the checks are false, print "invalid input"
```

Zsh, 205 223 bytes
set -e;e=Invalid\ input;trap '<<<$e' ERR
echo "^0d\n+$\nd+\n+d\n+.+\n[-|*]">p;[[ `grep -cfp<<<$1`>0 ]]&&<<<$e&&exit
q=(${(s: :)${1//(#s)d/1d}//[^0-9]/ });for i ({1..$q[1]})((s+=RANDOM%q[2]+1))
<<<$[s+q[3]]

Try it Online (with all test cases)
Writing the validation code was a chore. Without this guff, the solution would be a svelte 89 bytes:
q=(${(s: :)${1//(#s)d/1d}//[^0-9]/ });for i ({1..$q[1]})((s+=RANDOM%q[2]+1))
<<<$[s+q[3]]

Python3, 204B
Mine beats the existing Python answer by adding in the required error handling and reading d20 as 1d20 rather than 0d20 :)
import random,re
try:a,b,c=re.findall('^([1-9]\d*)?d(\d+)(\+\d+)?$',input())[0];I=int;R=sum(random.randrange(I(b))+1for x in[0]*(1if a==''else I(a)))+(0if c==''else I(c))
except:R='Invalid input'
print(R)

edited to fix 2 typos: I(x) => I(c), Invalid Input => Invalid input
edited to fix regex: \+?(\d*) => (\+\d+)?

According to the clarified question, this is an incorrect answer because it accepts the input 3d20+.

Good point! #filler

And not 01d01+01.

Go, unseeded, 366 bytes
import(."regexp";."strconv";."math/rand")
func f(s string)int{k:=MustCompile(`^(\d*)d(\d+)(\+\d+)?$`).FindAllStringSubmatch(s,-1)
if len(k)<1||k[0][2]==""{return-1}
r:=k[0]
var n,l,f,m,t int
l=len(r)
n,_=Atoi(r[1])
if n<1&&r[1]==""{n=1}else if n<1{return-1}
if l>2{f,_=Atoi(r[2])}
if f<1{return-1}
if l>3{m,_=Atoi(r[3])}
for i:=0;i<n;i++{t+=Intn(f)+1}
t+=m
return t}

Attempt This Online!
Go, seeded, 393 bytes
import(."regexp";."strconv";."math/rand";."time")
func f(s string)int{k:=MustCompile(`^(\d*)d(\d+)(\+\d+)?$`).FindAllStringSubmatch(s,-1)
if len(k)<1||k[0][2]==""{return-1}
r:=k[0]
var n,l,f,m,t int
l=len(r)
n,_=Atoi(r[1])
if n<1&&r[1]==""{n=1}else if n<1{return-1}
if l>2{f,_=Atoi(r[2])}
if f<1{return-1}
if l>3{m,_=Atoi(r[3])}
Seed(Now().Unix())
for i:=0;i<n;i++{t+=Intn(f)+1}
t+=m
return t}

Attempt This Online!

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


text:
Hiding information in Cats
You are a secret agent trying to communicate with your fatherland. Of course the information needs to be hidden so no one eaves drops your message. What would be better suited than a cat? Everyone loves funny pictures of cats [citation needed], so they won't suspect secret information hiding in there!

Inspired by the algorithm the game Monaco uses to save the level information of shared levels it is your tasks to write a program that encoded information into the least significant bit of the colors of an image.
Encoding format:

The first 24 bits determine the length of the remaining encoded byte-string in bits
The image is read from left to right and from top to bottom, obviously starting in the upper left pixel
The channels are read from red to green to blue
The least significant bit from each channel is read
Bits are saved in Big Endian order

Rules:

Your program takes a single byte-string to be encoded and a single image filename for the base image
The resulting image must be come out as a true color PNG file
You may use I/O in whatever form you like (ARGV, STDIN, STDOUT, writing / reading from a file), as long as you state how to use your program
You must choose a random image of a funny cat and encode your program into it to show that your program works
You may assume that you are only provided valid input, if the amount of bits are not sufficient, the image is not in true color format, the image does not exist or similar problems you may do what you want
You may assume that the provided image does not contain any alpha channel
Length is counted in UTF-8 bytes without BOM

You may use this PHP script to test your solution, provide the name of the PNG file as the first command line argument:
<?php
if ($argc === 1) die('Provide the filename of the PNG to read from');
$imageSize = @getimagesize($argv[1]);

if ($imageSize === false) die('Not a PNG file');
list($width, $height) = $imageSize;

$image = imagecreatefrompng($argv[1]);
$read = 0;
$bits = '';
for ($y = 0; $y < $height; $y++) {
    for ($x = 0; $x < $width; $x++) {
        $colorAt = imagecolorat($image, $x, $y);
        $red = ($colorAt >> 16) & 0xFF;
        $green = ($colorAt >> 8) & 0xFF;
        $blue = ($colorAt >> 0) & 0xFF;

        $bits .= ($red & 1).($green & 1).($blue & 1);
        $read += 3;
        if ($read == 24) {
            $length = (int) bindec($bits);
            $bits = '';
        }
        else if ($read > 24 && ($read - 24) > $length) {
            $bits = substr($bits, 0, $length);
            break 2;
        }
    }
}
if (strlen($bits) !== $length) die('Not enough bits read to fulfill the length');
$parts = str_split($bits, 8);
foreach ($parts as $part) {
    echo chr(bindec($part));
}

Your specification says "your program takes a single image as a base". In Mathematica an image is actually just an expression like everything else, so technically this specification would allow me to do the file-loading outside of the code that performs the computation (with the input parameter being an actual image instead of the image's file name). If you don't want stuff like that, you might want to specify that the program needs to take an image's file name as input.

ME helpimtrappedinacatfactory OW

Also, do the bits not used for encoding need to remain untouched? Or can we set them to whatever we want (since that won't really affect image quality and doesn't matter for decoding)?

@m.buettner Do whatever you want with the unused bits. About the Mathematica issue: Thanks, I'll see what I do.

@TimWolla cheers. Another question: you only said we may assume the input image is true colour. May we also assume it has an alpha channel?

@m.buettner I don't see how this helps, would you explain it?

@TimWolla well if there is already an alpha channel I have to skip it during encoding (assuming we're only encoding in the RGB channels as in the article you linked). If there is no alpha channel, I don't have to skip any channels. That does make a difference in my implementation. It also kind of matters for the output. Does the output need to preserve alpha channel? Is it allowed to introduce a alpha channel filled with all 255 if there was no alpha channel in the input? And so on... Of course it would be easiest if we could assume that there is never any alpha present.

@m.buettner I see. I just added „- You may assume that the provided image does not contain any alpha channel“

To be explicit, you're expecting us to write an encoder and not a decoder? And what's the endianness of the conversion between bitstream and bytes?

@PeterTaylor An encoder, yes. My decoder assumes Big Endian.

Can I use a non-built-in library to load and save the png file, eg PIL in Python?

@Claudiu Yes, you don't have to build PNG writing by hand. (I am using GD library in PHP myself)

@TimWolla Would it be valid to get the cat to swallow a memory stick then take a picture of it?

@SonicAtom Can you get the information back, afterwards?

@TimWolla From the cat? Keep it indoors and monitor the litter tray. From the photo? If you take a high enough resolution X-ray photo you may be able to see the state of the individual transistors in the flash chip. I'm certain this must be the most efficient method of passing secret information ever devised, although the cat may have other ideas.

Perl & ImageMagick (Linux), 198 190
Edit: By some coincidence, earlier I tested on a computer with Q8 (8 bit depth) version of ImageMagick installed. 'Standard' Q16 version requires explicit -depth 8 on command line. On Linux, identify result requires newline to be removed, too. Both factors lead to code size increase, therefore I post Linux (probably Mac too) version as an answer, with fixes applied, and also with some Windows-only stuff removed (cr-lf conversion, binary vs text etc.). Portable (slightly longer) version is posted near the end.
With newlines for readability:
$/=$1;
<>=~/\n/;
$_=`identify -format %wx%h $\``;
chop;
open O,"|convert -size $_ -depth 8 rgb: $`.png";
$_=`convert $\` rgb:`;
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

Run:
perl cat.pl

It reads from STDIN, image file name on first line, 'secret' message follows, terminated with ctrl-D. Output file name is original with .png appended - not very nice, it's only done for brevity.
Here's an image with some very secret information hidden within:

And with some comments:
# Undef input record separator, because we'll slurp input.

$/=$1;

# Read from STDIN, separate first line.
# $` (prematch) contains image file name,
# $' (postmatch) - text to encode.

<>=~/\n/;

# Get IM's 'identify' output, width and height of the image.
# Note: we don't have to separate them, \d+x\d+ string will
# do just fine.

$_=`identify -format %wx%h $\``;
chop;

# Open output pipe - IM's 'convert' command that takes raw RGB data from
# STDIN and writes output to PNG file. Interpolated into this command
# line is previous IM's 'identify' result. Convert wants '-size' command
# option in case of raw RGB input - for obvious reason.

open O,"|convert -size $_ -depth 8 rgb: $`.png";

# Get raw RGB data into $_.

$_=`convert $\` rgb:`;

# Last line does all the job.

# y//\376/cr --- create string same length as $_, fill with 0xFE
# $_&y//\376/cr --- zero least significant bit for all image bytes (1).
# pack(NX,2048*length$') --- multiply by 8 (bytes to bits count) and
#         shift left by 8 (because we'll pack long integer into 3 bytes) -
#         i.e. multiply by 2048.
# unpack('B*',pack(NX,2048*length$').$') ---- append 'secret text' to
#       its encoded length and convert to 'binary' (consisting of 1 and
#       0 characters) string.
# ... &y//\1/cr --- equivalent of tr/01/\0\1/. We don't have to worry
#       that raw RGB length is larger than encoded text length, because
#       '&' truncates longer string argument (2).
# Then bitwise-'or' (1) and (2) strings.

print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

Next is portable version, runs on both Windows (use ctrl-Z to terminate input) and Linux, byte count is 244.
$_=do{local$/;<>};
/\n/;
$_=`identify -format %wx%h $\``;
chomp;
open I,'-|:raw',"convert $` rgb:";
open O,'|-:raw',"convert -size $_ -depth 8 rgb: $`.png";
$_=do{local$/;<I>};
print O$_&y//\376/cr|unpack('B*',pack(NX,2048*length$').$')&y//\1/cr

Mathematica, 255 234 206 bytes
I've seen so many 255s while testing this, I'm unreasonably happy about the size of the code. :) And then my ambition to golf it down even further got the best of me...
f=(j=ImageData[Import@#2,t="Byte"];k=(d=IntegerDigits)[j,2,8]~Flatten~2;n=1;(k[[n++,-1]]=#)&/@d[Length@#,2,24]~Join~#&[Join@@d[ToCharacterCode@#,2,8]];ArrayReshape[#~FromDigits~2&/@k,Dimensions@j]~Image~t)&

It's technically a function and not a "program", but then again this is pretty much how you write "programs" in Mathematica, if that concept is even valid there. Call it like
f["my secret", "fully/qualified/cat.png"]

It will return an actual image expression (because that's the most natural way to return an image in Mathematica), so if you want a file, you need to export it:
Export["output-cat.png", f["my secret", "input-cat.png"]]

Here is the required example:

I'd love to show you the decoded message here, but it doesn't fit... so run it through the OP's decoder. ;)
Btw, I could make it work with UTF-8 secrets for just 7 bytes (change ToCharacterCode@# into #~ToCharacterCode~"utf8").
Ungolfed code:
f[secret_, filename_] := (
  bits = Join @@ IntegerDigits[ToCharacterCode[secret], 2, 8];
  bits = Join[d[Length @ bits, 2, 24], bits];
  data = ImageData[Import@#2, "Byte"];
  dims = Dimensions@data;
  data = Flatten[IntegerDigits[data, 2, 8], 2];
  m = n = 1;
  While[m <= Length @ bits,
    data[[n++, -1]] = bits[[m++]]
  ];
  Image[ArrayReshape[FromDigits[#, 2] & /@ data, dims], "Byte"]
)

"I'd love to show you the decoded message here, but it doesn't fit... so run it through the OP's decoder. ;)" - I did and it gives me "????????????+++++++??++++++++++++++++++++=================~===~============~::::~~~~~=[... for 9773 characters]"

@TessellatingHeckler, that's correct. try it in a monospaced font and be aware that there are UNIX-style new lines in there (e.g. try in a terminal or PowerShell with at least 180 characters width, or if you're running it in as a web script in your browser, then view the source) ;)

I see! Very meta. Helps that I'm in the KiTTY version of PuTTY, too

PHP, 530 byte
<?php function p($i,$j){return str_pad(decbin($i),$j,0,0);}extract(getopt("i:o:t:"));$t=file_get_contents($t);$_=imagecreatefrompng($i);list($w,$h)=getimagesize($i);$b="";for($i=0;$i<strlen($t);)$b.=p(ord($t[$i++]),8);$l=strlen($b);$b=p($l,24).$b;$l+=24;for($i=$x=$y=0;$y<$h;$y++){for(;$x<$w;){$C=imagecolorat($_,$x,$y);$R=($C>>16)&0xff;$G=($C>>8)&0xff;$B=$C&0xff;$i<$l&&$R=$b[$i++]|$R&~1;$i<$l&&$G=$b[$i++]|$G&~1;$i<$l&&$B=$b[$i++]|$B&~1;imagesetpixel($_,$x++,$y,imagecolorallocate($_,$R,$G,$B));if($i>$l){imagepng($_,$o);die;}}}

Run like php 25443.php -i<input image> -o<output image> -t<file to hide>.
And here's a sample image.

Ungolfed code is hidden in the sample image. Tested with OP's decoder. Sorry for not funny cat picture.

Please add the ungolfed code in your answer.

You can shorten 0xff to 255.

You can save 4 bytes if you assume short tags: <?function.


text:
Determine if a number is prime without using arithmetic
Write a program which determines if a given number is prime.
The catch: No digits or arithmetical operators. This means:

No digits from 0 to 9, anywhere in the program, and whatever the meaning
No using any built-in operators for addition (and incrementing), subtraction (and decrementing), multiplication, division, exponentiation, or modulus, anywhere in the program
This includes symbols like + and functions like num.add()
All other operations are permitted
You may define your own functions for the forbidden operations
You may use symbols like - when they mean things other than the forbidden operations

Shortest code wins - any language permitted.
Example solution
An ungolfed solution in Java can be found here.

It would be greatly appreciated if someone would explain the downvotes.

Probably because this is impossible? (Without abusing built-in prime functions, that is.)

Even if not impossible, it is so exclusive of the established techniques for prime detection to be kind of silly ... Feel free to post to Sandbox first to get a feel for how things will turn out before you post.

@ProgrammerDan I added a solution using a typical prime-detection method.

Quite similar to Is it a prime? w/o math?

@Ypnypn you should submit your solution as an answer :).

In light of algorithmshark's solution; Should point two be updated to prohibit built in primality tests?

Any constraints on performance or size of the primes? i.e. does it matter if the program only supports 31 bit primes or has exponential runtime?

it is no sense because even if in any programming language it is not used arithmetic, basically any computer will use arithmetic to make any "for" of "if".

Since we may not use any numbers, are we allowed to use length functions (like ''.length, 'a'.length, 'aa'.length,'aaa'.length for 0 up to 3, for example)?

@Nate yes; that's okay.

Does the increment operator also count as addition?

PHP, 117 characters
This one is based on regular expressions. If a string containing $n characters can be split into chunks of equal length, then $n must be composite.
(Assumes $n is a positive integer.)
function p($n){$u=true;$s=str_repeat('x',$n);return($s!='x'&&!preg_match('/^(xx{'.$u.',})\\'.$u.'{'.$u.',}$/U',$s));}

Output:
for ($i=1; $i<=100; $i++) if (p($i)) echo "$i ";

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

I believe this is the epitome of "two problems." +1

Sage, 18
Looks like this is allowed.
input()in Primes()

3 gives True, 4 gives False

PERL 53 54 52 48
('a'x($_=pop))=~/^a?$|^(?aa+?)\g{a}+$/||print

Thanks to reddit: http://www.reddit.com/r/programming/comments/crmhe/regular_expression_to_check_for_prime_numbers_1111/

Interesting. However, from the question: "1. No digits from 0 to 9, anywhere in the program, and whatever the meaning." The variable can be read in a shorter way: $a=pop;

Thanks, any character will do, i used 'a'.. but I need the \1 for the capture. :-S

A named capture helps: ('a'x($_=pop))=~/^a?$|^(?aa+?)\g{a}+$/||print (48 bytes)

Thanks you, I was looking for a short way to use name reference. Also I didn't know the empty print trick. :D

use of + not allowed by rule 3

@SeanCheshire Rule 3 only seems to disallow using + as an arithmetic operator, not as a regex symbol. This is in contrast to rule 1, which expressly forbids any use of digits in any context.

J - 7 char
Trivial.
(p:~=~)

This verb is in the form of a hook. Applied to an argument y, it will evaluate as follows. (Feel free to check for yourself: Hook, Reflex/Passive, Equals, Primes.)
(p:~=~) y          NB. (F G) y  becomes  y F (G y)   (Hook)
y p:~ (=~ y)       NB. x F~ y   becomes  y F x       (Passive)
(=~ y) p: y        NB. F~ y     becomes  y F y       (Reflex)
(y = y) p: y       NB. anything is equal to itself, so y=y becomes 1
1 p: y             NB. 1 p: y tests for primality of y

Usage:
   (p:~=~) 5
1
   (p:~=~) 6
0
   (p:~=~) 8675309
1
   NB. test every element of a list
   (p:~=~)every 1627 5231 7610 6311 4549 6990 4220 9028 4066 3496
1 1 0 1 1 0 0 0 0 0

I feel that using a built in primality tester goes against the spirit of the challenge.

@Taemyr (*@{.=*./)@(+.}.@i.) for 20 char. +. is GCD, *. is LCM, * is Signum. But until the specs change, the 7 char solution is the shortest valid solution.

Python 3, 85
(lambda i:not any(' '*i==(' '*u)*v for u in range(i)for v in range(i)))(int(input()))

Where * is not a multiplication operator but a string multiple self-concatenation operator.

Ruby, 30
require'prime';f=->n{n.prime?}

Declares a function that returns whether its argument is prime.
Alternative version (same length):
require'prime';f=proc &:prime?

Obviously bending the rules, but you never said built-in prime functions aren't allowed.

He shouldn't have to say it: http://meta.codegolf.stackexchange.com/a/1078/1416

PHP - 208
<?php
function i($n){if($n==strlen(" "))return!!"";foreach(range(strlen("  "),$n) as$_){if($_!=$n){$a=array_fill(!!"",$n,"");while(count($a)>=$_)array_splice($a,!!"",$_);if(!count($a))return!!"";}}return!"";}

Type juggling in PHP is fun!


text:
Mex table generation
There is a table (the matrix one, not the one in your kitchen) called the "mex table". It has a left-top cell, at coordinates (0,0), but extends to infinity rightwards and downwards. The x-coordinate increases to the right and the y-coordinate increases downwards.
Every cell has a value >=0, and the cell at (0,0) has the value 0. The value of any other cell is defined as the lowest integer, >=0, which does not occur directly above it or directly to the left of it.
The start of the mex table looks like this:
+---+---+---+---+---+-
| 0 | 1 | 2 | 3 | 4 | ..
+---+---+---+---+---+-
| 1 | 0 | 3 | 2 | 5 | ..
+---+---+---+---+---+-
| 2 | 3 | 0 | 1 | ..
+---+---+---+---+-
| 3 | 2 | 1 | ..
+---+---+---+-
| 4 | 5 | ..
+---+---+-
| : | : | \

So, for example, the cell at (2,1) is 3 because 0 occurs left of it, 1 occurs left of it and 2 occurs above the cell. The cell at (3,1) is 2, however, because in the part of the row directly to the left of (3,1) and the part of the column directly above (3,1), 0, 1 and 3 occur, but 2 doesn't.
Objective: Print, to standard output, the number in the cell at (x,y) given two integers, both >=0, on standard input, space-separated and newline-terminated.
Thunderbirds are GO!
(This is derived from a question from the national finals of the Dutch Informatics Olympiad of some time ago.)

This too easy if you know the trick. Two characters in golfscript.

Let them figure out... Took me some time too.

I don't understand directly as used. It just seems like "doesn't occur to the left, doesn't occur above".

@BillWoodger correct, the "directly" is to stress that we only count that very same row and column, not any cells in between. Whatever, you get the point.

Is there some other name for this table?

@Quincunx, yes, bitwise xor.

@PeterTaylor I wonder why.

GolfScript (2 chars)
~^

This is familiar to anyone who knows anything at all about combinatorial game theory.

Hmm. Not much change of beating that since I have to convert to and from binary too. :-(

technically, I have posted this very same answer 30 minutes ago ;-)

@JanDvorak, Ilmari beat us both to it by 18 months.

J, 7 characters
#.~:/#:

Usage:
   #.~:/#:3 5
6
   #.~:/#:2 3
1


text:
Count the unique fractions with only integers
Count the number of unique fractions with numerators and denominators from 1 to 100, and print the counted number. Example: 2/3 = 4/6 = ...
Rules:
You must actually count in some way. Only integers are allowed, no floating point numbers or fraction types.
Integers count as fractions. So 1/1, 2/1, etc is valid.

"no floating point numbers or fraction types" - does that mean, anywhere in the program?

@CompuChip Yes. Other non-number types are allowed

This question is pretty old, and as a result I don't think it meets the standards of clarity that we have established since.  Particularly what it means to "count in some way" and what "only integers" mean is pretty subjective. (the former is flouted here)  I think the former could be sidestepped by having the "100" input rather than hardcoded, but its a little late to make that change.  Feel free to re-ask this with new clear specs (there seems to be some recent intrest), and if you are wondering how to do that the sandbox may be able to help.

@WheatWizard yeah you're completely correct. I have some very bad early questions.

J - 21 17 char
+/1=,+./~1+i.100

Explained:

1+i.100 - The integers from 1 to 100.
+./~ - Table of GCDs.
1=, - Run into a list, and then check for equality to 1.
+/ - Add together the results (true is 1, false is 0).

Usage:
   +/1=,+./~1+i.100
6087

21 char version that actually constructs all the pairs of numbers:
#~.,/(,%+.)&>:/~i.100

&>: increments all the integers and also sets up another golfy thing, while ~. takes all the unique entries in the list of pairs we construct, and then # gives the length of that.

Ruby, 57 (67 without Rational) (-3 if run in IRB)
p((a=[*1..100]).product(a).map{|x|Rational *x}.uniq.size)

Output:
6087

Can be 3 less characters if run in IRB, because you can remove the p( and ).
Uses product for the numerator and denominator getting process, and then uses Rational for converting them to fractions. If you remove the .size at the end, it prints all of the fractions instead of how many there are.
It seems like it might take a long time to run, but it's actually almost instantaneous.
Here's an example IRB session to explain how the code works a bit better:
irb(main):027:0> (a=[*1..5]).product(a)
=> [[1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5]]
irb(main):028:0> Rational 1, 2
=> (1/2)
irb(main):029:0> Rational 2, 4
=> (1/2)

Rational *x uses the "splat" operator to call the Rational function with arguments given in the array x. This "splat" is also used in [*1..100].
Here's an alternative that doesn't use Rational, weighing in at 66 characters:
p((a=[*1..100]).product(a).map{|x,y|z=x.gcd y;[x/z,y/z]}.uniq.size)

The fraction simplification method is replaced with this:
z=x.gcd y;[x/z,y/z]

which divides the numberator and the denominator by their GCD (greatest common denominator), and then sticks them back in an array so that uniq can work.

Wow, that was fast. Are you sure "Rational" uses only integers? Nothing else is allowed

@qwr Rational stores the numbers as a numerator and a denominator, not as a floating point.

@qwr If you're interested, I've also added a new version that doesn't use Rational.

Bash + GNU tools, 47
$ echo 10^9\*{1..100}/{1..100}\;|bc|sort -u|wc -l
6087
$

Looks like a similar method to @Doorknob's answer.

Doesn't bc -l give a floating point answer? The question states that only integer types are allowed.

@user80551 Yes, you're right, I missed that in the question.  I've edited to use bc with no -l, and just premultiply everything so we still get the correct uniqueness.  Adds 3 chars.

Nice, but why escape the *.

@devnull: Not escaping the asterisk will cause problems if there's a file with name ./10^91/1;.

@Dennis Ah! Ugly globbing.

@devnull Yeah I guess escaping the * is not strictly necessary as I don't have any such named files and this is codegolf.  It does work if I remove the escape, but a lot slower as it still tries to match against every file 10000 times

Mathematica - 24
This is just a sequence A018805. EulerPhi[n] is the number of coprime to n integers m that are below n (gcd n m == 1)
2 Tr@EulerPhi@Range@100 - 1

J - 15
<:+:+/5&p:i.101

"You must actually count in some way. "

@ace This is counting. I just redirect half of it to the built-in function.

@RossMillikan That's why we double it, so it will count both 3/2 and 2/3, 3/1 and 1/3.

JavaScript, 64 characters
for(n=101,o=0,c={};--n;)for(d=101;--d;)!c[n/d]&&(c[n/d]=++o);o

Put into the JS console, returns 6087.

You can save 3 with c[n/d]=c[n/d]||++o

Also, if you change c to an array and assign it to o ([] casts to 0 with ++ operator) you can save 4 more bytes: (57 byte solution) for(n=101,o=c=[];--n;)for(d=101;--d;)c[n/d]=c[n/d]||++o;o

Haskell, 32 bytes
sum[1|1<-gcd<$>r<*>r]
r=[1..100]

Try it online!
Tries to follow the spirit of actually computing the result by having a "100" that can be replaced with any number.

Wow, I completely forgot I even asked this question. Well now all the answers use the hardcoded 100 so I guess there could be a better challenge with arbitrary input (if one doesn't already exist).

APL (Dyalog Extended), 12 bytes
≢⍸1=∘.∨⍨⍳100

Try it online!
Original:
(+/1=∘,⍳∘.∨⍳)100

Explanation:
  (+/1=∘, ⍳∘.∨⍳ )100
⍝ ^~~~~~v ^~~~v ^~~~v
⍝       |     |     100 x 100
⍝       |     greatest common divisor table of dimensions
⍝       flatten, count all values equal to one in

Sage, 62 or 42
Runs in the interactive prompt.
c=0
R=range(1,101)
for i in R:
 for j in R:
  c+=gcd(i,j)==1
c

Short and easy to understand.
If use of Euler's totient function is allowed, here's a 42-char one-liner:
2*sum(euler_phi(n)for n in range(1,101))-1

CJam - 18 22
100,:):X{dXf/}%:|,
Oops, I had missed the "no floating point" requirement. Here is an integer-based solution:
100,:):X_:*f*{Xf/}%:|,

CJam is a new language I am developing, similar to GolfScript - http://sf.net/p/cjam. Here is the explanation:
100, makes an array [0 1 ... 99]
:) increments all the elements of the array
:X assigns to variable X
_ duplicates the last value (the array)
:* multiplies the array elements together, thus calculating 100!
f* multiplies each array element with 100!
{...}% performs a "map" - applies the block to each element
Xf/ divides the current number by each element in X; since the numbers were already multiplied by 100!, it is an exact division
:| performs a fold with the | (set union) operator, on the array of arrays we obtained
, counts the number of elements

Hm... Is this some sort of emoticon language?

@ace haha, not intentionally :) I used ":" followed by an operator as a shortcut for map/fold operations

It totally should be an emoticon based language. I'd goof around with it a little.

Haskell 47
sum$filter(<2)[gcd a b|a<-[1..100],b<-[1..100]]

Run this from the interpreter.

Save 3 bytes with s=[1..100];sum$filter(<2)[gcd a b|a<-s,b<-s].

Husk, 11 bytes
LumF/π2ḣ100

Try it online!

Mathematica, 77
Length@Select[Range[100]~Tuples~2,#[[1]]==Numerator@Simplify[#[[1]]/#[[2]]]&]

Wow, this is the longest one here. Guess I'm not too good at thinking outside the box...

Oh wait, only integers are allowed. Oops... Disregard this! :D

C++ - 64
#include<iostream>
main(){int i=0;while(++i<6087);std::cout<<i;}

It counts in some way!

http://meta.codegolf.stackexchange.com/a/1063/17249

Quote from that link: "[if] the question doesn't require input and so a solution which just prints the answer would seem to meet the spec".

Python, 81 characters
I guess the following solution is more math golf than code golf: it prints all the fractions as well.  The algorithm might be an inspiration for code golfers, though.
def f(i,j,k,l):
    m,n = i+k,j+l
    if m > 100 or n > 100:
        return 0
    print("%d/%d" % (m,n))
    return f(i,j,m,n)+f(m,n,k,l)+1

print(f(0,1,1,0))

So after proving that this does the right thing (it would not be producing all the right fractions if it didn't, would it?), we can write this as
f=lambda i,j,k,l:i+k<101>j+l and f(i,j,i+k,j+l)+f(i+k,j+l,k,l)+1;print f(0,1,1,0)

Which is 81 characters.  At the interactive prompt, you can save the six characters "print " but that seems like a bit of cheating.
It's worth noting that putting 10001 instead of 101 and adding
import sys
sys.setrecursionlimit(100000)

in front allows to calculate the number of all fractions with nominator/denominator smaller than 10000 in less than a minute.  Which is impressive since every single of the 60794971 fractions is actually generated as well as counted separately.  And another thing worth noting is that discounting the break-off condition, all positive fractions in shortest terms are generated by this recursion, one per call.

05AB1E, 7 bytes
Port of isaacg's Haskell answer.
тLãʒ¿}g

Try it online!
Explanation
т         Push 100
 L        Length range: [1 .. 100]
  ã       All possible pairs
   ʒ      Filter where:
    ¿         The gcd of the pairs
     }        is equal to 1
      g   Find the length