Comment coincer 20 clowns dans une voiture

Chez Zenika, on aime les challenges techniques.
Aussi, quand on a vu le Java Champion Heinz Kabutz retweeter un quiz technique, on n’a pas pu résister 🙂
Le sujet du quiz : comment faire rentrer 20 clowns dans une voiture ?

Voici notre solution :

public class ClownStuffer {
    public static final int NB_CLOWNS = 20;
    public static final Volkswagen vw = new Volkswagen();
    public static final CountDownLatch latch = new CountDownLatch(NB_CLOWNS);
    public static void main(String args[]) throws InterruptedException {
        for (int i = 0; i < NB_CLOWNS; i++) {
            Thread t = new Thread() {
                public void run() {
                    vw.add(new MyClown());
                    latch.countDown();
                }
            };
            t.start();
        }
        latch.await();
        vw.done();
    }
    private static class MyClown extends Clown {
        private static int nbClowns = 0;
        @Override
        public int hashCode() {
            synchronized (vw) {
                nbClowns++;
                while (nbClowns != NB_CLOWNS) {
                    try {
                        // Needed to release the monitor so that other threads can call add()
                        vw.wait();
                    } catch (InterruptedException ignored) {
                    }
                }
                vw.notifyAll();
            }
            return super.hashCode();
        }
    }
}

Une petite explication s’impose. Ce code :

crée 20 threads

les fait tous rentrer un par un dans la methode Volkswagen.add()

les met en attente avant que la taille du Set ne soit réellement incrémentée, de manière à esquiver le test et à ne jamais lever l’exception

les relâche une fois que les 20 clowns ont passé la vérification sur la taille du Set

et pour finir, appelle la méthode done() qui constate la présence de la bande de joyeux drilles sur la banquette arrière. Victoire !

Toute la subtilité réside dans le fait que la methode Volkswagen.add est synchronisée. Dans la méthode hashCode, il était donc nécessaire de relâcher le moniteur afin que d’autres clowns puissent être ajoutés : c’est le rôle de l’instruction wait(), qui joue également le rôle de synchroniseur inter-threads.
Si vous trouvez d’autres solutions, vous pouvez les poster dans les commentaires !

3 pensées sur “Comment coincer 20 clowns dans une voiture

  • 17 février 2012 à 15 h 30 min
    Permalink

    Dans le même principe mais sans se compliquer la vie avec des Threads 😉

    (cf. https://gist.github.com/1853231 pour la coloration syntaxique)

    package you;

    import clowns.Clown;
    import clowns.Volkswagen;

    public class You {

     private static class BandOfClowns extends Clown {
       final int id;    final Volkswagen vw;
       public BandOfClowns(int id, Volkswagen vw) {      System.out.println("One more clown, I'm #" + id);      this.id = id;      this.vw = vw;    }
       public int hashCode() {      if (id != 1) {        vw.add(new BandOfClowns(id - 1, vw));      }      return super.hashCode();    }  }
     public static void main(String args[]) {    Volkswagen vw = new Volkswagen();    vw.add(new BandOfClowns(20, vw));    vw.done();  }

    }

    Répondre
  • 17 février 2012 à 18 h 36 min
    Permalink

    On reste dans le domaine du blocage des threads entre le Volkswagen.add() et l’incrémentation de la taille du set.
    Pas mal du tout cette solution en effet je n’y avais pas pensé 😉

    En y réfléchissant bien dans notre solution la boucle while n’a pas forcement un grand intérêt, il suffit de faire un wait sur 19 threads et le 20eme qui fait un notifyAll je pense. Ca simplifie un peu même si ta solution reste plus simple.

    Répondre
  • 18 février 2012 à 9 h 33 min
    Permalink

    Dans ma solution, il n’y a pas de blocage des threads, vu qu’il n’y a que le thread principal.

    Le gros bénéfice de votre solution c’est de bien faire réviser la gestion des moniteurs. C’est pas tous les jours qu’on emploie un wait()/notifyAll().

    Répondre

Répondre à Sébastien Lorber Annuler la réponse.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

%d blogueurs aiment cette page :