Casket Of Star

The Casket of Star (sic) is a device in the Touhou universe. Its purpose is to generate energy rapidly. Initially it contains n stars in a row. The stars are labeled 0 through n-1 from the left to the right. You are given a int[] weight, where weight[i] is the weight of star i.The following operation can be repeatedly used to generate energy:

Choose a star x other than the very first star and the very last star.  The x-th star disappears.  This generates weight[x-1] * weight[x+1] units of energy.  We decrease n and relabel the stars 0 through n-1 from the left to the right.

Examples
1)i/p={1,2,3,4}   Returns: 12
Steps are
{1,2,3,4}
(3+4){1,3,4} | (8+4) {1,2,4}

2)i/p={100,2,1,3,100} Returns: 10400

3)i/p={2,2,7,6,90,5,9} Returns: 1818

4)i/p={477,744,474,777,447,747,777,474} Returns: 2937951

4)i/p={3, 1, 4, 10, 3} Returns: 51
{3, 4, 10, 3} = 12 (12+30+9=>51, 12+12+9=>33)
{3, 10, 3} = 30 | {3, 4, 3} = 12 = 9 | = 9
{3, 1, 10, 3} = 10 (10+30+9=>49, 10+3+9=>22)
{3, 10, 3} = 30 | {3, 1, 3} = 3 = 9 | = 9
{3, 1, 4, 3} = 12 (12+12+9=>33, 12+3+9=>24)
{3, 4, 3} = 12 | {3, 1, 3} = 3 = 9 | = 9

public class CasketOfStarEasy {
    public int maxEnergy(int[] weight) {
        int max =0;
        for (int i=1;i<weight.length-1;i++) {
            int k=0, fb=0,tfb=0;
            int[] nweight = new int[weight.length-1];
            for (int j=0;j<weight.length;j++) {
                if (j!=i) nweight[k++] = weight[j];
            }
            if (weight.length>3) {
                fb = weight[i-1] * weight[i+1];
                //System.out.println(fb + " - " + Arrays.toString(nweight));
                tfb = fb+maxEnergy(nweight);
            } else {
                tfb = weight[0] * weight[2];
                //System.out.println(tfb + " - " + Arrays.toString(weight));
            }
            if (tfb>max) max= tfb;
        }
        return max;
    }
            
    public static void main(String[] args) {
        CasketOfStarEasy cse = new CasketOfStarEasy();
        System.out.println(cse.maxEnergy(new int[]    {1, 2, 3, 4}     ));
        System.out.println(cse.maxEnergy(new int[]    {100, 2, 1, 3, 100}     ));
        System.out.println(cse.maxEnergy(new int[]    {2, 2, 7, 6, 90, 5, 9}     ));
        System.out.println(cse.maxEnergy(new int[]    {477, 744, 474, 777, 447, 747, 777, 474}     ));
        System.out.println(cse.maxEnergy(new int[]    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}     ));
        System.out.println(cse.maxEnergy(new int[]    {213, 220, 224, 224, 197}     ));
        System.out.println(cse.maxEnergy(new int[]    {784, 783, 785, 785, 784, 783, 785, 785, 783}     ));
        System.out.println(cse.maxEnergy(new int[]    {526, 530, 662, 627, 472, 601, 626, 603, 634}     ));
        System.out.println(cse.maxEnergy(new int[]    {422, 792, 433}     ));
        System.out.println(cse.maxEnergy(new int[]    {546, 529, 545}     ));
        System.out.println(cse.maxEnergy(new int[]    {481, 652, 652}     ));
        System.out.println(cse.maxEnergy(new int[]    {748, 704, 728}     ));
        System.out.println(cse.maxEnergy(new int[]    {864, 638, 752, 820, 721, 697, 830, 726, 447, 664}     ));
        System.out.println(cse.maxEnergy(new int[]    {531, 342, 276, 421, 349, 279, 392, 183}     ));
    }
}

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: