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).

[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.

[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

[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.