Un nou tip de probleme (12 sunt deja postate aici)

[•madflame]

Iata ce propun: un nou tip de probleme - sau mai degraba probleme usoare dar care, din pricina unor restrictii devin interesante si evident mai grele.
Spre exemplu: "sorteaza un vector fara operatii de comparatii", "calculeaza log2(N) sau sin(N) fara sa folosesti functii prestabilite de limbaj", "umple o matrice dupa o regula fara sa folosesti for-uri sau while-uri (repeaturi) sau fara if-uri"...
Problemele acestea pun in principiu accentul pe complexitate memorie, sau complexitate numar de instructiuni, si/sau obliga programatorul sa gaseasca o solutie alternativa, il obliga sa-si foloseasca inventivitatea (sortarea fara comparatii este un exemplu).
Nu v-ati minunat oare cand ati auzit pentru prima data ca 2 variabile pot fi interschimbate fara una auxiliara? Problemele de acet tip nu prea au aplicabilitate (poate decat daca programati pe arhitecturi ciudate si crippled rau), dar sunt interesante daca sunt luate ca provocari, ca puzzleuri.
O parte buna a problemelor de genu este ca sunt mai usor de conceput/propus, sunt, dupa mine, mai interesante, si nu implica notiuni grele de genu programare dinamica. Sunt probleme obisnuite la care nu se cer performante, ci solutii alternative sub niste restrictii. (solutii alternative - creative/latheral thinking)
10 probleme de genu pot scrie, si daca fiecare din echipa infoarena mai coace cate 10...

Punerea in practica:
Am realizat deja evaluatorul care verifica sursele inainte ca acestea sa fie compilate si evaluate dupa evaluatorul deja existent.
Programul este scris in Pascal (stringurile mi se par hellish in c/c++)
Primeste ca parametru numele sursei de verificat (sursa.pas sursa.cpp)
Deschide fisierul de restrictii (sursa.phr) (... il si inchide)
In caz ca sursa.pas/cpp indeplineste restrictiile dorite returneaza exitcode:0 altfel 1
De aici incolo ar trebui sa plece catre evaluatorul vostru deja existent.

Sursa o dau oricarui dev infoarena care mi-o cere.
E-mail de contact (pentru orice eventualiatate): [email protected]; YMSG: madflame991

[•madflame]

Iata probleme despre care discutam mai devreme.
Martinel s-a angajat mai nou la o companie de electronice. Acesta are de programat fel de   electronice care nu sunt prea avansate. Unele au microprocesoare care nu inteleg operatii matematice, altele nu isi permit sa ruleze mai mult de 1 ciclu, altele nu stiu operatii conditionale. Ajutati-l pe Martinel sa rezolve urmatoarele probleme:

1) Sa se verifice daca un numar este palindrom fara sa se utilizeze notiunea de vector.
2) Sa se calculeze partea intreaga a lui Log2(N) (logaritm in baza doi din N) fara a folosi functia predefinita de limbaj (log, ln...)
3) Sa se creeze o "matrice tabla de sah" (01) NxN fara foruri, whileuri, repeaturi. Se permite un singur If.
Ex: pentru N = 5
01010
10101
01010
10101
01010

4) Sa se creeze o "matrice spirala" NxM cu un singur ciclu (for, while, repeat) si un singur if (se va porni din exterior spre interior din coltul stanga-sus in sensul invers acelor de ceasornic)
Ex: pentru N = 5, M = 4
1|14|13|12
2|15|20|11
3|16|19|10
4|17|18| 9
5| 6| 7| 8

5) Sa se calculeze Radical(N) fara a se folosi Sqrt(), Pow() (Se cere o precizie de 2 zecimale, neaproximat)
6) Sa se genereze primiele N patrate perfecte fara a se folosi Sqr, Pow, operatorul * (sau alta instructiune ASM echivalenta: MUL)
7) Sa se sorteze un vector fara a folosi operatii de comparare (vezi sortarea prin numarare de care pomenea Martinel)
Sa se calculeze Sin(N) fara a se folosi vreo functie trigonometrica existanta in limbaj (Se cere o precizie de 2 zecimale, neaproximat)
9) Se cere sa se calculeze CMMDC a doua numere fara a se folosi / % mod div
10) Sa se transforme un numar N din baza 10 in baza 2 fara a se folosi operatorii %, mod, /, div (adunarea ar trebui sa fie singura operatie necesara)
11) Sa se calculeze al N-lea numar alcatuit din cifrele 1 si 0 fara sa se foloseasca vreo functie (procedura), sau vreun vector
12) Sa se calculeze cate numere in baza N (3<=N<=16) mai mici decat M dat (in baza 10) au cifrele distincte 2 cate 2. Nu se vor folosi functii (sau proceduri).

[•miculprogramator]

Unde pot posta rezultatele, sau cui i le pot trimite?

Nu pot coda in C++ ? Stiu si Pascal, dar mi-ar veni mai usor in Cpp

[•madflame]

Poti coda in C++ fara probleme... (specificasem ca sursa evaluatorului este scrisa in pascal)
Unde poti verifica rezultatele? Eu am scris evaluatorul, am postat si aceste probleme... astept decizia echipei infoarena - daca doresc/e posibila sau nu introducerea noului tip de probleme.
Apreciez interesul. Am postat aceste probleme ca un fel de preview...

[•gabor_oliviu1991]

E super ok ideea. Te sustin Adi 

[•toni2007]

Cred ca este destul de complicat de implementat sa folosesti verificatorul tau inainte de compilare. O metoda mai simpla, ar fi sa fie lasata sursa in directorul in care este rulat binarul, iar evaluatorul tau sa fie introdus in loc de verificator, parsand sursa si verificand. Totusi, eu sunt de parere ca astfel de probleme nu ating scopul acestui site (de a pregati elevii pentru olimpiada). Un loc unde se pot implementa probleme de acest tip ar fi SPOJ-ul, unde exista sectiune de probleme intitulata 'challenge', unde este un evaluator mult mai flexibil, in care user-ul isi poate face chiar si evaluatorul pentru acea problema, scutind astfel echipa site-ului de un efort foarte mare.

[•miculprogramator]

As avea o intrebare, la problema 3.
Pot pune ceva de genul:

if (...) ....
   else if (....)....
      else if(...) ....

?
Asta e chiar faina. Cred ca ma tine pana dimineata...

[•gabor_oliviu1991]

Daca zice ca se permite doar un IF, si else IF tot una e. Tot la 3, se pot folosi subprograme/proceduri? Hint: uitate la paritatiile lui i si j in matrice 

[•miculprogramator]

thanks for the hint! mai bine spus la paritatea unei relatii dintre i si j.
acum ramane doar treaba cu for-urile...

[•toni2007]

Recursivitate .

[•miculprogramator]

Nu stiu...

[•madflame]

Chiar ma bucur pentru entuziasmul vostru.

@miculprogramator
Solutiile tale pot fi trimise spre evaluare tot pe infoarena DACA mai lucrez putin de tot la pharser si DACA sunt deacord cei de sus cu acest tip de concurs. Ai putintica rabadare sa vedem ce iese...

Problema 3: Un IF e un IF, nu 10; e corecta indicatia data de gaboru, numai ca if-ul acela nu trebuie irosit la verificarea paritatii... nu este permit nici un fel de for,while,repeat, dar sunt permise subprograme (acolo intervine si if-ul)

Catre Dl. Pripoae
De implementat verificatorul inainte de compilare... din cate cunosc procesu sta asa: serverul sitului apeleaza un script of some sort care suna la evaluatorul meu cu parametru "numele fisierului" si asteapta exitcode-ul ... daca acesta este 0 paseaaza sursa la compilator si mai departe la evaluatorul infoarena.
Nu ating scopul acestui site? Probabil (mie mi se par "puzzleuri programatoricesti"); Nu cred ca strica daca se adauga si ele, amaratele. Am incercat sa imbogatesc infoarena. Eu unul, nu ma antrenez pentru olimpiade, si tot urmaresc situl, e printre putinele forumuri programatoricesti romanesti.

[•miculprogramator]

In scurt timp o sa invat si eu subprograme, voi revenii la aceasta problema.Pana atunci ma concentrez pe celelalte.
Iti urez spor la treaba cu evaluatorul, rabdare promit ca o sa am!

[•toni2007]

De implementat verificatorul inainte de compilare... din cate cunosc procesu sta asa: serverul sitului apeleaza un script of some sort care suna la evaluatorul meu cu parametru "numele fisierului" si asteapta exitcode-ul ... daca acesta este 0 paseaaza sursa la compilator si mai departe la evaluatorul infoarena.

Cam asa e. Doar ca trebuie umblat si pe la mesajele din monitor, cand nu scrii evaluatorul bine la o problema, trebuia modificata pagina de creare a unei probleme, etc. Practic, trebuie un nou tip de problema. Desi se lucreaza de ceva timp, n-au fost terminate inca problemele interactive si cele de output-only. Poti scrie un IAP pe tema asta, in care sa descrii pe larg cam ce ar face acest tip de probleme.

[•devilkind]

Nu cred ca e neaparat nevoie de un nou tip de problema. M-am si eu acuma putin pe evaluatorul infoarena sa vad ce s-ar putea face, si cred ca iesa mai usor. S-ar putea un nou parametru pe fiecare task cu denumirea verificatorului, daca e vid atunci nu exista. Daca exista un parser, atunci il rulam si vedem ce returneaza. Daca zice ca nu e ok, returnam ca nu respecta conditiile problemei, daca a trecut atunci problema se evalueaza in continuare ca oricare alta. Nu cred ca e asa greu de implementat aceasta optiune. Nu sunt insa sigur pe cat de usor se implementeaza un verificator dinasta. Dar daca acesta ar fi 100% corect facut si nu ar putea exista smenuri prin care sa se poata trece de el, nu ar fi tocmai imposibil acest tip de probleme.

[•toni2007]

Asa m-am gandit si eu, doar ca nu stiu in ce fel sunt gestionate mesajele de genul 'SIGSEGV in verif', 'lipseste atasament grader_ceva.cpp la atasamente', etc. Totusi, in momentul in care este rulat verificatorul, exista sursa in director ? Ma refer la verificatorul normal de pana acum. Daca deja este, atunci nu mai este nevoie practic de nici o modificare .

[•bogdan2412]

Mie nu-mi pare usor de facut un parser pentru asa ceva, se gasesc o multime de moduri de a baga defineuri dubioase astfel incat sa nu fie evident ca cineva foloseste "for" de exemplu. (http://en.wikipedia.org/wiki/International_Obfuscated_C_Code_Contest) Trebuie parsat outputul dupa ce s-a rulat preprocesorul in C/C++ si nu stiu ce probleme mai apar dup-aia.

Sunt cam putine probleme care chiar ar beneficia de asa ceva dupa parerea mea si unele din problemele care le-ai propus nu te invata sa gandesti metode alternative de a face ceva, ci doar e o diferenta intre cum scrii cod: la problema 3 afisatul matricii folosind recursivitate in loc de for-uri nu mi se pare ca e o incercare intelectuala sau la problema 12 faptul ca nu poti folosi functii... Programul tau face acelasi lucru practic doar e scris altfel. Sunt si probleme ok: 6 de exemplu

[•Cosmin]

Alte doua probleme de pe stackoverflow.com

Sa se scrie o functie f in C++ astfel ca f(f(x)) == -x unde x este orice long pe 32 de biti.

Sa se scrie un program in C++ ce sa numere de la un parametru de intrare pana la 1, fara a folosi instructiuni de scadere sau inversare de stringuri.
Un program bun ar face urmatoarele:
apelat: solutie.exe 5
printeaza: 5 4 3 2 1

[•devilkind]

@toni: nu ai nevoie de sursa in directorul in care faci evaluarea. Tu nu ai nevoie sa testezi la fiecare pas daca sursa e ok sau nu, o verifici inainte de compilare.

[•toni2007]

@toni: nu ai nevoie de sursa in directorul in care faci evaluarea. Tu nu ai nevoie sa testezi la fiecare pas daca sursa e ok sau nu, o verifici inainte de compilare.

Da, m-am gandit gresit, doar ca asa cred ca ar fi folosit interfata deja existenta, dar nu prea merge, in primul rand deoarece sursa poate fi modificata de executabil. La compilare ar merge in schimb. Eram cam obosit aseara cand am scris postul.

[•madflame]

"Mie nu-mi pare usor de facut un parser pentru asa ceva" ...  suna generic
Explicatie pe larg a pharserului:
1) Se apeleaza pharserul cu parametru "numefis.pas/cpp"
2) Se citesc din "numefis.phr" (deja existent pe srv) ce cuvinte se admit de cate ori si ce caractere sunt nepermise... explic de indata
3) Se citeste sursa linie cu linie, se pun "cuvintele" intr-un vector; ca separatori se iau ' ' si '('
4) Se cauta daca cuvintele restrictionate se afla in vectorul de cuvinte al liniei curente si se incrementeaza numarul lor de aparitii; cand numarul de aparitii se depaseste se termina executia programului cu exitcode:1
Odata cu separarea cuvintelor se cauta si existenta caracterelor nepermise: ? daca avem restrictii la If si suntem in c++ sau [ daca avem restrictii legate de vectori; idem pentru operatii matematice de 1 caracter
5) pentru sursele Pascal se poate restrictiona recursivitatea daca restrictionam 'function' sau 'procedure' (problema apare la c++) Pentru C++ se cauta prima ocurenta a caracterului '(' in sursa - daca acetsa este precedat de ' main' atunci totu e ok

Exemplu: intre acolade sunt comentarii...
Daca dorim sa folosim un singur ciclu (for, while, repeat) scriem asa:
1 3 {este permisa o aparitie a oricarui dintre cele 3 urmatoare}
for
while
repeat

toate cele 3 sunt delimitate in pascal de spatii, in c++ dupa for si while se pune '('

Restrictionarea if-urilor
? {caracter nepermis}
2 1 {se admite de 2 ori cel 1 keyword de mai jos}
if

Daca se doreste restricionarea arrayurilor... se pomeneste '[' ca fiind caracter nepermis, simplu
"dar in pascal trebuiesc restrictionate si fUnction si FUnction si toate variantele" - raspuns: se trec pe downcase (ca la C)
Cat despre acele defineuri dubioase... se restrictioneaza '#define' si gata

"simplu ca placinta"!

[•sima_cotizo]

Cat despre acele defineuri dubioase... se restrictioneaza '#define' si gata

Deja nu imi mai place modul tau simplu de abordare a problemei. Daca vreau sa fac #define MAX 150 in loc de const int MAX=150, nu poti sa impui sa fac ca tine... Sunt sigur ca realizarea unui astfel de program care sa verifice anumite constrangeri este posibila, dar mult mai complicata decat o faci tu sa para (pentru a fi ceva solid, serios, nu un "facem asa ca tot aia e")... Si mai ales, nu poti sti niciodata ce smenuri dubioase (si nepermise) gaseste un concurent.

[•madflame]

... altfel se complica pharserul... asa poate sa obiecteze oricine ca vrea inline assembly.
interzicerea defineului e o solutie SIMPLA pe care am gasito, si daca exista alternative atunci... defapt daca vrei sa declari o constanta numerica "const int max=10" este foarte ok

[•devilkind]

Nu e chiar asa, adica nici mie nu prea imi convine sa nu pot folosi define-uri. De obicei le folosesc la lucru STL, fara ele mi se pare ca codul ar deveni foarte urat si nu mi-ar placea. Ai putea sa tii minte define-urile si cand dai de un cuvant sa vezi unde ajunge el dupa define-uri, insa pare cam complicat.

[•bogdan2412]

E usor de facut un parser simplist, doar ca se gasesc destule modalitati de a trece peste limitarile de genu nu ai voie sa folosesti caracterul "x".

Nu merge sa restrictionezi folosirea vectorilor doar interzicand caracterul [:

Cod:

#include <cstdio>
#include <cstdlib>

using namespace std;

int main()
{
    int* a = (int *)calloc(10, sizeof(int *));
    for (int i = 0; i < 10; i++) {
        *(a + i) = i;
    }

    for (int i = 0; i < 10; i++) {
        printf("%d\n", *(a + i));
    }

    return 0;
}

Ceva asemanator poti face si cu vectori din STL.

Ca sa faci un verificator calumea trebuie sa implementezi tu mare parte din ce face si un compilator Problema cu define-urile cred ca se rezolva verificand outputul produs de preprocesor (cpp in GCC).