introduction

Après une longue bataille, vous avez réussi à vaincre un Sphinx dans un concours d'énigmes. Le Sphinx, impressionné par votre habileté, souhaite vous donner une récompense à la mesure de votre intelligence et crée une bande de parchemin magique divisée en huit cases contenant chacune un chiffre.

"Pliez le parchemin", dit le Sphinx, "de telle sorte que les boîtes se chevauchent, et ces boîtes fusionneront soit par addition soit par multiplication. Quand une boîte restera, sa valeur sera votre récompense en pièces d'or."

Tâche

Vous devez écrire un programme ou une fonction qui prend en entrée une liste / tableau / n'importe lequel des huit nombres naturels, et retourne / imprime la récompense maximale possible pouvant être obtenue par une série d'opérations de «pli».

Mécanique

L'opération de «pli» est effectuée sur un certain nombre de cellules et avec +ou *comme opérateur. Les n premières cellules de la liste sont repliées et fusionnées avec leurs cellules de destination à l'aide de l'opérateur. Toutes les cellules qui ne sont pas consommées dans l'opération de fusion ne sont pas modifiées.

Voici un exemple de rainage utilisant n = 3 cellules:

en utilisant l'une ou l'autre addition, ce qui entraînerait ceci:

ou la multiplication, ce qui entraînerait ceci:

Remarque: Par souci de simplicité, le rainage avec moins de 1 cellule est interdit, tout comme le rainage avec un nombre de cellules supérieur ou égal à la longueur de la liste. Cependant, une liste peut être augmentée de plus de la moitié de son nombre de cellules.

Une liste de 8 cellules peut être augmentée de 5, résultant en une nouvelle liste de longueur 5: [0,1,2,3,4,5,6,7]augmentée de 5 cellules en utilisant l' +opérateur donnerait [9,9,9,1,0].

Notation

Règles de golf de code standard - le code qui produit une sortie correcte et qui a le moins de victoires d'octets.

Bonus: si votre code retourne / imprime également la séquence d'opérations de pli qui mène à la récompense maximale, multipliez votre score par 0,8. La sortie d'exemple pourrait ressembler à:

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

Exemples

Testez votre code à l'aide de ces entrées et résultats, sous la forme de 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 octets

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

Ceci définit une fonction, yqui calcule la valeur du pli.

Manifestation.

Celui-ci utilise la méthode récursive, en prenant le maximum du score de chaque successeur possible.

Le cas de base de la récursivité est implémenté en concaténant l'entrée aux valeurs triées des successeurs possibles, puis en prenant la fin de la liste résultante. S'il n'y a qu'un seul élément dans l'entrée, il n'y a pas de successeurs, et donc la fin de la liste est le seul élément dans l'entrée.

C #, 275 272 octets

C'est simplement une fonction récursive qui traverse chaque branche et renvoie le meilleur score.

En retrait pour plus de clarté:

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;
}