Discussion :

[Golgotha]

Bonjour !

Je vous propose chaque semaine, de participer à un petit défi algorithmique.

J'ouvre donc ce thread pour vous permettre à tous le monde de proposer sa solution, et surtout de discuter sur la façon de faire de chacun, les meilleurs pratiques, etc..

Chaque semaine aussi (je l'espère), un gagnant sera élu, et son code source sera publié sur mon blog, comme étant la meilleure résolution du défi.

J'espère que vous serez nombreux chaque semaine à participer, ça sera l'occasion de tester vos connaissances, et de les améliorer si besoin. Les défis que je propose, sont facilement abordables par tous, pour que le plus grand nombre de personne puissent participer, je suis aussi ouvert a toute proposition de défis, n'hésitez donc pas à m'écrire !

Bonne chance à tous !

Défis Terminé :

Les 100.000 boites
Participants :
- GhoStRideROriGinS (python)
- fearyourself (C)
- mabu (C/C++)
- Sylvain Togni (C++)
- pseudocode (java)
- st20085 (java)
- Waldar (SQL)


Le courrier est trop long !
Participants :
- pseudocode (java) : Longueur trouvé : 89188
- les Golgoths (VB.NET) : Longueur trouvé : 90334
- Sylvain Togni (C++) : Longueur trouvé : 89188


Défi en cours : Pas de triche
Participants :
- philben (nc)

Prochains défi : Lundi 12 avril

le blog : http://blog.developpez.com/cs-blog/p...oths/#more8756

ps : Merci de faire en sorte d'avoir toujours le temps d'exécution dans votre programme.

[Orange Mango]

Voici ma réponse pour le défi Les 10.000 boites:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
file = open('box.txt', 'r')
txt = file.read()
file.close()
 
txt = txt.split(';')
del(txt[-1])
 
list = {}
for x in txt:
    dim = x.split(',')
    size = int(dim[0]) * int(dim[1]) * int(dim[2])
    list[str(size)] = x
 
temp = []
for x in list:
    temp.append(x)
 
temp.sort()
 
box = ''
for x in temp:
    box = box + list[x] + ';'
 
file = open('box.txt', 'w')
file.write(box)
file.close()
 
raw_input('La boite la plus grande est de: ' + list[temp[-1]])

[fearyourself]

Bon je suppose que c'est un problème d'algorithmie donc la solution en C est peu intéressante mais là voici :-)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
#define MAX 100000
 
//Structure de base : largeur,longueur,hauteur et dimension
//On garde la dimension car cela accelere le tri
typedef struct sBoites 
{
    int largeur;
    int longueur;
    int hauteur;
    int dimension;
}SBoite;
 
//Lecture du fichier... Fonction basique...
SBoite *
lireFichier (FILE *f, int *nombre)
{
    int cnt = 0;
    //Pour cet exercice on va tricher et allouer directement MAX,
    //normalement on ferait un système d'agrandissement du tableau...
    SBoite *res = malloc (sizeof (*res) * MAX);
    assert (res);
 
    while (1)
    {
        int largeur, longueur, hauteur;
        int r = fscanf (f, "%d,%d,%d;", &longueur, &largeur, &hauteur);
 
        if (r != 3)
            break;
 
        res[cnt].largeur = largeur;
        res[cnt].longueur = longueur;
        res[cnt].hauteur = hauteur;
 
        //Calcul de la dimension
        res[cnt].dimension = largeur * longueur * hauteur;
        cnt++;
 
        //Paranoia
        assert (cnt <= MAX);
    }
 
    *nombre = cnt;
    return res;
}
 
//Ce tri mettra le plus grand en position 0
int 
comparBoites (const void *pva, const void *pvb)
{
    const SBoite *pba = pva;
    const SBoite *pbb = pvb;
 
    int dima = pba->dimension;
    int dimb = pbb->dimension;
 
    return dimb - dima;
}
 
//Tri utilisant qsort de la libc
void
triBoites (SBoite *boites, int nombre)
{
    qsort (boites, nombre, sizeof (*boites), comparBoites);
}
 
//Affichage
void
afficheBoite (SBoite *b)
{
    fprintf (stderr, "Boite plus grande %d,%d,%d\n", b->longueur,b->largeur,b->hauteur);
}
 
//Liberation du tableau
void
libereBoites (SBoite *boites)
{
    free (boites), boites = NULL;
}
 
//Ecriture
void
ecrireFichier (FILE *f, SBoite *boites, int nombre)
{
    int i;
    if (nombre > 0)
    {
        for (i=0; i < nombre - 1; i++)
        {
            fprintf (f, "%d,%d,%d;", boites[i].longueur, boites[i].largeur, boites[i].hauteur);
        }
        //Last one
        fprintf (f, "%d,%d,%d", boites[i].longueur, boites[i].largeur, boites[i].hauteur);
    }
}
 
int 
main (void)
{
    const char *fname = "box.txt",
               *foutname = "box_output.txt";
    FILE *f = fopen (fname, "r");
    SBoite *boites;
    int nombre = 0;
 
    if (f == NULL)
    {
        fprintf (stderr, "Fichier %s n'a pas ete ouvert", fname);
        return EXIT_FAILURE;
    }
 
    boites = lireFichier (f, &nombre);
 
    //On trie
    triBoites (boites, nombre);
 
    //On affiche le plus grand
    afficheBoite (boites);
 
    //On ferme
    fclose (f), f = NULL;
 
    //On ouvre pour ecrire
    f = fopen (foutname, "w");
    if (f == NULL)
    {
        fprintf (stderr, "Fichier %s n'a pas ete ouvert", foutname);
        return EXIT_FAILURE;
    }
 
    //Ecrire fichier
    ecrireFichier (f, boites, nombre);
 
    //On ferme
    fclose (f), f = NULL;
 
    //On libere la memoire
    libereBoites (boites), boites = NULL;
 
    return EXIT_SUCCESS;
}

J'ai :

Boite plus grande 997,979,997

real 0m0.150s
user 0m0.140s
sys 0m0.008s

[Golgotha]

Merci, ça serais bien de voir quelqu'un faire un algo de trie "a la main"

[droggo]

Goe,

ps : Merci de faire en sorte d'avoir toujours le temps d'exécution dans votre programme.

Alors ce n'est pas vraiment une question d'algorithme, mais d'implémentation (même si l'algorithme compte pour la vitesse, bien entendu).

[Golgotha]

Goe,

Alors ce n'est pas vraiment une question d'algorithme, mais d'implémentation (même si l'algorithme compte pour la vitesse, bien entendu).

Ce n'est qu'a titre informatif, le but est de faire voir des solutions différente et de les confronter.

[Trap D]

J'ai sans doute sauté une info, mais comment définis-tu l'ordre sur les boîtes, par le volume, la somme des dimensions ?
Y a-t-il des maxima pour les dimensions ?
(je n'ai pas lu les solutions proposées).

[Invité(e)]

Bonjour

Après le C, voici le C/C++.

Pourquoi C/C++ plutôt que C ou C++ (sans faire de troll) :

C : réponse déjà donnée par fearyourself (je vois mal comment faire mieux);
C++ : trop lent avec mes compétences (STL seule).

Le temps n'aurait pas été une contrainte, je serai resté au C++ pur.

Donc C/C++ : les accès aux fichiers et les formatages de chaines restent en C quand les opérations sont nombreuses.

Code c++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// pour perror et FILE
#include <cstdio>
// pour cout
#include <iostream>
// pour stringstream et string
#include <sstream>
// je vous laisse deviner
#include <vector>
// pour sort
#include <algorithm>
 
// structure qui contiendra la description d'une boite 
struct box {
    int m_x;
    int m_y;
    int m_z;
    int m_size;
 
    box(int x, int y, int z):m_x(x), m_y(y), m_z(z) {
        m_size = m_x * m_y * m_z;
    } 
 
    // pour le tri
    bool operator <(const box & op) const {
        return m_size < op.m_size;
    } 
 
    // pour qu'une boite s'identifie (méthode lente : utilise stringstream)
    std::string tell() const {
        std::stringstream ss;
        ss << m_x << "," << m_y << "," << m_z << ";";
        return ss.str();
    }
    // pour qu'une boite s'identifie
    // (méthode rapide : utilise sprintf sur un buffer déjà pret)
    void tell(char *buf) const {
        sprintf(buf, "%d,%d,%d;", m_x, m_y, m_z);
    }
};
 
int main(int argc, char *argv[])
{
    if (argc != 3) {
        std::cout << "usage: " << *argv << " in.txt out.txt" << std::endl;
    } else {
        std::vector < box > boxes;
 
        FILE *fin = NULL, *fout = NULL;
 
        do {
            // ouverture du fichier source
            fin = fopen(argv[1], "r");
            if (NULL == fin) {
                perror(argv[1]);
                break;
            }
 
            // ouverture du fichier destination
            fout = fopen(argv[2], "w");
            if (NULL == fout) {
                perror(argv[2]);
                break;
            }
 
            {
                // lecture du fichier
                int x, y, z;
                while (3 == fscanf(fin, "%d,%d,%d;", &x, &y, &z)) {
                    boxes.push_back(box(x, y, z));
                }
            }
 
            // tri de la liste
            std::sort(boxes.begin(), boxes.end());
 
            // affichage de la plus grande boite
            std::cout << "largest box is " << boxes.back().tell() << std::endl;
 
            {
                // on prend la taille de la plus grand boite pour déterminer la taille
                // nécessaire au stockage de la description de chaque boite.
                // A noter : cette approche est fausse : ici la plus grande boite
                // est 997x979x997. s'il existe une boite comme 
                //     10000x10000x1, 
                // on va avoir un beau dépassement mémoire.
                size_t str_size = boxes.back().tell().length() + 1;
                // buffer pour stocker le description des boites
                char *buf = new char[str_size];
                // stockage de la liste triée dans un autre fichier
                std::vector < box >::iterator it;
                for (it = boxes.begin(); it != boxes.end(); ++it) {
                    it->tell(buf);
                    fprintf(fout, buf);
                //fprintf(fout, it->tell().c_str());
                }
                delete [] buf;
            }
 
        } while (0);
        // fermeture des fichiers
        if (NULL != fin) {
            fclose(fin);
        }
        if (NULL != fout) {
            fclose(fout);
        }
    }
    return 0;
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
$ g++ -O3 -Wall -Wextra test.cc -o test && time ./test.exe box.txt sorted.txt
largest box is 997,979,997;
 
real    0m0.450s
user    0m0.358s
sys     0m0.062s

[Golgotha]

J'ai sans doute sauté une info, mais comment définis-tu l'ordre sur les boîtes, par le volume, la somme des dimensions ?
Y a-t-il des maxima pour les dimensions ?
(je n'ai pas lu les solutions proposées).

Oui, c'est bien le volume de la boite qui compte.

[Sylvain Togni]

Donc C/C++ : les accès aux fichiers et les formatages de chaines restent en C quand les opérations sont nombreuses.

Bof, voici une version 100% C++, elle semble au contraire plus rapide !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <fstream>
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>
 
struct Box
{
  int x;
  int y;
  int z;
};
 
std::istream& operator>>(std::istream& src, Box& b)
{
  char c1, c2, c3;
  return src >> b.x >> c1 >> b.y >> c2 >> b.z >> c3;
  if (c1 != ',' || c2 != ',' || c3 != ';')
    src.setstate(std::ios::failbit);
}
 
std::ostream& operator<<(std::ostream& dst, Box const& b)
{
  return dst << b.x << ',' << b.y << ',' << b.z << ';';
}
 
bool operator<(Box const& b1, Box const& b2)
{
  return b1.x*b1.y*b1.z < b2.x*b2.y*b2.z;
}
 
int main(int argc, char* argv[])
{
  // Usage
  if (argc != 3)
  {
    std::cerr << "Usage: " << argv[0] << " in.txt out.txt" << '\n';
    return EXIT_FAILURE;
  }
 
  // Lecture des boites
  std::ifstream src(argv[1]);
  std::vector<Box> boxes((std::istream_iterator<Box>(src)), std::istream_iterator<Box>());
  if (!src.eof())
  {
    std::cerr << "Erreur de lecture !\n";
    return EXIT_FAILURE;
  }
 
  // Tri des boites
  std::sort(boxes.begin(), boxes.end());
 
  // Affichage de la plus grande boite
  std::cout << "La plus grande boite est " << boxes.back() << '\n';
 
  // Sauvegarde des boites triées
  std::ofstream dst(argv[2]);
  std::copy(boxes.begin(), boxes.end(), std::ostream_iterator<Box>(dst));
  if (!dst)
  {
    std::cerr << "Erreur d'écriture !\n";
    return EXIT_FAILURE;
  }
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
$ g++ -O3 -Wall -Wextra test.cpp -o test && time ./test.exe box.txt sorted.txt
La plus grande boite est 997,979,997;
 
real    0m0.172s
user    0m0.171s
sys     0m0.031s

[Invité(e)]

Bof, voici une version 100% C++, elle semble au contraire plus rapide !

Attention, je n'ai pas accusé la STL, mais mes compétences.

[pseudocode]

Tout pareil que les autres, mais avec ce langage affreusement lent qu'est Java ()

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.FileReader;
import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
 
public class Test {
 
	static class Box {
		int x,y,z,volume;
		public Box(int x, int y, int z) {
			this.x=x; this.y=y; this.z=z;
			this.volume=x*y*z;
		}
		public String toString() {
			return this.x+","+this.y+","+this.z;
		}
	}
 
	public static void main(String[] args) throws Exception {
		ArrayList<Box> list = new ArrayList<Box>();
 
		// read file and insert into list
		FileReader reader = new FileReader("box.txt");
		while(reader.ready()) {
			int x=0,y=0,z=0,d;
			while((d=reader.read())!=',') x=10*x+(d-'0');
			while((d=reader.read())!=',') y=10*y+(d-'0');
			while((d=reader.read())!=';') z=10*z+(d-'0');
			list.add(new Box(x, y, z));
		}
		reader.close();
 
		// sort the list
		Collections.sort(list, new Comparator<Box>() {
			public int compare(Box b1, Box b2) { return b1.volume-b2.volume; }
		});
 
		// write the sorted list to file
		FileWriter writer = new FileWriter("sorted.txt");
		for(Box box:list)
			writer.append(box.toString()).append(';');
		writer.close();
	}
}

Durée : environ 300ms sur mon PC

[st20085]

Une version améliorée du code de Pseudocode

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
 
import java.io.*;
import java.util.*;
 
public class BoxTest
{
  static class Box implements Comparable<Box>
  {
    int x, y, z, volume;
 
    public Box(int x, int y, int z)
    {
      this.x = x;
      this.y = y;
      this.z = z;
      this.volume = x * y * z;
    }
 
    public String toString() {
      return this.x+","+this.y+","+this.z;
    }
 
 
    public void writeToBuffer(StringBuffer buffer)
    {
      buffer.append(x).append(',').append(y).append(',').append(z);
    }
 
    /*
     * @see java.lang.Comparable#compareTo(java.lang.Object)
     */
    @Override
    public int compareTo(Box box)
    {
      int result = volume-box.volume;
      if (result == 0)
        result = hashCode()-box.hashCode(); // tempo
      return result;
    }
  }
 
  public static void main(String[] args) throws Exception
  {
    //long time = System.currentTimeMillis();
    TreeSet<Box> list = new TreeSet<Box>();
 
    // read file and insert into set
    Reader reader = new BufferedReader(new FileReader("d:/box.txt"));
    while(reader.ready())
    {
      int x = 0, y = 0, z = 0, d;
      while((d = reader.read()) != ',')
        x = 10 * x + (d - '0');
      while((d = reader.read()) != ',')
        y = 10 * y + (d - '0');
      while((d = reader.read()) != ';')
        z = 10 * z + (d - '0');
      list.add(new Box(x, y, z));
    }
    reader.close();
    //System.out.println("TIME=" + (System.currentTimeMillis() - time));
 
    // write the sorted list to file
    StringBuffer buffer = new StringBuffer(1200000);
    for(Box box : list)
    {
      box.writeToBuffer(buffer);
      buffer.append(';');
    }
    Writer writer = new BufferedWriter(new FileWriter("d:/sorted.txt"));
    writer.write(buffer.toString());
    writer.close();
    //System.out.println("TIME=" + (System.currentTimeMillis() - time));
    System.out.println("La plus grande boite est "+list.last());
  }
}

[Waldar]

En SQL (Oracle 11g utilisée ici) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
With SR AS
(
  select x, y, z
    from box
order by x*y*z desc
)
select x,y,z
  from SR
 where rownum = 1;

Temps : environ 220 ms en lecture directe du fichier,
150 ms si chargement préalable dans une table.

Déclarations préalables :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
-- Déclaration du répertoire
CREATE OR REPLACE DIRECTORY BOX AS 'E:\BOX\';
 
-- Table externe (lecture directe du fichier)
CREATE TABLE box
(
    x  NUMBER(3),
    y  NUMBER(3),
    z  NUMBER(3)
)
ORGANIZATION EXTERNAL
(
  TYPE oracle_loader
  DEFAULT DIRECTORY BOX
    ACCESS PARAMETERS
    (
    RECORDS DELIMITED BY ';'
    BADFILE 'bad_%a_%p.bad'
    LOGFILE 'log_%a_%p.log'
    FIELDS TERMINATED BY ','
    MISSING FIELD VALUES ARE NULL
    REJECT ROWS WITH ALL NULL FIELDS
    (x, y, z)
    )
    LOCATION ('box.txt')
)
NOPARALLEL
NOMONITORING;
 
-- Table classique (import du fichier dans le SGBD)
CREATE TABLE box2
AS
SELECT * FROM box;

[Golgotha]

Un grand MERCI aux participants de cette première mise en bouche, on à même du SQL ! c'est génial.

Je pense que je vais clore cette introduction, et lancer un vrai défis dès ce soir, digne de vous mettre un peux plus à l'épreuve (enfin je l'espère).

Merci encore à tous les participants.

[Golgotha]

Bonsoir,

Je vous informe que le Second défis des Golgoths, est officiellement lancé :

http://blog.developpez.com/cs-blog/

Défi en cours : Le courrier est trop long !

Bonne chance à tous !

[Bucketpc]

Bonjour,

Il y a 30 points de passage, alors il y a 29! (FACT(29)) de solutions possibles. C'est un problème NP-complet, ce qui n'est pas possible a tester avec un pc (peut être l'exécution va prendre 20ans ). Ce problème est similaire au problème du voyageur de commerce.

Pour le résoudre, il est nécessaire d'utiliser une méthode d'optimisation heuristique (non-exacte), telle que les algorithmes génétique, la recherche dispersée, etc.
Les méthodes heuristiques donnent des solutions optimales dans un temps admissible. Mais rien ne garantit qu'il n'existe pas de meilleurs solutions qu'elles.

Pour l'exécution j'ai pas le courage pour saisir les 30 points, ainsi de calculer la distance entre chaque paire , et attendre le résultat. Sauf que je vois qu'il ne coutera rien d'expliquer comment ça se passe.

1. au début, il faut définir une population initiale de solutions (fixées aléatoirement, où en utilisant des heuristiques).
2. évaluer chaque solution présente dans la population, en s'appuyant sur des critères biens définis (ici la distance du parcours).
3. En s'appuyant sur l'évaluation, Sélectionner des solutions qui vont êtres combinées pour la création des nouvelles solutions. Ceci, en utilisant des méthodes de reproduction (croisement, mutation).
4. insérer les nouveaux individus (généralement ceux ayant une qualité meilleurs) dans une nouvelle population. Bien sûr, suivant des règles.
5. répéter les étapes 2, 3, 4, 5 jusqu'à la convergence vers une solution satisfaisante.

A+

[Golgotha]

Merci Bucketpc,

C'est effectivement un problème np-complet, impossible à résoudre en parcourant l'arbre des possibilités, il faut donc mettre au point un algorithme un peux plus subtile, comme vous le dite, les algorithmes génétique est une des voie qui peux donner une solution.

Je proposerais moi même un solution, dans quelques jours.

[Bucketpc]

Je rajoute, les coordonnés des villes sont en fonction de X, Y, et Z (repère 3D). Donc, le calcul de la distance entre deux villes se fait en utilisant une formule comme celle d'Euclide.
Distance (P1, P2) = racine( [(X1-Y1)^2] + [(X2-Y2)^2] + [(X3-Y3)^2]) // (X-Y)^au carrée

[pseudocode]

Pour le résoudre, il est nécessaire d'utiliser une méthode d'optimisation heuristique (non-exacte), telle que les algorithmes génétique, la recherche dispersée, etc.

j'ai codé un petit algo génétique a la va vite. Ca converge vers une solution en moins d'une minute. Je trouve un circuit fermé de longueur 89188. Mais je ne sais pas si c'est l'optimum.