blatt5_algodat

import org.junit.Test;

import java.util.ArrayList;
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() {
    }
    int[] values;
    int[][] score_tab;
    /**
     * 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
        //  return maxGain_help(values, 0);
        //die Tabelle fuer die besten scores erstellt
        int n = values.length;
        int[][] score_tab = new int[n][n]; //schon mit nullen initialisiert?
        //int len; //laenge der betrachteten zahlenfolge (1 fuer 1 schuessel, 2 fuer zwei schuessel usw)

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

        // 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);
            }
        }
        this.score_tab = score_tab;
        this.values = values;
        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) {
        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(){
    int n = values.length;

      int best_score = maxGain(values); //speichert score_tab schonmal
    //dies brauchen wir nicht wirklich, aber moechten sicherstellen dass die Funktion die score_tab berechnet hat
    ArrayList<Integer> sequence = new ArrayList<>();
    int i = n - 1, j = 0;
    while (i >= 0 && j < n) {
        int pickLeft = (j >= 0 && j + 1 < n) ? values[j] - score_tab[i][j + 1] : Integer.MIN_VALUE;
        int pickRight = (i > 0 && j >= 0) ? values[i] - score_tab[i - 1][j] : Integer.MIN_VALUE;
        if (pickLeft > pickRight) {
            sequence.add(j);
            if (sequence.toArray().length == n) break;
            j++;
        } else {
            sequence.add(i);
            if (sequence.toArray().length == n) break;
            i--;
        }

    }


    return sequence;
}

    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();
        }
}