12
\$\begingroup\$

Introduction

After a long battle, you have managed to defeat a Sphinx in a contest of riddles. The Sphinx, impressed with your skill, wishes to give you a reward commensurate with your cleverness, and conjures into existence a strip of magical parchment divided into eight boxes, each containing a numeral.

"Crease the parchment," says the Sphinx, "such that the boxes overlap, and those boxes will merge either through addition or multiplication. When one box remains, its value will be your reward in gold coins."

Task

You must write a program or function which takes as input a list/array/whatever of eight natural numbers, and returns/prints the maximum possible reward obtainable through a series of 'crease' operations.

Mechanics

The 'crease' operation is performed on some number of cells, and with either + or * as the operator. The first n cells of the list are folded across and merged with their destination cells using the operator. Any cells which are not consumed in the merge operation are left unmodified.

Here is an example of creasing using n=3 cells:

enter image description here

using either addition, which would result in this:

enter image description here

or multiplication, which would result in this:

enter image description here

Note: For simplicity, creasing with fewer than 1 cell is disallowed, as is creasing with a number of cells greater than or equal to the length of the list. However, a list can by creased by more than half its cell count.

A list of 8 cells can be creased by 5, resulting in a new list of length 5: [0,1,2,3,4,5,6,7] creased by 5 cells using the + operator would give [9,9,9,1,0].

Scoring

Standard code golf rules - the code which produces correct output and has the fewest number of bytes wins.

Bonus: If your code also returns/prints the sequence of crease operations which leads to the maximal reward, multiply your score by 0.8. Example output might look like:

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

Examples

Test your code using these inputs and results, in the form of 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
\$\endgroup\$
  • \$\begingroup\$ The example output under the "Scoring" heading is invalid. After creasing 5 and 2 there are only 3 cells left, so creasing 3 makes no sense. \$\endgroup\$ – Hand-E-Food Jul 26 '15 at 23:12
  • \$\begingroup\$ Good point. I'll change it. \$\endgroup\$ – phosgene Jul 27 '15 at 1:12
2
\$\begingroup\$

Pyth, 31 bytes

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

This defines a function, y, which computes the crease value.

Demonstration.

This uses the recusive method, taking the maximum of the score of every possible successor.

The base case of the recursion is implemented by concatenating the input to the sorted values of the possible successors, and then taking the end of the resultant list. If there is only 1 element in the input, there are no successors, and therefore the end of the list is the one element in the input.

\$\endgroup\$
  • \$\begingroup\$ It's hard to imagine this getting beaten. Maybe CJam has a chance? \$\endgroup\$ – phosgene Jul 29 '15 at 3:49
2
\$\begingroup\$

C#, 275 272 bytes

It's simply a recursive function that traverses every branch and returns the best score.

Indented for clarity:

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.