import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;

public class FizzBuzz {
    static int n = 2;

    static class FizzBuzzPair {
        int number;
        Object value; // either an integer between 1 and n, or "fizz", "buzz", or "fizzbuzz"

        public FizzBuzzPair(int number, Object value) {
            super();
            this.number = number;
            this.value = value;
        }

        public boolean isCorrect() {
            if (number % 15 == 0)
                return value.equals("fizzbuzz");
            else if (number % 3 == 0)
                return value.equals("fizz");
            else if (number % 5 == 0)
                return value.equals("buzz");
            else
                return (value instanceof Integer) && (number == ((Integer) value).intValue());
        }
    }

    public static List<List<FizzBuzzPair>> getAllCombinations() {
        long numCombinations = (long) Math.pow(n + 3, n);
        List<List<FizzBuzzPair>> allCombinations = new ArrayList<>();
        for (long i = 0; i < numCombinations; i++) {
            List<FizzBuzzPair> entry = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                int val = (int) ((i % (long) Math.pow(n + 3, j + 1)) / ((long) Math.pow(n + 3, j)));
                Object value;
                if (val == 0)
                    value = "fizzbuzz";
                else if (val == n + 1)
                    value = "fizz";
                else if (val == n + 2)
                    value = "buzz";
                else
                    value = val;
                entry.add(new FizzBuzzPair(j + 1, value));
            }
            allCombinations.add(entry);
        }
        return allCombinations;
    }

    public static <T> List<List<T>> getAllPermutations(List<T> list, long listLength) {
        List<List<T>> allPermutations = new ArrayList<>();
        if (listLength == 1) {
            allPermutations.add(new ArrayList<>(list));
            return allPermutations;
        }
        for (long i = 0; i < listLength; i++) {
            List<T> copy = new ArrayList<>(list);
            Iterator<T> iter = copy.iterator();
            for (long j = 0; j < i; j++) {
                iter.next();
            }
            T element = iter.next();
            iter.remove();
            for (List<T> l : getAllPermutations(copy, listLength - 1)) {
                List<T> copy2 = new ArrayList<>(l);
                copy2.add(0, element);
                allPermutations.add(copy2);
            }
        }
        return allPermutations;
    }

    public static int numIncorrect(List<FizzBuzzPair> list) {
        int count = 0;
        for (FizzBuzzPair pair : list) {
            if (!(pair.isCorrect()))
                count++;
        }
        return count;
    }

    public static <T> List<T> slowSort(List<T> list, long listLength, Comparator<T> comp) {
        OUTER: for (List<T> permutation : getAllPermutations(list, listLength)) {
            for (long i = 0; i < listLength - 1; i++) {
                Iterator<T> iter = permutation.iterator();
                for (long j = 0; j < i; j++) {
                    iter.next();
                }
                T element1 = iter.next();
                T element2 = iter.next();
                if (comp.compare(element1, element2) > 0) {
                    continue OUTER;
                }
            }
            return permutation;
        }
        throw new RuntimeException("This line should be unreachable");
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();

        /*
         * FizzBuzz associates every integer from 1 to n with a value; each value is either an
         * integer between 1 and n or "fizz", "buzz", and "fizzbuzz".
         *
         * The allCombinations() method constructs a list of all possible ways to assign one of
         * those n+3 values to each of the first n integers; in total, there are (n+3)^n
         * possibilities.
         */
        List<List<FizzBuzzPair>> allCombinations = getAllCombinations();

        /*
         * The list of combinations are then sorted by the number of numbers each combination
         * associates with the incorrect value.
         *
         * The slowSort() method operates by constructing every possible permutation of the input
         * list and then iterating through the permutations until it finds a sorted permutation.
         *
         * Since there are (n+3)^n elements in the list of combinations, slowSort() requires
         * constructing ((n+3)^n)! permutations.
         */
        List<List<FizzBuzzPair>> allCombinationsSorted = slowSort(allCombinations,
                (long) Math.pow(n + 3, n), Comparator.comparingInt(l -> numIncorrect(l)));
        for (FizzBuzzPair pair : allCombinationsSorted.get(0)) {
            System.out.println(pair.value);
        }
        long stop = System.currentTimeMillis();
        System.out.println();
        System.out.println("Elapsed time: " + ((stop - start) / 1000.0) + " seconds");
    }
}