package edu.bloomu.ch7b;

import java.util.Scanner;
import java.util.concurrent.ThreadLocalRandom;

/**
 * Calculates the expected number of songs that will be chosen at random from a playlist
 * before a repeat occurs.
 *
 * @author Drue Coles
 */
public class RandomizedPlaylist {

    public static void main(String[] args) {

        System.out.print("How many songs on the playlist? ");
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        final int trials = 1_000_000;
        int total = 0;  // number of songs played over all trials

        // Monte Carlo simulation
        for (int i = 0; i < trials; i++) {
            total += playSongs(n);
        }

        int result = total / trials;
        String out = "Expected number of songs played before one is repeated: %d%n";
        System.out.printf(out, result);
    }

    /**
     * Selects songs at random from a playlist until a repeat occurs.
     *
     * @param n number of songs in the playlist
     * @return number of songs played
     */
    private static int playSongs(int n) {

        boolean[] alreadyPlayed = new boolean[n];
        int numSongs = 0;

        // Keep playing songs until one is repeated.
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        while (true) {

            int k = rand.nextInt(n); // Select a song.
            
            if (alreadyPlayed[k]) {
                return numSongs;
            }

            alreadyPlayed[k] = true;
            numSongs++;
        }
    }
}