# Complex Dice Rolling Expressions

## Background

I play D&D on a regular basis with some friends. While talking about the complexity of some systems/versions when it comes to rolling dice and applying bonuses and penalties, we jokingly came up with some additional complexity for dice rolling expressions. Some of them were too outrageous (like extending simple dice expressions like 2d6 to matrix arguments1), but the rest make for an interesting system.

## The Challenge

Given a complex dice expression, evaluate it according to the following rules and output the result.

## Basic Evaluation Rules

• Whenever an operator expects an integer but receives a list for an operand, the sum of that list is used
• Whenever an operator expects a list but receives an integer for an operand, the integer is treated as a one-element list containing that integer

## Operators

All operators are binary infix operators. For the purpose of explanation, a will be the left operand, and b will be the right operand. List notation will be used for examples where operators can take lists as operands, but actual expressions consist only of positive integers and operators.

• d: output a independent uniform random integers in the range [1, b]
• Precedence: 3
• Both operands are integers
• Examples: 3d4 => [1, 4, 3], [1, 2]d6 => [3, 2, 6]
• t: take the b lowest values from a
• Precedence: 2
• a is a list, b is an integer
• If b > len(a), all values are returned
• Examples: [1, 5, 7]t1 => [1], [5, 18, 3, 9]t2 => [3, 5], 3t5 => [3]
• T: take the b highest values from a
• Precedence: 2
• a is a list, b is an integer
• If b > len(a), all values are returned
• Examples: [1, 5, 7]T1 => [7], [5, 18, 3, 9]T2 => [18, 9], 3T5 => [3]
• r: if any elements in b are in a, reroll those elements, using whatever d statement generated them
• Precedence: 2
• Both operands are lists
• Rerolling is done only once, so it is possible to still have elements of b in the result
• Examples: 3d6r1 => [1, 3, 4] => [6, 3, 4], 2d4r2 => [2, 2] => [3, 2], 3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
• R: if any elements in b are in a, reroll those elements repeatedly until no elements of b are present, using whatever d statement generated them
• Precedence: 2
• Both operands are lists
• Examples: 3d6R1 => [1, 3, 4] => [6, 3, 4], 2d4R2 => [2, 2] => [3, 2] => [3, 1], 3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
• +: add a and b together
• Precedence: 1
• Both operands are integers
• Examples: 2+2 => 4, [2]+[2] => 4, [3, 1]+2 => 6
• -: subtract b from a
• Precedence: 1
• Both operands are integers
• b will always be less than a
• Examples: 2-1 => 1, 5-[2] => 3, [8, 3]-1 => 10
• .: concatenate a and b together
• Precedence: 1
• Both operands are lists
• Examples: 2.2 => [2, 2], [1].[2] => [1, 2], 3.[4] => [3, 4]
• _: output a with all elements of b removed
• Precedence: 1
• Both operands are lists
• Examples: [3, 4]_[3] => [4], [2, 3, 3]_3 => [2], 1_2 => [1]

• If the final value of an expression is a list, it is summed before output
• Evaluation of terms will only result in positive integers or lists of positive integers - any expression that results in a non-positive integer or a list containing at least one non-positive integer will have those values replaced by 1s
• Parentheses can be used to group terms and specify order of evaluation
• Operators are evaluated in order of highest precedence to lowest precedence, with evaluation proceeding from left to right in the case of tied precedence (so 1d4d4 would be evaluated as (1d4)d4)
• The order of elements in lists does not matter - it is perfectly acceptable for an operator that modifies a list to return it with its elements in a different relative order
• Terms that cannot be evaluated or would result in an infinite loop (like 1d1R1 or 3d6R[1, 2, 3, 4, 5, 6]) are not valid

## Test Cases

Format: input => possible output

1d20 => 13
2d6 => 8
4d6T3 => 11
2d20t1 => 13
5d8r1 => 34
5d6R1 => 20
2d6d6 => 23
3d2R1d2 => 3
(3d2R1)d2 => 11
1d8+3 => 10
1d8-3 => 4
1d6-1d2 => 2
2d6.2d6 => 12
3d6_1 => 8
1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3)) => 61


All but the last test case were generated with the reference implementation.

## Worked Example

Expression: 1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))

1. 8d20t4T2 => [19, 5, 11, 6, 19, 15, 4, 20]t4T2 => [4, 5, 6, 11]T2 => [11, 6] (full: 1d(([11, 6])d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3)))
2. 6d6R1r6 => [2, 5, 1, 5, 2, 3]r1R6 => [2, 5, 3, 5, 2, 3]R6 => [2, 5, 3, 5, 2, 3] (1d([11, 6]d[2, 5, 3, 5, 2, 3]-2d4+1d2).(1d(4d6_3d3)))
3. [11, 6]d[2, 5, 3, 5, 2, 3] => 17d20 => [1, 6, 11, 7, 2, 8, 15, 3, 4, 18, 11, 11, 1, 10, 8, 6, 11] (1d([1, 6, 11, 7, 2, 8, 15, 3, 4, 18, 11, 11, 1, 10, 8, 6, 11]-2d4+1d2).(1d(4d6_3d3)))
4. 2d4 => 7 (1d([1, 6, 11, 7, 2, 8, 15, 3, 4, 18, 11, 11, 1, 10, 8, 6, 11]-7+1d2).(1d(4d6_3d3)))
5. 1d2 => 2 (1d([1, 6, 11, 7, 2, 8, 15, 3, 4, 18, 11, 11, 1, 10, 8, 6, 11]-7+2).(1d(4d6_3d3)))
6. [1, 6, 11, 7, 2, 8, 15, 3, 4, 18, 11, 11, 1, 10, 8, 6, 11]-7+2 => 133-7+2 => 128 (1d128).(1d(4d6_3d3)))
7. 4d6_3d3 => [1, 3, 3, 6]_[3, 2, 2] => [1, 3, 3, 6, 3, 2, 2] (1d128).(1d[1, 3, 3, 6, 3, 2, 2]))
8. 1d[1, 3, 3, 6, 3, 2, 2] => 1d20 => 6 (1d128).(6))
9. 1d128 => 55 (55.6)
10. 55.6 => [55, 6] ([55, 6])
11. [55, 6] => 61 (done)

## Reference Implementation

This reference implementation uses the same constant seed (0) for evaluating each expression for testable, consistent outputs. It expects input on STDIN, with newlines separating each expression.

#!/usr/bin/env python3

import re
from random import randint, seed
from collections import Iterable
from functools import total_ordering

def as_list(x):
if isinstance(x, Iterable):
return list(x)
else:
return [x]

def roll(num_sides):
return Die(randint(1, num_sides), num_sides)

def roll_many(num_dice, num_sides):
num_dice = sum(as_list(num_dice))
num_sides = sum(as_list(num_sides))
return [roll(num_sides) for _ in range(num_dice)]

def reroll(dice, values):
dice, values = as_list(dice), as_list(values)
return [die.reroll() if die in values else die for die in dice]

def reroll_all(dice, values):
dice, values = as_list(dice), as_list(values)
while any(die in values for die in dice):
dice = [die.reroll() if die in values else die for die in dice]
return dice

def take_low(dice, num_values):
dice = as_list(dice)
num_values = sum(as_list(num_values))
return sorted(dice)[:num_values]

def take_high(dice, num_values):
dice = as_list(dice)
num_values = sum(as_list(num_values))
return sorted(dice, reverse=True)[:num_values]

a = sum(as_list(a))
b = sum(as_list(b))
return a+b

def sub(a, b):
a = sum(as_list(a))
b = sum(as_list(b))
return max(a-b, 1)

def concat(a, b):
return as_list(a)+as_list(b)

def list_diff(a, b):
return [x for x in as_list(a) if x not in as_list(b)]

@total_ordering
class Die:
def __init__(self, value, sides):
self.value = value
self.sides = sides
def reroll(self):
self.value = roll(self.sides).value
return self
def __int__(self):
return self.value
__index__ = __int__
def __lt__(self, other):
return int(self) < int(other)
def __eq__(self, other):
return int(self) == int(other)
return int(self) + int(other)
def __sub__(self, other):
return int(self) - int(other)
__rsub__ = __sub__
def __str__(self):
return str(int(self))
def __repr__(self):
return "{} ({})".format(self.value, self.sides)

class Operator:
def __init__(self, str, precedence, func):
self.str = str
self.precedence = precedence
self.func = func
def __call__(self, *args):
return self.func(*args)
def __str__(self):
return self.str
__repr__ = __str__

ops = {
'd': Operator('d', 3, roll_many),
'r': Operator('r', 2, reroll),
'R': Operator('R', 2, reroll_all),
't': Operator('t', 2, take_low),
'T': Operator('T', 2, take_high),
'-': Operator('-', 1, sub),
'.': Operator('.', 1, concat),
'_': Operator('_', 1, list_diff),
}

def evaluate_dice(expr):
return max(sum(as_list(evaluate_rpn(shunting_yard(tokenize(expr))))), 1)

def evaluate_rpn(expr):
stack = []
while expr:
tok = expr.pop()
if isinstance(tok, Operator):
a, b = stack.pop(), stack.pop()
stack.append(tok(b, a))
else:
stack.append(tok)
return stack[0]

def shunting_yard(tokens):
outqueue = []
opstack = []
for tok in tokens:
if isinstance(tok, int):
outqueue = [tok] + outqueue
elif tok == '(':
opstack.append(tok)
elif tok == ')':
while opstack[-1] != '(':
outqueue = [opstack.pop()] + outqueue
opstack.pop()
else:
while opstack and opstack[-1] != '(' and opstack[-1].precedence > tok.precedence:
outqueue = [opstack.pop()] + outqueue
opstack.append(tok)
while opstack:
outqueue = [opstack.pop()] + outqueue
return outqueue

def tokenize(expr):
while expr:
tok, expr = expr[0], expr[1:]
if tok in "0123456789":
while expr and expr[0] in "0123456789":
tok, expr = tok + expr[0], expr[1:]
tok = int(tok)
else:
tok = ops[tok] if tok in ops else tok
yield tok

if __name__ == '__main__':
import sys
while True:
try:
dice_str = input()
seed(0)
print("{} => {}".format(dice_str, evaluate_dice(dice_str)))
except EOFError:
exit()


[1]: Our definition of adb for matrix arguments was to roll AdX for each X in a * b, where A = det(a * b). Clearly that's too absurd for this challenge.

• Sandbox link – user45941 Jul 14 '17 at 4:49
• With the guarantee on - that b will always be less than a I see no way to get non-positive integers, so the second additional rule seems pointless. OTOH, _ could result in an empty list, which seems useful in same cases but what does it mean when an integer is needed? Normally I'd say the sum is 0... – Christian Sievers Sep 13 '17 at 12:34
• @ChristianSievers 1) I added the additional note about non-positive integers for clarity. 2) The sum of an empty list is 0. By the no-non-positives rule, it would be evaluated as a 1. – user45941 Sep 13 '17 at 12:36
• Okay, but is it okay as intermediate result? So [1,2]_([1]_[1]) is [1,2]? – Christian Sievers Sep 13 '17 at 12:41
• @ChristianSievers No. That would result in [2], because [1]_[1] -> [] -> 0 -> 1 -> [1]. – user45941 Sep 13 '17 at 12:43

# Python 3, 803 788 753 749 744 748 745 740 700 695 682 680 bytes

exec(r'''from random import*
import re
class k(int):
p=0;j=l([d(randint(1,int(b)),b)range(a)]);__mul__=l(sorted()[:b]);__matmul__=l(sorted()[-b:]);__truediv__=l([d(randint(1,int(_.i)),_.i)if _==b else _ ]);__sub__=k(max(1,int.__sub__(a,b)))
def __mod__(a,b):
x=[]
while x!=:x=;a=a/b
l(x)
def :
if b.p:p=b.p;del b.p;l(+b.l)if~-p else l([_ if~-(_ in b.l)])
k(int.)
def __neg__(a):a.p+=1;a
def l(x):a=k(sum(x)or 1);=x;a
def d(v,i):d=k(v);d.i=i;d
w=lambda a:eval(re.sub("(\d+)","(k(\\1))",a).translate({100:".j",116:"*",84:"@",114:"/",82:"%",46:"+--",95:"+-"}))'''.translate({2:" for _ in ",3:"a.l",4:"lambda a,b:",5:"return ",6:"__add__(a,b)"}))


Try it online!

Contains a lot of unprintables, see the TIO link for the full code

-5 bytes thanks to Mr.Xcoder

-5 more bytes thanks to NGN

-about 40 bytes thanks to Jonathan French

Yuck, what a kludge! This works by using a regular expression to wrap all numbers in my k class, and converting all of the operators into operators python understands, then using the magic methods of the k class to handle the math. The +- and +-- at the end for . and _ are a hack to keep the precedence correct. Likewise, I can't use the ** operator for d because doing so would make 1d4d4 be parsed as 1d(4d4). Instead, I wrap all numbers in an extra set of parens and do d as .j, since method calls have higher precedence that operators. The last line evaluates as an anonymous function that evaluates the expression.

• def __mod__(a, b)... Why the space between a, and b? – Mr. Xcoder Sep 13 '17 at 19:39
• 744 bytes – Mr. Xcoder Sep 13 '17 at 19:42
• @Mr.Xcoder I think you can save a byte by removing an unnecessary space: ; __sub__. And possibly also here: lambda a,b: l(. – Jonathan Frech Sep 14 '17 at 21:19
• You could save some bytes by wrapping your entire code in an exec("""...""".replace("...","...")) statement and replacing strings that occur often (like return ) with a single character. However, to me the exec-strategy always seems a bit unelegant... – Jonathan Frech Sep 14 '17 at 21:26
• the bodies of __mod__ and __add__ don't need that much indent – ngn Sep 18 '17 at 19:24

# APL (Dyalog Classic), 367 bytes

d←{(⊢⍪⍨1+?)⍉⍪⊃⍴/⊃¨+/¨⍺⍵}⋄r←{z←⊣⌿⍺⋄((m×?n)+z×~m←z∊⊣⌿⍵)⍪n←⊢⌿⍺}⋄R←{⍬≡⊃∩/⊣⌿¨⍺⍵:⍺⋄⍵∇⍨⍺r⍵}
u←{⍺[;((⊃+/⍵)⌊≢⍉⍺)↑⍺⍺⊣⌿⍺]}⋄t←⍋u⋄T←⍒u⋄A←+/,⋄S←+/,∘-⋄C←,⋄D←{⍺/⍨~⊃∊/⊣⌿¨⍺⍵}
h←v←⍬⋄o←'drRtT+-._'⋄f←{8<i←o⍳⊃⍵:0⋄v⊢←(¯2↓v),(⍎i⊃'drRtTASCD')/¯2↑v}
{⊃⍵∊⎕d:v,←⊂⍪2↑⍎⍵⋄'('=⍵:h,←⍵⋄')'=⍵:h↑⍨←i-1⊣f¨⌽h↓⍨i←+/∨\⌽h='('⋄h,←⍵⊣h↓⍨←-i⊣f¨⌽h↑⍨-i←+/∧\⌽≤/(1 4 4 1/⌽⍳4)[o⍳↑⍵,¨h]}¨'\d+' '.'⎕s'&'⊢⍞
f¨⌽h⋄1⌈+/⊣⌿⊃v


Try it online!

This is the shunting yard algorithm from the reference implementation merged with evaluate_dice(), without the cruft and object-oriented nonsense. Only two stacks are used: h for the operators and v for the values. Parsing and evaluation are interleaved.

Intermediate results are represented as 2×N matrices where the first row are the random values and the second row are the number of sides on the dice that produced them. When a result is not produced by the dice-throwing "d" operator, the second row contains arbitrary numbers. A single random value is a 2×1 matrix and thus indistinguishable from a 1-element list.

## Python 3: 723722714711707675653 665 bytes

import re
from random import*
S=re.subn
e=eval
r=randint
s=lambda a:sum(g(e(a)))or 1
g=lambda a:next(zip(*a))
def o(m):a,o,b=m.groups();A=sorted(e(a));t=g(e(b));return str(o in"rR"and([([v,(r(1,d)*(o>"R")or choice([n+1for n in range(d)if~-(n+1in t)]))][v in t],d)for(v,d)in A])or{"t":A[:s(b)],"T":A[-s(b):],"+":[(s(a)+s(b),0)],"-":[(s(a)-s(b),0)],".":e(a)+e(b),"_":[t for t in e(a)if~-(t[0]in g(e(b)))]}[o])
def d(m):a,b=map(s,m.groups());return str([(r(1,b),b)for _ in" "*a])
p=r"($[^]]+$)"
def E(D):
D,n=S(r"(\d+)",r"[(\1,0)]",D)
while n:
n=0
for e in[("$$("+p+")$$",r"\1"),(p+"d"+p,d),(p+"([tTrR])"+p,o),(p+"(.)"+p,o)]:
if n<1:D,n=S(*e,D)
return s(D)


The entry point is E. This applies regular expressions iteratively. First it replaces all integers x with a singleton list tuple [(x,0)]. Then the first regular expression performs the d operation, by replacing all [(x,0)]d[(b,0)] with the string representation of an array of tuples like [(1,b),(2,b),(3,b)]. The second element of each tuple is the second operand to d. Then, subsequent regular expressions perform each of the other operators. There is a special regex to remove parens from fully calculated expressions.

Python 3, 695 bytes

import random,tatsu
A=lambda x:sum(x)or 1
H=lambda x:[[d,D(d.s)][d in x[2]]for d in x[0]]
R=lambda x:R([H(x)]+x[1:])if{*x[0]}&{*x[2]}else x[0]
class D(int):
def __new__(cls,s):o=super().__new__(cls,random.randint(1,s));o.s = s;return o
class S:
o=lambda s,x:{'+':[A(x[0])+A(x[2])],'-':[A(x[0])-A(x[2])],'.':x[0]+x[2],'_':[d for d in x[0]if d not in x[2]]}[x[1]]
f=lambda s,x:{'r':H(x),'R':R(x),'t':sorted(x[0])[:A(x[2])],'T':sorted(x[0])[-A(x[2]):]}[x[1]]
d=lambda s,x:[D(A(x[2]))for _ in' '*A(x[0])]
n=lambda s,x:[int(x)]
l=lambda s,x:sum(x,[])
lambda i:tatsu.parse("s=e$;e=o|t;o=e/[-+._]/t;t=f|r;f=t/[rRtT]/r;r=d|a;d=r/d/a;a=n|l|p;n=/\d+/;l='['@:','.{n}']';p='('@:e')';",i,semantics=S())  An interpreter built using tatsu, a PEG parser library. The first argument to tatsu.parser() is the PEG grammar. class D (for Die) subclasses the built in int type. It's value is the result of a roll. The attribute .s is the number of sides on the die. class S has the semantic actions for the parser, and implements the interpreter. ## Clojure, 731 720 bytes (when newlines are removed) Update: a shorter implementation of F. (defn N[i](if(seq? i)(apply + i)i)) (defn g[i](let[L(fn[i](let[v(g i)](if(seq? v)v(list v))))R remove T take](if(seq? i)(let[[o a b :as A]i](if(some symbol? A)(case o d(repeatedly(N(g a))(fn[](inc(rand-int(N(g b))))))t(T(N(g b))(sort(g a)))T(T(N(g b))(sort-by -(g a)))r(for[i(L a)](if((set(L b))i)(nth(L a)0)i))R(T(count(L a))(R(set(L b))(for[_(range)i(L a)]i)))+(+(N(g a))(N(g b)))-(-(N(g a))(N(g b))).(into(L a)(L b))_(R(set(L b))(g a)))A))i))) (defn F[T](if(seq? T)(if(next T)(loop[[s & S]'[_ . - + R r T t d]](let[R reverse[b a](map R(split-with(comp not #{s})(R T)))a(butlast a)](if a(cons s(map F[a b]))(recur S))))(F(first T)))T)) (defn f[i](N(g(F(read-string(clojure.string/replace(str"("i")")#"[^0-9]""$0 "))))))


This consists of four main parts:

• N: coerces a list into a number
• g: evaluates an abstract syntax tree (S-expressions with 3 items)
• F: converts an infix AST to prefix notation (S-expressions), also applies operand order precedence
• f: uses read-string to convert a string into a nested sequence of numbers and symbols (infix AST), pipes them through F -> g -> N, returning the result number.

I'm not sure how to thoroughly test this, maybe via statistical tests against a reference implementation? At least the AST and its evaluation is relatively easy to follow.

Example S-expression from 1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3)):

(. (d 1 (- (d (T (t (d 8 20) 4) 2)
(R (d 6 6) (r 1 6)))
(+ (d 2 4)
(d 1 2))))
(d 1 (_ (d 4 6) (d 3 3))))


Less golfed with internediate results and tests:

(def f #(read-string(clojure.string/replace(str"("%")")#"[^0-9]"" \$0 ")))

(defn F [T]
(println {:T T})
(cond
(not(seq? T))T
(symbol?(first T))T
(=(count T)1)(F(first T))
1(loop [[s & S] '[_ . - + R r T t d]]
(let[[b a](map reverse(split-with(comp not #{s})(reverse T)))
_ (println [s a b])
a(butlast a)]
(cond
a(do(println {:s s :a a :b b})(cons s(map F[a b])))
S(recur S))))))

(->> "3d6" f F)
(->> "3d6t2" f F)
(->> "3d2R1" f F)
(->> "1d4d4" f F)
(->> "2d6.2d6" f F)
(->> "(3d2R1)d2" f F)
(->> "1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))" f F)

(defn N[i](if(seq? i)(apply + i)i))

(defn g[i]
(let[L(fn[i](let[v(g i)](if(seq? v)v(list v))))]
(if(seq? i)
(let[[o a b :as A] i]
(println {:o o :a a :b b :all A})
(if(every? number? A)(do(println{:A A})A)
(case o
d (repeatedly(N (g a))(fn[](inc(rand-int(N (g b))))))
t (take(N (g b))(sort(g a)))
T (take(N (g b))(sort-by -(g a)))
r (for[i(L a)](if((set(L b))i)(nth(L a)0)i))
R (take(count(g a))(remove(set(L b))(for[_(range)i(g a)]i)))
+ (+(N (g a))(N (g b)))
- (-(N (g a))(N (g b)))
. (into(L a)(L b))
_ (remove(set(L b))(g a)))))
(do(println {:i i})i))))

(g '(. (d 3 5) (d 4 3)))
(g '(. 1 (2 3)))
(g '(+ 1 (2 3)))
(g '(R (d 10 5) (d 1 3)))
(g '(T (d 5 20) 3))
(g '(t (d 5 20) 3))
(g '(d (d 3 4) 10))
(g '(d 4 3))
(g '(_ (d 4 6) (d 3 3)))

(->> "1d(4d6_3d3)" f F g)
(->> "1r6" f F g)
(->> "(8d20t4T2)d(6d6R1r6)" f F g)
(->> "(8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3)" f F g)
(->> "1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))" f F g))