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 2d6
na 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 a
będzie lewym operandem i b
bę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ściowea
niezależ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źb
najniższe wartości za
- Pierwszeństwo: 2
a
jest listą,b
jest 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źb
najwyższe wartości za
- Pierwszeństwo: 2
a
jest listą,b
jest 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ś elementyb
sąa
, przerzucić te elementy, używając cokolwiekd
wygenerowanej instrukcji- Pierwszeństwo: 2
- Oba operandy są listami
- Ponowne przechodzenie jest wykonywane tylko raz, więc możliwe jest, aby nadal mieć elementy
b
w 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ś elementyb
są wa
środku, przewijaj je wielokrotnie, aż nie będzie żadnych elementówb
, używając cokolwiekd
instrukcji, 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]
+
: dodaja
ib
razem- Pierwszeństwo: 1
- Oba operandy są liczbami całkowitymi
- Przykłady:
2+2 => 4
,[2]+[2] => 4
,[3, 1]+2 => 6
-
: odejmijb
oda
- Pierwszeństwo: 1
- Oba operandy są liczbami całkowitymi
b
zawsze będzie mniej niża
- Przykłady:
2-1 => 1
,5-[2] => 3
,[8, 3]-1 => 10
.
: konkatenata
ib
razem- Pierwszeństwo: 1
- Oba operandy są listami
- Przykłady:
2.2 => [2, 2]
,[1].[2] => [1, 2]
,3.[4] => [3, 4]
_
: wyjściea
ze wszystkimi elementamib
usunię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
1
s - 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
1d4d4
był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
1d1R1
lub3d6R[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 adb
argumentów macierzy polegała na wprowadzeniu AdX
dla każdego X
w a * b
, gdzie A = det(a * b)
. Najwyraźniej jest to zbyt absurdalne dla tego wyzwania.
-
tob
zawsze będzie mniej niża
nie 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 jest0
...0
. Zgodnie z regułą nie-pozytywną byłby oceniany jako1
.[1,2]_([1]_[1])
jest[1,2]
?[2]
, ponieważ[1]_[1] -> [] -> 0 -> 1 -> [1]
.Odpowiedzi:
Python 3,
803 788 753 749 744 748 745 740 700 695682 bajtów-5 bajtów dzięki Mr.Xcoder
-5 więcej bajtów dzięki NGN
- około 40 bajtów dzięki Jonathanowi Frenchowi
Fuj, co za kludge! Działa to poprzez użycie wyrażenia regularnego do zawijania wszystkich liczb w mojej
k
klasie i przekształcenie wszystkich operatorów w operatory, które rozumie Python, a następnie użycie magicznych metodk
klasy do obsługi matematyki.+-
I+--
na koniec dla.
i_
są hack zachować pierwszeństwo poprawne. Podobnie, nie mogę użyć**
operatora dla d, ponieważ spowodowałoby1d4d4
to parsowanie jako1d(4d4)
. Zamiast tego zawijam wszystkie liczby w dodatkowy zestaw parens i robię d as.j
, ponieważ wywołania metod mają wyższy priorytet niż operatory. Ostatni wiersz jest analizowany jako anonimowa funkcja, która ocenia wyrażenie.źródło
def __mod__(a, b)
... Dlaczego przestrzeń międzya,
ib
?; __sub__
. I ewentualnie również tutaj:lambda a,b: l(
.exec("""...""".replace("...","..."))
instrukcji i zastępując ciągi, które występują często (jakreturn
) jednym znakiem. Jednak dla mnie strategiaexec
zawsze wydaje się nieco nieelegancka ...__mod__
i__add__
nie potrzebują tak wiele wcięćAPL (Dyalog Classic) , 367 bajtów
Wypróbuj online!
Jest to algorytm manewrowania stoczni z implementacji referencyjnej scalony
evaluate_dice()
, bez bzdury i obiektowych bzdur. Używane są tylko dwa stosy:h
dla operatorów iv
dla wartości. Analiza składniowa i ocena są przeplatane.Wyniki pośrednie są reprezentowane jako macierze 2 × N, gdzie pierwszy rząd to losowe wartości, a drugi rząd to liczba boków kostki, która je wytworzyła. Gdy wynik „d” nie rzuca kostką, drugi rząd zawiera dowolne liczby. Pojedyncza wartość losowa to macierz 2 × 1, a zatem nie można jej odróżnić od listy 1-elementowej.
źródło
Python 3:
723722714711707675653665 bajtówPunktem wejścia jest
E
. Dotyczy to iteracyjnie wyrażeń regularnych. Najpierw zastępuje wszystkie liczby całkowitex
krotką listy singletonów[(x,0)]
. Następnie pierwsze wyrażenie regularne wykonujed
operację, zastępując wszystko[(x,0)]d[(b,0)]
ciągiem reprezentującym tablicę krotek takich jak[(1,b),(2,b),(3,b)]
. Drugim elementem każdej krotki jest drugi operand dod
. Następnie kolejne wyrażenia regularne wykonują każdy z pozostałych operatorów. Istnieje specjalna regex do usuwania parens z w pełni obliczonych wyrażeń.źródło
Clojure,
731720 bajtów(po usunięciu nowych linii)
Aktualizacja: krótsza implementacja
F
.Składa się z czterech głównych części:
N
: wymusza listę na liczbęg
: ocenia abstrakcyjne drzewo składniowe (wyrażenia S z 3 elementami)F
: konwertuje przedrostek AST na notację przedrostkową (wyrażenia S), stosuje również pierwszeństwo kolejności operandówf
: używaread-string
do konwersji łańcucha na zagnieżdżoną sekwencję liczb i symboli (infix AST), przepuszcza je przez F -> g -> N, zwracając liczbę wynikową.Nie jestem pewien, jak dokładnie to przetestować, może za pomocą testów statystycznych w odniesieniu do implementacji referencyjnej? Przynajmniej AST i jej ocena jest stosunkowo łatwa do naśladowania.
Przykładowe wyrażenie S z
1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))
:Mniej golfa dzięki międzynarodowym wynikom i testom:
źródło
Python 3, 695 bajtów
Interpreter zbudowany przy użyciu
tatsu
biblioteki parserów PEG. Pierwszym argumentemtatsu.parser()
jest gramatyka PEG.class D
(dla Die) podklasuje wbudowanyint
typ. Jego wartość jest wynikiem rzutu. Atrybutem.s
jest liczba stron na kości.class S
ma działania semantyczne dla analizatora składni i implementuje interpreter.źródło