Evaluate dice rolling notation strings

2019-03-08 10:34发布

站内文章 / 前沿技术

29 0

混吃等死

女 | 书童

私信

可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):

问题:

Rules

Write a function that accepts string as a parameter, returning evaluated value of expression in dice notation, including addition and multiplication.

To clear the things up, here comes EBNF definition of legal expressions:

roll ::= [positive integer], "d", positive integer
entity ::= roll | positive number
expression ::= entity { [, whitespace], "+"|"*"[, whitespace], entity }

Example inputs:

"3d6 + 12"
"4*d12 + 3"
"d100"

Using eval functions, or similar, is not forbidden, but I encourage to solving without using these. Re-entrancy is welcome.

I cannot provide test-cases, as output should be random ;).

Format your answers' titles: language, n characters (important notes — no eval, etc.)

My ruby solution, 92 81 characters, using eval:

def f s
eval s.gsub(/(\d+)?d(\d+)/i){eval"a+=rand $2.to_i;"*a=($1||1).to_i}
end

Another ruby solution, not shorter (92 characters), but I find it interesting — it still uses eval but this time in quite creative way.

class Fixnum
def**b
eval"a+=rand b;"*a=self
end
end
def f s
eval s.gsub(/d/,'**')
end

回答1:

C# class. It evaluates recursively for addition and multiplication, left-to-right for chained die rolls

Edits:

Removed .Replace(" ","") on each call
Added .Trim() on int.TryParse instead
All work is now done in single method
If die face count is not specified, assumes 6 (see Wiki article)
Refactored redundant call to parse left side of "d"
Refactored unnecessary if statement

Minified: (411 bytes)

class D{Random r=new Random();public int R(string s){int t=0;var a=s.Split('+');if(a.Count()>1)foreach(var b in a)t+=R(b);else{var m=a[0].Split('*');if(m.Count()>1){t=1;foreach(var n in m)t*=R(n);}else{var d=m[0].Split('d');if(!int.TryParse(d[0].Trim(),out t))t=0;int f;for(int i=1;i<d.Count();i++){if(!int.TryParse(d[i].Trim(),out f))f=6;int u=0;for(int j=0;j<(t== 0?1:t);j++)u+=r.Next(1,f);t+=u;}}}return t;}}

Expanded form:

    class D
    {
        /// <summary>Our Random object.  Make it a first-class citizen so that it produces truly *random* results</summary>
        Random r = new Random();

        /// <summary>Roll</summary>
        /// <param name="s">string to be evaluated</param>
        /// <returns>result of evaluated string</returns>
        public int R(string s)
        {
            int t = 0;

            // Addition is lowest order of precedence
            var a = s.Split('+');

            // Add results of each group
            if (a.Count() > 1)
                foreach (var b in a)
                    t += R(b);
            else
            {
                // Multiplication is next order of precedence
                var m = a[0].Split('*');

                // Multiply results of each group
                if (m.Count() > 1)
                {
                    t = 1; // So that we don't zero-out our results...

                    foreach (var n in m)
                        t *= R(n);
                }
                else
                {
                    // Die definition is our highest order of precedence
                    var d = m[0].Split('d');

                    // This operand will be our die count, static digits, or else something we don't understand
                    if (!int.TryParse(d[0].Trim(), out t))
                        t = 0;

                    int f;

                    // Multiple definitions ("2d6d8") iterate through left-to-right: (2d6)d8
                    for (int i = 1; i < d.Count(); i++)
                    {
                        // If we don't have a right side (face count), assume 6
                        if (!int.TryParse(d[i].Trim(), out f))
                            f = 6;

                        int u = 0;

                        // If we don't have a die count, use 1
                        for (int j = 0; j < (t == 0 ? 1 : t); j++)
                            u += r.Next(1, f);

                        t += u;
                    }
                }
            }

            return t;
        }
    }

Test cases:

    static void Main(string[] args)
    {
        var t = new List<string>();
        t.Add("2d6");
        t.Add("2d6d6");
        t.Add("2d8d6 + 4d12*3d20");
        t.Add("4d12");
        t.Add("4*d12");
        t.Add("4d"); // Rolls 4 d6

        D d = new D();
        foreach (var s in t)
            Console.WriteLine(string.Format("{0}\t{1}", d.R(s), s));
    }

回答2:

J

With cobbal's help, squeeze everything into 93 characters.

$ jconsole
   e=:".@([`('%'"_)@.(=&'/')"0@,)@:(3 :'":(1".r{.y)([:+/>:@?@$) ::(y&[)0".}.y}.~r=.y i.''d'''@>)@;:

   e '3d6 + 12'
20
   e 10$,:'3d6 + 12'
19 23 20 26 24 20 20 20 24 27
   e 10$,:'4*d12 + 3'
28 52 56 16 52 52 52 36 44 56
   e 10$,:'d100'
51 51 79 58 22 47 95 6 5 64

回答3:

JavaScript solution, 340 chars when compressed (no eval, supports prefixed multiplicator and suffixed addition):

function comp (s, m, n, f, a) {
    m = parseInt( m );
    if( isNaN( m ) ) m = 1;
    n = parseInt( n );
    if( isNaN( n ) ) n = 1;
    f = parseInt( f );
    a = typeof(a) == 'string' ? parseInt( a.replace(/\s/g, '') ) : 0;
    if( isNaN( a ) ) a = 0;
    var r = 0;
    for( var i=0; i<n; i++ )
        r += Math.floor( Math.random() * f );
    return r * m + a;
};
function parse( de ) {
    return comp.apply( this, de.match(/(?:(\d+)\s*\*\s*)?(\d*)d(\d+)(?:\s*([\+\-]\s*\d+))?/i) );
}

Test code:

var test = ["3d6 + 12", "4*d12 + 3", "d100"];
for(var i in test)
    alert( test[i] + ": " + parse(test[i]) );

Compressed version (pretty sure you can do shorter):

function c(s,m,n,f,a){m=parseInt(m);if(isNaN(m))m=1;n=parseInt(n);if(isNaN(n))n=1;f=parseInt(f);a=typeof(a)=='string'?parseInt(a.replace(/\s/g,'')):0;if(isNaN(a))a=0;var r=0;for(var i=0;i<n;i++)r+=Math.floor(Math.random()*f);return r*m+a;};function p(d){return c.apply(this,d.match(/(?:(\d+)\s*\*\s*)?(\d*)d(\d+)(?:\s*([\+\-]\s*\d+))?/i));}

回答4:

Clojure, 854 characters as is, 412 shrunk

Just run "(roll-dice "input-string")".

(defn roll-dice
  [string]
  (let [parts (. (. (. string replace "-" "+-") replaceAll "\\s" "") split "\\+")
        dice-func (fn [d-notation]
                    (let [bits (. d-notation split "d")]
                      (if (= 1 (count bits))
                        (Integer/parseInt (first bits))  ; Just a number, like 12
                        (if (zero? (count (first bits)))
                          (inc (rand-int (Integer/parseInt (second bits))))  ; Just d100 or some such
                          (if (. (first bits) contains "*")
                            (* (Integer/parseInt (. (first bits) replace "*" ""))
                                (inc (rand-int (Integer/parseInt (second bits)))))
                            (reduce +
                              (map #(+ 1 %)
                                    (map rand-int
                                        (repeat
                                          (Integer/parseInt (first bits))
                                          (Integer/parseInt (second bits)))))))))))]      
    (reduce + (map dice-func parts))))

To shrink, I made variables 1 letter, moved the (first bits)/(second bits) into variables, made dice-func an anonymous function, made a wrapper for Integer.parseInt called 'i', and stripped out comments and extra whitespace.

This should work on anything valid, with or without whitespace. Just don't go asking it for "15dROBERT", it will throw an exception.

They way it works is by splitting up the string into dice (that's the 3rd line, the let). So "5d6+2*d4-17" becomes "5d6","2*d4","-17".

Each of those is then processed by the function dice-func, and the results are added up (this is the map/reduce on the last line)

Dice-func takes a little dice string (such a "5d6") and splits it on the "d". If there is only one part left, it was a simple number (6, -17, etc).

If the first part contains a *, we multiply that number by a random interger, 1 to (number after d), inclusive.

If the first part doesn't contain a *, we take first number random rolls (just like previous line) and add them up (this is the map/reduce in the middle).

This was fun little challenge.

回答5:

perl eval version, 72 chars

sub e{$_=pop;s/(\d+)?d(\d+)/\$a/i;$a+=1+int rand$2-1for 0...$1-1;eval$_}

runs like

print e("4*d12+3"),"\n";

Based on the ruby solution, can only run once(you should undef $a between runs).

shorter version, 68 chars, funky (0 based) dice

sub e{$_=pop;s/(\d+)?d(\d+)/\$a/i;$a+=int rand$2for 0...$1-1;eval$_}

EDIT

perl 5.8.8 didn't like the previous version, here's a 73 char version that works

sub e{$_=pop;s/(\d+)?d(\d+)/\$a/i;$a+=1+int rand$2-1for 1...$1||1;eval$_}

70 char version supporting multiple rolls

sub e{$_=pop;s/(\d*)d(\d+)/$a=$1||1;$a+=int rand$a*$2-($a-1)/ieg;eval}

回答6:

F# (no eval and no regex)

233 characters

This solution should be fully generic, in that it can handle just about any string you throw at it, even something crazy such as:

43d29d16d21*9 + d7d9*91 + 2*d24*7

Need to define this globally:

let r = new System.Random()

Fully obfuscated version:

let f(s:string)=let g d o i p (t:string)=t.Split([|d|])|>Array.fold(fun s x->o s (p x))i in g '+'(+)0(g '*' (*) 1 (fun s->let b=ref true in g 'd'(+)1(fun t->if !b then b:=false;(if t.Trim()=""then 1 else int t)else r.Next(int t))s))s

Readable version:

let f (s:string) =
    let g d o i p (t:string) =
        t.Split([|d|]) |> Array.fold (fun s x -> o s (p x)) i
    g '+' (+) 0 (g '*' (*) 1 (fun s ->
                                        let b = ref true
                                        g 'd' (+) 1 (fun t ->
                                        if !b then b := false; (if t.Trim() = "" then 1 else int t)
                                        else r.Next(int t)) s)) s

I'm challenging someone to beat this solution (in any language) without using eval or regular expressions. I think it's likely to be possible, but I am interested in seeing the approach still.

回答7:

Python 124 chars with eval, 154 without.

Just to show python doesn't have to be readable, here's a 124 character solution, with a similar eval-based approach to the original:

import random,re
f=lambda s:eval(re.sub(r'(\d*)d(\d+)',lambda m:int(m.group(1)or 1)*('+random.randint(1,%s)'%m.group(2)),s))

[Edit] And here's a 154 character one without eval:

import random,re
f=lambda s:sum(int(c or 0)+sum(random.randint(1,int(b))for i in[0]*int(a or 1))for a,b,c in re.findall(r'(\d*)d(\d+)(\s*[+-]\s*\d+)?',s))

Note: both will work for inputs like "2d6 + 1d3 + 5" but don't support more advanced variants like "2d3d6" or negative dice ("1d6-4" is OK, but "1d6-2d4" isn't) (You can shave off 2 characters to not support negative numbers at all in the second one instead)

回答8:

python, 197 chars in obscured version.

Readable version: 369 chars. No eval, straight forward parsing.

import random
def dice(s):
    return sum(term(x) for x in s.split('+'))
def term(t):
    p = t.split('*')
    return factor(p[0]) if len(p)==1 else factor(p[0])*factor(p[1])
def factor(f):
    p = f.split('d')
    if len(p)==1:
        return int(f)
    return sum(random.randint(1, int(g[1]) if g[1] else 6) for \
               i in range(int(g[0]) if g[0] else 1))

compressed version: 258 chars, single character names, abused conditional expressions, shortcut in logical expression:

import random
def d(s):
 return sum(t(x.split('*')) for x in s.split('+'))
def t(p):
 return f(p[0])*f(p[1]) if p[1:] else f(p[0])
def f(s):
 g = s.split('d')
 return sum(random.randint(1, int(g[1] or 6)) for i in range(int(g[0] or 1))) if g[1:] else int(s)

obscured version: 216 chars, using reduce, map heavily to avoid "def", "return".

import random
def d(s):
 return sum(map(lambda t:reduce(lambda x,y:x*y,map(lambda f:reduce(lambda x,y:sum(random.randint(1,int(y or 6)) for i in range(int(x or 1))), f.split('d')+[1]),t.split('*')),1),s.split('+')))

Last version: 197 chars, folded in @Brain's comments, added testing runs.

import random
R=reduce;D=lambda s:sum(map(lambda t:R(int.__mul__,map(lambda f:R(lambda x,y:sum(random.randint(1,int(y or 6))for i in[0]*int(x or 1)),f.split('d')+[1]),t.split('*'))),s.split('+')))

Tests:

>>> for dice_expr in ["3d6 + 12", "4*d12 + 3","3d+12", "43d29d16d21*9+d7d9*91+2*d24*7"]: print dice_expr, ": ", list(D(dice_expr) for i in range(10))
... 
3d6 + 12 :  [22, 21, 22, 27, 21, 22, 25, 19, 22, 25]
4*d12 + 3 :  [7, 39, 23, 35, 23, 23, 35, 27, 23, 7]
3d+12 :  [16, 25, 21, 25, 20, 18, 27, 18, 27, 25]
43d29d16d21*9+d7d9*91+2*d24*7 :  [571338, 550124, 539370, 578099, 496948, 525259, 527563, 546459, 615556, 588495]

This solution can't handle whitespaces without adjacent digits. so "43d29d16d21*9+d7d9*91+2*d24*7" will work, but "43d29d16d21*9 + d7d9*91 + 2*d24*7" will not, due to the second space (between "+" and "d"). It can be corrected by first removing whitespaces from s, but this will make the code longer than 200 chars, so I'll keep the bug.

回答9:

perl, no evals, 144 chars, works multiple times, supports multiple dice rolls

sub e{($c=pop)=~y/+* /PT/d;$b='(\d+)';map{$a=0while$c=~s!$b?$_$b!$d=$1||1;$a+=1+int rand$2for 1..$d;$e=$2;/d/?$a:/P/?$d+$e:$d*$e!e}qw(d T P);$c}

Expanded version, with comments

sub f {
    ($c = pop); #assign first function argument to $c
    $c =~ tr/+* /PT/d;  #replace + and * so we won't have to escape them later.
                        #also remove spaces
    #for each of 'd','T' and 'P', assign to $_ and run the following
    map {
        #repeatedly replace in $c the first instance of <number> <operator> <number> with
        #the result of the code in second part of regex, capturing both numbers and
        #setting $a to zero after every iteration
        $a=0 while $c =~ s[(\d+)?$_(\d+)][
            $d = $1 || 1;   #save first parameter (or 1 if not defined) as later regex 
                            #will overwrite it
            #roll $d dice, sum in $a
            for (1..$d)
            {
                $a += 1 + int rand $2;
            }
            $e = $2;        #save second parameter, following regexes will overwrite
            #Code blocks return the value of their last statement
            if (/d/)
            {
                $a; #calculated dice throw
            }
            elsif (/P/)
            {
                $d + $e;
            }
            else
            {
                $d * $e;
            }
        ]e;
    } qw(d T P);
    return $c;
}

EDIT cleaned up, updated explanation to latest version

回答10:

Ruby, 166 characters, no eval

In my opinion quite elegant ;).

def g s,o=%w{\+ \* d}
o[a=0]?s[/#{p=o.pop}/]?g(s.sub(/(\d+)?\s*(#{p})\s*(\d+)/i){c=$3.to_i
o[1]?($1||1).to_i.times{a+=rand c}+a:$1.to_i.send($2,c)},o<<p):g(s,o):s
end

Deobfuscated version + comments:

def evaluate(string, opers = ["\\+","\\*","d"])
  if opers.empty?
    string
  else
    if string.scan(opers.last[/.$/]).empty? # check if string contains last element of opers array

      # Proceed to next operator from opers array.

      opers.pop
      evaluate(string, opers)

    else # string contains that character...

      # This is hard to deobfuscate. It substitutes subexpression with highest priority with
      # its value (e.g. chooses random value for XdY, or counts value of N+M or N*M), and
      # calls recursively evaluate with substituted string.

      evaluate(string.sub(/(\d+)?\s*(#{opers.last})\s*(\d+)/i) { a,c=0,$3.to_i; ($2 == 'd') ? ($1||1).to_i.times{a+=rand c}+a : $1.to_i.send($2,c) }, opers)

    end
  end
end

回答11:

Python, 452 bytes in the compressed version

I'm not sure if this is cool, ugly, or plain stupid, but it was fun writing it.

What we do is as follows: We use regexes (which is usually not the right tool for this kind of thing) to convert the dice notation string into a list of commands in a small, stack-based language. This language has four commands:

mul multiplies the top two numbers on the stack and pushes the result
add adds the top two numbers on the stack and pushes the result
roll pops the dice size from the stack, then the count, rolls a size-sided dice count times and pushes the result
a number just pushes itself onto the stack

This command list is then evaluated.

import re, random

def dice_eval(s):
    s = s.replace(" ","")
    s = re.sub(r"(\d+|[d+*])",r"\1 ",s) #seperate tokens by spaces
    s = re.sub(r"(^|[+*] )d",r"\g<1>1 d",s) #e.g. change d 6 to 1 d 6
    while "*" in s:
        s = re.sub(r"([^+]+) \* ([^+]+)",r"\1 \2mul ",s,1)
    while "+" in s:
        s = re.sub(r"(.+) \+ (.+)",r"\1 \2add ",s,1)
    s = re.sub(r"d (\d+) ",r"\1 roll ",s)

    stack = []

    for token in s.split():
        if token == "mul":
            stack.append(stack.pop() * stack.pop())
        elif token == "add":
            stack.append(stack.pop() + stack.pop())
        elif token == "roll":
            v = 0
            dice = stack.pop()
            for i in xrange(stack.pop()):
                v += random.randint(1,dice)
            stack.append(v)
        elif token.isdigit():
            stack.append(int(token))
        else:
            raise ValueError

    assert len(stack) == 1

    return stack.pop() 

print dice_eval("2*d12+3d20*3+d6")

By the way (this was discussed in the question comments), this implementation will allow strings like "2d3d6", understanding this as "roll a d3 twice, then roll a d6 as many times as the result of the two rolls."

Also, although there is some error checking, it still expects a valid input. Passing "*4" for example will result in an infinite loop.

Here is the compressed version (not pretty):

import re, random
r=re.sub
def e(s):
 s=r(" ","",s)
 s=r(r"(\d+|[d+*])",r"\1 ",s)
 s=r(r"(^|[+*] )d",r"\g<1>1 d",s)
 while"*"in s:s=r(r"([^+]+) \* ([^+]+)",r"\1 \2M ",s)
 while"+"in s:s=r(r"(.+) \+ (.+)",r"\1 \2A ",s)
 s=r(r"d (\d+)",r"\1 R",s)
 t=[]
 a=t.append
 p=t.pop
 for k in s.split():
  if k=="M":a(p()*p())
  elif k=="A":a(p()+p())
  elif k=="R":
   v=0
   d=p()
   for i in [[]]*p():v+=random.randint(1,d)
   a(v)
  else:a(int(k))
 return p()

回答12:

Ruby, 87 characters, uses eval

Here's my Ruby solution, partially based on the OP's. It's five characters shorter and only uses eval once.

def f s
eval s.gsub(/(\d+)?[dD](\d+)/){n=$1?$1.to_i: 1;n.times{n+=rand $2.to_i};n}
end

A readable version of the code:

def f s
    eval (s.gsub /(\d+)?[dD](\d+)/ do
        n = $1 ? $1.to_i : 1
        n.times { n += rand $2.to_i }
        n
    end)
end

回答13:

JAVASCRIPT, 1399 chars, no eval

old post, i know. but i try to contribute

Roll = window.Roll || {};

Roll.range = function (str) {
    var rng_min, rng_max, str_split,
        delta, value;

    str = str.replace(/\s+/g, "");
    str_split = str.split("-");
    rng_min = str_split[0];
    rng_max = str_split[1];

    rng_min = parseInt(rng_min) || 0;
    rng_max = Math.max(parseInt(rng_max), rng_min) || rng_min;

    delta = (rng_max - rng_min + 1);

    value = Math.random() * delta;
    value = parseInt(value);

    return value + rng_min;
};

Roll.rollStr = function (str) {
    var check,
        qta, max, dice, mod_opts, mod,
        rng_min, rng_max,
        rolls = [], value = 0;

    str = str.replace(/\s+/g, "");
    check = str.match(/(?:^[-+]?(\d+)?(?:\/(\d+))?[dD](\d+)(?:([-+])(\d+)\b)?$|^(\d+)\-(\d+)$)/);

    if (check == null) {return "ERROR"}
    qta = check[1];
    max = check[2];
    dice = check[3];
    mod_opts = check[4];
    mod = check[5];
    rng_min = check[6];
    rng_max = check[7];
    check = check[0];

    if (rng_min && rng_max) {return Roll.range(str)}

    dice = parseInt(dice);
    mod_opts = mod_opts || "";
    mod = parseInt(mod) || 0;
    qta = parseInt(qta) || 1;
    max = Math.max(parseInt(max), qta) || qta;

    for (var val; max--;) {
        val = Math.random() * dice;
        val = Math.floor(val) + 1;
        rolls.push(val);
    }

    if (max != qta) {
        rolls.sort(function (a, b) {return a < b});
        rolls.unshift(rolls.splice(0, qta));
    }

    while (rolls[0][0]) {value += rolls[0].shift();}

    if (mod_opts == "-") {value -= mod;}
    else {value += mod;}

    return value
};

if (!window.diceRoll) {window.diceRoll= Roll.rollStr;}

it's a single dice roll, like "2d8+2" or "4-18" "3/4d6" (best 3 of 4 d6)

diceRoll("2d8+2"); 
diceRoll("4-18");
diceRoll("3/4d6");

to check cumulative rolls, better loop on matched result ove rthe input string like

r = "2d8+2+3/4d6"
r.match(/([-+])?(\d+)?(?:\/(\d+))?[dD](\d+)(?:([-+])(\d+)\b)?/g);
// => ["2d8+2", "+3/4d6"]
// a program can manage the "+" or "-" on the second one (usually is always an addiction)

回答14:

PHP, 147 symbols, no eval:



preg_match('/(\d+)?d(\d+)[\s+]?([\+\*])?[\s+]?(\d+)?/',$i,$a);$d=rand(1,$a[2])*((!$a[1])?1:$a[1]);$e['+']=$d+$a[4];$e['*']=$d*$a[4];print$e[$a[3]];

$i contains input string.

Edit: oops, forgot about prefixed operation. brb.

标签： language-agnostic dice expression-evaluation

混吃等死

女 | 书童

私信

收藏的人(0)

Ta的文章更多文章

0条评论

还没有人评论过~