Fondo

Juego D&D regularmente con algunos amigos. Mientras hablamos de la complejidad de algunos sistemas / versiones cuando se trata de lanzar dados y aplicar bonos y penalizaciones, bromeamos con cierta complejidad adicional para las expresiones de lanzamiento de dados. Algunos de ellos eran demasiado escandalosos (como extender expresiones simples de dados, como los 2d6argumentos de matriz ¹ ), pero el resto crea un sistema interesante.

El reto

Dada una expresión de dados compleja, evalúela de acuerdo con las siguientes reglas y genere el resultado.

Reglas básicas de evaluación

• Siempre que un operador espera un número entero pero recibe una lista para un operando, se utiliza la suma de esa lista
• Cada vez que un operador espera una lista pero recibe un entero para un operando, el entero se trata como una lista de un elemento que contiene ese entero

Operadores

Todos los operadores son operadores infix binarios. Para fines de explicación, aserá el operando izquierdo y bserá el operando derecho. La notación de lista se usará para ejemplos en los que los operadores pueden tomar listas como operandos, pero las expresiones reales consisten solo en enteros positivos y operadores.

• d: salida de aenteros aleatorios uniformes independientes en el rango[1, b]
  • Precedencia: 3
  • Ambos operandos son enteros.
  • Ejemplos: 3d4 => [1, 4, 3],[1, 2]d6 => [3, 2, 6]
• t: toma los bvalores más bajos dea
  • Precedencia: 2
  • aes una lista, bes un entero
  • Si b > len(a), se devuelven todos los valores
  • Ejemplos: [1, 5, 7]t1 => [1], [5, 18, 3, 9]t2 => [3, 5],3t5 => [3]
• T: toma los bvalores más altos dea
  • Precedencia: 2
  • aes una lista, bes un entero
  • Si b > len(a), se devuelven todos los valores
  • Ejemplos: [1, 5, 7]T1 => [7], [5, 18, 3, 9]T2 => [18, 9],3T5 => [3]
• r: Si cualquier elemento en bestán en a, volver a tirar esos elementos, usando cualquier ddeclaración que genera
  • Precedencia: 2
  • Ambos operandos son listas
  • El cambio de rol se realiza solo una vez, por lo que aún es posible tener elementos de ben el resultado
  • Ejemplos: 3d6r1 => [1, 3, 4] => [6, 3, 4], 2d4r2 => [2, 2] => [3, 2],3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
• R: Si cualquier elemento en bestán en a, volver a tirar los elementos repetidamente hasta que no hay elementos de bestán presentes, usando cualquier ddeclaración que genera
  • Precedencia: 2
  • Ambos operandos son listas
  • Ejemplos: 3d6R1 => [1, 3, 4] => [6, 3, 4], 2d4R2 => [2, 2] => [3, 2] => [3, 1],3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
• +: agregar ay bjuntos
  • Precedencia: 1
  • Ambos operandos son enteros.
  • Ejemplos: 2+2 => 4, [2]+[2] => 4,[3, 1]+2 => 6
• -: restar bdea
  • Precedencia: 1
  • Ambos operandos son enteros.
  • b siempre será menor que a
  • Ejemplos: 2-1 => 1, 5-[2] => 3,[8, 3]-1 => 10
• .: concatenar ay bjuntos
  • Precedencia: 1
  • Ambos operandos son listas
  • Ejemplos: 2.2 => [2, 2], [1].[2] => [1, 2],3.[4] => [3, 4]
• _: salida acon todos los elementos de beliminado
  • Precedencia: 1
  • Ambos operandos son listas
  • Ejemplos: [3, 4]_[3] => [4], [2, 3, 3]_3 => [2],1_2 => [1]

Reglas Adicionales

• Si el valor final de una expresión es una lista, se suma antes de la salida
• La evaluación de los términos solo dará como resultado enteros positivos o listas de enteros positivos: cualquier expresión que dé como resultado un entero no positivo o una lista que contenga al menos un entero no positivo tendrá esos valores reemplazados por 1s
• Los paréntesis pueden usarse para agrupar términos y especificar el orden de evaluación
• Los operadores se evalúan en orden de precedencia más alta a precedencia más baja, y la evaluación se realiza de izquierda a derecha en el caso de precedencia vinculada (por 1d4d4lo que se evaluaría como (1d4)d4)
• El orden de los elementos en las listas no importa: es perfectamente aceptable que un operador que modifica una lista la devuelva con sus elementos en un orden relativo diferente
• Los términos que no pueden evaluarse o darían lugar a un bucle infinito (como 1d1R1o 3d6R[1, 2, 3, 4, 5, 6]) no son válidos

Casos de prueba

Formato: 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

Todos menos el último caso de prueba se generaron con la implementación de referencia.

Ejemplo trabajado

Expresión: 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](completo: 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 (hecho)

Implementación de referencia

Esta implementación de referencia utiliza la misma semilla constante ( 0) para evaluar cada expresión para resultados comprobables y consistentes. Espera entrada en STDIN, con nuevas líneas que separan cada expresión.

#!/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]

def add(a, b):
    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)
    def __add__(self, other):
        return int(self) + int(other)
    def __sub__(self, other):
        return int(self) - int(other)
    __radd__ = __add__
    __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, add),
    '-': 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]: Nuestra definición de adbargumentos de matriz era rodar AdXpara cada Xen a * b, donde A = det(a * b). Claramente eso es demasiado absurdo para este desafío.}

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

exec(r'''from random import*
import re
class k(int):
 p=0;j=Xl([d(randint(1,int(b)),b)Zrange(a)]);__mul__=Xl(sorted(Y)[:b]);__matmul__=Xl(sorted(Y)[-b:]);__truediv__=Xl([d(randint(1,int(_.i)),_.i)if _==b else _ ZY]);__sub__=Xk(max(1,int.__sub__(a,b)))
 def __mod__(a,b):
  x=[]
  while x!=Y:x=Y;a=a/b
  Wl(x)
 def V:
  if b.p:p=b.p;del b.p;Wl(Y+b.l)if~-p else l([_ZY if~-(_ in b.l)])
  Wk(int.V)
 def __neg__(a):a.p+=1;Wa
def l(x):a=k(sum(x)or 1);Y=x;Wa
def d(v,i):d=k(v);d.i=i;Wd
lambda a:eval(re.sub("(\d+)","(k(\\1))",a).translate({100:".j",116:"*",84:"@",114:"/",82:"%",46:"+--",95:"+-"}))'''.translate({90:" for _ in ",89:"a.l",88:"lambda a,b:",87:"return ",86:"__add__(a,b)"}))

-5 bytes gracias a Mr.Xcoder

-5 bytes más gracias a NGN

-aproximadamente 40 bytes gracias a Jonathan French

¡Qué asco, qué tontería! Esto funciona mediante el uso de una expresión regular para ajustar todos los números en mi kclase, y la conversión de todos los operadores en operadores que Python entiende, y luego utilizando los métodos mágicos de la kclase para manejar las matemáticas. El +-y +--al final para .y _son un truco para mantener la precedencia correcta. Del mismo modo, no puedo usar el **operador para d porque al hacerlo 1d4d4se analizaría como 1d(4d4). En cambio, envuelvo todos los números en un conjunto adicional de parens y hago d as .j, ya que las llamadas a métodos tienen mayor prioridad que los operadores. La última línea se evalúa como una función anónima que evalúa la expresión.

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

Pruébalo en línea!

Este es el algoritmo de yardas de derivación de la implementación de referencia fusionada con evaluate_dice(), sin la tontería cruda y orientada a objetos. Solo se utilizan dos pilas: hpara los operadores yv para los valores. El análisis y la evaluación están intercalados.

Los resultados intermedios se representan como matrices 2 × N, donde la primera fila son los valores aleatorios y la segunda fila es el número de lados en los dados que los produjeron. Cuando el operador "d" que lanza los dados no produce un resultado, la segunda fila contiene números arbitrarios. Un único valor aleatorio es una matriz 2 × 1 y, por lo tanto, no se puede distinguir de una lista de 1 elemento.

Python 3: 723 722 714 711 707 675 653 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)

El punto de entrada es E. Esto aplica expresiones regulares de forma iterativa. Primero reemplaza todos los enteros xcon una tupla de lista singleton [(x,0)]. Luego, la primera expresión regular realiza la doperación, reemplazando todo [(x,0)]d[(b,0)]con la representación de cadena de una matriz de tuplas como [(1,b),(2,b),(3,b)]. El segundo elemento de cada tupla es el segundo operando a d. Luego, las expresiones regulares posteriores realizan cada uno de los otros operadores. Hay una expresión regular especial para eliminar parens de expresiones totalmente calculadas.

Clojure, 731 720 bytes

(cuando se eliminan nuevas líneas)

Actualización: una implementación más corta de 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 "))))))

Este consta de cuatro partes principales:

• N: coacciona una lista en un número
• g: evalúa un árbol de sintaxis abstracta (expresiones S con 3 elementos)
• F: convierte un AST infijo en notación de prefijo (expresiones S), también aplica la prioridad de orden de operando
• f: usos read-string para convertir una cadena en una secuencia anidada de números y símbolos (infijo AST), los canaliza a través de F -> g -> N, devolviendo el número de resultado.

No estoy seguro de cómo probar esto a fondo, ¿tal vez a través de pruebas estadísticas contra una implementación de referencia? Al menos el AST y su evaluación son relativamente fáciles de seguir.

Ejemplo de expresión S de 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))))

Menos golf con resultados y pruebas de internado:

(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))

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())

Un intérprete creado con tatsuuna biblioteca de analizador PEG. El primer argumento tatsu.parser()es la gramática PEG.

class D(para Die) subclases del inttipo incorporado . Su valor es el resultado de un rollo. El atributo .ses el número de lados en el dado.

class S tiene las acciones semánticas para el analizador e implementa el intérprete.