tło
Gram w D&D regularnie z kilkoma przyjaciółmi. Mówiąc o złożoności niektórych systemów / wersji, jeśli chodzi o rzucanie kostkami oraz stosowanie bonusów i kar, żartobliwie wymyśliliśmy dodatkową złożoność wyrażeń rzucanych kostkami. Niektóre z nich były zbyt oburzające (np. Rozszerzanie prostych wyrażeń kostek, jak 2d6na argumenty matrycowe 1 ), ale reszta tworzy interesujący system.
Wyzwanie
Biorąc pod uwagę złożone wyrażenie kostki, oceń je zgodnie z następującymi regułami i wyślij wynik.
Podstawowe zasady oceny
- Ilekroć operator oczekuje liczby całkowitej, ale otrzymuje listę argumentów, używana jest suma tej listy
- Ilekroć operator oczekuje listy, ale otrzymuje liczbę całkowitą dla argumentu, liczba całkowita jest traktowana jako lista jednoelementowa zawierająca tę liczbę całkowitą
Operatorzy
Wszyscy operatorzy są operatorami binarnych infix. Dla celów wyjaśnienia abędzie lewym operandem i bbędzie prawym operandem. Notacja listy będzie używana w przykładach, w których operatorzy mogą traktować listy jako operandy, ale rzeczywiste wyrażenia składają się tylko z dodatnich liczb całkowitych i operatorów.
d: wyjścioweaniezależne jednolite losowe liczby całkowite w zakresie[1, b]- Pierwszeństwo: 3
- Oba operandy są liczbami całkowitymi
- Przykłady:
3d4 => [1, 4, 3],[1, 2]d6 => [3, 2, 6]
t: weźbnajniższe wartości za- Pierwszeństwo: 2
ajest listą,bjest liczbą całkowitą- Jeśli
b > len(a)wszystkie wartości są zwracane - Przykłady:
[1, 5, 7]t1 => [1],[5, 18, 3, 9]t2 => [3, 5],3t5 => [3]
T: weźbnajwyższe wartości za- Pierwszeństwo: 2
ajest listą,bjest liczbą całkowitą- Jeśli
b > len(a)wszystkie wartości są zwracane - Przykłady:
[1, 5, 7]T1 => [7],[5, 18, 3, 9]T2 => [18, 9],3T5 => [3]
r: Czy jakieś elementybsąa, przerzucić te elementy, używając cokolwiekdwygenerowanej instrukcji- Pierwszeństwo: 2
- Oba operandy są listami
- Ponowne przechodzenie jest wykonywane tylko raz, więc możliwe jest, aby nadal mieć elementy
bw wyniku - Przykłady:
3d6r1 => [1, 3, 4] => [6, 3, 4],2d4r2 => [2, 2] => [3, 2],3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
R: jeśli jakieś elementybsą waśrodku, przewijaj je wielokrotnie, aż nie będzie żadnych elementówb, używając cokolwiekdinstrukcji, która je wygenerowała- Pierwszeństwo: 2
- Oba operandy są listami
- Przykłady:
3d6R1 => [1, 3, 4] => [6, 3, 4],2d4R2 => [2, 2] => [3, 2] => [3, 1],3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
+: dodajaibrazem- Pierwszeństwo: 1
- Oba operandy są liczbami całkowitymi
- Przykłady:
2+2 => 4,[2]+[2] => 4,[3, 1]+2 => 6
-: odejmijboda- Pierwszeństwo: 1
- Oba operandy są liczbami całkowitymi
bzawsze będzie mniej niża- Przykłady:
2-1 => 1,5-[2] => 3,[8, 3]-1 => 10
.: konkatenataibrazem- Pierwszeństwo: 1
- Oba operandy są listami
- Przykłady:
2.2 => [2, 2],[1].[2] => [1, 2],3.[4] => [3, 4]
_: wyjścieaze wszystkimi elementamibusuniętymi- Pierwszeństwo: 1
- Oba operandy są listami
- Przykłady:
[3, 4]_[3] => [4],[2, 3, 3]_3 => [2],1_2 => [1]
Dodatkowe zasady
- Jeśli końcową wartością wyrażenia jest lista, jest ona sumowana przed wyjściem
- Ocena pojęć da w wyniku tylko dodatnie liczby całkowite lub listy dodatnich liczb całkowitych - każde wyrażenie, które skutkuje nieujemną liczbą całkowitą lub listą zawierającą co najmniej jedną nieujemną liczbę całkowitą, spowoduje zastąpienie tych wartości
1s - Nawiasów można używać do grupowania terminów i określania kolejności oceny
- Operatory są oceniane w kolejności od najwyższego pierwszeństwa do najniższego pierwszeństwa, przy czym ewaluacja przebiega od lewej do prawej w przypadku powiązanego pierwszeństwa (tak
1d4d4byłoby oceniane jako(1d4)d4) - Kolejność elementów na listach nie ma znaczenia - operator, który modyfikuje listę, jest w pełni akceptowalny, aby zwrócić ją wraz z elementami w innej kolejności względnej
- Warunki, których nie można ocenić lub które mogłyby spowodować nieskończoną pętlę (jak
1d1R1lub3d6R[1, 2, 3, 4, 5, 6]) są nieprawidłowe
Przypadki testowe
Format: 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
Wszystkie przypadki testowe oprócz ostatniego zostały wygenerowane z implementacją referencyjną.
Przykład działania
Wyrażenie: 1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))
8d20t4T2 => [19, 5, 11, 6, 19, 15, 4, 20]t4T2 => [4, 5, 6, 11]T2 => [11, 6](pełny1d(([11, 6])d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3)):)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)))[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)))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)))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)))[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)))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]))1d[1, 3, 3, 6, 3, 2, 2] => 1d20 => 6(1d128).(6))1d128 => 55(55.6)55.6 => [55, 6]([55, 6])[55, 6] => 61(gotowy)
Wdrożenie referencyjne
Ta implementacja referencyjna używa tego samego stałego seed ( 0) do oceny każdego wyrażenia w celu uzyskania spójnych wyników. Oczekuje danych wejściowych na STDIN, z nowymi liniami oddzielającymi każde wyrażenie.
#!/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]: Nasza definicja adbargumentów macierzy polegała na wprowadzeniu AdXdla każdego Xw a * b, gdzie A = det(a * b). Najwyraźniej jest to zbyt absurdalne dla tego wyzwania.
Link do piaskownicy
—
Mego
Z gwarancją na
—
Christian Sievers
-to bzawsze będzie mniej niż anie widzę żadnego sposobu na uzyskanie dodatnich liczb całkowitych, więc druga dodatkowa zasada wydaje się bezcelowa. OTOH, _może zaowocować pustą listą, co wydaje się przydatne w tych samych przypadkach, ale co to znaczy, gdy potrzebna jest liczba całkowita? Zwykle powiedziałbym, że suma jest 0...
@ChristianSievers 1) Dodałem dodatkową notatkę o nieujemnych liczbach całkowitych dla jasności. 2) Suma pustej listy wynosi
—
Mego
0. Zgodnie z regułą nie-pozytywną byłby oceniany jako 1.
Okej, ale czy to w porządku jako wynik pośredni? Tak
—
Christian Sievers
[1,2]_([1]_[1])jest [1,2]?
@ChristianSievers Nie. To spowodowałoby
—
Mego
[2], ponieważ [1]_[1] -> [] -> 0 -> 1 -> [1].