Examen final

Étant donné que UnionView est une vue, son constructeur ne doit rien faire d'autre que stocker les deux ensembles reçus dans des attributs.

private final Set<E> set1, set2;

public UnionView(Set<E> set1, Set<E> set2) {
  this.set1 = set1;
  this.set2 = set2;
}

La taille de l'union peut se calculer comme la taille du premier ensemble plus le nombre d'éléments qui se trouvent dans le second ensemble mais pas dans le premier.

public int size() {
  int size = set1.size();
  for (E e : set2) if (!set1.contains(e)) size += 1;
  return size;
}

Ce calcul peut également se faire au moyen de la programmation par flots :

public int size() {
  return set1.size() +
    (int)set2.stream().filter(e -> !set1.contains(e)).count();
}

La manière la plus simple d'écrire iterator est de lui faire retourner une instance d'une classe anonyme, comme c'est souvent le cas. Cette classe utilise les techniques vues au cours, à savoir :

• un attribut nommé remaining qui compte le nombre d'éléments restants à retourner, qui simplifie beaucoup l'écriture des méthodes hasNext et next,
• un appel à hasNext au début de next afin de lever l'exception requise si cette méthode est appelée alors qu'il ne reste aucun élément à parcourir.

La méthode next utilise une technique similaire à la méthode size, dans le sens où elle commence par retourner tous les éléments du premier ensemble (obtenus au moyen d'un itérateur sur ses éléments) puis tous les éléments du second ensemble qui ne se trouvent pas dans le premier.

public Iterator<E> iterator() {
  return new Iterator<>() {
    int remaining = size();
    Iterator<E> it1 = set1.iterator();
    Iterator<E> it2 = set2.iterator();

    @Override
    public boolean hasNext() {
      return remaining > 0;
    }

    @Override
    public E next() {
      if (!hasNext()) throw new NoSuchElementException();
      remaining -= 1;
      if (it1.hasNext()) return it1.next();
      E e = it2.next();
      while (set1.contains(e)) e = it2.next();
      return e;
    }
  };
}

Oui, il est judicieux de redéfinir isEmpty car la version de AbstractSet est forcément basée sur size et parcourt donc la totalité de l'un des deux ensembles. Or il est possible d'écrire isEmpty de manière à ce qu'aucun des deux ensembles ne soit parcouru, étant donné que l'union de deux ensembles n'est vide que si ces deux ensembles le sont également.

public boolean isEmpty() {
  return set1.isEmpty() && set2.isEmpty();
}

Il s'agit du patron Composite.

Comme tous les caractères de ISO 8859-1 sont représentables en Unicode, la méthode iso8859_1ToUtf8 est la plus simple à écrire des deux. Elle doit juste parcourir tous les octets du tableau reçu en argument et, sachant que chacun d'entre eux représente un caractère dont le code est donné par cet octet, examiner son bit de poids fort pour déterminer comment l'encoder en UTF-8. Si ce bit vaut 0, l'octet est conservé tel quel, sinon il est représenté au moyen de 2 octets successifs, selon le schéma donné dans l'énoncé.

static byte[] iso8859_1ToUtf8(byte[] isoLatin1) {
  ByteArrayOutputStream utf8S = new ByteArrayOutputStream();
  for (byte inByte: isoLatin1) {
    if ((inByte & 0b1000_0000) == 0) {
      utf8S.write(inByte);
    } else {
      utf8S.write(0b110_00000 | (inByte & 0b11_000000) >> 6);
      utf8S.write(0b10_000000 | (inByte & 0b00_111111));
    }
  }
  return utf8S.toByteArray();
}

La méthode utf8ToIso8859_1 est un peu plus difficile à écrire pour deux raisons :

1. un caractère ISO 8859-1 peut être représenté par un ou deux octets en UTF-8,
2. certains caractères Unicode ne sont pas représentables en ISO 8859-1.

Il est dès lors plus simple de lire les octets de la séquence reçue au moyen d'un flot de type ByteArrayInputStream. Pour chaque octet lu de ce flot, on détermine s'il représente à lui tout seul un caractère, ou s'il doit être combiné avec l'octet suivant, en examinant son bit de poids fort. Si celui-ci vaut 0, l'octet est écrit tel quel, sinon un second octet est lu. Si les deux octets combinés représentent un caractère qui appartient à ISO 8859-1, son code est calculé puis écrit, sinon une exception est levée.

static byte[] utf8ToIso8859_1(byte[] utf8) {
  ByteArrayInputStream utf8S = new ByteArrayInputStream(utf8);
  ByteArrayOutputStream latin1S = new ByteArrayOutputStream();

  int utf8B;
  while ((utf8B = utf8S.read()) != -1) {
    if ((utf8B & 0b1_0000000) == 0)
      latin1S.write(utf8B);
    else {
      int utf8B2 = utf8S.read();
      if (utf8B2 == -1) throw new IllegalArgumentException();
      if ((utf8B & 0b111_00000) != 0b110_00000
          || ((utf8B2 & 0b11_000000) != 0b10_000000))
        throw new IllegalArgumentException();
      int codePoint = ((utf8B & 0b000_11111) << 6)
        | (utf8B2 & 0b00_111111);
      if (codePoint <= 0xFF) latin1S.write(codePoint);
      else throw new IllegalArgumentException();
    }
  }
  return latin1S.toByteArray();
}

La classe AbstractSubject est très similaire à la classe Cell du cours sur le patron Observer, à trois différences près :

1. AbstractSubject est générique,
2. son attribut observers est protégé, et contient des observateurs génériques,
3. sa méthode notifyObservers ne passe pas le sujet lui-même en argument à l'observateur, mais la nouvelle valeur reçue (newValue ci-dessous).

abstract class AbstractSubject<T> implements Subject<T> {
  protected final List<Observer<T>> observers =
    new ArrayList<>();

  @Override
  public void addObserver(Observer<T> observer) {
    observers.add(observer);
  }

  @Override
  public void removeObserver(Observer<T> observer) {
    observers.remove(observer);
  }

  protected void notifyObservers(T newValue) {
    for (Observer<T> o : observers) o.update(newValue);
  }
}

La classe Cell est très similaire à la classe ValueCell du cours sur le patron Observer, à la différence près qu'elle est générique et stocke donc une valeur d'un type quelconque plutôt qu'un entier de type int.

final class Cell<T> extends AbstractSubject<T> {
  private T value;

  public Cell(T initialValue) {
    this.value = initialValue;
  }

  public T get() {
    return value;
  }

  public void set(T newValue) {
    // Autre option:
    // if (value != newValue
    //     && (value == null || !value.equals(newValue)))
    if (!Objects.equals(value, newValue)) {
      value = newValue;
      notifyObservers(value);
    }
  }
}

Pour écrire la classe MappedSubject, il faut commencer par se rendre compte qu'elle doit prendre deux paramètres de type : le premier (T ci-dessous) représentant le type du sujet à transformer, le second (U ci-dessous) représentant le type du sujet après transformation.

Une fois cela compris, le reste du code n'est pas très difficile à écrire. Il ne faut pas oublier qu'une instance de MappedSubject ne doit surveiller le sujet qu'elle transforme que si elle est elle-même observée ; cela peut se faire en consultant la liste des observateurs dans les méthodes addObserver et removeObserver, afin de déterminer quand le premier observateur lui est ajouté, ou le dernier supprimé.

Pour observer le sujet à transformer, une instance de MappedSubject a deux possibilités :

1. être elle-même l'observatrice du sujet, comme ci-dessous, ce qui implique que MappedSubject implémente Observer et possède une méthode update,
2. utiliser un observateur externe, stocké dans un attribut de la classe et créé au moyen d'une lambda, Observer étant une interface fonctionnelle.

final class MappedSubject<T, U>
    extends AbstractSubject<U>
    implements Observer<T> {
  private final Subject<T> subject;
  private final Function<T, U> function;

  public MappedSubject(Subject<T> subject,
                       Function<T, U> function) {
    this.subject = subject;
    this.function = function;
  }

  @Override
  public void addObserver(Observer<U> observer) {
    if (observers.isEmpty()) subject.addObserver(this);
    super.addObserver(observer);
  }

  @Override
  public void removeObserver(Observer<U> observer) {
    super.removeObserver(observer);
    if (observers.isEmpty()) subject.removeObserver(this);
  }

  @Override
  public void update(T newValue) {
    notifyObservers(function.apply(newValue));
  }
}

La méthode map doit bien entendu créer et retourner une instance de MappedSubject. Elle doit de plus être générique, car le type du sujet résultant de l'application de la fonction (U ci-dessous) peut être quelconque. De plus, le sujet à passer en premier argument au constructeur est bien entendu this.

default <U> Subject<U> map(Function<T, U> function) {
  return new MappedSubject<>(this, function);
}

Comme le dit l'énoncé, les méthodes de Integer décrites dans le formulaire permettent de simplifier l'écriture des méthodes demandées. En effet :

• numberOfLeadingZeros permet, au prix d'un petit calcul, de déterminer la position du bit valant 1 le plus à gauche d'un nombre, ce qui est utile pour chunkIndex,
• highestOneBit permet d'obtenir une valeur n'ayant que ce bit-là à 1, ce qui permet de l'effacer dans indexInChunk au moyen d'un « ou exclusif » bit à bit.

En s'aidant de ces méthodes, on peut écrire celles demandées ainsi :

static int chunkIndex(int index) {
  return Integer.SIZE
    - Integer.numberOfLeadingZeros(index + 1) - 1;
}

static int indexInChunk(int index) {
  int index1 = index + 1;
  return index1 ^ Integer.highestOneBit(index1);
}

static int chunkSize(int chunkIndex) {
  return 1 << chunkIndex;
}

La méthode addLast doit ajouter l'élément reçu à la fin du tableau dynamique, donc à l'index size. Au moyen de cet index et des méthodes définies ci-dessus, elle peut calculer l'index du morceau dans lequel placer cet élément. Si ce morceau n'existe pas encore, elle le créée, puis elle y stocke le nouvel élément avant d'incrémenter la taille.

public void addLast(E value) {
  int index = size;
  int chunkIndex = chunkIndex(index);
  if (chunks[chunkIndex] == null)
    chunks[chunkIndex] =
      (E[]) new Object[chunkSize(chunkIndex)];
  chunks[chunkIndex][indexInChunk(index)] = value;
  size += 1;
}

La méthode get commence par valider l'index avant d'utiliser les méthodes de la partie 1 pour déterminer l'index du morceau contenant l'élément à extraire, et l'index de cet élément dans le morceau.

public E get(int index) {
  // Autre option:
  // if (!(0 <= index && index < size))
  //   throw new IndexOutOfBoundsException();
  Objects.checkIndex(index, size);
  return chunks[chunkIndex(index)][indexInChunk(index)];
}

La méthode set est très similaire à get, mais est un peu plus longue à écrire car elle doit retourner la valeur qui se trouvait précédemment à l'index donné.

public E set(int index, E value) {
  // Autre option:
  // if (!(0 <= index && index < size))
  //   throw new IndexOutOfBoundsException();
  Objects.checkIndex(index, size);
  E[] chunk = chunks[chunkIndex(index)];
  int indexInChunk = indexInChunk(index);
  E oldValue = chunk[indexInChunk];
  chunk[indexInChunk] = value;
  return oldValue;
}

Étant donné l'existence de la méthode get, et le fait qu'elle s'exécute en \(O(1)\), il est très facile de définir l'itérateur, qui conserve l'index du prochain élément à retourner dans un attribut (nextI ci-dessous).

public Iterator<E> iterator() {
  return new Iterator<>() {
    int nextI = 0;

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

    @Override
    public E next() {
      if (!hasNext()) throw new NoSuchElementException();
      return get(nextI++);
    }
  };
}

Les points généralisés ont pour but de combiner le rang et les points effectivement obtenus en une seule valeur que l'algorithme MCTS essaie ensuite de maximiser. Sachant que :

• le rang constitue le critère principal, et doit être minimisé (car le rang 0 est celui du vainqueur), et que
• les points constituent le critère secondaire, et doivent être maximisés,

on en conclut que les points généralisés doivent être composés du complément du rang dans les chiffres de poids fort, et des points dans les chiffres de poids faible. Donc sont valides les formules qui multiplient le complément du rang par une valeur supérieure au plus grand nombre de points qu'il est possible d'obtenir à Ajul (240), et qui lui ajoutent ensuite les points, à savoir :

1. \(P_j = \overline{r_j}\times 246 + p_j\)
3. \(P_j = p_j + 256\times\overline{r_j}\)
6. \(P_j = 240 + 256\times\overline{r_j} - \overline{p_j}\)

La dernière est correcte car \(\overline{p_j} = 240 - p_j\), et cette formule est donc équivalente à la précédente, qui est celle utilisée dans le projet.

Pour répondre correctement à cette question il faut se souvenir que l'heuristique utilisée par HeuristicMoveSelector consiste à choisir :

• un coup remplissant exactement une ligne de motif, s'il y en a au moins un, sinon
• un coup remplissant partiellement une ligne de motif, s'il y en a au moins un, sinon
• un coup quelconque.

Lorsque c'est au joueur P1 de jouer, il est facile de voir qu'il existe au moins un coup qui lui permet de remplir exactement une ligne de motif, à savoir 1A1 (prendre la tuile de couleur A de la fabrique 1 et la placer dans la première ligne de motif). On en conclut que, parmi les coups proposés, seuls ceux remplissant exactement une ligne de motif pourraient être choisis, à savoir :

12. 2C3,
13. 1D2.

Lorsque c'est au joueur P2 de jouer, aucun coup ne permet de remplir exactement une ligne de motif, par contre un coup au moins permet d'en remplir partiellement une, p. ex. 1D3. Dès lors, parmi les coups proposés, seuls ceux remplissant partiellement une ligne de motif pourraient être choisis, à savoir :

15. 1D4,
17. 5A5.

Pour répondre à cette question, le plus simple est probablement d'essayer de trouver un contre-exemple, c.-à-d. une situation dans laquelle la première étape proposée produirait une animation incorrecte. Si on est incapable d'en trouver un, on peut en conclure que la première étape serait valide.

Avant cela, on peut constater que la proposition 23 est la première étape de l'algorithme utilisé dans le projet, tandis que la proposition 22 en est la seconde étape. Or il est possible d'échanger leur ordre sans changer le comportement de l'algorithme, car elles sont indépendantes : la première (23) ne s'applique qu'à la fin d'une manche, tandis que la seconde (22) ne s'applique qu'après qu'un coup ait été joué. On en conclut donc déjà que ces deux propositions sont valides, et il ne reste plus qu'à chercher des contre-exemples pour les propositions 20 et 21.

Pour la proposition 20, il faut tout d'abord constater que le seul cas dans lequel il existe simultanément de l'offre d'une source et de la demande hors du plateau est lorsqu'un coup vient d'être joué, que certaines tuiles auraient dû aller sur la ligne plancher, mais qu'elle était pleine. Imaginons donc l'état de partie suivant :

• la zone centrale contient une tuile de couleur A, une de couleur B et le marqueur de premier joueur,
• la ligne plancher du joueur courant contient 7 tuiles de couleur B et est donc pleine.

Si le joueur courant prend la tuile de couleur A de la zone centrale pour la placer sur son plateau (peu importe où), le marqueur de premier joueur doit être placé sur sa ligne plancher, où il remplace une tuile de couleur B. De plus, en raison de la disparition de la tuile de couleur A, la tuile de couleur B restant dans la zone centrale doit être déplacée. Si on considère les tuiles de couleur B, il y a donc :

• un élément dans la demande hors du plateau, dû à l'éjection, par le marqueur de premier joueur, de la tuile qui se trouvait sur la ligne plancher,
• un élément dans l'offre de source, dû à la réorganisation de la zone centrale.

Or en satisfaisant cette demande avec cette offre, on génère une animation incorrecte, qui sort du plateau la tuile restante de la zone centrale, alors qu'elle ne devrait qu'être déplacée au sein de cette zone. La proposition 20 est donc invalide.

Pour la proposition 21, un contre-exemple est un peu plus facile à trouver. Imaginons l'état de partie suivant :

• une fabrique contient une tuile de couleur A et trois tuiles de couleur B,
• la zone centrale contient une unique tuile de couleur B.

Si le joueur courant prend les tuiles de couleur B et les place sur son plateau (peu importe où), la tuile de couleur A doit être déplacée dans la zone centrale, dont elle provoque la réorganisation puisque cette tuile doit être placée avant celle de couleur B déjà présente. Donc en considérant les tuiles de couleur B, on constate qu'il y a :

• un élément dans la demande de la zone centrale, dû à la réorganisation,
• quatre éléments dans l'offre de source, qui sont, dans l'ordre : les trois derniers emplacements de la fabrique, de gauche à droite, et l'emplacement de la zone centrale.

Or en satisfaisant cette demande avec le premier élément de l'offre, on génère une animation invalide, qui déplace vers la zone centrale la tuile jouée la plus à gauche, alors qu'elle devrait aller sur le plateau du joueur.

En conclusion, les deux seuls appariements qui pourraient constituer la première étape d'un algorithme ayant les mêmes caractéristiques que celui du projet sont les deux derniers, 22 et 23.

Les affirmations suivantes sont vraies :

30. car les ancres sont le seul moyen utilisé pour placer les tuiles à l'écran,
33. car les tuiles visibles à l'écran ne se chevauchent effectivement jamais lorsqu'elles ne sont pas en déplacement, les seules tuiles se chevauchent étant celles hors du plateau, qui occupent toutes la même position (-30, -30),
35. car c'est effectivement la technique que nous utilisons pour déterminer si une destination doit être mise en évidence.

Les affirmations restantes sont fausses :

31. car toutes les ancres, à l'exception de celles se trouvant dans les sources, sont visibles et représentent les cases des lignes de motif, de la ligne plancher et du mur,
32. car des ancres sont bien associées aux sources, elles sont juste invisibles,
34. car les systèmes de coordonnées utilisés pour placer les ancres et les tuiles sont différents, et il faut faire un changement de système de coordonnées pour déterminer la position d'une tuile à partir de la position de l'ancre correspondante.