Задний план

Я регулярно играю в D & D с друзьями. Говоря о сложности некоторых систем / версий, когда речь идет о броске кубиков и применении бонусов и штрафов, мы в шутку придумали некоторую дополнительную сложность для выражений броска кубиков. Некоторые из них были слишком возмутительными (например, расширение простых выражений в виде костей, как 2d6в матричных аргументах ¹ ), но остальные создают интересную систему.

Соревнование

Учитывая сложное выражение кости, оцените его согласно следующим правилам и выведите результат.

Основные правила оценки

• Всякий раз, когда оператор ожидает целое число, но получает список для операнда, используется сумма этого списка
• Всякий раз, когда оператор ожидает список, но получает целое число для операнда, целое число обрабатывается как одноэлементный список, содержащий это целое число

операторы

Все операторы являются бинарными инфиксными операторами. В целях объяснения, aбудет левый операнд, и bбудет правым операндом. Нотация списка будет использоваться для примеров, где операторы могут принимать списки в качестве операндов, но фактические выражения состоят только из натуральных чисел и операторов.

• d: вывести aнезависимые равномерные случайные числа в диапазоне[1, b]
  • Старшинство: 3
  • Оба операнда являются целыми числами
  • Примеры: 3d4 => [1, 4, 3],[1, 2]d6 => [3, 2, 6]
• t: взять самые bнизкие значения изa
  • Старшинство: 2
  • aсписок, bцелое число
  • Если b > len(a)все значения возвращены
  • Примеры: [1, 5, 7]t1 => [1], [5, 18, 3, 9]t2 => [3, 5],3t5 => [3]
• T: принять самые bвысокие значения изa
  • Старшинство: 2
  • aсписок, bцелое число
  • Если b > len(a)все значения возвращены
  • Примеры: [1, 5, 7]T1 => [7], [5, 18, 3, 9]T2 => [18, 9],3T5 => [3]
• r: Если какие - либо элементы bв a, перебросить эти элементы, используя любое dзаявление генерироваться их
  • Старшинство: 2
  • Оба операнда являются списками
  • Перекат делается только один раз, так что можно еще элементы bв результате
  • Примеры: 3d6r1 => [1, 3, 4] => [6, 3, 4], 2d4r2 => [2, 2] => [3, 2],3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
• R: Если какие - либо элементы bв a, перебросить эти элементы , пока никаких элементов bнет, используя любое dзаявление генерироваться их
  • Старшинство: 2
  • Оба операнда являются списками
  • Примеры: 3d6R1 => [1, 3, 4] => [6, 3, 4], 2d4R2 => [2, 2] => [3, 2] => [3, 1],3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
• +: добавить aи bвместе
  • Старшинство: 1
  • Оба операнда являются целыми числами
  • Примеры: 2+2 => 4, [2]+[2] => 4,[3, 1]+2 => 6
• -: вычесть bизa
  • Старшинство: 1
  • Оба операнда являются целыми числами
  • b всегда будет меньше чем a
  • Примеры: 2-1 => 1, 5-[2] => 3,[8, 3]-1 => 10
• .: concateate aи bвместе
  • Старшинство: 1
  • Оба операнда являются списками
  • Примеры: 2.2 => [2, 2], [1].[2] => [1, 2],3.[4] => [3, 4]
• _: вывод aсо всеми bудаленными элементами
  • Старшинство: 1
  • Оба операнда являются списками
  • Примеры: [3, 4]_[3] => [4], [2, 3, 3]_3 => [2],1_2 => [1]

Дополнительные правила

• Если конечное значение выражения является списком, оно суммируется перед выводом
• Оценка терминов приведет только к положительным целым числам или спискам положительных целых чисел - любое выражение, которое приводит к неположительному целому числу или списку, содержащему хотя бы одно неположительное целое число, будет заменять эти значения на 1s
• Скобки можно использовать для группировки терминов и определения порядка оценки
• Операторы оцениваются в порядке наивысшего приоритета и наименьшего приоритета, причем оценка выполняется слева направо в случае связанного приоритета (поэтому 1d4d4будет оцениваться как (1d4)d4)
• Порядок элементов в списках не имеет значения - он вполне приемлем для оператора, который изменяет список, чтобы возвращать его со своими элементами в другом относительном порядке.
• Термины, которые не могут быть оценены или могут привести к бесконечному циклу (например, 1d1R1или 3d6R[1, 2, 3, 4, 5, 6]), недействительны

Тестовые случаи

Формат: 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

Все, кроме последнего контрольного примера, были созданы с помощью эталонной реализации.

Работал пример

Выражение: 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](полный текст 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 (сделанный)

Реализация эталона

Эта эталонная реализация использует одну и ту же константу seed ( 0) для оценки каждого выражения для проверяемых, согласованных выходных данных. Он ожидает ввода в STDIN, с символами новой строки, разделяющими каждое выражение.

#!/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]: Наше определение adbдля матричных аргументов состояло в том, чтобы переходить AdXдля каждого Xin a * b, где A = det(a * b). Очевидно, что это слишком абсурдно для этого вызова.}

Python 3, 803 788 753 749 744 748 745 740 700 695 682 байта

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 байт благодаря Mr.Xcoder

-5 больше байтов благодаря NGN

- около 40 байтов благодаря Джонатану Френчу

Фу, какой клудж! Это работает с помощью регулярного выражения, чтобы обернуть все числа в моем kклассе, и преобразование всех операторов в операторы, понятные Python, а затем использование магических методов kкласса для обработки математических операций . +-И +--в конце для .и _являются хак , чтобы сохранить преимущество правильно. Аналогично, я не могу использовать **оператор для d, потому что при этом будет 1d4d4проанализировано как 1d(4d4). Вместо этого я обертываю все числа в дополнительный набор символов и делаю d as .j, поскольку вызовы методов имеют более высокий приоритет, чем операторы. Последняя строка оценивается как анонимная функция, которая оценивает выражение.

APL (Dyalog Classic) , 367 байтов

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

Попробуйте онлайн!

Это алгоритм маневрового двора из эталонной реализации, слитый evaluate_dice()без лишних и объектно-ориентированных глупостей. Используются только два стека: hдля операторов и vдля значений. Разбор и оценка чередуются.

Промежуточные результаты представлены в виде матриц 2 × N, где первая строка - это случайные значения, а вторая строка - количество сторон на кости, которая их произвела. Когда результат не выдается оператором «d», бросающим кости, вторая строка содержит произвольные числа. Одно случайное значение представляет собой матрицу 2 × 1 и, таким образом, неотличимо от списка из 1 элемента.

Python 3: 723 722 714 711 707 675 653 665 байт

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)

Точка входа есть E. Это применяет регулярные выражения итеративно. Сначала он заменяет все целые числа xнабором одноэлементного списка [(x,0)]. Затем первое регулярное выражение выполняет dоперацию, заменяя все [(x,0)]d[(b,0)]строковым представлением массива кортежей типа [(1,b),(2,b),(3,b)]. Второй элемент каждого кортежа является вторым операндом d. Затем последующие регулярные выражения выполняют каждый из остальных операторов. Существует специальное регулярное выражение для удаления паренов из полностью вычисляемых выражений.

Clojure, 731 720 байт

(когда удаляются новые строки)

Обновление: более короткая реализация 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 "))))))

Он состоит из четырех основных частей:

• N: приводит список в число
• g: оценивает абстрактное синтаксическое дерево (S-выражения с 3 элементами)
• F: преобразует инфиксный AST в префиксную нотацию (S-выражения), также применяет приоритет операнда
• f: использует read-stringдля преобразования строки во вложенную последовательность чисел и символов (инфикс AST), передает их через F -> g -> N, возвращая номер результата.

Я не уверен, как тщательно это проверить, может быть, с помощью статистических тестов с эталонной реализацией? По крайней мере, AST и его оценка относительно просты для отслеживания.

Пример S-выражения из 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))))

Меньше игры в гольф с промежуточными результатами и тестами:

(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 байт

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

Интерпретатор построен с использованием tatsuбиблиотеки синтаксического анализатора PEG. Первым аргументом tatsu.parser()является грамматика PEG.

class D(для Die) подклассы встроенного intтипа. Это значение является результатом броска. Атрибутом .sявляется количество сторон на кристалле.

class S имеет семантические действия для синтаксического анализатора и реализует интерпретатор.