Posts Tagged ‘Probleme interesante’
Euristici
(Meditatio XXXIV)
The positive heuristic of the programme saves the scientist
from becoming confused by the ocean of anomalies.
Recent, s-a terminat primul concurs al lui Al Zimmermann la care am participat și eu. Deși nu mai trimit soluții la celalt concurs rămas în funcțiune, ceea ce am aflat ieri citind mailurile se potrivește în ambele locuri și nu numai. Practic, e vorba de cazurile în care euristica nu e prea bună.
Uniformitate
Să zicem că avem de construit niște întrebări pentru un test. Întrebările au anumite grade de dificultate, să zicem că sunt clasificate în x categorii. Avem de asemenea y surse de unde trebuie să extragem întrebările. Problema este următoarea: Cum ne dăm seama de cât de uniforme sunt întrebările distruite în domeniul surselor și al dificultăților?
Septembrie
Nu doar o enunțare a chestiilor care se petrec acum ci ceva mai mult.
Meditatio IV
(Falling into the Void*)
An idea can turn to dust or magic
Mai ţineţi minte ultima întrebare de la ultimul articol? “Concurăm cu persoane care ştiu mult mai multe ca noi sau ne băgăm la un Dota?” Acum o pot extinde la “Are rost să ne testăm forţele de tineri în diverse competiţii sau ne distrăm cât de mult putem şi lăsăm rafinarea skillurilor pentru viitor?“
Haskell versus C
Să zicem că mă plicitseam într-o zi şi am dat peste un concurs interesant în timp ce citeam feed-ul asociat reddit. Deşi problema propusă este destul de dificilă, am zis să-mi testez şi eu forţele puţin. Read the rest of this entry »
Final de concurs
Concursul de programare s-a terminat.
Nu vă grăbiți,nu s-a terminat integral. Doar problemele ușoare s-au terminat.
Problemele 3, 5, 6, 7 si 8 au rămas si vor rămâne multă vreme în așteptare de soluții.
Rezultate parțiale aveți aici. Felicitări tuturor participanților și multă baftă în spargerea recordurilor cu celelalte probleme. Practic, cine face una din cele 5 probleme rămasa (8 mai ales) își asigură un loc de frunte în ierarhie.
Multă baftă în continuare și mult spor.
Tower Defence
A trecut mult de la ultima problemă. Nu prea am avut timp să construiesc un fișier de input și am decis să vă dau frâu liber imaginației.
Problema de azi este una simplă ca enunț, complicată foarte tare ca rezolvare.
Se dă jocul Astral Tower Defence. Se cere un program capabil de a anunța o strategie de joc astfel încât să se atingă un nivel cât mai mare.
Puteți trimite un program care funcționează doar pe una din hărți sau pe toate (caz în care se va realiza o medie a performanțelor). Fișierul readme trebuie să descrie modul prin care prelucrați datele nivelului precum și orice alte detalii interesante.
Scorul este 1000/numărul valului atins.
Total puncte problemă: 1000.
Conform regulamentului, concursul a ajuns la final. În această săptămână se vor accepta ultimele submisii la problemele 1, 2, 3 și 4. Celelalte probleme vor avea timp de lucru mai lung.
Multă baftă.
Totalled Recall
Voi sintetiza aici aspectele importante aflate pe ordinea zilei în această parte de Univers.
În primul rând, nu uitați că puteți descărca noua versiune de Ubutnu via un sistem de torenți din cadrul ACS, așa cum am mai anunțat și aici și mai în spate.
Continui cu a remarca că există pe glob peste 6 miliarde de oameni. O mulțime de o cardinalitate imensă. Din ei, unii mint pentru a păstra aceleași aparențe și pe ziua de mâine, alții abia azi descoperă adevărul, alții știu adevărul dar nu vor să acționeze conform lui. Mulțimile nu sunt neapărat disjuncte. Cel mai important este că peste tot există un moment în care este nevoie doar de o singură persoană.
Practic, am ajuns acum să reiterez ce a spus Albert pe blog-ul lui abia creat. De la primul articol de acolo se trage paragraful anterior. De fapt, și de la un final de film (nu știu filmul, știu doar finalul). Oricum, citind ce a fost scris acolo mi-am amintit de o discuție cu tct și de diferențele între 42 și 52. Topic închis.
Ca alte chestii la ordinea zilei, ar mai fi de trecut aici de verificat și corectat câteva teme, de pregătit câteva laboratoare și lucrări, de redactat diverse teme și de codat diverse chestii. De asemenea, a venit momentul să termin experimentul curent și să finalizez concursul de programare din acest an. Deși cred că imediat după începerea etapei de finalizare al lui voi începe un altul, ceva mai dificil. Să nu uităm de pus bazele viitoarelor proiecte rsoc din această vară.
Și dacă tot am ajuns la proiectele rsoc, trebuie să vă reamintesc că data de 1 Mai va fi data în care noua echipă de hfall se va forma și va începe ultima etapă în dezvoltarea acestui proiect. Citiți anunțul complet aici.
Păcat că săptămâna asta de vacanță mai are, pentru mine, dar 20 de ore (plus cele de somn). Sunt multe de făcut într-un timp puțin dar cred că am găsit entuziasmul necesar să fac multe.
The door opens.
The Edges meet.
Step through and you find yourself lost.
Stay where you are and you go nowhere.
Prefer să mă rătăcesc undeva prin jungla 42 decât să mai stau prea mult la intersecția curentă între cele două drumuri.
Decay of memory or fate?
Sau nu-mi mai amintesc eu anumite chestii sau numărul alarmant de mare de deja-vu-uri este real?
Sau, s-o luăm altfel: săptămâna asta de vacanță am folosit RATC-ul (RATB-ul local) de aproximativ 14 ori. Și am avut același controlor în mașină de 10 ori. Dacă sunt cam 30 de mașini în oraș și cam 3 încasatori pe tură, care este probabilitatea unei întâmplări aleatorii? Aștept asemenea răspunsuri.
What is fate then but persistent hope in the face of relentless doubt?
Funcție
Deși am zis recent că sunt destul de ocupat, îmi permit o mică pauză în care să dau o altă problemă pentru concurs. Nu o voi da pe cea de 500 de puncte promisă data trecută, pentru că nu am găsit acel curs la care să mă plictisesc și să nu am de făcut nimic astfel încât să-mi permit să fac datele de intrare. Voi da ceva mai complicat dar fezabil.
Se cere să se construiască o funcție f : RxR -> R cunoscând un set de puncte prin care trece ea. Se știe că funcția este formată utilizând doar următoarele primitive: +, *, -, / (deci fără sin, cos, etc.) și următoarele constante 0, 1, 2 (în funcție nu vor apărea și alte argumente). Funcția nu este obligatoriu să fie polinomială dar va fi sigur continuă.
Pentru simplitatea problemei, domeniul maxim de definiție va fi un cerc cu raza 100, centrat în origine.
Programul va primi ca argument în linia de comandă numele unui fișier în care se vor afla setul de puncte și un număr reprezentând numărul de primitive folosite în funcție. Fișierul va fi structurat astfel:
- prima linie: doi întreg, primul reprezentând numărul n de puncte de control iar al doilea reprezentând numărul de primitive folosite. Numărul de constante folosite în funcție este lăsat ascuns.
- următoarele n puncte: 3 valori reale a, b, r cu proprietatea că r = f(a, b).
Programul vostru va produce un fișier în care se va afla o funcție C, python sau haskell (nu se acceptă bash pentru că nici nu am văzut concurenți care să-l folosească dar și din alte motive), fișier conținând implementarea funcției f sub formă de algoritm.
De exemplu, pentru fișierul de intrare
3 1 1 2 3 0 1 1 5 10 15
se poate produce un fișier de ieșire (în python, chiar dacă ați programat în C):
def f(a, b): return a+b
Desigur, există mai multe soluții posibile dar veți avea fișiere conținând aproximativ 50-80 de puncte de test. Se va testa programul pe acele puncte de test din fișier la care se vor mai adăuga uns et de puncte astfel încât numărul total de evaluări al funcției să fie 100.
Fiecare test trecut va primi un număr de puncte egal cu diferența dintre 100 și numărul de rezultate întoarse de funcția de output corespunzând rezultatelor așteptate. Vor exista 10 fișiere de test, 8 se vor face publice la prima submisie sau cu puțin timp înainte de finalizarea concursului (finalizarea as in ultima problemă propusă, soluții se vor putea trimite o perioadă mai lungă de timp). Scorul L este suma acestor punctaje pe cele 10 teste și va trebui minimizat (concursul a fost mereu unul de minimizare a unei expresii).
Se consideră test picat acel test care eșuaează în a găsi o funcție în 10 minute de rulare sau returnează o funcție nedefinită pe tot intervalul scanat (pentru care va exista o pereche de puncte a, b într-un fișier de test astfel încât funcția sa nu fie definită în (a, b)). Un test picat va aduce 101 puncte la scorul L.
Se va trimite o arhivă zip conținând următoarele:
- fișier cod sursă, eventual cu comentarii (rutare + extensii)
- makefile conținând regula implicită all (care va construi executabilul cu excepția cazurilor în care folosiți Python și bash, caz în care regula nu va face nimic) și regula clean care va șterge acest executabil (dacă l-a creat)
- fișier opțional de feedback (care poate fi trecut și în corpul mesajului din mail dacă este nevoie).
Total puncte disponibile: 200 (următoarea sper că va fi cea care va avea 500). Baftă la rezolvat 
PS: Funcțiile pot conține și paranteze, numărul lor nu este știut.
