Die Multiplikation zwischen 2 ganzen Zahlen kann wie folgt zu einer Reihe von Additionen reduziert werden

3 * 5 = 3 + 3 + 3 + 3 + 3 = 5 + 5 + 5

Die Potenzierung (Erhöhen von a zur Potenz von b ) kann auch in eine Reihe von Multiplikationen reduziert werden:

5 ^ 3 = 5 * 5 * 5

Daher kann die Exponentiation durch Erzeugen eines Multiplikationsausdrucks in eine Reihe von Additionen und dann in eine Reihe von Additionen reduziert werden. Zum Beispiel kann 5 ^ 3(5 Würfel) als umgeschrieben werden

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

Ihre Aufgabe ist es, gegebene Ausdrücke, die aus Exponentiation, Multiplikation und Addition bestehen, auf die kürzeste Additionsserie zu reduzieren. Der "kürzeste" Ausdruck ist definiert als der Ausdruck mit der geringsten Anzahl von +Symbolen, wobei immer noch nur eine der beiden Zahlen im ursprünglichen Ausdruck verwendet wird. Zum Beispiel kann der kürzeste Ausdruck 10 * 2ist 10 + 10.

Die an der Eingabe beteiligten Zahlen sind alle positive Ganzzahlen, und der Ausdruck besteht nur aus +(Addition), *(Multiplikation) und ^(Exponentiation) sowie aus Ganzzahlen und Klammern ( ()), um die Vorrangstellung anzuzeigen.

Die Ausgabe sollte nur aus positiven Ganzzahlen und +Symbolen bestehen. Sie sollten nicht die einzelnen Reduktionsschritte ausgeben, sondern nur die endgültige Ausgabe. Die Ausgabe darf keine Zahlen enthalten, die nicht in der Eingabe enthalten sind. Sie können jedoch auch 3 verschiedene Symbole anstelle von verwenden +*^. Geben Sie jedoch an, um welche Symbole es sich handelt

Die Leerzeichen zwischen Ein- und Ausgängen können in Ihren Programmen verwendet werden oder auch nicht, dh sie 3 * 5können entweder als 5 + 5 + 5oder ausgegeben werden 5+5+5.

Beachten Sie, dass die Addition in den meisten Fällen nicht durchgeführt wird. Der einzige Fall, in dem das Hinzufügen durchgeführt werden soll, ist, wenn Sie so etwas 5 ^ (1 + 2)haben. In diesem Fall ist das Hinzufügen erforderlich, um fortzufahren -> 5 ^ 3 -> 5 * 5 * 5 -> .... Siehe Testfall 4.

Ihr Code muss keine Eingaben verarbeiten, die zu einem mehrdeutigen Ausdruck führen. Zum Beispiel (2 + 2) * (4 + 1). Aufgrund der bisher festgelegten Regeln ist es nicht das Ziel, die Antwort zu berechnen, sondern das Ziel, das Hinzufügen zu vereinfachen. Das Ergebnis kann je nach der Reihenfolge, in der Ausdrücke aufgelöst oder umgewandelt werden, unterschiedlich sein (welche Zusätze sind zu vereinfachen, welche zu belassen?). Ein weiteres ungültig Beispiel: ((3 + 2) ^ 2) ^ 3 -> ((3 + 2) * (3 + 2)) ^ 3 -> ???.

Das ist Code-Golf, also gewinnt der kürzeste Code

Testfälle

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

Retina , 302 Bytes

Ich bin mir sicher, dass man Golf spielen kann, aber jetzt bin ich froh, dass es funktioniert. Exponentiation und Multiplikation sind sich sehr ähnlich, aber da die Reihenfolge der Operationen wichtig ist, weiß ich nicht, wie ich sie kombinieren soll.

y- Potenzierung
x- Multiplikation
p- Addition

\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

Probieren Sie es online aus - alle Testfälle

Testfall-Konverter

Erläuterung

\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

Möglicherweise stellen Sie auch fest, dass die am häufigsten verwendete Gruppe ist (\(\w+\)|1+). Dies entspricht einem inneren Ausdruck mit Klammern oder einer ganzen Zahl. Ich habe mich für die Symbole entschieden, die ich verwendet habe, damit ich keine \wZeichenklasse verwenden kann. Ich bin mir nicht sicher, ob es besser ist, Symbole zu verwenden, die keine Wörter sind, und einige Lookarounds durch Wortrahmen zu ersetzen ( \b).

Mathematica, 250 218 183 170 Bytes

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@{##}&),"+"]

^{Es klappt! Endlich!}

Definiert die Funktion in f.

Die Eingabe ist ein einfacher mathematischer Ausdruck. (dh 1 + 2nicht "1 + 2").

Probieren Sie es online!

Beachten Sie, dass der TIO-Link einen etwas anderen Code hat, als der TIO (der vermutlich den Mathematica-Kernel verwendet) Infix. Ich habe Rifflestattdessen das gleiche Aussehen wie Mathematica REPL erhalten.

Ungolfed

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 Bytes

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

Ungolfed und erklärte

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

Ich ging zu einem sehr viel Mühe den folgenden Effekt zu erhalten: Diese Funktion nimmt als Eingabe einen Standard - Mathematica - Ausdruck, mit der üblichen +, *und ^Operationen (und Klammern) darin und gibt , was aussieht wie ein Standard - Mathematica - Ausdruck (aber mit "deaktiviert" (Pluszeichen) als Antwort.

Die obige Funktion beginnt mit dem Deaktivieren aller Operationen im Eingang. Dann werden wiederholt Erweiterungsregeln angewendet, bis nichts mehr vereinfacht werden kann. Immer wenn es auf ein Produkt wie z. B. stößt 2 * 3 * 4, das auf verschiedene Arten erweitert werden kann, erstellt es eine Liste möglicher Erweiterungen und fährt fort. Am Ende erhalten wir eine Liste möglicher endgültiger Antworten, und die kürzeste wird ausgewählt.