Bonjour,

Le deuxième défi se termine, avec des participants motivés qui ont bien sûr relevé le défi.

Le défi était donc de trouver une solution au problème du voyageur de commerce, avec une petite variante, qui était que le calcul de la distance entre 2 points se faisait dans l’espace en 3D, et non en 2D, avec donc, 30 points.

Les Golgoths on été très étonnés de la réponse rapide, et efficace de pseudocode.

Il a su utiliser avec génie, un algorithme génétique, ce n’était pas évident pourtant.
Je vous laisse découvrir sa solution sur le forum

Ensuite, Sylvain Togni a livré une version avec un algorithme de type branch & bound, qui a donc confirmé le résultat du meilleur chemin déjà trouvé par pseudocode (89188), tout de même un très bel effort de la part de Sylvain Togni

Les Golgoths tiennent à féliciter ces deux membres, pour leur ingéniosité. Bravo !!

Lire la suite →

Bonsoir,

Je sens que vous manquez de challenges, mais les Golgoths vous préparent de grands défis, en voici un qui devrait laisser tout votre talent s’exprimer correctement..

Le voyage dans l’espace.

Pour ce défi, j’ai contacté le concepteur des voyages interstellaires (oui, les Golgoths voyagent depuis longtemps de planète en planète…) pour qu’il m’explique un peu plus en détails les modalités.. JoeChip va donc vous expliquer tout ça en détail :

– Aujourd’hui, notre réseau de distribution de courrier ne s’effectue plus dans les délais, et les Golgoths sont de plus en plus mécontents de ne pas avoir de nouvelles de leur voisinage interstellaire. Nous avons actuellement 30 planètes où circule le courrier, et il nous faudrait déterminer quel est le plus court chemin entre ces 30 planètes, en ne passant qu’une fois pour chaque planète.

Voici donc les emplacements de nos planètes :

nom;X,Y,Z

P-1:914,9904,1583;
P-2:2371,7086,9327;
P-3:6266,5886,6028;
P-4:4451,7026,7292;
P-5:1573,6693,8829;
P-6:8875,18,5462;
P-7:1582,6028,8613;
P-8:9426,2272,9831;
P-9:6310,2007,903;
P-10:6896,5130,8681;
P-11:4086,6387,991;
P-12:2897,2825,9816;
P-13:851,5771,2018;
P-14:3020,1260,9760;
P-15:570,5348,766;
P-16:3168,1099,5495;
P-17:4893,9563,7652;
P-18:7634,4480,3935;
P-19:5114,1487,7632;
P-20:1752,6060,5080;
P-21:8425,9370,757;
P-22:7346,365,640;
P-23:6302,8676,3868;
P-24:9013,8025,4246;
P-25:3444,8561,4769;
P-26:8853,8857,6923;
P-27:9065,3143,909;
P-28:5407,2004,5566;
P-29:1030,6451,1908;
P-30:7055,7782,1339;

Aide les Golgoths postiers, à trouver le chemin le plus court !

Bonsoir,

Les Golgoths ont décidé de clore le premier défi, qui n’était en réalité qu’une introduction.. aux autres défis qu’ils vous réservent, enfin, vous le verrez dans les prochaines semaines.

Déjà, un grand bravo, à tous les participants ! Les golgoths sont fiers d’avoir eu autant de volontaires dès la première épreuve.

Le défi consistait donc à calculer le volume des boites, puis à trier la liste, de sorte que la plus grosse boite se trouve directement au bout de la liste.

Voici, une des participation, parmi les autres que vous pouvez retrouver sur le forum

La participation de pseudocode en java :

   1: import java.io.FileReader;

   2: import java.io.FileWriter;

   3: import java.util.ArrayList;

   4: import java.util.Collections;

   5: import java.util.Comparator;

   6:  

   7: public class Test {

   8:  

   9:     static class Box {

  10:         int x,y,z,volume;

  11:         public Box(int x, int y, int z) {

  12:             this.x=x; this.y=y; this.z=z;

  13:             this.volume=x*y*z;

  14:         }

  15:         public String toString() {

  16:             return this.x+,+this.y+,+this.z;

  17:         }

  18:     }

  19:     

  20:     public static void main(String[] args) throws Exception {

  21:         ArrayListBox> list = new ArrayListBox>();

  22:         

  23:         // read file and insert into list

  24:         FileReader reader = new FileReader(box.txt);

  25:         while(reader.ready()) {

  26:             int x=0,y=0,z=0,d;

  27:             while((d=reader.read())!=',') x=10*x+(d-'0');

  28:             while((d=reader.read())!=',') y=10*y+(d-'0');

  29:             while((d=reader.read())!=';') z=10*z+(d-'0');

  30:             list.add(new Box(x, y, z));

  31:         }

  32:         reader.close();

  33:  

  34:         // sort the list

  35:         Collections.sort(list, new ComparatorBox>() {

  36:             public int compare(Box b1, Box b2) { return b1.volume-b2.volume; }

  37:         });

  38:  

  39:         // write the sorted list to file

  40:         FileWriter writer = new FileWriter(sorted.txt);

  41:         for(Box box:list)

  42:             writer.append(box.toString()).append(';');

  43:         writer.close();

  44:     }

  45: }

Encore un grand merci, à tous les participants, qui je l’espère seront là pour le prochain défi !

Bonjour,

Les Golgoths ne tolèrent pas les tricheurs, et ont donc mis au point une technique qui ne permet à aucun élève d’une classe de tricher lors d’un examen important.

Comme le montre l’image ci dessus, l’élève peux essayer de tricher en regardant sur la copie en haut à droite, en haut à gauche, à droite et à gauche. Les Golgoths ont donc décidé qu’il serait interdit de placer les élèves de sorte qu’ils puissent effectivement tricher. Il y a aussi dans les salles de classe des places qui ne sont plus praticables, où les chaises ou les tables sont cassées, ou absentes.

Votre tâche est donc de déterminer, suivant la classe que nous vous donnerons, le maximum d’élèves que la classe peut contenir, sans qu’aucun des élèves puisse tricher.

La première ligne du fichier vous donne le nombre de salles de classe.
Chaque salle de classe est décrite comme ceci : deux entiers, la longueur et la largeur de la salle.
Les lignes suivantes décrivent la classe en elle même. Chaque caractère est soit un ‘.’ ce qui signifie que la place peut être occupée, soit un ‘x’ qui signifie que la place ne peut pas être occupée (la table est cassée…)

Pour chaque classe, vous devez indiquer le maximum d’élèves que la classe peut contenir sans qu’aucun des élèves puisse tricher.

voici le fichier des classes

Ce problème est inspiré d’une épreuve de Google code Jam (GCJ 2008 Round 3).