Sfida nga PR-TECH: Trungu - Llogaritja e lidhjeve

[edspace]

Sfida është hapur nga Grupi Teknologjik i Prishtinës. Po e hedhim në forum që anëtarët të mund të diskutojnë zgjidhjet dhe të mësojnë nga eksperienca e njëri-tjetrit. Tema do qëndrojë e mbyllur gjatë kohës që sfida është e hapur dhe zgjidhja juaj nuk duhet bërë publike gjatë kësaj kohe. Kur të skadojë afati i lejuar, tema do hapet dhe pastaj mund të postoni përgjigjet tuaja dhe të diskutoni me anëtarët e tjerë.

Trungu - Llogaritja e lidhjeve
Problemi eshte i hapur
Prej:11/12/2004 Deri:20/12/2004
Edituar me 11/12/04

Kjo sfidë ka ta të bëjë me manupulim të trungut (tree). Detyra është që të llogaritet rruga prej burimit deri te destinacioni. Ne figurën e mëposhtme ndodhen rrathët (A, B, C...) dhe lidhjet në mes të atyre rrathëve. Rrathët janë unik. Lidhja në mes tyre bëhet vetëm në një drejtim (shiko shigjetat) si dhe supozohet që NUK ka raste të cikleve. Cdo rreth lidhet për së paku një rreth tjetër dhe mund të degëzohet në më shumë se një drejtim. Detyra është që të shkruhet funksioni (procedura) që kthen numrin e lidhjeve me anë te cilave janë lidhur dy rrathët e dhënë. Psh. nese kërkohet kerko('A','D') duhet të kthehet 2, ndërsa nëse nuk gjindet asgjë atëherë 0, psh kerko('B','P') është 0. Poashtu ('D','A') është 0 për shkak të shigjetave një kahëshe.


Shikoni fotografinë e bashkëngjitur.

Në mënyrë që t'a zgjidhni këtë detyrë, ju e përdorni databazën (e ndërtuar në bazë të figurës) ku çdo rresht i korrespondon nje lidhjeje.

A G
A B
G I
B D
B L
D J
D F
J K
L M            
P R
R T
T E
E C
C H

Mënyrën se si kjo databazë do të lexohet/krijohet zgjidhni ju (nga skeda, nga përdoruesi, "hard-code" etj) . Me rëndësi është qe funksioni "kerko(X, Y)" te kthen vlerën e sakte dhe që databaza te jetë fleksibile (të mund të ndryshohet lehtë). Merreni parasysh qe funksioni mund te funksionojë edhe duke përdorur hyrje të tjera.
Testoni funksionin për këto raste (pavarësisht nga gjuha):

kerko('A','I') // 2 (kthen 2)
kerko('A','G') // 1
kerko('A','F') // 3
kerko('A','D') // 2
kerko('A','M') // 3
kerko('A','L') // 2
kerko('A','K') // 4
kerko('J','K') // 1
kerko('B','L') // 1
kerko('L','B') // 0
kerko('P','H') // 5
kerko('E','T') // 0
kerko('M','P') // 0
kerko('R','D') // 0

Programi mundet të shkruhet në C, C++, Java, Perl, Visual Basic (VB.NET), C# . Kësaj rradhe ju mund të perdorni edhe Scheme/Lisp si dhe Prolog për shkak të natyrës së problemit. Nëse programi juaj përmbanë më shumë se një skedar atëherë le të arkivohet si tar.gz apo zip dhe si i tillë le të dërgohet në programim ET pr-tech PIKË net.

[edspace]

Kam pas bërë një program të ngjashëm në shkollë dhe vendosa të përdorja strukturën e hartës (MAP) për ndërtimin e pemës.
Për ata që nuk i kanë përdorur më parë, hartat janë si matricat por të lejojnë të zgjedhësh vetë tipin e indeksit. Janë pak a shumë si hash array të PERL dhe associative array të PHP.
Në matrica janë vetëm indekset me numra matrica[0], matrica[1], ... ndërsa për hartat mund të kesh indekse të çdo tipi. Për këtë program do mjaftonte indeksi char sepse kemi vetëm një shkronjë por unë zgjodha strings që programi të punojë edhe me fjalë.

Shikoni figurën e bashkëngjitur si shëmbull.

Hartat në brëndësi janë ndërtuar mbi pemët. Dmth kemi tre shtresa strukturash:
pemë me dy degezime -> hartë -> pemë me shumë degëzime
Programuesi menaxhon vetëm një shtresë ndërsa të tjerat janë të gatshme në STL (STANDARD TEMPLATE LIBRARY).

Pyetje, këshilla, kritika?

// Programi: Llogaritja e lidhjeve
// Data: 20/12/04 
// Pershkrim: Sfida e Javes nga Grupi Teknologjik i Prishtines 
// Perpiluesi: Dev-C++ 4.9.9.1 
// Perdorimi: 
//    Formo nje peme nga skedari databaza.txt dhe llogarit numrin e lidhjeve 
//    per kerkesat e perdoruesit. 
//    Databaza mund te permbaje shkronja (psh. P T) ose fjale (psh. PRISHTINA TECH).
//    Programi ben dallime midis shkronjave te medha dhe te vogla. A != a
//    Nuk ka kufizim per numrin e degezimeve. 0 -> oo
// 
#include <iostream>
#include <fstream> // File Stream: Per leximin e skedareve
#include <string> 
#include <map> // harte[celes] = vlere  // C++ STL

using namespace std;

// nyje[dege] = nyje1
// nyje1[dege] = nyje2
// nyje3[dege] = nyje4
// ...
typedef map < string, void * > nyje; 
typedef nyje peme; // edhe pema mund te mendohet si nje nyje 

//*****************************************************************************
// lexon skedarin dhe kthen treguesin e nje peme 
// pema eshte bosh nqs skedari nuk mund te hapet
//
peme * lexo_databazen( string skedari );

//*****************************************************************************
// lidh fillimin me fundin ne pemen p
// kthen PO (true) nqs ben lidhjen
// kthen JO (false) nqs nuk e ben dot lidhjen (fillimi nuk gjendet ne peme)
// funksion veteperserites/rekursiv
//
bool hidh_ne_peme( peme * p, const string & fillimi, const string & fundi );

//*****************************************************************************
// kerkon nyjen me emrin varg ne pemen p
// kthen treguesin nqs e gjen ose NULL nqs nuk e gjen. 
// rezultati = distanca nga renja e pemes p deri tek nyja me emrin varg
// shkalla tregon distancen (qe natyrisht fillon nga 1)
// funksion veteperserites/rekursiv
//
peme * kerko( peme * const p, const string & varg, int & rezultati, int shkalla = 1);


//**************************** MAIN *******************************
int main(int argc, char *argv[])
{
    peme * p = lexo_databazen("databaza.txt"); // formojme pemen p
    
    if( p->empty() ) // nqs databaza eshte bosh
    {
        cerr << "Gabim: Databaza nuk mund te hapej ose eshte bosh" << endl;
        return 0;
    }
    
    string fillimi, fundi; // fillimi ----- lidhja -----> fundi
    int rezultati = 0;     // permban distancen nga filimi --> fundi
    nyje * n;              // tregues per nje nyje te pemes

    cout << "Jep komandat per te kerkuar (psh: 'A G' pa thonjza gjen distancen nga A ne G)." << endl;
    cout << "Shkruaj 'mbyllu' pa thonjza per te mbyllur programin." << endl;

    while( true )  // merr komanda nga perdoruesi
    {              // deri sa perdoruesi te shkruaj komanden "mbyllu"        
        cin >> fillimi;   
        if( fillimi == "mbyllu" ) return 0; 
        
        cin >> fundi;      // merr fundin 
        
        n = kerko(p, fillimi, rezultati);  // kerkojme fillimin ne peme
        rezultati = 0;                        
        
        if( n != NULL ) // nqs nyja e fillimi ka dege te tjera
            kerko(n, fundi, rezultati);  // kerkojme fundin
        
        cout << fillimi << " -> " << fundi << " = " << rezultati << endl;
        
        rezultati = 0;
    }
    
    return 0;
}

//**************************** LEXO DATABAZEN *******************************
peme * lexo_databazen( string skedari )
{
     ifstream db (skedari.c_str(), ios::in); // hapim db per lexim

     peme * p = new peme; // assert(p != null) // krijojme pemen kryesore
     string fillimi, fundi;     
     
     while( db.good() )  // per aq kohe sa mund te lexojme nga skedari
     {
        db >> fillimi;   // lexojme fillimin
        db >> fundi;     // lexojme fundin
        
        // nqs nuk i lidhim dot
        if( !fillimi.empty() && !fundi.empty() && !hidh_ne_peme( p, fillimi, fundi ) )  
        {
            nyje * n = new nyje; // assert(n != null)  // formo nje nyje te re
            n->insert(make_pair(fundi, (void *)NULL)); // lidh fundin
            p->insert(make_pair(fillimi, n));          // lidh fillimin
        }
     }
     
     return p; // kthejme mbrapsh pemen/databazen
}

//**************************** HIDH NE PEME *******************************
bool hidh_ne_peme( peme * p, const string & fillimi, const string & fundi )
{
     peme::iterator i = p->find(fillimi); // kerkojme fillimin ne pemen p
     
     if( i != p->end() ){                // nqs e gjejme
         if( i->second == NULL )         // po te mos kete dege te tjera
         {                               // formojme degen e pare
             nyje * n = new nyje; // assert(n != null)
             n->insert(make_pair(fundi, (void *)NULL)); // lidhim fundin
             i->second = n;                             // lidhim fillimin
         }
         else     // nqs ka dege te tjera, shtojme nje me shume
             ((peme *)(i->second))->insert( make_pair(fundi, (void *)NULL));
             
         return true; // lidhja u be me sukses
     }
     
     // nqs nuk e gjetem fillimin ne kete peme, do kerkojme nyjet e tjera
     // duke thirrur vetvetet per cdo nyje te pemes (nen-peme)
     
     for( i = p->begin(); i != p->end(); i++ )
          if( (peme *)i->second != NULL )      
              if( hidh_ne_peme( (peme *)i->second, fillimi, fundi ) )     
                    return true;  // kthejme PO (true) nqs e gjejme fillim     
                    
     return false; // kthejme JO (false) nqs fillimi nuk gjendet ne peme
}

//**************************** KERKO PEMEN *******************************
peme * kerko( peme * const p, const string & varg, int & rezultati, int shkalla )
{
     peme::iterator i = p->find(varg); // kerkojme vargun ne pemen p
     
     if( i != p->end() )               // nqs e gjejme
     {
         rezultati = shkalla;  // = numri i degezimeve nga renja deri tek vargu
         return (peme *)i->second;  // kthejme degezimet e vargut (mund te mos kete)
     }
     
     nyje * n;
     
     shkalla++;
     
     // mqns nuk e gjetem ne kete nyje, shikojme nyjet e tjera (nen-pemet)
     for( i = p->begin(); i != p->end(); i++ )
     {
         if( i->second != NULL )
         {
             n = kerko( (peme *)i->second, varg, rezultati, shkalla );
             if( rezultati != 0 ) return n;
         }
     }
     
     return NULL;
}

// fund 

[josif]

// Me poshte eshte zgjidhja ime per sfiden:

#include <iostream>
#include <cstdlib>
using namespace std;

class Trungu{

private:
    struct Node{
        char e;
        Node** femije;
        int no_femije;

        Node(char element);
    };
    
    Node** nyjet;
    int no_nyjeve;

    Node* gjej(char e);
    int _kerko(Node* & _e1, char e2);
    int permireso(int distanca);

public:
    Trungu();
    ~Trungu();
    void shto(char e1, char e2);
    int  kerko(char e1, char e2);
};

Trungu::Node::Node(char element) : e(element){ femije= NULL; no_femije=0; }

Trungu::Trungu(){ nyjet= NULL; no_nyjeve= 0; }

Trungu::~Trungu(){    for(int i=0; i< no_nyjeve; i++) delete nyjet[i]; }

void Trungu::shto(char e1, char e2){

Node * _e1= NULL, * _e2= NULL;
_e1= gjej(e1); _e2= gjej(e2);

if(!_e1){
    _e1= new Node(e1);
    nyjet=(Node**)realloc(nyjet, sizeof(Node*) * (no_nyjeve + 1));
    nyjet[no_nyjeve]= _e1; no_nyjeve++;
    }
if(!_e2){
    _e2= new Node(e2);
    nyjet=(Node**)realloc(nyjet, sizeof(Node*) * (no_nyjeve + 1));
    nyjet[no_nyjeve]= _e2; no_nyjeve++;
    }

_e1->femije=(Node**)realloc(_e1->femije, sizeof(Node*) * (_e1->no_femije + 1));
_e1->femije[_e1->no_femije]= _e2; _e1->no_femije++;
}

Trungu::Node* Trungu::gjej(char e){
    for(int i=0; i<no_nyjeve; i++) if(nyjet[i]->e == e) return nyjet[i];
return NULL;
}

int Trungu::kerko(char e1, char e2){
    Node* _e1= gjej(e1);
return permireso(_kerko(_e1, e2));
}

int Trungu::permireso(int distanca){ return (distanca == -1) ? 0 : distanca; }

int Trungu::_kerko(Node* & _e1, char e2){
    if((_e1->e) == e2) return 0;
    for(int i=0; i< _e1->no_femije; i++){
        int x=0;
        if( (x= _kerko(_e1->femije[i], e2)) != -1)
            return 1 + x;
    }
return -1;
}