L-systèmes

Le code du corrigé est fourni sous la forme d'une archive Zip, et des explications concernant les principales difficultés des exercices sont données ci-dessous.

L'enregistrement et son constructeur compact sont très simples à définir et ne méritent pas de description détaillée.

public record LSystem(String string,
                      Map<Character, String> rules,
                      Set<Character> lineChars,
                      int turningAngle) {
  public LSystem {
    rules = Map.copyOf(rules);
    lineChars = Set.copyOf(lineChars);
  }
}

Le constructeur secondaire doit s'aider d'une méthode auxiliaire capable de transformer une chaîne en ensemble, qui peut se définir ainsi :

private static Set<Character> setFromString(String s) {
  Set<Character> set = new HashSet<>();
  for (int i = 0; i < s.length(); ++i)
    set.add(s.charAt(i));
  return unmodifiableSet(set);
}

Grâce à cet méthode, ce constructeur s'écrit très simplement :

public LSystem(String string,
               Map<Character, String> rules,
               String lineChars,
               int turningAngle) {
  this(string, rules, setFromString(lineChars), turningAngle);
}

Pour faire évoluer un L-système, il suffit de parcourir les caractères de sa chaîne de départ, et de remplacer chacun d'eux par la chaîne leur correspondant dans les règles. Etant donné que les caractères pour lesquels aucune règle n'existe doivent être gardés tels quels, la méthode getOrDefault de l'interface Map peut être utilisée ici à bon escient.

public LSystem evolve() {
  StringBuilder b = new StringBuilder();
  for (int i = 0; i < string.length(); ++i) {
    char c = string.charAt(i);
    b.append(rules.getOrDefault(c, String.valueOf(c)));
  }
  String s = b.toString();
  return new LSystem(s, rules, lineChars, turningAngle);
}

Une fois la première méthode d'évolution définie, il n'est pas difficile de définir la seconde, qui consiste simplement à appliquer la première le nombre de fois donné.

public LSystem evolve(int steps) {
  if (! (steps >= 0))
    throw new IllegalArgumentException();

  LSystem l = this;
  for (int i = 0; i < steps; ++i)
    l = l.evolve();
  return l;
}

Il faut noter que cette méthode peut également s'écrire de manière récursive :

public LSystem evolveRec(int steps) {
  if (!(steps >= 0))
    throw new IllegalArgumentException();

  return steps == 0 ? this : evolve().evolveRec(steps - 1);
}

En examinant le flocon de Koch, on se rend compte qu'il est composé de trois courbes de Koch organisées en triangle. Pour l'obtenir, il suffit donc d'utiliser la chaîne de départ suivante :

F++F++F

A noter que le sens de rotation est important (c-à-d qu'il n'est pas possible d'utiliser systématiquement - à la place de + dans cette chaîne) car la pointe de la courbe de Koch doit se trouver à l'extérieur du triangle formant le flocon.

La définition des L-systèmes de cet exercice est très simple, son principal intérêt étant les images produites par ces systèmes.

Les tortues sauvegardées le sont sur une pile, qui peut être définie ainsi :

List<Turtle> turtleStack = new ArrayList<>();

Bien entendu, il aurait aussi été possible d'utiliser une autre collection pour représenter cette pile, comme un deque (ArrayDeque) ou une liste chaînée (LinkedList). La seule chose qui importe est que cette mise en œuvre offre des opérations d'ajout et de suppression à une extrémité en O(1).

Une fois cette pile définie, la sauvegarde de la tortue se fait en la plaçant au sommet de la pile au moyen de la méthode addLast :

case '[' -> turtleStack.addLast(t);

tandis que la restauration se fait en extrayant la tortue au sommet de la pile et en faisant l'appel à moveTo décrit dans l'énoncé :

case ']' -> {
  t = turtleStack.removeLast();
  p.moveTo(t.x(), t.y());
}

Une fois ces ajouts faits, les deux derniers L-systèmes sont faciles à définir.