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 * 2to 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 * 5mogą być wyprowadzane jako albo 5 + 5 + 5albo 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

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ęgowanie
x- Mnożenie
p- Dodawanie

\d+
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)
>$0<
(?<=>(\(\w+\)|1+)y1*)1
$1x
>(\(\w+\)|1+)y
(
x<
)
\((1+(x1+)*)\)(?!y)
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)
$2x$1
1`(\(\w+\)|1+)x1+
>$0<
(?<=>(\(\w+\)|1+)x1*)1
$1p
>(\(\w+\)|1+)x
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)
$1
y\((1+)p([1p]*\))
y($1$2
}`y\((1+)\)
y$1
1+
$.0

Wypróbuj online - wszystkie przypadki testowe

Konwerter przypadków testowych

Wyjaśnienie

\d+                             Convert to unary
$*
{1`(\(\w+\)|1+)y(\(\w+\)|1+)    Begin loop: Delimit current exponentiation group
>$0<
(?<=>(\(\w+\)|1+)y1*)1          Replace exponentiation with multiplication
$1x
>(\(\w+\)|1+)y                  Replace garbage with parentheses
(
x<
)
\((1+(x1+)*)\)(?!y)             Remove unnecessary parentheses around multiplication
$1
(?<!1)(1+)x(\(\w+\)|1+\1)(?!1)  Maybe swap order of multiplicands
$2x$1
1`(\(\w+\)|1+)x1+               Delimit current multiplication group
>$0<
(?<=>(\(\w+\)|1+)x1*)1          Replace multiplication with addition
$1p
>(\(\w+\)|1+)x                  Replace garbage with parentheses
(
p<
)
(?<!x|y)\((1+(p1+)*)\)(?!x|y)   Remove unnecessary parentheses around addition
$1
y\((1+)p([1p]*\))               Handle the 4th test case by adding if necessary
y($1$2
}`y\((1+)\)                     End of loop
y$1
1+                              Convert unary back to decimal
$.0

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ć \wklasy 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).

Mathematica, 250 218 183 170 bajtów

f~(s=SetAttributes)~HoldAll;{a,t}~s~Flat;f@n_:=Infix[Hold@n//.{a_~Power~b_:>t@@Hold@a~Table~b,Times->t,Plus->a,Hold->Dot}/.t->(a@@Table[#,1##2]&@@Reverse@Sort@{##}&),"+"]

^{To działa! Wreszcie!}

Definiuje funkcję w f.

Dane wejściowe to proste wyrażenie matematyczne. (tj. 1 + 2nie "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łem Rifflezamiast tego, aby uzyskać taki sam wygląd jak Mathematica REPL.

Bez golfa

f~(s = SetAttributes)~HoldAll;  (* make f not evaluate its inputs *)

{a, t}~s~Flat;  (* make a and t flat, so that a[a[1,a[3]]] == a[1,3] *)

f@n_ :=  (* define f, input n *)

 Infix[

  Hold@n  (* hold the evaluation of n for replacement *)

    //. {  (* expand exponents *)

     (* change a^b to t[a,a,...,a] (with b a's) *)
     a_~Power~b_ :> t @@ Hold@a~Table~b,

     (* Replace Times and Plus with t and a, respectively *)
     Times -> t, 
     Plus -> a, 

     (* Replace the Hold function with the identity, since we don't need
         to hold anymore (Times and Plus are replaced) *)
     Hold -> Dot 

     } /.  (* Replace; expand all t (= `Times`) to a (= `Plus`) *)

        (* Take an expression wrapped in t. *)
        (* First, sort the arguments in reverse. This puts the term
            wrapped in `a` (if none, the largest number) in the front *)
        (* Next, repeat the term found above by <product of rest
            of the arguments> times *)
        (* Finally, wrap the entire thing in `a` *)
        (* This will throw errors when there are multiple elements wrapped
           in `a` (i.e. multiplying two parenthesized elements) *)
        t -> (a @@ Table[#, 1 ##2] & @@
               Reverse@Sort@{##} &),

  "+"]  (* place "+" between each term *)

Mathematica, 405 406 bajtów

f~SetAttributes~HoldAll;p=(v=Inactive)@Plus;t=v@Times;w=v@Power;f@x_:=First@MinimalBy[Inactivate@{x}//.{w[a___,b_List,c___]:>(w[a,#,c]&/@b),t[a___,b_List,c___]:>(t[a,#,c]&/@b),p[a___,b_List,c___]:>(p[a,#,c]&/@b),p[a_]:>a,w[a_,b_]:>t@@Table[a,{Activate@b}],t[a___,t[b__],c___]:>t[a,b,c],p[a___,p[b__],c___]:>p[a,b,c],{a___,{b__},c___}:>{a,b,c},t[a__]:>Table[p@@Table[i,{Activate[t@a/i]}],{i,{a}}]},Length];f

Nie golfił i wyjaśnił

SetAttributes[f, HoldAll]
p = Inactive[Plus]; t = Inactive[Times]; w = Inactive[Power];
f[x_] := First@MinimalBy[
   Inactivate[{x}] //. {
     w[a___, b_List, c___] :> (w[a, #, c] & /@ b),
     t[a___, b_List, c___] :> (t[a, #, c] & /@ b),
     p[a___, b_List, c___] :> (p[a, #, c] & /@ b),
     (* distribute lists of potential expansions over all operations *)
     p[a_] :> a,
     (* addition of a single term is just that term *)
     w[a_, b_] :> t @@ Table[a, {Activate@b}],
     (* a^b simplifies to a*a*...*a b times no matter what b is *)
     t[a___, t[b__], c___] :> t[a, b, c],
     p[a___, p[b__], c___] :> p[a, b, c],
     {a___, {b__}, c___} :> {a, b, c},
     (* operations are associative *)
     t[a__] :> Table[p @@ Table[i, {Activate[t@a/i]}], {i, {a}}]
     (* for a product, generate a list of potential expansions *)}
   , Length]
f

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.