Examen intermédiaire

La méthode of peut s'écrire facilement en parcourant les éléments de la valeur itérable reçue au moyen d'une boucle for-each et en ajoutant chacun d'entre eux à un ensemble initialement vide, qui est finalement retourné.

static long of(Iterable<Integer> elements) {
  long pkIntSet = EMPTY;
  for (int e : elements) pkIntSet = add(pkIntSet, e);
  return pkIntSet;
}

La taille de l'ensemble n'est rien d'autre que le nombre de bits valant 1 dans sa représentation empaquetée, qui peut s'obtenir sans effort avec la méthode bitCount de Long.

static int size(long pkIntSet) {
  return Long.bitCount(pkIntSet);
}

Une manière simple d'écrire forEachIndexed est de faire une boucle dans laquelle on teste le bit de poids faible de la représentation empaquetée de l'ensemble, avant de la décaler d'un bit vers la droite afin de traiter le prochain bit dans l'itération suivante. Lorsque le bit de poids faible vaut 1, on sait que l'élément correspondant fait partie de l'ensemble, et on appelle donc la méthode accept du consommateur avec l'index de cet élément (i ci-dessous), et cet élément (e ci-dessous). L'itération cesse dès que tous les éléments ont été traités, c.-à-d. dès que la représentation empaquetée de l'ensemble est égale à celle de l'ensemble vide.

static void forEachIndexed(long pkIntSet,
                           IntBiConsumer consumer) {
  for (int e = 0, i = 0; pkIntSet != EMPTY; e += 1) {
    if ((pkIntSet & 1) == 1) consumer.accept(i++, e);
    pkIntSet >>>= 1;
  }
}

Il est aussi possible d'utiliser les méthodes numberOfTrailingZeros et lowestOneBit de Long pour écrire une version plus simple et plus efficace de forEachIndexed, ainsi :

static void forEachIndexed(long pkIntSet,
                           IntBiConsumer consumer) {
  for (int i = 0; pkIntSet != EMPTY; i += 1) {
    consumer.accept(i, Long.numberOfTrailingZeros(pkIntSet));
    pkIntSet = pkIntSet ^ Long.lowestOneBit(pkIntSet);
  }
}

En s'aidant des autres méthodes de PkIntSet64, en particulier de forEachIndexed, il n'est pas très difficile d'écrire toArray en :

• créant le tableau destiné à recevoir les éléments, dont la taille est donnée par la méthode size,
• remplissant ce tableau au moyen de forEachIndexed.

static int[] toArray(long pkIntSet) {
  int[] array = new int[size(pkIntSet)];
  forEachIndexed(pkIntSet, (i, e) -> array[i] = e);
  return array;
}

La classe AbstractImmuList n'est pas très difficile à écrire, sa méthode toString utilisant un StringJoiner de manière standard pour construire la représentation textuelle.

Le parcours des éléments de la liste se fait bien entendu à l'aide des deux seules méthodes de l'interface ImmuList, à savoir size — qui permet de déterminer les index des éléments — et get — qui permet d'obtenir les éléments eux-mêmes.

abstract class AbstractImmuList<E> implements ImmuList<E> {
  @Override
  public String toString() {
    StringJoiner j = new StringJoiner(",", "[", "]");
    for (int i = 0; i < size(); i += 1)
      j.add(get(i).toString());
    return j.toString();
  }
}

La classe OfArray utilise, grosso modo, le patron Adapter pour permettre de voir un tableau comme une liste immuable. La seule différence par rapport au patron est que le tableau passé au constructeur doit être copié afin de garantir l'immuabilité de la classe.

final class OfArray<E> extends AbstractImmuList<E> {
  private final E[] array;

  public OfArray(E[] array) {
    this.array = array.clone();
  }

  @Override
  public int size() {
    return array.length;
  }

  @Override
  public E get(int i) {
    return array[i];
  }
}

La classe Reversed utilise le patron Decorator pour représenter la version inversée d'une liste. Cela se fait simplement en adaptant l'index reçu dans la méthode get avant d'appeler la méthode get de la liste sous-jacente.

final class Reversed<E> extends AbstractImmuList<E> {
  private final ImmuList<E> list;

  public Reversed(ImmuList<E> list) {
    this.list = list;
  }

  @Override
  public int size() {
    return list.size();
  }

  @Override
  public E get(int i) {
    Objects.checkIndex(i, size());  // optionnel
    return list.get(list.size() - 1 - i);
  }
}

La classe Concat utilise le patron Composite pour représenter la liste résultant de la concaténation de deux autres listes. Sa méthode size retourne donc la somme de la taille des listes concaténées, et sa méthode get utilise l'index reçu pour déterminer si elle doit obtenir l'élément de la première ou de la seconde liste.

final class Concat<E> extends AbstractImmuList<E> {
  private final ImmuList<E> l1, l2;

  public Concat(ImmuList<E> l1, ImmuList<E> l2) {
    this.l1 = l1;
    this.l2 = l2;
  }

  @Override
  public int size() {
    return l1.size() + l2.size();
  }

  @Override
  public E get(int i) {
    Objects.checkIndex(i, size());  // optionnel
    return i < l1.size() ? l1.get(i) : l2.get(i - l1.size());
  }
}

La normalisation d'une liste de branche se fait en calculant tout d'abord la somme des probabilités de toutes les branches, puis en divisant la probabilité de chacune par cette somme.

La somme est calculée par une première boucle qui parcourt toutes les branches, puis les nouvelles branches sont calculées dans une seconde boucle. Finalement, une copie immuable de la nouvelle liste de branches est retournée, comme demandé dans l'énoncé.

private static List<Branch> normalize(List<Branch> branches) {
  if (branches.isEmpty()) throw new IllegalArgumentException();

  double sum = 0;
  for (Branch b : branches) sum += b.probability;
  List<Branch> normalized = new ArrayList<>(branches.size());
  for (Branch b : branches)
    normalized.add(new Branch(b.probability / sum,
                              b.expansion));
  // Autre option :
  // return Collections.unmodifiableList(normalized);
  return List.copyOf(normalized);
}

Il est aussi possible d'utiliser la programmation par flots pour obtenir une version plus concise et élégante de normalize :

private static List<Branch> normalize(List<Branch> branches) {
  if (branches.isEmpty()) throw new IllegalArgumentException();

  double sum = branches.stream()
    .mapToDouble(Branch::probability)
    .sum();
  return branches.stream()
    .map(b -> new Branch(b.probability / sum, b.expansion))
    .toList();
}

Pour écrire la méthode choose, l'idée est de considérer que les différentes branches occupent chacune une partie de l'intervalle [0;1] dont la taille est égale à leur probabilité. Ensuite, un nombre aléatoire réparti uniformément dans cet intervalle est tiré au hasard, et la branche qui occupe la partie dans laquelle se trouve ce point est choisie.

Dans le code ci-dessous, cela est fait en tenant à jour une variable nommée remaining, que l'on peut voir comme la distance restant à parcourir pour atteindre le nombre tiré aléatoirement. Chaque nouvelle branche fait diminuer la distance de sa probabilité, et dès que la distance devient négative (ou nulle), cela signifie que la branche courante est celle choisie.

private String choose(List<Branch> branches,
                      RandomGenerator random) {
  double remaining = random.nextDouble();
  for (Branch branch : branches) {
    remaining -= branch.probability;
    if (remaining <= 0) return branch.expansion;
  }
  return branches.getLast().expansion();
}

Garantir l'immuabilité de la classe implique de faire une copie profonde de la table des règles. Donc il faut copier non seulement la table des règles, mais aussi chacune des listes de branches qu'elle contient. De plus, la table et les listes doivent être rendues non modifiables.

La méthode normalize se charge déjà de copier la liste des branches et d'en retourner une version non modifiable, le constructeur n'a donc plus qu'à se charger de copier la table et de la rendre non modifiable. Cela peut se faire, par exemple, en parcourant l'ensemble de ses paires clef/valeur :

public LSystem {
  Map<Character, List<Branch>> nRules = new HashMap<>();
  for (Map.Entry<Character, List<Branch>> e : rules.entrySet())
    nRules.put(e.getKey(), normalize(e.getValue()));

  // Autre option :
  // rules = Collections.unmodifiableMap(nRules);
  rules = Map.copyOf(nRules);
  lineChars = Set.copyOf(lineChars);
}

Sachant qu'une source de tuiles peut contenir soit des tuiles colorées, soit le marqueur de premier joueur (pour la zone centrale), et qu'elle peut contenir des doublons, les types qui conviendraient sont :

1. List<TileKind>,
4. Map<TileKind, Integer> (la clef étant le type de tuile, la valeur le nombre de copies de cette tuile),
7. TileKind[].

Les autres types ne conviennent pas, pour différentes raisons :

• ceux qui utilisent TileKind.Colored n'admettent pas le marqueur de premier joueur,
• ceux qui utilisent des ensembles (Set ou HashSet) n'admettent pas les doublons,
• Map<TileSource.Factory, List<TileKind>​> n'a pas de sens.

Le mur peut être indexé de trois manières, qui sont :

• par une paire (ligne de motif, colonne),
• par une paire (ligne de motif, couleur),
• par un index compris.

Dès lors, les index corrects sont :

11. ligne de motif PATTERN_2, couleur E,
16. case d'index 12.

Tous les autres sont invalides, pour différentes raisons :

• les lignes de motif vont de PATTERN_1 à PATTERN_5,
• les index vont de 0 à 24 (inclus),
• les couleurs vont de A à E.

Les points d'un joueur vont de 0 à 240 (inclus), ce qui peut être représenté au moyen de 8 bits. Donc dans un entier de type int (32 bits), il y a assez de place pour stocker les points. La seule bonne réponse à cette question est donc la 22 (oui).

Pour mémoire, lorsqu'on utilise l'échantillonnage par réservoir pour obtenir un échantillon de taille n d'un ensemble de taille m, l'algorithme commence par copier les n premiers éléments de l'ensemble dans le tableau. Dès lors, ces éléments-là ne peuvent pas apparaître à des positions quelconques dans le résultat.

Ici, sachant que l'ensemble contient 3 tuiles de couleur A, 4 de couleur C et 5 de couleur E, et sachant que le parcours des tuiles se fait dans l'ordre des couleurs, l'algorithme commence par remplir le tableau ainsi :

[A,A,A,C,C]

Ensuite, les éléments suivants peuvent chacun être placés ou non dans l'un des éléments de ce tableau. Il en découle que parmi les propositions données, seules les suivantes pourraient représenter le contenu du tableau après l'appel :

30. [A,C,C,C,E],
32. [E,E,E,E,E].

Les autres propositions sont impossibles, pour différentes raisons :

31. [A,E,A,C,A] (les tuiles de couleur A doivent se trouver dans les 3 premières positions),
33. [A,A,A,A,C] (il n'y a que 3 tuiles de couleur A dans l'ensemble),
34. [A,A,B,C,C] (il n'y a aucune tuile de couleur B dans l'ensemble),
35. [C,C,C,E,C] (seules 2 tuiles de couleur C peuvent occuper les 3 premières positions du tableau, car les 2 autres sont initialement placées dans ses 2 dernières positions).

La zone centrale, à laquelle correspond le bit d'index 0 (le plus à droite) de pkUniqueTileSources, n'est unique que si elle ne contient aucune tuile colorée. On peut donc rapidement déterminer que les configurations 40, 42 et 43 sont les seules pour lesquelles ce bit-là devrait valoir 0. Les valeurs de pkUniqueTileSources correspondantes sont donc forcément les 50, 54 et 55.

À partir de cette constatation, on peut découper le problème en deux parties et résoudre chacune d'entre elles séparément.

Pour apparier (40, 42, 43) à (50, 54, 55), on peut constater que seule la fabrique 2 de 43 est vide, donc pas unique, et le bit qui lui correspond doit donc valoir 0. Elle correspond dont à 54. Les valeurs 50 et 55 diffèrent au niveau de leurs 2 bits de poids fort uniquement, et en les examinant, on conclut que 50 correspond à 42, et 55 à 40. À ce stade, on a donc déjà les appariements (40, 55), (42, 50) et (43, 54).

Les autres appariements peuvent être déterminés de manière similaire pour obtenir finalement : (40, 55), (41, 53), (42, 50), (43, 54), (44, 51), (45, 52).