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."


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.


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].


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 *


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
  • \$\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\$ Jul 26, 2015 at 23:12
  • \$\begingroup\$ Good point. I'll change it. \$\endgroup\$
    – phosgene
    Jul 27, 2015 at 1:12

2 Answers 2


Pyth, 31 bytes


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


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.

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

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;
        return n[0];
        int[]m=new int[k=M.Max(i,l-i)],o=new int[k];
    return b;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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