Partage
  • Partager sur Facebook
  • Partager sur Twitter

Arbre binaire ayant plusieurs requetes

Bugs

AlNonyme
  • Langage C++
    31 août 2018 à 11:55:45

    Salut à tous,

    je code depuis quelques temps, et j'ai entrepris de coder un algorithme d'arbre binaire ayant plusieurs requetes sur intervalles . J'ai entendu parler de la lazy propagation et j'imagine que cela pourrait optimiser mon algorithme, mais je ne suis pas ici pour cela, même si je ne refuserai pas des conseils de ce type :-°

    Enfin bref, voilà l'algorithme auquel je suis confronté :

    Vous devez simuler un jeu à la Tetris™. Dans cette variante, toutes les formes sont des bâtons d'épaisseur 1 et de longueur variable. Le cadre du jeu est un rectangle infiniment haut, et des bâtons tombent du ciel les uns après les autres.

    On vous dit pour chaque bâton s'il est orienté horizontalement ou verticalement, on vous donne sa longueur, et on vous indique enfin sa position latérale. Le bâton tombe alors tout droit vers le bas, sans se retourner d'aucune manière, et s'arrête dès qu'il touche le sol ou bien repose sur un bâton déjà placé.

    On part d'un cadre de jeu initialement tout vide, et on vous donne la suite des bâtons qui tombent. Votre tâche est de calculer la hauteur maximale atteinte par les bâtons, c'est-à-dire la hauteur de la case la plus haute contenant un morceau de bâton.

    Limites de temps et de mémoire (C++)

    • Temps : 1 s sur une machine à 1 GHz.
    • Mémoire : 64 000 ko.

    Contraintes

    Le cadre du jeu contiendra toujours 100000 colonnes, numérotées de 0 à 99999 inclus. Il n'y a a prioripas de limite au nombre de lignes.

    Entrée

    La première ligne de l'entrée contient un entier N : le nombre de bâtons qui vont tomber, avec 1 <= N <= 10000.

    Chacune des N lignes suivantes contient la description d'un bâton.
    Un bâton est décrit par une lettre puis deux entiers, séparés par des espaces :

    • une lettre qui donne l'orientation du bâton : 'H' pour horizontale, 'V' pour verticale.
    • un entier qui donne la longueur Li du bâton, avec 1 <= Li <= 100.
    • un entier qui donne la colonne Ci du bord le plus à gauche du bâton, avec 0 <= Ci <= 99.

    Remarque à propos du bord le plus à gauche du bâton :

    • Si le ième bâton est vertical, Ci donne l'indice de la colonne dans laquelle tombe le bâton.
    • Si le ième bâton est horizontal, le bâton s'étend entre les colonnes d'indice Ci et Ci + Li - 1 incluses.

    Sortie

    Affichez un unique entier : la hauteur maximale atteinte.

    Vu les contraintes, il est clair que le brute force ne convient pas . J'ai donc opté pour une résolution utilisant un arbre binaire ^^

    Voilà mon code :

    #include <bits/stdc++.h>
#define int long long
using namespace std;
const int indexPremier = pow(2, log2(100*1000));
struct arbreBinaire
{
   int valeur = 0, idrequete = -1, maximum=0;
};
arbreBinaire arbre[indexPremier*2];
void maximum(int indice )
{
   while ( indice > 0 )
   {
      arbre[indice/2].maximum = max(arbre[indice].maximum, arbre[indice+1].maximum);
      indice /= 2;
   }
}
void mettreValeur(int debut, int fin, int valeur, int irequete )
{
   while (fin >= debut )
   {
      if (fin%2 == 0 )
      {
         arbre[fin].valeur = valeur;
         arbre[fin].idrequete = irequete;
         arbre[fin].maximum = valeur;
         maximum(fin);
      }
      if (debut%2 == 1)
      {
         arbre[debut].valeur = valeur;
         arbre[debut].idrequete = irequete;
         arbre[debut].maximum = valeur;
         maximum(debut);
      }
      debut = (debut+1)/2;
      fin = (fin - 1)/2;
   }
}
int maxInter(int gauche, int droite)
{
   int resultat = -1;
   if (gauche%2 == 1 )
   {
      resultat = max(resultat, arbre[gauche++].maximum);
   }
   if (droite % 2 == 0)
      resultat = max(resultat, arbre[droite--].maximum);
   if (gauche <= droite)
      resultat = max(resultat, maxInter(gauche / 2, droite / 2));
   return resultat;
}
int valeur(int indice )
{
   int requeteCourante = -1, valeurCourante;
   int id = indice;
   while (id > 0 )
   {
      if (arbre[id].idrequete > requeteCourante )
      {
         requeteCourante = arbre[id].idrequete ;
         valeurCourante = arbre[id].valeur;
      }
   //   if (indice == indexPremier + 1)
   //   {cout << valeurCourante << " " << requeteCourante << "\n";}
      id /= 2;
   }
   return valeurCourante;
}
void debug()
{
   cout << arbre[indexPremier/16].maximum << "\n";
   cout << arbre[indexPremier/8].maximum << " " << arbre[indexPremier/8+1].maximum << "\n";
   cout << arbre[indexPremier/4].maximum << " " << arbre[indexPremier/4+1].maximum <<" "<< arbre[indexPremier/4 + 2].maximum << " " << arbre[indexPremier/4+3].maximum<< "\n";
   for (int i = 0; i < 8; i ++ )
   {
      cout << arbre[indexPremier/2+i].maximum << " ";
   }
   cout << "\n";
   for (int i = 0; i < 16; i++ )
   {
      cout << arbre[indexPremier+i].maximum << " " ;
   }
   cout<< "\n\n";
   
}
signed main()
{
   int nbBatons;
   cin >> nbBatons;
   for (int irequete = 0; irequete < nbBatons; irequete ++ )
   {
      char typeRequete;
      int longueur, bordGauche;
      cin >> typeRequete >>  longueur >> bordGauche;
      bordGauche += indexPremier;
      if (typeRequete == 'H' )
      {
         mettreValeur(bordGauche, bordGauche + longueur, maxInter(bordGauche, bordGauche + longueur )+1, irequete );
      }
      else
      {
         //cout << valeur(bordGauche) << "\n";
         arbre[bordGauche].valeur = valeur(bordGauche) + longueur;
         arbre[bordGauche].idrequete = irequete;
         arbre[bordGauche].maximum = arbre[bordGauche].valeur;
         maximum(bordGauche);
      }
    //  debug();
     // cout << valeur(indexPremier+1) <<" "<< arbre[indexPremier + 1].idrequete <<" "<< arbre[indexPremier + 1].maximum <<"\n";
   }
   cout << arbre[1].maximum;
   return 0;
}

    Mais on m'a dit que dans certain cas de figure, il n'afficherait pas le bon résultat . Tout ce que je sais, c'est qu'il afficherait un résultat en dessous de la réponse attendue .

    Pouvez vous m'aider à débuguer mon code ? J'avoue être à court d'idée après plusieurs semaines de recherches ...


    N'hésitez pas à me dire si mon code n'est pas clair, je me ferais une choix de vous le détailler :D

    Merci d'avance !

    -
    Edité par AlNonyme 3 septembre 2018 à 9:41:45

    • Partager sur Facebook
    • Partager sur Twitter
    Un random qui fait de l'algo
    AlNonyme
    • Langage C++
      2 septembre 2018 à 9:30:50

      Vraiment personne pour m'aider ?:euh:
      • Partager sur Facebook
      • Partager sur Twitter
      Un random qui fait de l'algo
      koala01
      • Langage C++
        2 septembre 2018 à 21:09:45

        Salut,

        En fait, la force brute fonctionnera parfaitement dans le cas présent... il suffit de la doser correctement :D

        Car on n'a absolument aucun besoin de maintenir une grille complète avec le contenu des différents bâtons : il faut juste garder une trace de la hauteur à laquelle ira le morceau du baton qui se posera sur la colonne indiquée en sachant que:

        • si le bâton est vertical, le début du bâton arrivera à la hauteur de la colonne + 1 et que la fin du bâton arrivera à la hauteur de la colonne + 1 + la taille du bâton
        • si le baton est horizontal, tous ses éléments se trouveront à la hauteur maximale des colonnes qu'il recouvre +1

        On peut donc commencer par représenter la notion de bâton sous une forme proche de

        /* par facilité, pour la compréhesion */
enum orientation{
    horizontal,
    vertical,
    MAX;
}
struct Stick{
    Orientation orientation;
    size_t size;
    size_t column;
};

        et décider de garder la hauteur maximale atteinte pour toutes les colonnes sous une forme proche de

        std::vector<size_t> heights;
heigths.resize(10000); // on a jusqu'à 10 000 colonnes

        Une fois que nous aurons lu le contenu du fichier (j'y viendrai plus tard ;) ), nous aurons donc "simplement" besoin d'une fonction qui nous indique la hauteur maximale atteinte par la colonne la plus haute qui sera recouverte par le bâton.  Elle pourrait parfaitement prendre une forme proche de

        size_t maxHeight(std::vector<size_t> const & heights, 
                 Stick const & stick){
	if(stick.orientation == vertical)
		return heights[stick.column];
	size_t max{0};
	for(size_t i=stick.column; i<stick.column+stick.size 
            && i < heights.size(); ++i){
		if(heights[i]> max){
			max=heights[i];
		}
	}
	return max;
}

        Ensuite, nous aurons besoin d'une fonction qui s'occupera de mettre la hauteur à jour pour les colonnes "recouvertes" par le bâton.  Cela pourrait prendre une forme proche de

        void update(std::vector<size_t> &heights, size_t & height, Stick const & stick){
	if(stick.orientation == vertical){
		heights[stick.column]+=(stick.size+1);
		height=heights[stick.column];
	}else{
		++height;
		for(size_t i = stick.column; i<stick.column+stick.size && i< heights.size();++i){
			heights[i]=height ;
		}
	}
}

        Et, enfin, il ne nous manquera "plus" qu'une fonction qui calcule la hauteur maximale atteinte par les différents bâtons que nous devons ajouter.  Elle pourrait prendre une forme proche de

        void compute(std::vector<Stick> const & batons){
	std::vector<size_t> columns;
	columns.resize(10000);
	for(size_t i = 0; i<columns.size();++i)
		columns[i]=0;
	size_t max{0};
	for(auto const & bat: batons){
		size_t result = maxHeight(columns, bat);
		update(columns,result, bat);
		if(result> max)
			max=result;
	}
		std::cout<< "maximal height : "<<max<<"\n";
}

        Sauf que, bien sur, j'oublie que l'on doit lire les données depuis un fichier... 

        Nous avons donc besoin d'une fonction qui puisse extraire les données d'un baton depuis une chaine de caractères.  Elle pourrait prendre une forme proche de

        Stick fromString(std::string & temp){
	Stick s;
	switch(temp[0]){
		case 'H':
			s.orientation= horizontal;
			break;
		case 'V':
			s.orientation=vertical;
			break;
		default:
			throw std::runtime_error("bad horientation");
	}
	temp= temp.substr(2);
	size_t pos{0};
	s.size = std::stoull(temp, &pos);
	temp=temp.substr(pos+1);
	s.column=std::stoull(temp);
	if(s.size ==0 || s.size>100)
		throw std::runtime_error("bad size");
	if(s.column>99)
		throw std::runtime_error("bad column");
	return s;
}

        (comme tu le remarques, elle lance une exception si les données que nous obtenons sont incohérentes, parce que nous ne pouvons pas faire confiance à celui qui nous fournira le fichier, et que c'est à lui -- celui qui fournit le fichier -- que revient la responsabilité de s'assurer qu'il est cohérent ;) )

        Et comme nous devrons créer un ensemble de bâtons à partir d'un fichier, nous aurons besoin d'une fonction qui permette de lire le fichier en question.  Elle prendra une forme proche de

        std::vector<Stick> readFromFile(std::string const & filename){
	
	std::vector<Stick> tab;
	std::ifstream ifs(filename);
        if(!ifs)
            throw std::runtime_error("bad filename");
	std::string temp;
	std::getline(ifs,temp);
	size_t max{std::stoull(temp)};
	tab.reserve(max);
	while(std::getline(ifs,temp)){
		auto stick=fromString(temp);
		tab.push_back(stick);
	}
	if(tab.size()!= max)
		throw std::runtime_error("Bad data file");
	return tab;
}

        Encore une fois, tu remarqueras qu'elle va lancer une exception si le nombre de bâtons obtenus ne correspond pas à celui qui était attendu.  C'est parce que la responsabilité de s'assurer que ce soit le cas revient à celui qui nous fournira le fichier.

        Ah mais oui, j'oubliais encore une chose: on va fournir notre code à un serveur, qui nous fournira le fichier que l'on doit lire...

        Mais, si on travaille en local, il faudra que nous puissions créer le fichier adéquat. Et, tant qu'à faire, nous voudrons pouvoir utiliser le même programme, en adaptant les option d'exécution.

        Nous allons donc prévoir un moyen "simple" pour envoyer les données de nos bâtons vers un flux de sortie.  Cela prendra une forme proche de

        std::ostream& operator<<(std::ostream & ofs, Orientation o){
	static std::array<char, MAX> const HStrings={'H', 'V'};
	ofs<<HStrings[static_cast<size_t>(o)]<<" ";
	return ofs;
}
std::ostream & operator <<(std::ostream & ofs, Stick const & stick){
	ofs<<stick.orientation<<" "<<stick.size<<" "<<stick.column<<"\n";
	return ofs;
}

        et nous voudrons pouvoir générer un ensemble de bâtons de manière aléatoire.  Pour ce faire, nous allons créer la notion de "générateur", qui prendra une forme proche de

        struct Generator{
	Generator():rd{},gen{rd()}{
	}
	Orientation orientation(){
		std::uniform_int_distribution<size_t> dist(0, 1);
		return static_cast<Orientation>(dist(gen));
	}
	size_t size(){
		std::uniform_int_distribution<size_t> dist(1,100);
		return dist(gen);
	}
	size_t column(){
		std::uniform_int_distribution<size_t> dist(1,99);
		return dist(gen);
		
	}
	size_t count(){
		std::uniform_int_distribution<size_t> dist(1,300);
		return dist(gen);
		
	}
	std::random_device rd;
	 std::mt19937 gen; 
};

        Le tout nous permettra de créer une fonction qui génère un fichier dont le nom est donné sous forme de paramètre et qui prendra une forme proche de

        void createFile(std::string const & filename){
	std::cout<<"creating file "<<filename<<"\n";
	Generator gen;
	std::vector<Stick> tab;
	size_t max{gen.count()};
	for(size_t i=0;i<max; ++i){
		Stick stick{gen.orientation(), gen.size(), gen.column()};
		tab.push_back(stick);
	}
	std::ofstream ofs(filename);
        if(!ofs)
            throw std::runtime_error("unable to open output file");
	ofs<<tab.size()<<"\n";
	for(auto const & it : tab){
		ofs<<it;
	}
}

        Comme il est toujours sympa de permettre à l'utilisateur d'une application de savoir comment il doit l'utiliser, nous allons rajouter une fonction d'affichage d'une aide, sous la forme de

        void printHelp(){
	std::cout<<"Tetris \n"
	         <<"\n "
	         <<"Program options:\n"
	         <<"--help | -h      print this help and exits\n"
	         <<"-r <filename>    reads <filename> file to compute it\n"
	         <<"-c <filename>    create <filename> with game datas\n"
	         <<"<filename>       reads <filename> file to compute it\n"
	         <<"\n\n";
}

        On va enfin créer une fonction qui vérifie les paramètres transmis à l'application sous une forme proche de

        void execute(int argc, char ** argv){
	if(argc == 3){
	    std::string option{argv[1]};
	    std::string filename{argv[2]};
	    if(option=="-c")
		createFile(filename);
	    else if(option=="-r"){
		auto tab = readFromFile(filename);
		compute(tab);
            }
	}else if(argc == 2){
	    std::string filename{argv[1]};
	    auto tab = readFromFile(filename);
            compute(tab);
        }else{
            printHelp();
        }
}

        Et, enfin, nous pourrons créer notre fonction principale qui se contentera de faire appel à la fonction execute, sous une forme proche de

        int main(int argc, char ** argv){
	execute(argc, argv);
	return 0;
}

        Grâce à tout cela, nous pouvons générer un fichier de données à l'aide de la commande

        ./aout -c data.txt

        qui nous générera un fichier proche de

        50
V  65 56
H  62 46
V  39 97
V  37 67
V  9 57
V  74 87
H  90 5
V  36 49
V  23 52
V  59 54
V  58 10
H  44 89
V  29 84
H  86 87
H  53 20
H  82 60
H  63 64
H  1 84
V  85 87
V  72 53
H  16 97
V  15 68
V  82 38
V  50 70
V  90 7
V  53 58
H  11 67
V  60 51
H  67 42
H  15 73
V  54 2
H  89 86
V  30 29
V  57 77
H  35 27
V  96 81
V  24 66
V  93 90
V  32 18
H  65 27
V  82 87
H  32 63
V  41 49
V  66 51
H  4 67
V  45 2
H  4 63
H  79 9
H  58 37
H  78 82

        ou proche de

        292
H  94 93
H  47 35
V  82 69
H  97 72
V  72 23
V  8 90
V  72 74
V  2 35
V  65 2
H  61 87
H  45 40
H  6 24
V  54 70
V  78 43
V  10 36
V  78 34
H  13 94
H  98 13
H  18 46
H  5 26
H  66 10
H  84 14
V  86 59
H  91 24
H  60 60
V  37 31
H  62 68
V  28 23
V  5 82
H  49 3
H  73 22
V  10 73
H  39 79
V  92 69
V  26 7
V  20 86
V  56 19
V  30 58
V  81 22
V  96 79
H  8 37
V  85 15
V  64 37
H  25 54
V  59 58
V  5 99
H  77 47
V  60 61
H  56 31
H  58 59
H  30 52
V  88 84
V  1 8
H  3 63
V  62 3
H  98 38
H  60 82
V  76 11
V  25 44
H  91 75
V  56 63
H  69 45
V  79 85
V  4 90
H  16 43
V  50 75
V  74 41
V  85 17
V  53 99
V  52 46
V  94 30
V  81 26
H  30 56
H  30 18
V  41 21
V  29 70
V  76 50
H  6 71
H  92 32
H  81 20
V  55 64
V  45 42
H  92 75
H  88 76
H  81 36
V  97 44
H  65 95
V  99 11
V  99 86
H  98 48
V  61 77
H  32 82
H  86 33
H  98 67
V  27 73
H  15 38
H  15 72
H  39 61
H  34 53
V  97 13
H  10 36
V  8 20
V  62 78
V  31 26
H  59 68
V  43 82
V  68 39
V  82 9
H  34 67
H  85 39
H  40 35
H  66 27
H  13 71
V  53 69
H  77 52
H  63 88
V  26 32
V  40 50
V  90 92
H  74 38
V  25 47
V  65 37
H  53 15
H  58 51
H  40 68
H  21 5
H  73 80
V  70 44
H  42 1
H  33 12
V  42 29
V  78 38
H  33 19
H  58 67
V  40 76
H  42 57
V  10 9
H  42 95
H  69 45
H  23 33
H  12 81
V  55 26
V  82 14
V  10 70
V  38 45
H  75 88
H  29 97
H  9 6
V  43 23
V  74 77
H  45 15
H  93 13
V  53 87
V  99 85
V  45 39
H  85 43
V  81 4
H  60 4
H  83 57
V  94 96
V  48 62
V  36 25
H  15 87
H  99 93
V  87 16
V  56 45
H  100 9
V  99 8
H  63 10
V  7 17
V  68 80
V  50 2
V  1 24
V  80 58
H  40 43
H  16 27
H  3 15
H  67 60
H  87 49
V  88 68
H  64 22
H  44 42
V  90 95
H  30 41
V  92 15
V  40 63
V  84 91
V  60 63
V  4 70
V  42 80
V  38 96
H  5 99
V  97 27
V  25 2
H  46 41
V  35 80
H  15 68
H  63 30
H  12 45
H  60 67
V  3 40
H  42 70
V  62 27
H  55 83
V  10 10
H  69 73
H  95 73
H  47 88
V  67 1
V  93 42
V  36 47
V  95 32
H  17 4
H  51 55
V  57 13
H  86 3
V  37 65
V  72 70
H  14 69
H  25 29
V  22 15
H  28 48
V  92 39
H  56 33
V  21 53
V  70 82
H  63 73
H  44 47
H  27 69
V  16 29
V  75 39
V  74 19
V  70 77
V  37 55
V  6 49
H  66 6
V  24 32
H  85 26
V  59 3
H  54 25
H  78 64
H  11 18
V  96 29
H  80 22
H  80 40
V  51 94
V  24 61
V  39 83
H  81 67
H  61 58
V  21 7
H  75 71
V  4 66
H  51 55
H  58 16
H  89 97
V  43 27
V  53 17
H  6 18
V  16 79
V  91 72
V  76 58
H  24 11
V  2 73
H  47 96
V  23 92
V  53 6
V  86 54
V  95 34
V  83 55
V  28 10
V  25 78
V  21 87
V  38 47
V  99 12
H  3 44
H  95 53
H  11 34
V  91 22
V  63 34
V  20 30
H  36 89
H  35 22
V  36 9
H  85 31
H  71 31
V  83 29
H  90 44
H  47 20
V  91 94
H  83 2
V  97 44

        (c'est ca la beauté du geste: on ne peut absolument pas prédire combien de bâtons nous obtiendrons lors de la création de notre fichier :D )

        et, une fois le fichier créé, nous pourrons le traité grâce -- au choix -- à la commande

        ./a.out -r datas.txt

        ou à la commande

        ./a.out datas.txt

        Et, si les paramètres transmis à l'application ne correspondent pas, nous obtiendrons un affichage proche de

        ./a.out 
Tetris 

 Program options:
--help | -h      print this help and exits
-r <filename>    reads <filename> file to compute it
-c <filename>    create <filename> with game datas
<filename>       reads <filename> file to compute it

        Avoue que c'est pas mal, hein???

        EDIT: pour info, je me suis amusé à modifier mon code pour générer des fichiers qui contiennent entre 500 000 et 600 000 batons.

        Le temps de traitement de ce genre de fichier, sur mon système reste de 0,411 secondes pour un fichier de 5.3Mb (510 078 bâtons) ;)

        -
        Edité par koala01 2 septembre 2018 à 21:27:22

        • Partager sur Facebook
        • Partager sur Twitter
        Ce qui se conçoit bien s'énonce clairement. Et les mots pour le dire viennent aisément.Mon nouveau livre : Coder efficacement - Bonnes pratiques et erreurs  à éviter (en C++)Avant de faire ce que tu ne pourras défaire, penses à tout ce que tu ne pourras plus faire une fois que tu l'auras fait

        Arbre binaire ayant plusieurs requetes

        × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
        × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
        • Editeur ●
        • Markdown