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
* 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:
using either addition, which would result in this:
or multiplication, which would result in this:
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
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