Examen final
corrigé

Itérateur de liste

L'itérateur de liste est très similaire à l'itérateur standard du cours. Une différence importante est qu'il n'offre pas de méthode remove, ce qui rend inutile l'attribut canRemove.

Tout comme l'itérateur standard, l'itérateur de liste stocke l'index du prochain élément retourné par next en attribut. Cela rend les méthodes hasNext et next identique à celle du cours, et la mise en œuvre de nextIndex triviale.

Les méthodes hasPrevious, previous et previousIndex ne sont pas beaucoup plus difficile à écrire, sachant que l'index du prochain élément que doit retourner previous est simplement nextI - 1.

Finalement, la méthode set s'écrit très facilement à condition d'ajouter un attribut à l'itérateur — lastI ci-dessous — qui mémorise l'index de l'élément retourné par le dernier appel à next ou à previous. Cet attribut doit toutefois être correctement initialisé et mis à jour dans les méthodes next et previous. Ici nous avons choisi de l'initialiser à -1 afin de facilement pouvoir détecter qu'aucun appel à next ou previous n'a été fait et de lever l'exception demandée. 

public SListIterator<E> listIterator() {
  return new SListIterator<E>() {
    private int nextI = 0;
    private int lastI = -1;

    @Override
    public boolean hasNext() {
      return nextI < size;
    }

    @Override
    public int nextIndex() {
      return nextI;
    }

    @Override
    public E next() {
      if (! hasNext())
	throw new NoSuchElementException();
      lastI = nextI++;
      return array[lastI];
    }

    @Override
    public boolean hasPrevious() {
      return 0 < nextI;
    }

    @Override
    public int previousIndex() {
      return nextI - 1;
    }

    @Override
    public E previous() {
      if (! hasPrevious())
	throw new NoSuchElementException();
      lastI = --nextI;
      return array[lastI];
    }

    @Override
    public void set(E newValue) {
      if (lastI == -1)
	throw new IllegalStateException();
      array[lastI] = newValue;
    }
  };
}

Sérialisation ASCII

Partie 1

La classe IntSerde permettant de (dé)sérialiser des entiers 32 bits, elle implémente l'interface AsciiSerde<Integer>.

La méthode alphabet retourne simplement l'ensemble décrit dans l'énoncé, composé des chiffres de 0 à 9 et du signe moins (-).

La méthode serialize est triviale, car la méthode toString de Integer — ou valueOf de String, qui fait la même chose — retourne une représentation textuelle de l'entier en base 10 qui a les propriétés demandées, c-à-d sans signe plus ou zéro superflus en tête.

La méthode deserialize est plus délicate à écrire, malgré l'existence de la méthode parseInt de Integer, pour deux raisons :

  • parseInt lève NumberFormatException si la chaîne ne représente pas un entier valide, mais deserialize doit lever IllegalArgumentException dans ce même cas,
  • parseInt accepte un signe plus ou des zéros superflus en tête de la chaîne, alors que deserialize doit lever IllegalArgumentException lorsqu'ils sont présents.

Le premier problème se résout facilement au moyen d'un try/catch qui attrape l'exception NumberFormatException et lève IllegalArgumentException.

Le deuxième problème se résout en détectant les chaînes invalides du point de vue de deserialize mais valides du point de vue de parseInt, qui sont :

  • celles commençant par un zéro et comportant plus d'un caractère (p.ex. 00),
  • celles commençant par un signe moins suivi d'un zéro (-0),
  • celles commençant pas un signe plus (+).

La méthode startsWith de String permet de détecter ces trois cas facilement. 

public final class IntSerde implements AsciiSerde<Integer> {
  @Override
  public Set<Character> alphabet() {
    return new TreeSet<>(Arrays.asList('-', '0', '1', '2',
				       '3', '4', '5', '6',
				       '7', '8', '9'));
  }

  @Override
  public String serialize(Integer value) {
    return Integer.toString(value);
  }

  @Override
  public Integer deserialize(String str) {
    if ((str.startsWith("0") && str.length() > 1)
	|| str.startsWith("-0")
	|| str.startsWith("+"))
      throw new IllegalArgumentException();
    try {
      return Integer.parseInt(str);
    } catch (NumberFormatException e) {
      throw new IllegalArgumentException(e);
    }
  }
}

Partie 2

La classe CheckingSerde permettant de vérifier le comportement d'un serde quelconque, elle doit être générique, son paramètre de type (T ci-dessous) représentant le type des valeurs (dé)sérialisées par le serde à vérifier.

Le constructeur vérifie que l'alphabet ne contient bien que des caractères ASCII et lève IllegalArgumentException si ce n'est pas le cas. Sinon, il stocke le serde dont le comportement est à vérifier afin de pouvoir appeler ses méthodes ultérieurement.

Les méthodes alphabet et deserialize sont triviales et ne font rien d'autre qu'appeler les méthodes correspondantes du serde dont le comportement est à vérifier.

La méthode serialize quant à elle appelle d'abord la méthode correspondante du serde à vérifier puis valide la chaîne qu'elle retourne en vérifiant que tous ses caractères font partie de l'alphabet du serde. 

public final class CheckingSerde<T> implements AsciiSerde<T> {
  private final AsciiSerde<T> checkedSerde;

  public CheckingSerde(AsciiSerde<T> checkedSerde) {
    for (char c: checkedSerde.alphabet()) {
      if (! isAscii(c))
	throw new IllegalSerdeException();
    }
    this.checkedSerde = checkedSerde;
  }

  @Override
  public Set<Character> alphabet() {
    return checkedSerde.alphabet();
  }

  @Override
  public String serialize(T value) {
    String s = checkedSerde.serialize(value);
    Set<Character> alphabet = checkedSerde.alphabet();
    for (int i = 0; i < s.length(); ++i) {
      if (! alphabet.contains(s.charAt(i)))
	throw new IllegalSerdeException();
    }
    return s;
  }

  @Override
  public T deserialize(String str) {
    return checkedSerde.deserialize(str);
  }
}

Partie 3

La classe MapSerde est générique et ses deux paramètres de type représentent, comme décrit dans l'énoncé, le type des clefs (K ci-dessous) et le type des valeurs (V ci-dessous) des tables associatives qu'elle (dé)sérialise. Étant donné que MapSerde (dé)sérialise des tables associatives dont les clefs ont le type K et le valeurs ont le type V, elle implémente l'interface AsciiSerde<Map<K, V>>.

Le constructeur de MapSerde prend en arguments les serde permettant de (dé)sérialiser les clefs (keySerde) et les valeurs (valSerde) ainsi que le caractère de séparation décrit dans l'énoncé.

Le constructeur commence par calculer l'alphabet du serde, qui est simplement l'union de l'alphabet du serde des clefs et de l'alphabet du serde des valeurs, plus le caractère de séparation. Pour vérifier que ce dernier ne fait pas partie de l'alphabet de l'un des deux serde, on peut simplement l'ajouter en dernier à l'alphabet, et vérifier au moyen de la valeur de retour de la méthode add que cet ajout a bien modifié l'alphabet.

Une fois l'alphabet calculé, une vue non modifiable est stockée en attribut, afin d'éviter que les appelants de la méthode alphabet ne puissent le modifier et violer ainsi l'encapsulation de la classe.

Finalement, le caractère de séparation est stocké sous forme de chaîne, afin de faciliter son utilisation dans les méthodes serialize et deserialize.

La méthode serialize se contente de parcourir les paires clef/valeur de la table qu'elle reçoit en argument et de sérialiser les clefs et les valeurs au moyen des serde correspondants. Le résultat de ces sérialisations est placé dans un « joigneur » de chaînes de type StringJoiner, qui utilise le caractère de séparation comme séparateur.

La méthode deserialize commence par découper la chaîne à désérialiser au moyen du caractère de séparation pour obtenir un tableau contenant à la fois les clefs et les valeurs de la table, sous forme sérialisée1. Si le tableau résultant de ce découpage a une taille impaire, elle lève l'exception demandée. Sinon elle désérialise les clefs et les valeurs au moyen de leur serde respectif, et les place dans la table associative qu'elle retourne finalement. 

public final class MapSerde<K, V>
      implements AsciiSerde<Map<K, V>> {
  private final Set<Character> alphabet;
  private final AsciiSerde<K> keySerde;
  private final AsciiSerde<V> valSerde;
  private final String separatorStr;

  public MapSerde(AsciiSerde<K> keySerde,
		  AsciiSerde<V> valSerde,
		  char separator) {
    Set<Character> alphabet = new HashSet<>();
    alphabet.addAll(keySerde.alphabet());
    alphabet.addAll(valSerde.alphabet());
    if (! (isAscii(separator) && alphabet.add(separator)))
      throw new IllegalArgumentException();

    this.alphabet = Collections.unmodifiableSet(alphabet);
    this.keySerde = keySerde;
    this.valSerde = valSerde;
    this.separatorStr = String.valueOf(separator);
  }

  @Override
  public Set<Character> alphabet() {
    return alphabet;
  }

  @Override
  public String serialize(Map<K, V> value) {
    StringJoiner j = new StringJoiner(separatorStr);
    value.forEach((k, v) -> {
	j.add(keySerde.serialize(k));
	j.add(valSerde.serialize(v));
      });
    return j.toString();
  }

  @Override
  public Map<K, V> deserialize(String str) {
    String[] kvs = str.split(separatorStr);
    if (kvs.length % 2 != 0)
      throw new IllegalArgumentException();

    Map<K, V> m = new HashMap<>();
    for (int i = 0; i < kvs.length; i += 2) {
      K k = keySerde.deserialize(kvs[i]);
      V v = valSerde.deserialize(kvs[i + 1]);
      m.put(k, v);
    }
    return m;
  }
}

Partie 4

  1. CheckingSerde est un décorateur (patron Decorator),
  2. MapSerde est un composite (patron Composite).

Algorithme MCTS

Partie 1

Les 4 premières itérations ajoutent chacune un nœud fils à la racine, correspondant aux 4 cartes que le joueur 4 a en main.

Étant donné que le joueur 4 est le dernier à jouer durant ce pli, et étant donné que l'arbre ne contient jamais de nœuds correspondant aux plis pleins, le pli associé à chacun de ces nœuds est le pli (suivant) vide.

Le nombre de points associé à chacun des nœuds est celui obtenu par l'équipe 2 lors de la fin de tour aléatoire, car le joueur 4 appartient à cette équipe et c'est lui qui joue les cartes menant aux différents nœuds.

Le nombre de tours simulés à partir de chaque nœud vaut bien entendu 1 pour chacun d'entre eux.

En combinant ces différentes informations, on obtient l'arbre ci-dessous, sur lequel les nœuds correspondant à un état dans lequel l'équipe 2 a la main sont en gras (ce qui n'était pas demandé dans l'énoncé, mais facilite la compréhension de la partie 2 ci-dessous).

tree_4_f.png

Figure 1 : Arbre de jeu après 4 itérations

Partie 2

Si une itération supplémentaire de l'algorithme était exécutée, le nouveau nœud serait ajouté comme fils du nœud ayant le plus grand nombre de points, étant donné que tous les nœuds ont le même nombre de tours simulés (1).

Dès lors, le nouveau nœud serait ajouté comme fils du troisième nœud depuis la gauche, dont le nombre de points moyen vaut 103.

Comme le nœud parent de ce nouveau nœud est un nœud dans lequel le joueur 4 doit jouer — car il a gagné le pli précédent en coupant avec le 6 de trèfle (♣6) —, la carte correspondant à ce nœud serait la première de la main du joueur 4, à savoir le huit de pique (♠8).

Liaisons

Seules les versions 3 et 5 sont correctes. Elles font en gros la même chose mais de deux manières différentes : la version 5 utilise les liaisons, tandis que la version 3 utilise un auditeur.

Les autres versions sont incorrectes pour les raison suivantes :

  • La version 1 appelle set plutôt que bind sur la propriété t.textProperty(), ce qui modifie sa valeur au moment de l'appel (de manière incorrecte, qui plus est), mais ne met pas en place les mécanismes nécessaires pour que cette valeur soit mise à jour ultérieurement.
  • La version 2 appelle get sur les propriétés i, fr et frToEn, ce qui permet d'obtenir leur valeur (correcte) au moment de l'appel, mais pas de s'assurer que la valeur de t.textProperty() changera ultérieurement ; elle reste donc constante, ce qui est incorrect.
  • La version 4 appelle get pour obtenir la version anglaise du nom du chiffre, en lui passant en argument une valeur qui n'a même pas le type des clefs de la table ! Malheureusement, ce code est accepté en Java, car la méthode get de Map prend un argument de type Object. La valeur retournée vaut toutefois null, et donc la valeur de t.textProperty() est incorrecte.

Notes de bas de page

1

Il faut noter que ce code n'est pas correct, car la méthode split de String interprète la chaîne qu'on lui passe comme une expression régulière, comme l'explique sa documentation.

Comme le concept d'expression régulière n'avait pas été vu au cours, et que le comportement exact de la méthode split n'avait pas été décrit dans le projet, le formulaire attaché à l'examen décrivait la méthode split comme prenant une chaîne normale en argument, et le code plus haut est écrit en fonction. Il est toutefois important de savoir que ce code est incorrect, et que la version correcte de ce code est : 

String[] kvs = str.split(Pattern.quote(separatorStr));