Latar Belakang
Saya bermain D&D secara teratur dengan beberapa teman. Ketika berbicara tentang kerumitan beberapa sistem / versi ketika datang untuk melempar dadu dan menerapkan bonus dan penalti, kami bercanda menemukan beberapa kompleksitas tambahan untuk ekspresi dadu bergulir. Beberapa dari mereka terlalu keterlaluan (seperti memperluas ekspresi dadu sederhana seperti 2d6
argumen matriks 1 ), tetapi sisanya membuat sistem yang menarik.
Tantangan
Dengan ekspresi dadu yang kompleks, evaluasilah sesuai dengan aturan berikut dan hasilkan hasilnya.
Aturan Evaluasi Dasar
- Setiap kali operator mengharapkan bilangan bulat tetapi menerima daftar untuk operan, jumlah daftar itu digunakan
- Setiap kali operator mengharapkan daftar tetapi menerima integer untuk operan, integer diperlakukan sebagai daftar satu elemen yang mengandung integer itu
Operator
Semua operator adalah operator infus biner. Untuk tujuan penjelasan, a
akan menjadi operan kiri, dan b
akan menjadi operan kanan. Notasi daftar akan digunakan untuk contoh di mana operator dapat mengambil daftar sebagai operan, tetapi ekspresi aktual hanya terdiri dari bilangan bulat positif dan operator.
d
: outputa
bilangan bulat acak seragam independen di kisaran[1, b]
- Diutamakan: 3
- Kedua operan adalah bilangan bulat
- Contoh:
3d4 => [1, 4, 3]
,[1, 2]d6 => [3, 2, 6]
t
: ambil nilaib
terendah daria
- Diutamakan: 2
a
adalah daftar,b
adalah bilangan bulat- Jika
b > len(a)
, semua nilai dikembalikan - Contoh:
[1, 5, 7]t1 => [1]
,[5, 18, 3, 9]t2 => [3, 5]
,3t5 => [3]
T
: ambil nilaib
tertinggi daria
- Diutamakan: 2
a
adalah daftar,b
adalah bilangan bulat- Jika
b > len(a)
, semua nilai dikembalikan - Contoh:
[1, 5, 7]T1 => [7]
,[5, 18, 3, 9]T2 => [18, 9]
,3T5 => [3]
r
: Jika ada unsur-unsur dib
dalama
, reroll elemen-elemen, menggunakan apa pund
pernyataan yang dihasilkan mereka- Diutamakan: 2
- Kedua operan adalah daftar
- Rerolling dilakukan hanya sekali, sehingga dimungkinkan untuk tetap memiliki elemen
b
dalam hasilnya - Contoh:
3d6r1 => [1, 3, 4] => [6, 3, 4]
,2d4r2 => [2, 2] => [3, 2]
,3d8r[1,8] => [1, 8, 4] => [2, 2, 4]
R
: Jika ada unsur-unsur dib
dalama
, reroll elemen-elemen berulang kali sampai tidak ada unsur-unsurb
yang hadir, menggunakan apa pund
pernyataan yang dihasilkan mereka- Diutamakan: 2
- Kedua operan adalah daftar
- Contoh:
3d6R1 => [1, 3, 4] => [6, 3, 4]
,2d4R2 => [2, 2] => [3, 2] => [3, 1]
,3d8R[1,8] => [1, 8, 4] => [2, 2, 4]
+
: tambahkana
danb
bersama - sama- Diutamakan: 1
- Kedua operan adalah bilangan bulat
- Contoh:
2+2 => 4
,[2]+[2] => 4
,[3, 1]+2 => 6
-
: kurangib
daria
- Diutamakan: 1
- Kedua operan adalah bilangan bulat
b
akan selalu kurang daria
- Contoh:
2-1 => 1
,5-[2] => 3
,[8, 3]-1 => 10
.
: menyatukana
danb
bersama - sama- Diutamakan: 1
- Kedua operan adalah daftar
- Contoh:
2.2 => [2, 2]
,[1].[2] => [1, 2]
,3.[4] => [3, 4]
_
: outputa
dengan semua elemen yangb
dihapus- Diutamakan: 1
- Kedua operan adalah daftar
- Contoh:
[3, 4]_[3] => [4]
,[2, 3, 3]_3 => [2]
,1_2 => [1]
Aturan tambahan
- Jika nilai akhir ekspresi adalah daftar, itu dijumlahkan sebelum output
- Evaluasi istilah hanya akan menghasilkan bilangan bulat positif atau daftar bilangan bulat positif - ekspresi yang menghasilkan integer non-positif atau daftar yang berisi setidaknya satu bilangan bulat non-positif akan memiliki nilai-nilai digantikan oleh
1
s - Tanda kurung dapat digunakan untuk mengelompokkan istilah dan menentukan urutan evaluasi
- Operator dievaluasi dalam urutan prioritas tertinggi ke prioritas terendah, dengan evaluasi berjalan dari kiri ke kanan dalam kasus diutamakan terikat (sehingga
1d4d4
akan dievaluasi sebagai(1d4)d4
) - Urutan elemen dalam daftar tidak masalah - sangat dapat diterima untuk operator yang memodifikasi daftar untuk mengembalikannya dengan elemen-elemennya dalam urutan relatif berbeda
- Istilah yang tidak dapat dievaluasi atau akan menghasilkan loop tak terbatas (suka
1d1R1
atau3d6R[1, 2, 3, 4, 5, 6]
) tidak valid
Uji Kasus
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
Semua kecuali kasus uji terakhir dihasilkan dengan implementasi referensi.
Contoh yang berhasil
Ekspresi: 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]
(penuh1d(([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
(selesai)
Implementasi Referensi
Implementasi referensi ini menggunakan seed konstan yang sama ( 0
) untuk mengevaluasi setiap ekspresi untuk hasil yang konsisten dan dapat diuji. Ia mengharapkan input pada STDIN, dengan baris baru memisahkan setiap ekspresi.
#!/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]: Definisi kami adb
untuk argumen matriks adalah untuk menggulung AdX
untuk masing-masing X
dalam a * b
, di mana A = det(a * b)
. Jelas itu terlalu absurd untuk tantangan ini.
-
itub
akan selalu kurang dari yanga
saya lihat tidak ada cara untuk mendapatkan bilangan bulat non-positif, sehingga aturan tambahan kedua tampaknya tidak ada gunanya. OTOH,_
dapat menghasilkan daftar kosong, yang tampaknya berguna dalam kasus yang sama tetapi apa artinya ketika integer diperlukan? Biasanya saya katakan jumlahnya adalah0
...0
. Dengan aturan no-non-positif, itu akan dievaluasi sebagai1
.[1,2]_([1]_[1])
juga[1,2]
?[2]
, karena[1]_[1] -> [] -> 0 -> 1 -> [1]
.Jawaban:
Python 3,
803 788 753 749 744 748 745 740 700 695682 byte-5 byte terima kasih kepada Mr.Xcoder
-5 byte lebih banyak berkat NGN
-tentang 40 byte berkat Jonathan French
Yuck, benar-benar tolol! Ini bekerja dengan menggunakan ekspresi reguler untuk membungkus semua angka di
k
kelas saya , dan mengubah semua operator menjadi operator python mengerti, kemudian menggunakan metode ajaibk
kelas untuk menangani matematika. The+-
dan+--
pada akhir untuk.
dan_
adalah hack untuk menjaga diutamakan yang benar. Demikian juga, saya tidak dapat menggunakan**
operator untuk d karena hal itu akan membuat1d4d4
diuraikan sebagai1d(4d4)
. Sebagai gantinya, saya membungkus semua angka dalam seperangkat parens tambahan dan melakukan apa pun.j
, karena pemanggilan metode memiliki prioritas lebih tinggi daripada operator. Baris terakhir mengevaluasi sebagai fungsi anonim yang mengevaluasi ekspresi.sumber
def __mod__(a, b)
... Mengapa ruang antaraa,
danb
?; __sub__
. Dan mungkin juga di sini:lambda a,b: l(
.exec("""...""".replace("...","..."))
pernyataan dan mengganti string yang sering muncul (sepertireturn
) dengan satu karakter. Namun, bagi sayaexec
-strategy selalu tampak agak tidak menarik ...__mod__
dan__add__
tidak perlu bahwa banyak indentAPL (Dyalog Classic) , 367 byte
Cobalah online!
Ini adalah algoritma halaman shunting dari implementasi referensi digabung dengan
evaluate_dice()
, tanpa omong kosong dan berorientasi objek omong kosong. Hanya dua tumpukan yang digunakan:h
untuk operator danv
untuk nilai. Parsing dan evaluasi saling terkait.Hasil antara direpresentasikan sebagai matriks 2 × N di mana baris pertama adalah nilai acak dan baris kedua adalah jumlah sisi pada dadu yang menghasilkannya. Ketika hasil tidak dihasilkan oleh operator "d" melempar dadu, baris kedua berisi angka acak. Nilai acak tunggal adalah matriks 2 × 1 dan dengan demikian tidak dapat dibedakan dari daftar 1-elemen.
sumber
Python 3:
723722714711707675653665 byteTitik masuknya adalah
E
. Ini berlaku persamaan reguler berulang. Pertama itu mengganti semua bilangan bulatx
dengan tuple daftar tunggal[(x,0)]
. Kemudian ekspresi reguler pertama melakukand
operasi, dengan mengganti semua[(x,0)]d[(b,0)]
dengan representasi string dari array tuple seperti[(1,b),(2,b),(3,b)]
. Elemen kedua dari setiap tuple adalah operan keduad
. Kemudian, ekspresi reguler berikutnya melakukan masing-masing operator lainnya. Ada regex khusus untuk menghapus parens dari ekspresi yang dihitung penuh.sumber
Clojure,
731720 byte(saat baris baru dihapus)
Pembaruan: implementasi yang lebih singkat dari
F
.Ini terdiri dari empat bagian utama:
N
: memaksa daftar menjadi angkag
: mengevaluasi struktur sintaksis abstrak (ekspresi-S dengan 3 item)F
: mengonversi infix AST ke notasi awalan (S-expressions), juga menerapkan prioritas urutan operanf
: digunakanread-string
untuk mengubah string menjadi urutan angka dan simbol (infiks AST), pipa mereka melalui F -> g -> N, mengembalikan nomor hasil.Saya tidak yakin bagaimana menguji secara menyeluruh ini, mungkin melalui uji statistik terhadap implementasi referensi? Setidaknya AST dan evaluasinya relatif mudah diikuti.
Contoh S-ekspresi dari
1d((8d20t4T2)d(6d6R1r6)-2d4+1d2).(1d(4d6_3d3))
:Kurang bermain golf dengan hasil dan tes internasional:
sumber
Python 3, 695 byte
Juru bahasa yang dibangun menggunakan
tatsu
, perpustakaan parser PEG. Argumen pertamatatsu.parser()
adalah tata bahasa PEG.class D
(untuk Die) subkelas tipe bawaanint
. Nilainya adalah hasil dari roll. Atributnya.s
adalah jumlah sisi pada die.class S
memiliki tindakan semantik untuk parser, dan mengimplementasikan penerjemah.sumber