import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/*
  Checks the chance of having duplicate elements, when getting random numbers between 1 and 14. Both mathematical and experimental chances (and
  their differences) are printed. java.util.Random is used for getting random numbers.
 */
public class RelicDuplicate {

  static List<Double> math = new ArrayList<>();
  static List<Double> exp = new ArrayList<>();
  static final double NUMBER_OF_TRIES = Math.pow(10, 8); //100 million

  public static void main(String[] args) {
    mathematical();
    experimental();

    showChanceDifference();
  }

  /*
    Chance of NOT having duplicate values in N distinct values with K tries:
    P = K! * (N choose K) / N^K = (N!/(N-K)!)/N^K
    Chance of HAVING duplicate values: 1 - P
   */
  public static void mathematical() {
    double chance;
    for (int i = 1; i <= 14; i++) {
      chance = 1 - ((factorialOf(14) / factorialOf(14 - i)) / Math.pow(14, i));
      math.add(chance);
      System.out.println("MATHEMATICAL CHANCE AT ROLL " + i + " FOR DUPLICATE: " + chance);
    }
  }

  public static void experimental() {
    Random r = new Random();
    int low = 1;
    int high = 14;

    List<Integer> duplicateIndexes = new ArrayList<>();
    Set<Integer> oneRoundResults = new HashSet<>();

    for (int i = 0; i < NUMBER_OF_TRIES; i++) {
      for (int j = 1; j <= 14; j++) {
        // nextInt(bound) returns numbers between 0 (inclusive) and bound (exclusive), so with this, we get numbers between 1 and 14
        int relic = r.nextInt(high - low) + low;
        oneRoundResults.add(relic);

        /* Sets can not have duplicate elements, trying to add one will have no effect. So if the size of the set is less than j, we had a duplicate
           element.
        */
        if (oneRoundResults.size() < j) {
          duplicateIndexes.add(j);
          break;
        }
      }

      oneRoundResults.clear();
    }

    double sum = 0.0;
    double frequency;
    double frequencySum = 0.0;
    for (int i = 1; i <= 14; i++) {
      frequency = (double) Collections.frequency(duplicateIndexes, i);
      frequencySum += frequency;
      sum += (frequency / duplicateIndexes.size());
      exp.add(sum);
      System.out.println("EXPERIMENTAL CHANCE AT ROLL " + i + ": " + sum + " (with frequnce of " + frequency + " out of " + NUMBER_OF_TRIES + ")");
    }

    if (frequencySum != NUMBER_OF_TRIES) {
      System.out.println("The experimental part has a bug. Frequency sum: " + frequencySum);
    }
  }

  public static void showChanceDifference() {
    for (int i = 0; i < 14; i++) {
      System.out.println("Experimental chance - mathematical chance at roll " + (i + 1) + ": " + String.valueOf(exp.get(i) - math.get(i)));
    }
  }

  public static double factorialOf(int a) {
    if (a < 0) {
      throw new IllegalArgumentException("cheese");
    }
    if (a == 0) {
      return 1;
    }
    double factorial = 1.0;
    for (int i = 2; i <= a; i++) {
      factorial *= i;
    }

    return factorial;
  }

}