:: Enseignements :: ESIPE :: E4INFO :: 2015-2016 :: Java Avancé ::

Examen de Java Avancée (2ième session)

Les deux exercices sont indépendants et peuvent être traités dans n'importe quelle ordre.
Rappel, vous devez configurer le workspace d'eclipse (File > Switch WorkSpace) pour qu'il corresponde au répertoire EXAM présent dans le home de votre session de TP noté.
Attention à bien lire le sujet en entier.

Exercice 1 - Find Digits (7)

Given an integer, N, traverse its digits (d1,d2,...,dn) and determine how many digits evenly divide N (i.e.: count the number of times N divided by each digit di has a remainder of 0).
Print the number of evenly divisible digits.
Note: Each digit is considered to be unique, so each occurrence of the same evenly divisible digit should be counted (i.e.: for N = 111, the answer is 3).

Input Format
The first line is an integer, T , indicating the number of test cases. The T subsequent lines each contain an integer, N.

Constraints

  1 <= T <= 15
  0 < N < 10**9

Output Format
For every test case, count and print (on a new line) the number of digits in N that are able to evenly divide N.

Sample Input

2
12
1012

Sample Output

2
3

Explanation
The number 12 is broken into two digits, 1 and 2. When 12 is divided by either of those digits, the calculation's remainder is 0; thus, the number of evenly-divisible digits in 12 is 2.
The number 1012 is broken into four digits, 1, 0, 1, and 2. 1012 is evenly divisible by its digits 1, 1, and 2, but it is not divisible by 0 as division by zero is undefined; thus, our count of evenly divisible digits is 3.

Indication in Java
You can use a Stream of the digits !

Exercice 2 - BogoSort (13)

Les tests JUnit pour toutes les questions de cet exercice sont dans la classe BogoSortTest.java.

On souhaite trier un ensemble d'élement (pas forcément que des entiers) en utilisant un algo assez lent et stupide. L'idée consiste pour un ensemble de valeur à générer toutes les permutations possibles puis de sélectionner parmis les permutations celle qui est triée (il n'y en a qu'une car l'ensemble initiale n'accepte pas de doublon).

Après un petit tour sur StackOverflow, vous récupérez le code suivant qui permet de générer les permutations des élements d'un Set en Java, malheureusement, le code a été écrit pour une vielle version de Java qui ne supporte pas les types paramétrés, il va donc falloir dans un premier temps, générifier le code en introduisant des types paramètrés là où il faut.
Note, le code des méthodes printPermutation doit continuer à fonctionner avec n'importe quel type de valeur, pas uniquement avec des chaines de caractères !

  public static void printPermutation(Set set) {
    printPermutation(Collections.emptyList(), set);
  }

  static void printPermutation(List prefix, Set set) {
    if (set.isEmpty()) {
      System.out.println(prefix);
      return;
    }
    for (Object element : set) {
      ArrayList newPrefix = new ArrayList(prefix);
      newPrefix.add(element);
      HashSet newSet = new HashSet(set);
      newSet.remove(element);
      printPermutation(newPrefix, newSet);
    }
  }
  
  public static void main(String[] args) {
    HashSet set = new HashSet(Arrays.asList("b", "a", "c"));
    permutation(set);
  }

Vérifier que vous n'avez pas oublié de wildcard (? extends ou ? super) lorsque vous avez générifié le code, sinon faite les changements qui s'imposent.
printPermutation est pas très flexible comme méthode, car elle ne permet pas de faire quelque chose avec les permutations trouvées à part les afficher.
Pour pouvoir faire quelque chose avec les permutations, l'idée est d'ajouter un second paramètre qui est une fonction qui prend une permutation en paramètre et qui est appelée à chaque fois qu'une permutation est trouvée.
Ecrire la méthode forAllPermutations qui en plus du Set prend, en second paramètre, une fonction qui prend une permutation en paramètre.
Note: normalement, forAllPermutations(set, System.out::println) doit faire la même chose que printPermutation(set)
Ecrire une méthode permutations qui prend un Set en paramètre et renvoie une liste des toutes les permuations (une liste de liste d'élements).
Note: il n'est pas nécessaire de dupliquer le code ici, vous pouvez ré-utiliser forAllPermutations.
Il nous faut maintenant une méthode qui vérifie si une liste de valeur est trié ou non. Ecrire une méthode isSorted qui renvoie vrai si tous les élements d'une liste fournie en argument sont triés.
Faite en sorte que cette méthode ne puisse être appelée qu'avec une liste dont les élements sont comparables entre eux (erreur de compilation sinon).
Ecrire une méthode bogoSort qui prend un ensemble de valeurs (comparable entre elles) en paramètre, calcule la liste de toutes les permutations et renvoie la permutation qui est triée.
Indiquer de plus dans les commentaires qu'elle est la complexité de l'algo bogoSort.