Salut toata lumea,

Ma chinuie rau problema asta de cateva zile, si din cate am citit nu este deloc una usoara (este de tipul NP-Hard deci nu poate fi rezolvata numai prin algoritmi clasici, deterministi - probabil are o complexitate asemanatoare cu a Ciclului Hamiltonian de Cost Minim).
Mi se da un graf orientat tare conex (oricare ar fi nodurile u, v, exista drum de la u la v) si mi se cere un subgraf, tot tare conex, care sa fie de cost minim (suma costurilor muchiilor sale sa fie minim), sau, altfel spus, sa nu existe alt subgraf tare conex de cost mai mic decat al acestuia.
Prin subgraf inteleg aceleasi noduri, mai putine muchii.

Deja m-am convins ca algoritmi gen APM, sau flux, nu au cu ce sa ma ajute.

Orice idei ajuta

Un ghid incepe sa fie publicat pentru evaluatorul meu aici: http://bitbucket.org/dan.sanduleac/eval2/wiki/Home
Evaluatorul meu e cel pe care se bazeaza cel facut de toni, al lui implementand in plus fata de al meu posibilitatea evaluarii de runde intregi (mai multi utilizatori, mai multe probleme de-odata, totul automat).
Momentan, in ghidul meu nu apar decat o introducere simpla si putine detalii de implementare, un "Cum se foloseste" urmand a fi scris in curand. Oricum, daca sunteti interesati, probabil veti folosi mai degraba interfata facuta de toni pentru ca ofera mai multe functii
In schimb, daca vreti sa stiti cum functioneaza ambele evaluatoare, ghidul acesta va va ajuta mult

[import contest.round_name.round_name_config]

Dar nu merge chiar asa, import dirA.dirB.fisier (pentru dirA/dirB/fisier.py). Eu zic ca ai cam 3 posibilitati:

• Incarci configul cu import, calea fiind relativa la directorul curent. Dar nu e o cale normala, pentru ca directoarele insiruite cand servesti calea sunt de fapt pachete python, deci de ex daca faci import contest.round_name.round_name_config ca sa importi contest/round_name/round_name_config.py, trebuie ca `contest` si `contest/round_name` sa fie pachete (adica fiecare director sa contina cate un __init__.py gol in el).
  Apropo, daca faci asa sau ca la metoda 2, nu poti avea round_name-config pt ca liniuta nu e admisa intr-un nume de variabila. (si instructiunea ar importa exact acel nume ca variabila).
  
  
• Ca la metoda 1, numai ca in loc ca directorul `contest` sa fie pachet, il adaugi la calea de importare a lui python. Dar il adaugi pe primul loc, ca nu cumva sa existe alt pachet cu numele rundei prin librariile standard.
  Exemplu:
  import sys
  sys.path.insert(0, 'contest')
  import test.test_config as config_runda # pt runda test
  del sys.path[0] # takes O(1) time
  # in pachet se vor afla variabilele rundei
  print config_runda.studs
  print config_runda.probs
  
  
• Sa incarci efectiv textul fisierului de configurare intr-o variabila, sa-l compilezi cu functia builtin compile, si apoi sa il executi cu keywordul `exec` (preferabil in cadrul unei clase, in constructor, dar in orice caz, apoi trebuie sa convertesti din variabilele locale definite in fisierul ala de config in variabile membre ale clasei, pt a putea fi accesate ulterior). Un cod care ar face asta (da, m-am chinuit degeaba la asta  ):
  class Round:
  
      __params__ = ['problems', 'students']
  
      def __validate_param(self, x):
          return x[0] in self.__params__
  
      def __init__(self, name):
          config_file = 'contest/%s/%s_config.py' % (name, name)
          exec compile(open(config_file).read(), '/dev/null', 'exec')
  
          self.__dict__.update(
              filter(self.__validate_param, locals().items())
          )
  

Eu de ex am ales sa folosesc metoda 2, dar in loc sa folosesc un fisier de configurare, daca tot am facut din directorul rundei un pachet, am mutat codul de configurare in __init__.py (de ex pt runda test, in contest/test/__init__.py) si asa poti face direct import test si cu asta basta

Intr-adevar, poate iti merge cum a zis bogdan, dar exemplul tau din py nu face acelasi lucru cu cel din C++, unde instantiezi un a() respectiv b() in constructor, si nu static.
Cred ca de fapt vreu sa faci

Cod:

class foo(models.Model):
    def __init__(self): # constructor
        self.a = models.ForeignKey(bar)

class bar(models.Model):
    def __init__(self):
        self.a = models.ForeignKey(foo)

foo()
bar()

in fiecare atribuire din __init__, foo sau bar sunt cautate local apoi global, adica apartinand modulei, unde vor fi gasite. Dar important e ca vor fi cautate de-abia la instantiere, cand clasele vor exista deja.

Nu pot pune sa evalueze un director intreg, pt ca astfel ar evalua toti concurentii, iar daca am userii de la 2 concursuri ar evalua tot.

da, dar poti sa separi de la bun inceput utilizatorii in directoare corespunzatoare concursului, care sa nu fie neaparat in dir unde e evalul tau, ci oriunde. Chiar si daca ar fi in acelasi dir, poti avea cv gen "stud/<round_name>/<username>/..." si aclo sa fie sursele.

@toni: Te-as sfatui sa schimbi in evalul tau folosirea fisierelor temporare cu nume unic
Ca idee, de ex daca doi useri lucreaza pe acelasi calculator cu evalul tau, unul dintre ei va crea fisierul temporar nush care, iar celalalt va primi frumos access denied pe acel fisier din momentul acela incolo. Asadar, foloseste `mktemp` ca sa creezi un fisier temporar cu nume random, si sterge-l dupa folosire.  (comanda iti returneaza numele fisierului generat)

Asa, si 2:
Dupa ce rulezi evalul tau, va modifica (adica suprascrie probabil) niste fisiere care nu au ce cauta acolo de la bun inceput (acolo, adica in repository). Dupa ce le modifica, daca vrei sa faci commit, le tragi dupa tine pe alea modificate degeaba.
Ma refer la

Cod:

M contest/test/allres.txt
M contest/test/scores.txt
M scripts/evalcore.pyc

nu stiu daca sunt si altele. In orice caz, scapa de pyc, ca ala se genereaza automat la prima folosire, si de txt-uri

Edit:
inca ceva, pentru runde mai bine nu zici decat numele problemelor, iar utilizatorii sa fie sub forma de foldere cu numele lor intr-un director de utilizatori, evaluatorul evaluand automat pe toti userii dintr-un folder dat, pe acele probleme. (mai flexibil asa)

Am impresia ca proiectele noastre (al meu si al lui toni) au cam stagnat. Cu toate astea, ambele erau functionale ultima data cand am verificat.
http://informatrix.ro/svn/eval/eval2/branches/testing-0.6 - cred ca uitasem sa actualizez linkul catre svn-ul meu, s-a schimbat.

Nu am dev-c++, dar uite:
daca tu tastezi caractere romanesti si in program ele apar diferit, gen ă apare ca 'a' cu sedilă, inseamna ca editorul lui dev-c++ nu vede fisierul sursa ca avand un encoding de tip unicode (adica utf-8, utf-16, whatever), ci il vede ca ASCII sau altceva. Pentru asta as cauta prin optiuni, prin meniuri, ceva gen file encoding, pe care sa-l setez pe utf-8.

Acuma, ca sa folosesti stringuri unicode din C++ mai mult ca sigur iti trebuie si tipuri speciale de siruri de caractere, ceva gen wchar_t (wide char something, am auzit si eu si el, nu am folosit), sau poate std::string, dar trebuie cautata documentatia de la stl pentru folosirea sirurilor unicode. In orice caz, nu va merge cu un sir de 'char'.

[guiapp]

Am scos versiunea 0.65 cu niste modificari mari la structura programului si cateva bugfixuri. De asemenea am modificat guiapp sa foloseasca output generat de consoleapp pentru fereastra de 'log' a sa. Well, pe cine intereseaza  

Aceasta versiune este inca netestata, si am creat un branch special pt ea, in general pentru ultima versiune a programului care este cat de cat stabila, 'testing'. Puteti s-o descarcati prin svn:

svn co http://informatrix.ro/svn/eval/eval2/branches/testing-0.6 eval2-testing

CHANGELOG-ul e in directorul aplicatiei, sau puteti sa-l accesati direct la adresa aceasta

Apropo, devil, daca mai vrei sa dezvolti in java un GUI, ultimul release 'stable' nu va merge cu Jython. Merge in schimb versiunea 0.65 de sub testing

Merge sa-i faci o interfata swing, daca rulezi evalul din Jython din cadrul lui java, in loc sa folosesti CPython care e "default".

In legatura cu lipsa fisierelor, nu stiu ce sa zic ca s-a intamplat, daca intru din browser pe acel link vad toate fisierele prezente.
config.py trebuie sa contina doar linia:
TestDBRoot = 'o cale pentru directorul de teste'
pentru ca evalul sa functioneze. Dar mi se pare ciudat ca nu gasesti fisierele, nu iti apar cand intri aici ?
http://informatrix.ro/svn/eval2/tags/stable-0.6/

Tot de la Harvard, computer science 50, dar din anul precedent: http://cs50.tv/

[generala]

Wow, sunt mirat ca din ce am zis a iesit un intreg flame war. Nu am citit definitia de pe wiki a algoritmului inainte sa postez, insa nu mi se pare ca am gresit in ce am zis.
Here's why:
Cand m-am referit la algoritm (si implicit la algoritmica) ma refeream la un procedeu, o idee, care rezolva o problema generala, deci care este utilizabil in situatii variate (eu unul asa il vad). Nu am auzit pe nimeni sa se refere la cazul trivial de a afisa "Hello world!" pe ecran, drept "algoritmul de implementare a primului tau program intr-un anumit limbaj".
Algoritmul lui Dijkstra este de fapt implementarea (sau optimizarea) lui Dijkstra a "algoritmului care gaseste cea mai mica distanta de la un nod la altele", iar acest algoritm are aplicatii in mai multe zone. Cel mai simplu exemplu ar fi Google Maps, care il utilizeaza ca sa gaseasca cel mai scurt drum intre doua orase, sau GPS-ul. Insa dupa cum stim, sunt tone de probleme de informatica care nu cer explicit "cea mai mica distanta de la un nod la altul", dar a caror rezolvare necesita folosirea acestui algoritm. Un exemplu este binecunoscutul algoritm de determinare a fluxului maxim de cost minim.
All in all, ma bucur ca am zis ce am zis, ca altfel cineva ar putea crede ca utilizez si algoritmul de prajit cartofi copti in aplicatia mea.

[guiapp.py]

Am actualizat primul mesaj pentru a reflecta noua versiune, 0.64 rc1.
Mie mi se pare stabila, dar nu am avut posibilitatea de a o testa foarte mult.
Daca gasiti buguri, va rog raportati

Aceasta versiune introduce cateva adaugiri si schimbari nu neaparat majore.
In schimb, a fost reorganizata masiv, in materie de cod, fata de 0.62, pentru a fi mai usor de dezolvat si mai usor de refolosit intr-un proiect mai amplu.
0.64 este backwards compatible cu 0.62 in ceea ce priveste parametrii pe care ii primeste si fisierul de configurare, insa afisarea a fost modificata pentru a arata mai prezentabil.
Una dintre schimbarile importante a fost separarea codului de evaluare de codul de "interfata" de consola. De aici a reiesit in mod natural reorganizarea aplicatiei pe mai multe fisiere. Prin aceasta, am putut apoi cu usurinta incepe dezvoltarea unei interfete grafice folosind GTK si Python.
(puteti sa o incercati prin rularea guiapp.py)

[Folosire]

Am postat in pagina mea "nightly buildul" noii versiuni care este "currently in development", pt toni.
Pentru ca am facut multe modificari si restructurari programului, care nu au fost inca finalizate (sau testate), acesta este inca o pre-versiune a versiunii 0.64 (hence the -13 de la revizia 13).
Programul este backwards compatible cu 0.62.
Una din functiile noi: afiseaza borderoul dupa cum mi-a cerut toni (hopefully).
Folosire: consoleapp.py a inlocuit fostul eval.py. Rulati consoleapp.py.
Pentru interfata de consola este nevoie de consoleapp.py si evalcore.py.

Nu e un bug. Afisarea scorului pe teste are loc doar cand in directorul de teste exista tests.txt, care indica exact cate puncte are fiecare test, ca sa se stie exact de unde vine punctajul. Altfel, scorul pe test este pur si simplu 100/nr_teste. tests.txt contine linii de tipul "i j", i fiind33*88 nr testului iar j punctele pt acel test.

Okay, i-am facut checkout. Nu am avut timp sa vad daca merge though

Este un alt fel de programare. Nu e algoritmica, e "application development". In teorie un evaluator mai rudimentar se face rapid. Asa am inceput si eu, dar dupa aceea am tot adaugat features si am rezolvat diverse probleme ce tot apareau si ma incomodau. Am vazut si ca trebuia sa-l adaptez ca sa fie cat mai general, mai flexibil. Nu poti sa zici ca "ia mult", ci mai degraba ca este un proiect in continua dezvoltare, ca multe altele de acest gen.
Evaluatorul.. l-am inceput in alt limbaj cam acum 2 (3?) ani, l-am portat in python (pt ca era mult mai flexibil si mai productiv si imi inlatura anumite constrangeri) anul trecut, si l-am mai tot imbunatatit de cand l-am scris prima oara in python. Desi am lucrat la el doar din cand in cand, s-au adunat poate 1-2 saptamani de lucru mai consistent. Fiindca a fost folosit si de diriginta mea, si de mine, am avut si ocazia de a gasi mai multe buguri, pe langa faptul ca am primit si sugestii de imbunatatire, si astfel am reusit sa il aduc intr-o stare destul de stabila si user-friendly, zic eu.

Well, multumesc pt incurajare

Pai, cand am extras arhiva nu era Better safe than sorry, poate il sterge cineva si apoi se mira de ce i-a disparut eval-ul
Bafta multa la lot!!! Il voi da si eu la ora 2

[0.5]

Gata! Am facut schimbarile.
Acestea sunt modificarile, care sunt reflectate si in `eval.py --help`:
[Changelog de la ver. 0.5 la 0.6]
FEATURES:
Doi noi parametri:

-q	afiseaza doar scorul in stdout
-O fisier	afiseaza doar scorul in stdout + scrie borderoul (fara culori) in acel fisier

BUGFIXES:
 - elimina culorile daca stdout nu este un tty (adica daca redirectezi sau folosesti un pipe)

Sa-mi zici cum merge
----------------------------------------------------------------------------------------
Apropo eval-ul tau are o mica buba. Cand il rulez prima data incearca sa stearga tot (dar i-au scapat directoarele, ca rm-ul a fost chemat fara -r ) din propriul sau director.
Asta se intampla la clear-all.sh, pt ca faci `cd work` si daca directorul work nu exista, va ajunge sa dea eroare si sa stearga tot din directorul curent...
fixed:

Cod:

##################################################################################################################
#            part of grader scripts, please don't modify it unless you know what you are doing                   #
#================================================================================================================#

# asserts :
#               pwd : eval

if [ -d work ]; then
    rm -rf work/*
fi

Am o intrebare... cum se sorteaza un vector <pair <int,int> > folosind sort din algorithm crescator dupa prima componenta, iar in caz de egalitate descrescator dupa a doua componenta, de exemplu 

Mai simplu: ai

Cod:

vector<pair<int, int> > A;
// adaugi elementele in felul urmator: daca vrei sa inserezi perechea (x, y), adaugi cu A.push_back( make_pair(x, -y) )
// apoi
sort(A.begin(), A.end());
//apoi cand accesezi elementele din vector, folosesti A[i].first si  -A[i].second pentru a obtine cele doua campuri.

Da, si eu am patit asta cand am upgradat la Ubuntu 9.04 care vine de asemenea cu Python 2.6. Foloseam o librarie veche, am schimbat de ieri acea bucata si am pus noul script pe pagina contului meu, dar am uitat sa mentionez.
Go get it (poate ar trebui sa fac un fel de versioning, ca sa se reflecte schimbarile)

Ne-am sincronizat, ca sa vezi.

[raspuns la ultimul post]
Ma bucur ca e chiar ce-ti trebuia Si da, as putea sa fac cu return code, sau sa implementez -q, care afiseaza doar scorul in stdout si iese (mi se par la fel de usor de parsat ambele alternative).
O sa ma apuc sa modific aceste chestii cand apuc. Apropo, am pus o versiune noua a evalului, erau cateva linii cu buguri minore pe la verif, get your new copy off my account page

Edit :: acuma am vazut ca ai atasat eval-ul, o sa-l incerc cu prima ocazie. Chiar seamana cu cel al lui M Patrascu, nu l-am folosit pe acela niciodata dar recunosc "interfata".

[la postul precedent]

Pai uite cum sta treaba cu verif (probabil am facut eu helpul cam neclar):

Programul verificator va primi trei parametri din partea lui eval.py, si anume cele trei fisiere  (in-ul out-ul concurentului si (optional) ok-ul). El poate sau nu sa le foloseasca, dar nu poate cauta aceste fisiere in directorul curent dupa numele lor pur si simplu.
Parametri: VERIF fisier.in fisier.out fisier.ok
                        Returneaza: "mesaj\n(procent punctaj din max)"
                        Exemplu: Gresit\n0 ; sau: OK\n100
Apropo, la "procent punctaj din max" cred ca ai inteles despre ce e vorba, dar ca sa nu fiu neclar, ideea era numarul este cat% din cat ar lua testul acela (adica, in principiu, 100puncte / numarul de teste) ii acorzi (si nu cat% din punctajul total pe problema). Pentru 10 teste, 100 acolo inseamna 10 puncte la scorul final care e maxim 100p.

Asa.. Scriptul tau din bash zice ca nu gaseste `adun.ok` pentru ca nu se afla in directorul curent. Directorul din care e rulat verif-ul este un director temporar. Acolo se afla in-ul copiat pentru testul curent, out-ul returnat de sursa evaluata, si executabilul evaluat. Fisierul de ok insa nu e copiat acolo de evalul meu, este in directorul de teste.
De aceea pasez acei parametri: ai sa vezi ca daca printezi $@ din bash vor aparea (inlocuieste si tu ? cu orice nr de test):

Cod:

/home/toni/Desktop/eval_alpha/tests/adun/?-adun.in /tmp/UNNUMEDUBIOS/adun.out /home/toni/Desktop/eval_alpha/tests/adun/?-adun.ok

Acelea sunt fisierele cu care vrei sa lucrezi, care iti sunt date cu cale completa.
Mesajul 'Wrong answer in: adun.out' (si scorul) este doar preluat din out-ul verif-ului de catre eval.py si afisat acolo.

Pare interesant ce zici. Dar nu stiu de ce vrei sa te chinui in bash cu asta, este totusi un limbaj destul de limitat (desi.. evaluatorul meu a fost initial scris in bash, si apoi adaptat + re-codat in python).
Chiar sunt curios ce interfata faci. In orice caz, va fi amuzant ca eval-ul tau se va folosi de al meu care se foloseste de jrun Este un exemplu perfect de a crea un proiect pe baza codului modular, peste care se poate construi mai departe.

Singura intrebare e.. ce planuri ai pentru un evaluator care sa evalueze runde intregi? Sa-l lansezi ca proiect Open Source sau sa-l propui asociatiei infoarena in schimbul eval-ului in PHP pe care-l folosesc ei acuma?

Apropo, daca parsezi codul evaluatorului meu din al tau, poate ar fi mai bine sa introduc niste cod care sa omita culorile in output daca acesta este redirectat, ca nu prea isi au farmecul decat in terminal (stiu ca se putea cumva detecta asta), sau eventual niste optiuni gen -q, de la quiet, pentru a afisa doar scorul, borderoul fiind afisabil printr-un alt nou flag `-w fisier_borderou`. Spune-mi cum mai sta treaba si daca pot sa te ajut cumva.

PS: ruby arata dubios, prefer python gets.chomp.to_i parca e nefiresc, mai degraba un int(f.readline().trim())

[eval.py --help]

M-am uitat. Merge destul de bine, singura chestie care nu mi-a mers, a fost cand am incercat sa fac un program pentru a + b (in ruby). Mi-am luat Blocked System Call de la interpreter. Ar trebui reglata treaba asta.

[LE] Ar merge sa poti seta din linia de comanda timpul si memoria, preferabil ceva de genul urmator :

Cod:

./eval.py prob 100 16384

Aa, pai uite-te in eval.py --help.
Ca zice acolo asa:

Cod:

  -t TIME, --time=TIME  time limit in milisecunde
  -m MEM, --memory=MEM  limita memorie, kb

in which case, folosesti:

Cod:

./eval.py prob -t 100 -m 16384

(Apropo, evaluatorul, daca nu-i precizezi aceste valori, le foloseste ca default exact pe cele scrise mai sus.)

Blocked System Call e vina lui jrun, care are grija sa nu iti permita sa folosesti metode de sistem (ex. fork) in codul tau. Asta este pentru siguranta serverului evaluator (infoarena) si pentru ca nu ar trebui sa ai nevoie (sau voie) sa folosesti acele "system calls" cand rezolvi probleme de informatica.

Trebuie sa-mi zici cum ai incercat sa rulezi programul din ruby, si cum arata acesta.
Eu de exemplu am reusit sa evaluez un program facut in python. Pur si simplu l-am facut executabil (chmod +x) si i-am adaugat #!/usr/bin/python in header. And it worked. No blocked system calls of any kind.
I'm wondering why it didn't with Ruby...

Apropo, limbajele "interpreted" (Python, Ruby, PHP, ...) au un mare deficit in a putea executa rapid cod pentru tipul de probleme "de informatica" (care tin de algoritmica) care se gasesc la olimpiade, concursuri si pe infoarena, pentru ca au un mare overhead datorita obiectelor folosite pretutindeni (desi.. si aceste limbaje pot refolosi cod compilat sub forma de librarii sau pot imbrica cod C++ direct in sursa lor - Python cel putin sigur poate).  Asa ca nu prea vad cum ar putea fi eficiente si pentru alte aplicatii mai greoaie, gen recursivitati, chestii cu vectori multi, arbori si alte computatii cpu-intensive.
Aici se poate vedea ca atat Python cat si Python 3.0 sunt way behind C++ pentru acest tip de operatii. Pentru arbori binari de ex, pot fi de 300 de ori mai lenti.
Java, de ex, is doing a much better job, dar fiindca si el ruleaza intr-o masina virtuala, are de asemenea multe zone in care este si de 10 ori mai lent decat C/C++.
Well, the rant's gotta end somewhere.

Am uploadat pe serverul infoarena fisierele, scuze pentru intarzierea de a face acest lucru.
In curând voi face si un script care va automatiza instalarea evaluatorului si lui jrun, pentru mai putina bătaie de cap.

@toni2007: ai încercat evaluator-ul pe care l-am postat eu?

@Laurentiu: Start a different thread, please - [moderator] Done