Solutions du TD-2, Systèmes de Lindenmayer

1 La tortue

Source solution. C'est plutôt simple. La méthode interp prend en argument un programme (prog), ainsi que l'état initial de la tortue (coordonnées x et y, et direction angle) et ne renvoie rien.

static void interp (String prog, double angle, double x, double y)

Ensuite, positionnement initial du crayon (avec arondis et casts).

moveTo((int)Math.round(x), (int)Math.round(y));

Ensuite, boucle sur tout le programme :

  for (int i=0 ; i < prog.length() ; i++) {
      char c = prog.charAt(i) ;
      if (c == 'F' ) {
        x = x + step * Math.cos(angle) ;
        y = y + step * Math.sin(angle) ;
        lineTo((int)Math.round(x), (int)Math.round(y));
      } else if (c == 'f') { ...
      }
       ...

(Notez les else if, sans accolades après le else, c'est de bon goût.)

2 Définitions

Classes solutions, Rule et Fractal.

Il faut une structure de données quelconque pour représenter les règles. Je choisis une classe à part, Rule qui définit une bête structure de paires.

class Rule {
  char lhs ;
  String rhs ;

  Rule (char lhs, String rhs) {
    this.lhs = lhs ;
    this.rhs = rhs ;
  }
}

(Notez l'astuce de nommage dans le constructeur, avec this, voir aussi ici.) Ensuite, il peut y avoir plusieures règles (si il y a plusieures options -rule. Je choisis une solution simple : il y aura au plus RULEMAX règles et je range les règles dans un tableau de taille RULEMAX.

// Règles
  final static int RULEMAX=16 ; // Ça suffira bien
  static int nrules = 0 ;       // Pas de règles au départ
  static Rule [] rules = new Rule [RULEMAX] ;

Ensuite j'écris une méthode statique pour trouver l'expansion d'un caracatère donné :

// Trouver le membre droit de la règle de membre gauche c
// Renvoie null is ça rate.
  static int findRule(char c) {
    for (int j = 0 ; j < nrules ; j++) {
      if (c == rules[j].lhs)
        return rules[j].rhs;
    }
    return null ;
  }

Bien, je suis maintenant équipé pour écrire l'expanseur. Le plus simple est sans doute d'écrire un expanseur qui exapanse une fois, puis de l'appeler depth fois.

static String uneFois(String prog) {
  StringBuffer r = new StringBuffer () ;
  for (int i = 0 ; i < prog.length () ; i++) {
    char c = prog.charAt(i) ;
    String s = findRule(c) ;
    if (s == null)
      r.append (c) ;
    else
      r.append (s) ;
  }
  return r.toString () ;
}

static String expand (int d, String prog) {
  for ( ; d > 0 ; d--) {
    prog = uneFois(prog) ;
  }
  return prog ;
}

Mais ce n'est pas une très bonne solution car beaucoup de chaînes sont allouées. Il vaut mieux mélanger parcours du programme initial et expansion :

// Expanseur, notez qu'il est récursif et procède par effet de bord
// en remplissant le buffer exp.

  static void expandRec(int d, String s, StringBuffer exp) {
      if (d <= 0)
        exp.append(s) ;
      else {
        for (int i = 0 ; i < s.length () ; i++) {
          char c = s.charAt(i) ;
          String rhs = findRule(c) ;
          if (rhs ==null)
            // Les caractères non-définis sont laissés tels quels
            exp.append(c) ;
          else
            // expansion, avec d <- d-1
            expandRec(d-1, rhs, exp) ;
        }
    }
  }

  // Appel initial de l'expanseur, qui suit la signature de l'énoncé.
  static String expand(int d,String s) {
    StringBuffer r = new StringBuffer () ;
    expandRec(d, s, r) ;
    return r.toString() ;
  }

(Cela revient à expanser les caractères un par un.)

Interprète récursif

La classe Fractal possède déjà les instructions ``['' et ``]''. L'astuce principale est l'utlisation d'une valeur de retour de type entier pour reprendre l'interprétation après le dernier ] exécuté.

Prolongements

Quelques fractales

Île de Von Koch.

java Fractal -x 89 -y 89 -step 13 -rule F F+F-F-FF+F+F-F F+F+F+F -depth 2 -delta 90

Courbe de Hilbert.

java Fractal -rule H -JF+HFH+FJ- -rule J +HF-JFJ-FH+ -delta 90 H -depth 6

Courbe du dragon.

java Fractal -x 96 -y 96 -step 7 -rule D FD+FB -rule B FD-FB D -rule F "" -delta 90 -depth 10

Interpréteur optimisé en mémoire

Les sources FractalOpt et Stack sont la solution.

Le programme calcule aussi les bonnes valeurs de l'état initial de la tortue.

Compte tenu du fait que l'interprète peut retourner pour deux raisons (un ] ou la fin du code). Il devient plus simple de coder l'état de la tortue (qui est en quelque sorte global) par des variables globales (soit static). De mêmes les sauvegardes des états ne peuvent plus se faire avec des variables locales de méthode. Il va falloire gérer explicitement une pile globale de l'état. (voir le code).

Enfin, la solution ne fait pas l'hypothèse simplificatrice de l'énoncé. Cette hypothèse revient à dire que, lorsque l'on retourne par ``]'' alors on a sûrement été appelé par un ``[''. De même lorsque l'on a fini le code, alors l'interpréteur avait été appelé pour expanser un caractère. Donc tous les tests sur pc_res deviennent inutiles. On peut ensuite utiliser la pile des appels de méthode et se passer de la classe Stack en adoptant les astuces de la classe Fractal.

Ce document a été traduit de L^AT_EX par H^EV^EA.