rows

import org.junit.Test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.stream.Collector;
import java.util.stream.Collectors;

/**
 * This class implements a game of Row of Bowls.
 * For the games rules see Blatt05. The goal is to find an optimal strategy.
 */
public class RowOfBowls {

    public RowOfBowls() {
    }

    /**
     * Implements an optimal game using dynamic programming
     * @param values array of the number of marbles in each bowl
     * @return number of game points that the first player gets, provided both parties play optimally
     */
    public int maxGain(int[] values)
    {
        // TODO
        //die Tabelle fuer die besten scores erstellt
        int n = values.length;
        int[][] score_tab = new int[n][n]; //schon mit nullen initialisiert?
        //int length; //laenge der betrachteten zahlenfolge (1 fuer 1 schuessel, 2 fuer zwei schuessel usw)
        //int diag;

        if (n==0) return  0; //keine schuessel

        //diagonale fühlen - auf der diagonale steht uns immer eine schuessel zur verfuegung
        /*
        for (int i = 0; i < score_tab.length; i++) {
            for (int j = 0; j < score_tab[i].length; j++) {

                diag= i - j;
                // n = 0 fuer "nulle" diagonale -> leange 1
                // n = 1 fuer die erste diagonale -> laenge = 2, usw...
                // diag or diag_counter is = n-1 -> bessere berechnung

                //diagonale 0 -> laenge 1 -> eine schuessel steht zur verfuegung
                if (diag == 0) score_tab[i][j] = values[i];
                // {4 7 3} laenge 3 (diag_counter = 2) -> max(4 - {7 3}, 3 - {4 7})
                int pickLeft = score_tab[i-diag][j] - score_tab[i][j+1];
                int pickRight = score_tab[i][j+diag] - score_tab[i-1][j];
                score_tab[i][j] = Math.max(pickRight, pickLeft);
            }
        }

         */
        // Basisfälle: Nur eine Schüssel
// Basisfälle: Nur eine Schüssel
        for (int k = 0; k < n; k++) {
            score_tab[k][k] = values[k];
        }

        for (int len = 2; len <= n; len++) {
            for (int i = len-1; i < n; i++) {
                int j = i - len + 1;
                int pickLeft = (j >= 0 && j+1 < n) ? values[j] - score_tab[i][j+1] : 0;
                int pickRight = (i-1 >= 0 && j >= 0) ? values[i] - score_tab[i-1][j] : 0;
                score_tab[i][j] = Math.max(pickLeft, pickRight);
            }
        }

        return score_tab[n-1][0];
    }



    /**
     * Implements an optimal game recursively.
     *
     * @param values array of the number of marbles in each bowl
     * @return number of game points that the first player gets, provided both parties play optimally
     */
    public int maxGainRecursive(int[] values) {
        if (values.length == 0) return 0;
        return maxGainRecursive(values, 0, values.length - 1);
    }

    private int maxGainRecursive(int[] values, int left, int right) {
        // Basisfall: Wenn keine Murmeln mehr übrig sind
        /*if (left > right) {
            return scoreA - scoreB;
        }

        int pickLeft, pickRight;
        if (player == 1) { // Spieler A ist dran, versucht zu maximieren
            pickLeft = maxGainRecursive(values, left + 1, right, -player, scoreA + values[left], scoreB);
            pickRight = maxGainRecursive(values, left, right - 1, -player, scoreA + values[right], scoreB);
            return Math.max(pickLeft, pickRight);
        } else { // Spieler B ist dran, versucht zu minimieren
            pickLeft = -maxGainRecursive(values, left + 1, right, -player, scoreA, scoreB + values[left]);
            pickRight = -maxGainRecursive(values, left, right - 1, -player, scoreA, scoreB + values[right]);
            return Math.max(pickLeft, pickRight); // Negation für Minimierung
        }

         */
         //anker
        if (right == left){
            return values[right];
        }

        int res;
        int score_right;
        int score_left;

        //linken teilbaum
         int pickLeft = values[left];
         score_left = pickLeft-maxGainRecursive(values, left+1, right);
        // fuer 7 4 3 2 wenn 7 nehmen: score = 7 - maxScore(4 3 2)

         //rechten teilbaum
         int pickRight = values[right];
         score_right = pickRight-maxGainRecursive(values, left, right-1);
        // fuer 7 4 3 2 wenn 2 nehmen: score = 2 - maxScore(7 4 3)

         res = Math.max(score_left, score_right);
         return res;
    }


    /**
     * Calculates an optimal sequence of bowls using the partial solutions found in maxGain(int values)
     * @return optimal sequence of chosen bowls (represented by the index in the values array)
     */
    public Iterable<Integer> optimalSequence()
    {
        // TODO
        return null;
    }



    public static void main(String[] args)
    {
        // For Testing
        RowOfBowls game = new RowOfBowls();
        int[] values = {7, 4, 3, 2};
        System.out.println("Max gain (recursive): " + game.maxGainRecursive(values));
        //game.testRowOfBowls();
        }
}