Einführung

Nach einem langen Kampf hast du es geschafft, eine Sphinx in einem Rätselwettbewerb zu besiegen. Die Sphinx, beeindruckt von Ihrem Können, möchte Ihnen eine Belohnung geben, die Ihrer Klugheit entspricht, und zaubert einen magischen Pergamentstreifen ins Leben, der in acht Schachteln mit jeweils einer Ziffer unterteilt ist.

"Falten Sie das Pergament", sagt die Sphinx, "so, dass sich die Kästchen überlappen und diese Kästchen entweder durch Addition oder Multiplikation verschmelzen. Wenn ein Kästchen übrig bleibt, ist sein Wert Ihre Belohnung in Goldmünzen."

Aufgabe

Sie müssen ein Programm oder eine Funktion schreiben, die eine Liste / ein Array / eine beliebige Zahl aus acht natürlichen Zahlen als Eingabe verwendet und die maximal mögliche Belohnung ausgibt, die durch eine Reihe von Knitteroperationen erzielt werden kann.

Mechanik

Die "Falten" -Operation wird an einer bestimmten Anzahl von Zellen und entweder mit +oder *als Operator durchgeführt. Die ersten n Zellen der Liste werden über den Operator hinweg gefaltet und mit ihren Zielzellen zusammengeführt. Alle Zellen, die bei der Zusammenführungsoperation nicht verbraucht werden, bleiben unverändert.

Hier ist ein Beispiel für eine Rillung mit n = 3 Zellen:

Verwenden Sie eine der beiden Additionen, was zu Folgendem führen würde:

oder Multiplikation, was dazu führen würde:

Hinweis: Der Einfachheit halber ist das Falten mit weniger als einer Zelle nicht zulässig, ebenso wie das Falten mit einer Anzahl von Zellen, die größer oder gleich der Länge der Liste sind. Eine Liste kann jedoch um mehr als die Hälfte ihrer Zellenzahl gekürzt werden.

Eine Liste mit 8 Zellen kann um 5 gekürzt werden, was zu einer neuen Liste mit der Länge 5 führt: [0,1,2,3,4,5,6,7]Wird die Liste mit dem +Operator um 5 Zellen gekürzt, ergibt sich [9,9,9,1,0].

Wertung

Standardcode-Golfregeln - Der Code, der die korrekte Ausgabe erzeugt und die geringste Anzahl von Bytes aufweist, gewinnt.

Bonus: Wenn Ihr Code auch die Folge von Knickoperationen ausgibt, die zur maximalen Belohnung führt, multiplizieren Sie Ihre Punktzahl mit 0,8. Die Beispielausgabe könnte folgendermaßen aussehen:

crease 5 +
crease 2 *
crease 2 +
crease 1 *

Beispiele

Testen Sie Ihren Code mit diesen Eingaben und Ergebnissen in Form von input - maximum reward:

[0, 1, 2, 3, 4, 5, 6, 7] - 7560
[0, 9, 0, 3, 2, 6, 1, 5] - 1944
[0, 1, 0, 3, 0, 2, 0, 4] - 36
[6, 0, 9, 1, 9, 0, 7, 3] - 11907
[0, 5, 2, 0, 1, 3, 8, 8] - 2560

Pyth, 31 Bytes

Le+bSyMsm,sMJ.T,_<bd>bdm*FkJtUb

Dies definiert eine Funktion, ydie den Knickwert berechnet.

Demonstration.

Hierbei wird die Recusive-Methode verwendet, wobei das Maximum der Punktzahl jedes möglichen Nachfolgers verwendet wird.

Der Basisfall der Rekursion wird implementiert, indem die Eingabe mit den sortierten Werten der möglichen Nachfolger verkettet wird und dann das Ende der resultierenden Liste erreicht wird. Befindet sich nur 1 Element in der Eingabe, gibt es keine Nachfolger. Daher ist das Ende der Liste das einzige Element in der Eingabe.

C #, 275 272 Bytes

Es ist einfach eine rekursive Funktion, die jeden Zweig durchläuft und die beste Punktzahl zurückgibt.

Zur Verdeutlichung eingerückt:

using M=System.Math;
int F(int[]n){
    int b=0,g,h,i=0,j,k,l=n.Length;
    if(l<2)
        return n[0];
    for(;++i<l;){
        int[]m=new int[k=M.Max(i,l-i)],o=new int[k];
        for(j=0;j<k;j++){
            m[j]=((g=i-j-1)<0?0:n[g])+((h=i+j)<l?n[h]:0);
            o[j]=h<l&g>=0?n[g]*n[h]:m[j];
        }
        b=M.Max(b,M.Max(F(m),F(o)));
    }
    return b;
}