javadynamicdynamic-programming

Array of buckets with dynamic programming problem


I’m doing a task with dynamic programming in Java and I got stuck: In the task we are given an array of buckets with random number of rocks inside, where both players know their amount from the start. Players take tours and pick one border bucket from the sides:

Buckets: (3)(3)(8)(2)(10)(4)

P1: (3) buckets left: (3)(8)(2)(10)(4),

P2:(4) buckets left: (3)(8)(2)(10),

P1:(10) buckets left: (3)(8)(2),

P2(3) buckets left: (8)(2),

P1:(8) buckets left (2),

P2:(2) end

Final score is calculated with (rocks of player 1) - (rocks of player2)

Score = (3+10+8)-(4+3+2) = 12

We play player1 and our goal is to find the OPTIMAL pick order in which we have the biggest score.

I know the concept of DP but I have no idea what could I save in order to improve the time. The main part of the code I did with minmax algorithm and it worked but I have no idea how to combine it with dynamic programming

I tried having a matrix with rows as buckets from left and columns as buckets from right, so I can save there answers for when we use the same “part” of the array, but I had some problems with it...

EDIT1: added my code

public int maxGain(int[] values)
{
    this.moves = new int[values.length+1][values.length+1];
    return  _maxGain(values,0,values.length-1,0,0,values.length,true,0,0);
}

public int _maxGain(int[] values, int leftBowl, int rightBowl, int valuePlayer1, int valuePlayer2,int leftBowls, boolean ifFirstPlayer, int leftMoves, int rightMoves){
        //Check if end of the game
        if(leftBowls == 0) {
            //Calculate the final score
            return valuePlayer1 - valuePlayer2;
        }
        //System.out.println("Left:"+values[leftBowl]+", right: "+values[rightBowl]);
        // If first player
        if(ifFirstPlayer){
            int maxEval = Integer.MIN_VALUE;
            int eval;
            for(int i=0;i<2;i++){
                if(i==0){
                    //Do move
                    valuePlayer1 = valuePlayer1+values[leftBowl];
                    leftBowls--;
                    leftMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    leftMoves--;
                    maxEval = Math.max(maxEval,eval);
                    //Undo move
                    valuePlayer1 = valuePlayer1-values[leftBowl];
                    leftBowls++;
                }else{
                    //Do move
                    valuePlayer1 = valuePlayer1+values[rightBowl];
                    leftBowls--;
                    rightMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, false, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    rightMoves--;
                    maxEval = Math.max(maxEval,eval);
                    //Undo move
                    valuePlayer1 = valuePlayer1-values[rightBowl];
                    leftBowls++;
                }
            }
            return maxEval;
            //If second player
        }else{
            int minEval = Integer.MAX_VALUE;
            int eval;
            for(int i=0;i<2;i++){
                if(i==0){
                    //Do move
                    valuePlayer2 = valuePlayer2+values[leftBowl];
                    leftBowls--;
                    leftMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl + 1, rightBowl, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    leftMoves--;
                    minEval = Math.min(minEval,eval);
                    //Undo move
                    valuePlayer2 = valuePlayer2-values[leftBowl];
                    leftBowls++;
                }else{
                    //Do move
                    valuePlayer2 = valuePlayer2+values[rightBowl];
                    leftBowls--;
                    rightMoves++;
                    if(moves[leftMoves][rightMoves] != 0){
                        eval = moves[leftMoves][rightMoves];
                        System.out.println("USED! Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                    }else {
                        eval = _maxGain(values, leftBowl, rightBowl - 1, valuePlayer1, valuePlayer2, leftBowls, true, leftMoves, rightMoves);
                        moves[leftMoves][rightMoves] = eval;
                        System.out.println("Left:"+leftMoves+",right: "+rightMoves+" Moves: " + moves[leftMoves][rightMoves] );
                        for(int x=0;x<this.moves.length;x++){
                            for(int j=0;j<this.moves.length;j++){
                                System.out.print(this.moves[x][j]+" ");
                            }
                            System.out.println();
                        }
                    }
                    rightMoves--;
                    minEval = Math.min(minEval,eval);
                    //Undo move
                    valuePlayer2 = valuePlayer2-values[rightBowl];
                    leftBowls++;
                }
            }
            return minEval;
        }
    }

Solution

  • Ok, so I have found on Github the code for exactly this type of task, I will leave it for other people if they need it later:

    https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java?fbclid=IwAR2PZ8MvNJcQmlU13wj1n_c6m1UhQY7FXAY07RwaI6wOOXAMgDOVRxFahD0