33
votes
Programming Challenge: Dice Roller
Its been a while since we did one of these, which is a shame.
Create a program that takes is an input of the type: "d6 + 3" or "2d20 - 5", and return a valid roll.
The result should display both the actual rolls as well as the final result. The program should accept any valid roll of the type 'xdx'
Bonuses:
- Multiplication "d6 * 3"
- Division "d12 / 6"
- Polish notation "4d6 * (5d4 - 3)"
As a side note, it would be really cool if weekly programming challenges became a thing
I usually write Python code, but Pascal was my first programming language - almost two decades ago now - and I have been using it a bit lately to solve some DMOJ problems. It's a decent fit for a lot of them, and it produces ridiculously lean programs to boot.
The bonuses, though, will have to wait. Unless reverse polish notation is acceptable?
Pascal (fpc 3.0.0)
Python 3.x
Edit:
s/dices/dice/g
,s|(\d*)d(\d+)(([+-])(\d+))?|(\d*)\s*d\s*(\d+)\s*(([+-])\s*(\d+))?|
The input "4d6 + 12" throws an error, as does any addition attempt
The Pascal one will just ignore the
+ 12
, as I forgot to sprinkle around enough\s*
in the regex (and(\d*)\s*d\s*(\d+)\s*(([+-])\s*(\d+))?
should do the trick), but, as far as the Python version is concerned, that's an user error.It's using reverse polish notation, not infix notation, so it should either be
4d6+12
(and thus a single "dice roll" token), or4d6 12 +
:4d6 + 12
reads4d6
, reads+
, tries to pop two elements from a single-element-tall stack, and throws up its hands in failure at the stack underflow it gets as a result.Ah I see, I misunderstood.
A simple
would fix that no?
edit: indeed it does
Edit 2: multiplication and division don't work, inputs of
"2d1 * 2
1 1
2" and "3d5 / 5
4 5 1
10" are wrong
Ok this is bothering me.
elif token in operators:
b, a = stack.pop(-1), stack.pop(-1)
stack.append(operators[token](a, b))
print(stack)
never executes
OK for operators only entries of the form 3d6 12 * are accepted, but if its + or - , 3d6+12 works fine, I assume cuz the other function works with them
No, that would break the tokenizer. I'm following Forth's example and just splitting the stream on spaces. I need to distinguish between
A
andB
inA B +
, removing spaces would just make the program seeC+
and break - this is not aiming at being smart, or parsing infix notation at all, and the fact that3d6+12
works at all is a more-or-less happy mistake, as I copy-pasted the regex before deciding to write the RPN function.Ignore me I was being a fool
Ok so I'm just being an idiot, the rolling function can do addition and subtraction, but not the others, so infix worked for those, while multiplication and division only work for post fix
Looking at the Python code it seems like this requires inputs use postfix operators, right?
Yeah, reverse polish notation. I mentioned it at the beginning of my comment.
Feel free to use any form of notation, the point is more to accept full mathematical formulas
Yo, just a heads-up: "dice" is already a plural of "die". Python code, line 5.
Yeeeah, I always forget that. Thanks.
This one was really fun to implement and a good reminder that I know how to do a tiny subset of things in C++ very well and many, many things very badly.
Does 2.5/3 bonuses (takes expressions in polish notation)
C++
I know this isn't in keeping with the spirit of a challenge, but like @onyxleopard, I'd like to share one of these I wrote several years ago, in Python 2.7. It was part of an RPG project which never took off, but this feels like a good chance to dust it off and set it free, for whatever it's worth.
It satisfies the main criteria and the 3 bonuses, and can also handle exponentiation and implied multiplication with parentheses, like
2d4(3d2+9)^2
. It will even work with eldritch dice expressions in which the number of dice, the number of sides the dice have, and the exponent are themselves determined by dice rolls:(2d4)d((3d20)^2d20)
.Finally, it can output the result as a number, or it can return a dictionary listing the results of each individual roll, and how the dice expression was tokenized:
The original idea was that this structure could be used by other libraries, or marshaled to JSON. The code theoretically uses a Top down operator precedence parser or Pratt parser, but I wasn't a CS major, so it probably shouldn't be used as an exemplar of the form. All the same, I hope this code might be useful to someone, or at least entertaining.
It’s fascinating to me that the influence of tabletop games (which I personally haven’t even played much) have led to a de facto standard for dice rolling notation. I like this, and esp. the JSON schema you created, but it also seems a bit like overkill. I think tabular data would be preferable, as the only structured info that is required for the output is very amenable to simple columns. The detailed explanation of the parsing works better as JSON, but is probably only useful for debugging (not a bad motivation for implementing it, but I’ve been on a kick lately to try to force myself to think harder about how to do things as simply as possible).
Extremely fun challenge! This is actually a lot like making a very simple compiler, which is always very fun. I will take a look at completing it tonight :)
Some SML for functional action. Might implement RPN in a bit:
Note: Somehow I'm screwing up the random function so it is currently deterministic
This is a Python3 dice rolling simulator (I wrote a few years ago).
I can't code.. but I'm alright with Sheets. I didn't know what
2d20 - 5
meant, but a friend said its 2x 20 sided dice minus 5 -- so I went with that.edit: this is overkill
These solutions seem very nice and well-written, but they're all enormous: the smallest of the two Python versions is almost an entire kilobyte, without even implementing parentheses in the input.
The problem here is trying to figure out the parsing. That seems like too much work for my style of approaching these challenges, so I'll just avoid doing it entirely:
By avoiding every challenging part of this challenge, this code is only 196 bytes. It accepts as input any valid Python expression, where XdY can replace numbers, and will return first the final value, then all the rolls involved.
Thus:
d6+3 ==> 21 [[7]]
4d6 * (5d4 - 3) ==> 312 [[5, 7, 7, 7], [2, 3, 5, 3, 2]]
4d6**2d4 ==> 7776 [[2, 2, 1, 1], [4, 1]]
4d8 > 15 ==> True [[7, 4, 9, 1]]
Obviously, this allows arbitrary code execution. But in this case, that's arguably a feature. For example:
__import__("math").exp(-(5d8+3))
__import__("numpy").average([3d7,8d8])
["Failure","Success"][4d8 > 15]
(__import__("time").sleep(4d8),[o.fork() for (o,i) in [(__import__('os'), __import__('itertools'))] for x in i.count()])
There are two known issues:
sum(4d8 for _ in range(0,1000))
will not roll 4000 d8s. This could be handled, but the challenge would be to keep track of each roll.Woo that was a trip. Never done anything like this before, so this a pretty horrific and fragile way to handle it.
I started out with the idea of using a tree to represent the math-y witchcraft, which seemed like a good idea at the time. Had a super hard time actually turning a string into a tree structure though.
First attempt worked pretty okay, but didn't implement any order of operations. So
2d5+5
was fine but5 + 2d5
was run as(5+2)d5
. Figured that out after I fed it2d5000000 + 5d5
. It just kept spitting out dice rolls lol.Second version creates an "unfinished" flat list of tokens then uses a new per-operator Priority to gradually fold it into a tree. Then once the tree is made you ask the root node for its value and the request cascades down the tree until a result appears.
Output:
I think it'd be really cool to try and print out the finished tree structure but I could not figure out how to pull that off.
I am a little late to this since I was travelling, but I wanted to share something a little different. I present the Quantum Dice Roller. This was written in Python 3.7 using IBM's qiskit platform. In order to generate randomness, this program places a single quantum bit (qubit) into a superposition of 0 and 1 with equal probability, and then measures this state in order to return 0 or 1 with perfectly equal probability. It uses these random 0s and 1s to build a random string of 0s and 1s which is interpreted as a binary number in order to get the desired random result. So, for example, if you are rolling a d4 it will find the number of bits needed to represent "4" and create a string of that length. The only catch here is that sometimes the result will be greater than the number of sides. For example, for a d4 the program will create a bit string of length 3, which in principle could be "111" which is greater than 4. Thus, it checks the final result and tries again until a valid result is obtained.
In principle, this program could be run on one of IBM's actual quantum computers. As it is written, it uses a simulated quantum processor (and thus probably some standard PRNG). However all it would take is changing the specified backend and making an IBM account to change this. I might do so later just for the novelty of it. I'm happy to answer questions if anyone has them
Cool. Trying this in Rust. I'm not a super adept programmer, so I'm having a bit of trouble splitting the input string by regular expression. If I gather number of dice, number of sides, and modifiers separately it's a fairly trivial task, but of course that's not in the spirit of the challenge.
Also, does anyone know how to extract the last digit of a number? I'm trying to be clever and print proper ordinal numbers, but what I have right now only works for the first ten digits.
Also, there's a lot of repetition, so I imagine it can get even more clever.
What are you trying to do? Print the rolls as
1st, 2nd, 3rd, 40th
?If so, use the remainder operator, but you might want to keep in mind the rules for forming ordinals in English:
So you could write something like
Okay, so this also seems to work:
but maybe it can be cleaner. I guess I can separate it into its own function.
Oh, this is clever. You are matching the result of an if..else expression, yes? On both
i + 1 % 10
andi + 1
, that is? I didn't know that Rust could do that.Still, I would definitely move it to its own function, which would also avoid the whole "having to repeat
i + 1
seven times" thing.Yea, I wasn't quite sure if it'd evaluate, either..until I tried it!
This is the function I ended up with:
The only pain being that Rust is strongly typed and anything that gets thrown into the function has to be cast as a u32. I initiated the dice values as u8, since that seems to be enough for dice and maybe I save a few bytes of memory?
Edit: Ooo, also didn't consider anything past 100, so 111 shows as "111st" instead of "111th." Well, better fix that...
EditEdit: Okay, fixed. I think.
Unless you are on a microcontroller or another such system where memory is measured in kBs, don't bother. Really. Hell, I'd go for u64 - you lose quite a bit by going down to u8 and, more importantly, you are not really gaining anything. Unless you are dealing with an array of thousands of such elements, the 3 bytes you are gaining from that (and from other such premature optimizations) are not going to be significant.
I have been doing a few DMOJ problems each day for a while, and I picked Pascal back up because I wanted to tackle one such problem with a fairly restrictive memory limit (I hit the time limit instead). I have been looking at the best solutions leaderboards for a bit, and - Pascal often uses as little as 4 kB, while Python 3 is usually around 8.9 MB. Python 2, 5.5 MB or so. C, around one MB (890 kB+ even for things as trivial as Hello, World!). C++, ~1.5 MB.
Rust seems to use 2x to 1.1x more memory than C - 1.0 MB to 1.9 MB for Hello, World!, and any gains measured in bytes are going to be absolutely swamped by whatever it does setting up its environment.
Edit: apparently DMOJ doesn't let you link to a particular submission, you need to be logged in and to have solved that problem to see it. In any case, here's the best submissions for Hello, World!, just to get an idea of how much base memory your program will end up using in different programming languages.
Haha, yea. Figured it didn't really matter on any modern system. For some reason it just feels more satisfying using as small a variable as possible. I also want to be exposed to type errors so I can figure out how to fix em. For example,
ordinal_append()
initially didn't have.to_string()
attached, which gave me a type error.DMOJ looks like a cool spot for problems. Gotta practice my Rust syntax some more...
Check also out Project Euler (heavy on mathematics) and Rosalind (bio-informatics, heavy on string manipulation) while you are at it.
Ah, yea. Didn't consider that case. And I figured I'd use the remainder operator, but I must've forgot how it worked. Ha, that was going to be my go to solution but talked myself out of it.
Hm, why do you need the last digit of a number? What I recommend is to split around the "d", separating it into the before the d (number of dice) and after the d (faces on each die).
Purely for nice looking ordinal printing. E.g., "1st roll, 2nd roll, 3rd roll" etc. My solution handles up to "10th", but adds "th" to each subsequent number. If I checked only the last digit I believe I'd handle every case. Just an aesthetics thing, not really part of thtw challenge, but a nice little challenge in itself. :)
I looked up the documentation and some examples on Rust's regular expressions and I understand where I should split, but the syntax is a little confusing to me.
I'm very much not a programmer, just someone with an interest in coding. Here's my attempt in python, which probably breaks an awful lot of conventions and rules: