fundo

Eu jogo D&D regularmente com alguns amigos. Enquanto falamos sobre a complexidade de alguns sistemas / versões quando se trata de rolar dados e aplicar bônus e penalidades, brincamos com uma complexidade adicional para expressões de rolar dados. Alguns deles eram muito escandalosos (como estender expressões de dados simples, como os 2d6argumentos da matriz ¹ ), mas o resto cria um sistema interessante.

O desafio

Dada uma expressão complexa de dados, avalie-a de acordo com as seguintes regras e produza o resultado.

Regras básicas de avaliação

• Sempre que um operador espera um número inteiro, mas recebe uma lista para um operando, a soma dessa lista é usada
• Sempre que um operador espera uma lista, mas recebe um número inteiro para um operando, o número inteiro é tratado como uma lista de um elemento que contém esse número inteiro

Operadores

Todos os operadores são operadores de infix binários. Para fins de explicação, aserá o operando esquerdo e bserá o operando direito. A notação de lista será usada para exemplos em que os operadores podem receber listas como operandos, mas as expressões reais consistem apenas em números inteiros positivos e operadores.

• d: agera números inteiros aleatórios uniformes independentes no intervalo[1, b]
  • Precedência: 3
  • Ambos os operandos são inteiros
  • Exemplos: 3d4 => [1, 4, 3],[1, 2]d6 => [3, 2, 6]
• t: pegue os bvalores mais baixos dea
  • Precedência: 2
  • aé uma lista, bé um número inteiro
  • Se b > len(a)todos os valores forem retornados
  • Exemplos: [1, 5, 7]t1 => [1], [5, 18, 3, 9]t2 => [3, 5],3t5 => [3]
• T: pegue os bvalores mais altos dea
  • Precedência: 2
  • aé uma lista, bé um número inteiro
  • Se b > len(a)todos os valores forem retornados
  • Exemplos: [1, 5, 7]T1 => [7], [5, 18, 3, 9]T2 => [18, 9],3T5 => [3]
• r: Se quaisquer elementos bestão em a, refazer esses elementos, usando qualquer ddeclaração los gerado
  • Precedência: 2
  • Ambos os operandos são listas
  • A nova rolagem é feita apenas uma vez, portanto, é possível ainda ter elementos bno resultado
  • Exemplos: 3d6r1 => [1, 3, 4] => [6, 3, 4], 2d4r2 => [2, 2] => [3, 2],3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
• R: Se quaisquer elementos bestão em a, refazer esses elementos repetidamente até que há elementos de bestão presentes, usando qualquer ddeclaração los gerado
  • Precedência: 2
  • Ambos os operandos são listas
  • Exemplos: 3d6R1 => [1, 3, 4] => [6, 3, 4], 2d4R2 => [2, 2] => [3, 2] => [3, 1],3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
• +: adicionar ae bjuntar
  • Precedência: 1
  • Ambos os operandos são inteiros
  • Exemplos: 2+2 => 4, [2]+[2] => 4,[3, 1]+2 => 6
• -: subtrair bdea
  • Precedência: 1
  • Ambos os operandos são inteiros
  • b sempre será menor que a
  • Exemplos: 2-1 => 1, 5-[2] => 3,[8, 3]-1 => 10
• .: concatenar ae bjuntos
  • Precedência: 1
  • Ambos os operandos são listas
  • Exemplos: 2.2 => [2, 2], [1].[2] => [1, 2],3.[4] => [3, 4]
• _: saída acom todos os elementos de bremovido
  • Precedência: 1
  • Ambos os operandos são listas
  • Exemplos: [3, 4]_[3] => [4], [2, 3, 3]_3 => [2],1_2 => [1]

Regras adicionais

• Se o valor final de uma expressão for uma lista, ele será somado antes da saída
• A avaliação de termos resultará apenas em números inteiros positivos ou em listas de números inteiros positivos - qualquer expressão que resulte em um número inteiro não positivo ou em uma lista que contenha pelo menos um número inteiro não positivo terá esses valores substituídos por 1s
• Parênteses podem ser usados ​​para agrupar termos e especificar a ordem da avaliação
• Os operadores são avaliados na ordem da precedência mais alta à precedência mais baixa, com a avaliação prosseguindo da esquerda para a direita no caso de precedência vinculada (isso 1d4d4seria avaliado como (1d4)d4)
• A ordem dos elementos nas listas não importa - é perfeitamente aceitável que um operador que modifique uma lista retorne-a com seus elementos em uma ordem relativa diferente
• Termos que não podem ser avaliados ou resultariam em um loop infinito (como 1d1R1ou 3d6R[1, 2, 3, 4, 5, 6]) não são válidos

Casos de teste

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, exceto o último caso de teste, foram gerados com a implementação de referência.

Exemplo Trabalhado

Expressão: 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 (feito)

Implementação de referência

Essa implementação de referência usa a mesma semente constante ( 0) para avaliar cada expressão para resultados consistentes e testáveis. Ele espera entrada no STDIN, com novas linhas separando cada expressão.

#!/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]: A nossa definição de adbpara argumentos de matriz era rolo AdXpara cada Xno a * b, onde A = det(a * b). Claramente, isso é absurdo demais para esse desafio.}

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 graças a Mr.Xcoder

-5 mais bytes graças a NGN

cerca de 40 bytes graças a Jonathan French

Eca, que kludge! Isso funciona usando uma expressão regular para agrupar todos os números da minha kclasse e convertendo todos os operadores em operadores que python entende, depois usando os métodos mágicos da kclasse para lidar com a matemática. O +-e +--no final de .e _são um hack para manter a precedência correta. Da mesma forma, não posso usar o **operador para d porque isso seria 1d4d4analisado como 1d(4d4). Em vez disso, agrupo todos os números em um conjunto extra de parênteses e o faço como .j, pois as chamadas de método têm maior precedência que os operadores. A última linha é avaliada como uma função anônima que avalia a expressão.

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

Experimente online!

Esse é o algoritmo do shunting yard da implementação de referência mesclada evaluate_dice(), sem o cruft e o absurdo orientado a objetos. Apenas duas pilhas são usadas: hpara os operadores e vpara os valores. A análise e a avaliação são intercaladas.

Os resultados intermediários são representados como matrizes 2 × N, onde a primeira linha são os valores aleatórios e a segunda linha é o número de lados nos dados que os produziram. Quando um resultado não é produzido pelo operador "d" de lançamento de dados, a segunda linha contém números arbitrários. Um único valor aleatório é uma matriz 2 × 1 e, portanto, indistinguível de uma 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)

O ponto de entrada é E. Isso aplica expressões regulares iterativamente. Primeiro, ele substitui todos os números inteiros xpor uma tupla da lista de singleton [(x,0)]. Em seguida, a primeira expressão regular executa a doperação, substituindo todos [(x,0)]d[(b,0)]pela representação em cadeia de uma matriz de tuplas como [(1,b),(2,b),(3,b)]. O segundo elemento de cada tupla é o segundo operando para d. Em seguida, expressões regulares subsequentes executam cada um dos outros operadores. Existe uma regex especial para remover parênteses de expressões totalmente calculadas.

Clojure, 731 720 bytes

(quando novas linhas são removidas)

Atualização: uma implementação mais curta do 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 "))))))

Isso consiste em quatro partes principais:

• N: força uma lista a um número
• g: avalia uma árvore de sintaxe abstrata (expressões S com 3 itens)
• F: converte um AST infixo em notação de prefixo (expressões S), também aplica precedência de ordem de operando
• f: usa read-stringpara converter uma sequência em uma sequência aninhada de números e símbolos (infixo AST), canaliza-os através de F -> g -> N, retornando o número do resultado.

Não sei como testá-lo completamente, talvez por meio de testes estatísticos em uma implementação de referência? Pelo menos o AST e sua avaliação são relativamente fáceis de seguir.

Exemplo de expressão 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 jogado com resultados e testes intermediários:

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

Um intérprete criado usando tatsuuma biblioteca de analisador PEG. O primeiro argumento para tatsu.parser()é a gramática PEG.

class D(para matriz) subclasses do inttipo incorporado . Seu valor é o resultado de um rolo. O atributo .sé o número de lados no dado.

class S possui as ações semânticas para o analisador e implementa o intérprete.