Mnożenie dwóch liczb całkowitych można zredukować do szeregu dodatków
3 * 5 = 3 + 3 + 3 + 3 + 3 = 5 + 5 + 5
Potęgowanie (zwiększenie a do potęgi b ) można również zredukować do szeregu mnożenia:
5 ^ 3 = 5 * 5 * 5
Dlatego potęgowanie można zredukować do szeregu dodatków, tworząc wyrażenie mnożenia, a następnie do szeregu dodatków. Na przykład,5 ^ 3
(5 kostek) można przepisać jako
5 ^ 3 = 5 * 5 * 5
= (5 + 5 + 5 + 5 + 5) * 5
= (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5) + (5 + 5 + 5 + 5 + 5)
= 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5
Twoim zadaniem jest, biorąc pod uwagę wyrażenia dodane razem, takie jak potęgowanie, mnożenie i dodawanie, zredukuj je do najkrótszej serii dodatków. „Najkrótsze” wyrażenie jest zdefiniowane jako wyrażenie o najmniejszej liczbie+
symboli, wciąż używając tylko jednej z dwóch liczb w pierwotnym wyrażeniu. Na przykład najkrótsze wyrażenie 10 * 2
to 10 + 10
.
Liczby biorące udział w danych wejściowych będą dodatnimi liczbami całkowitymi, a wyrażenie będzie składać się tylko z +
(dodawanie), *
(mnożenie) i ^
(potęgowanie), wraz z liczbami całkowitymi i nawiasami kwadratowymi ( ()
) w celu wskazania pierwszeństwa.
Dane wyjściowe powinny składać się wyłącznie z dodatnich liczb całkowitych i +
symboli. Nie powinieneś wyprowadzać poszczególnych kroków redukcji, tylko końcowy wynik. Dane wyjściowe mogą nie zawierać żadnych liczb, które nie pojawiają się na wejściu. Zamiast tego możesz użyć 3 różnych symboli +*^
, ale powiedz, jakie to są symbole
Przestrzenie oddzielające wejścia i wyjścia mogą lub nie mogą być wykorzystywane w programach, to znaczy 3 * 5
mogą być wyprowadzane jako albo 5 + 5 + 5
albo 5+5+5
.
Zauważ, że w większości przypadków dodawanie nie jest faktycznie wykonywane. Jedynym przypadkiem, w którym należy wykonać dodawanie, jest coś takiego 5 ^ (1 + 2)
, w którym to przypadku dodawanie jest konieczne, aby kontynuować -> 5 ^ 3 -> 5 * 5 * 5 -> ...
. Zobacz przypadek testowy nr 4.
Twój kod nie musi obsługiwać danych wejściowych, które powodują niejednoznaczne wyrażenie. Na przykład (2 + 2) * (4 + 1)
. Ze względu na zasady określone do tej pory celem nie jest obliczenie odpowiedzi, celem jest uproszczenie dodatków. Zatem wynik może być różny w zależności od kolejności, w której wyrażenia są rozwiązywane lub zamieniane (które dodatki uprościć, a które zostawić?). Innym przykładem nieważne: ((3 + 2) ^ 2) ^ 3 -> ((3 + 2) * (3 + 2)) ^ 3 -> ???
.
To jest golf golfowy, więc wygrywa najkrótszy kod
Przypadki testowe
Input => output
5 ^ 3 + 4 * 1 ^ 5 => 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 5 + 4
2 ^ 1 * 2 + 3 + 9 => 2 + 2 + 3 + 9
2 ^ 1 * (2 + 3) + 9 => 2 + 3 + 2 + 3 + 9
2 ^ (1 * (2 + 3)) + 9 => 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 9
10 + 3 * 2 + 33 ^ 2 => 10 + 3 + 3 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33 + 33
100 * 3 => 100 + 100 + 100
2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 8 ^ 1 => 2 + 2 + 2 + 2 + 8
(1 + 2 + 5 * 8 + 2 ^ 4) * 2 => 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 1 + 2 + 8 + 8 + 8 + 8 + 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2
źródło
**
zamiast^
?using only one of the two numbers in the original expression.
ale oryginalne wyrażenie może mieć więcej niż dwie liczby. Nie rozumiem, dlaczego8 + 8
nie jest prawidłowym wyjściem dla2 ^ 1 + 2 ^ 1 + 2 ^ 2 + 8 ^ 1
. To pytanie jest nadal dla mnie dość niejasne.Odpowiedzi:
Siatkówka , 302 bajty
Jestem pewien, że można grać w golfa, ale w tym momencie cieszę się, że to działa. Sekcje potęgowania i mnożenia są bardzo podobne, ale ponieważ kolejność operacji jest ważna, nie wiem, jak je połączyć.
y
- Potęgowaniex
- Mnożeniep
- DodawanieWypróbuj online - wszystkie przypadki testowe
Konwerter przypadków testowych
Wyjaśnienie
Możesz również zauważyć, że najczęściej używaną grupą jest
(\(\w+\)|1+)
. Odpowiada to wyrażeniu wewnętrznemu z nawiasami lub liczbą całkowitą. Zdecydowałem się użyć symboli, które zrobiłem, aby móc użyć\w
klasy postaci. Nie jestem pewien, czy lepiej byłoby użyć symboli niebędących słowami i zastąpić niektóre wyszukiwania granicami słów (\b
).źródło
Mathematica,
250218183170 bajtówTo działa! Wreszcie!
Definiuje funkcję w
f
.Dane wejściowe to proste wyrażenie matematyczne. (tj.
1 + 2
nie"1 + 2"
).Wypróbuj online!
Zauważ, że łącze TIO ma nieco inny kod, ponieważ TIO (które, jak przypuszczam, używa jądra Mathematica) nie lubi
Infix
. UżyłemRiffle
zamiast tego, aby uzyskać taki sam wygląd jak Mathematica REPL.Bez golfa
źródło
Mathematica,
405406 bajtówNie golfił i wyjaśnił
Poszedłem do dużo trudu, aby uzyskać następujący efekt: Ta funkcja przyjmuje jako wejście standardowe wyrażenia Mathematica, przy czym zwykle
+
,*
i^
operacje (i nawiasów) w nim i wyjść, co wygląda jak standardowy ekspresji Mathematica (ale z „dezaktywowane” plus znaki) jako odpowiedź.Powyższa funkcja rozpoczyna się od dezaktywacji wszystkich operacji na wejściu. Następnie stosuje wielokrotnie reguły ekspansji, aż nic już nie można uprościć. Za każdym razem, gdy napotyka produkt
2 * 3 * 4
, który można rozszerzyć na wiele sposobów, tworzy listę możliwych rozszerzeń i kontynuuje działanie. Na koniec otrzymujemy listę możliwych ostatecznych odpowiedzi i wybierana jest najkrótsza.źródło