Prolog: Transmission

• Responsabil: Andrei Olaru
• Deadline soft: 23.05.2016, apoi depunctare 0.5p/ zi
• Deadline hard: 24.05.2016 ora 23.59
• Data publicării: 10.05.2016
• Data ultimei modificări: 10.05.2016
• Tema se va încărca pe vmchecker
• Data tester-ului: 22.05.2016 | 13.05.2016 (teste)
• Forum temă

• 22.05.2016:
  • corecție testare cu antene de emisie – unele soluții puteau fi refuzate pentru că un nod primea prea multă informație, însumată de la o antenă și din alte surse (mulțumesc Andrei-Bogdan Stănescu);
  • implementare switch amFacutBonus pentru a nu rula testele pentru bonus dacă predicatul amFacutBonus nu întoarce adevărat (mulțumesc Igor Parvan);
  • corecție însumare punctaje – suma afișată (dar nu cea considerată de vmchecker) considera și punctaje pentru testele care ies din timp (mulțumesc Mihaela-Elena Beboeanu).
• 21.05.2016: mențiune legături uni-sens în descrierea legăturilor (mențiune deja existentă în secțiunea scopul jocului) (mulțumesc Georgian Tănase).
• 18.05.2016: ajustare formatare tester; vmchecker activ.
• 17.05.2016: adăugat comentarii în tester și afișare punctaje. Reparat numele unei structuri din testul 4-2 (mulțumesc Andrei-Bogdan Stănescu).
• 13.05.2016: Adăugat tester și încă un test (3-7).

• Utilizarea mecanismelor oferite de limbajul Prolog pentru a rezolva probleme prin backtracking prin specificarea proprietăților soluției, și nu prin implementarea explicită a algoritmului de backtracking.
• Dezvoltarea capacităților de a lucra în Prolog cu liste și structuri de diverse tipuri.

Tema își propune soluționarea automată (cu scop didactic) a primelor niveluri din jocul Transmission, mai precis a nivelurilor de tipul celor din primele 3 capitole (Telegraph, Telephone, Computer), și pentru bonus din capitolul 4 (Broadcast).

Notă: pentru rezolvarea corectă a temei nu este necesară descărcarea, instalarea, sau jucarea jocului Transmission, dar pentru a înțelege mai bine mecanica jocului poate fi utilă urmărirea de clipuri care prezintă rezolvarea nivelurilor jocului, în special cum testele sunt bazate în mod direct pe anumite niveluri din joc.

Jocul Transmission cere jucătorului soluționarea unor probleme de „transmitere a informației“. Date fiind mai multe elemente de joc (surse de informație – „Transmitter“, receptoare de informație – „Receiver“, relee de informație – „Transceiver“, etc), așezate într-un spațiu bi-dimensional, jucătorul trebuie să realizeze legături între aceste elemente astfel încât informația (reprezentată în joc în forma unor cuburi mici) să „circule“ între elemente în așa fel încât toate elementele ce trebuie să primească informație să o facă, în cantitățile necesare.

Notă: jocul Transmission nu folosește în mod corect ideile de informație, propagare a informației, etc, de exemplu într-o rețea de calculatoare. Mai departe vom folosi conceptele din joc așa cum sunt ele considerate în joc, nu așa cum sunt în realitate.

Jocul are mai multe elemente (noduri) între care se pot face legături. Pe aceste legături circulă unități de informație. Fiecare element din joc are o caracteristică pe care o numim „lățime“ (marcată, în joc, prin numărul de cuburi goale din interiorul elementului).

Legăturile între elemente sunt unidirecționale (formează un graf orientat).

O legătură este permisă dacă:

• este realizată între noduri diferite;
• nu există deja o legătură între aceleași noduri și în sens invers;
• nu trece, geometric, printr-un alt nod (de exemplu, dacă avem 3 noduri coliniare A, B și C, dispuse în această ordine, nu se poate realiza o legătură directă între A și C, pentru că este B este între cele două noduri și coliniar cu acestea);
• nodul sursă conține unități de informație (cubulețe în afara nodului);
• nodul destinație are lățime disponibilă.

O aceeași unitate de informație poate circula de mai multe ori pe o legătură (parte dintr-un ciclu), consumând de fiecare dată din lățimea nodurilor prin care trece.

Există următoarele tipuri de noduri:

• O sursă de informație este caracterizată de numărul de unități de informație pe care le produce (aceasta va fi lățimea sursei). O sursă nu poate să aibă legături către aceasta;
• Un receptor de informație este caracterizat de numărul de unități necesare pentru ca soluția să fie corectă (aceasta va fi lățimea receptorului). Un receptor nu poate avea legături care pleacă din acesta;
• Un releu de informație este caracterizat de un număr de unități de informație care trebuie să circule prin acesta (poate fi și aceeași informație care ciclează) (aceasta va fi lățimea releului). Legături pot fi create către releu atâta timp cât mai este lățime disponibilă, și pot fi create din releu către alte noduri atunci când este informație în releu și destinația are lățime disponibilă.
  • Unele relee pot conține deja informație de la început. Acest lucru va fi specificat explicit în datele de intrare.
  • Se cere ca unele relee să rămână cu unități de informație atunci când soluția este completă. Acest lucru va fi specificat explicit în datele de intrare.
• (Pentru bonus) O antenă de emisie primește informație dintr-una sau mai multe surse, și transmite această informație tuturor nodurilor din raza sa.
  • Dacă o antenă primește n unități de informație, toate nodurile din raza sa cu lățime disponibilă vor primi câte n unități de informație, în limita lățimii disponibile.
  • Un nod care primește informație de la antenă nu poate transmite în mod direct informație înapoi antenei. De exemplu, dacă un nod dă unei antene un cub de informație, și se află în raza antenei, nu va primi cubul de informație înapoi de la antenă, și nici nu va primi alte informații de la antenă, chiar dacă acestea vin către antenă din alte noduri.
  • O antenă poate să emită oricâtă informație primește (are lățime nelimitată).

Scopul jocului este de a crea o mulțime de legături astfel încât unitățile de informație să circule de la surse, prin noduri, pentru a ajunge la receptori, consumând integral lățimea disponibilă atât în relee cât și la receptori.

Dacă considerăm nodurile ca fiind nodurile unui graf ale cărui muchii sunt toate legăturile posibil legale între noduri (legătura nu trece printr-un alt nod, legătura nu este către o sursă și nu este de la un receptor), soluția este o mulțime de drumuri prin graf astfel încât:

• din fiecare sursă pleacă un număr de drumuri cel mult egal cu lățimea sursei;
• în fiecare receptor ajung un număr de drumuri egal cu lățimea receptorului;
• prin fiecare releu trec un număr de drumuri (de fapt, în fiecare releu ajung un număr de muchii care sunt parte din drumuri) egal cu lățimea releului;
• dacă două drumuri folosesc aceeași muchie din graf, ambele o folosesc în același sens.

Mai jos sunt reprezentate grafic câteva exemple de teste, împreună cu soluțiile lor. Am reprezentat cu cerc o sursă, cu pătrat mare un receptor, cu cerc (cu pătrate înăuntru) un releu, cu pătrate mici cantitatea necesară de informație (lățimea) și cu pătrat negru unitățile de informație.

În figură sunt date și o reprezentare text a testului (prezentă și în comentariile din tester), și o soluție, dată în forma cerută de temă. Reprezentarea testului folosește simbolurile + pentru sursă de informație, - pentru receptor, și = pentru releu. Lățimea elementului este dată de numărul de simboluri.

Este prezentată și o variantă intermediară a soluției.

Scopul temei este realizarea unui program în limbajul Prolog pentru rezolvarea corectă a nivelurilor jocului Transmission.

Realizarea va avea următoarele părți:

1. Prelucrarea datelor primite despre o problemă concretă (un nivel) pentru a obține un format cu care să se lucreze mai ușor în rezolvarea problemei; acest format va sta la baza afișării datelor problemei, într-un format la alegere;
2. Producerea unei soluții corecte pentru o problemă, în formatul cerut.
3. (Pentru bonus) producerea unei soluții pentru nivelurile care conțin antene de emisie.

Prelucrarea intrării se va face prin predicatul

parse(+Raw, -Problem)

care primește descrierea unui test și produce o descriere a problemei cu care se va lucra în continuare în program.

Notă: acest predicat trebuie să existe, dar nu este absolut necesar să realizeze prelucrări. El este dat ca element ajutător în realizarea temei.

Argumentul ​Raw​ va fi transmis lui ​parse​ ca o listă care conține mai multe structuri ce descriu problema. Unele dintre aceste structuri vor conține liste pe care le vom numi liste de lățimi. Listele de lățimi conțin identificatori de noduri și numere. Nodurile vor fi identificate prin litere mici. Dacă în lista de lățimi un identificator de nod este urmat de un număr, atunci numărul este lățimea nodului; dacă nu este urmat de un număr, atunci nodul are lățime 1. Exemplu: în lista ​[a,​ b, 2, c, d, 3]​ nodurile ​a​ și ​c​ au lățime 1, ​b​ are lățime 2, iar nodul ​d​ are lățime 3. Lista ​Raw​ conține un subset suficient din următoarele elemente (într-o ordine oarecare):

• o structură ​sources(L),​ unde ​L​ este lista de lățimi a nodurilor sursă – câte unități de informație are fiecare inițial.
• o structură ​receivers(L),​ unde ​L​ este lista de lățimi ​a nodurilor receptor – câte unități de informație trebuie să primească fiecare.
• o structură ​transceivers(L),​ unde ​L​ este lista de lățimi a nodurilor releu – câte unități de informație trebuie să treacă prin fiecare.
• o structură ​source_transceivers(L),​ unde ​L​ este lista de lățimi a nodurilor releu care au inițial unități de informație.
• o structură ​star_transceivers(L),​ unde ​L​ este lista de lățimi a nodurilor releu care trebuie ca la sfârșit să aibă unități de informație pe care să nu le treacă mai departe.
• o structură collinear(L), unde L este o listă de liste de identificatori de noduri, fiecare dintre liste semnificând că nodurile respective sunt coliniare, în ordinea dată. De exemplu, dacă unul dintre membrii lui L este [a, b, c], înseamnă că nodurile a, b și c sunt coliniare, deci nu este posibilă o legătură de la a la c (sau invers).

Pentru a verifica parsarea, se va implementa și un predicat

describe(+Problem)

care va afișa la consolă descrierea unei probleme de rezolvat, într-un format la alegere (e.g. ce proprietăți are fiecare nod).

Punctajul pentru prima cerință va fi dat astfel:

• pentru parse (20p):
  • în mod implicit, punctajul va fi calculat ca proporțional cu punctajul la testele fără bonus(testele de la 11 până la 37): dacă pe teste se primesc f*75 de puncte (cu f din [0, 1]), parse va primi f*20 de puncte.
  • altfel (în cazul în care nu trec toate testele), dacă parse prelucrează integral intrarea (rezultatul produs nu păstrează structura argumentului Raw), în urma prezentării se vor acorda pentru parse 20 de puncte.
• pentru describe se acordă 5 puncte în urma prezentării temei.

Se cere rezolvarea unei probleme de tipul celor prezentate. Implementarea rezolvării se va face în predicatul

solve(+Problem, -Solution)

Argumentul Problem este exact în forma legată de parse. Argumentul Solution trebuie legat la o descriere a soluției, care trebuie să fie reprezentată ca o listă de lățimi de muchii. Fiecare element din Solution va fi o listă [X, Y, W] conținând sursa, respectiv destinația unei muchii din soluție, și de asemenea lățimea muchiei, semnificând câte unități de informație trec prin muchia respectivă în soluție (vezi și exemplele).

Punctajul va fi dat depinzând de testele care pot fi rezolvate de temă. Dificultatea testelor este crescătoare.

Cei care implementează bonusul trebuie să aibă în temă un predicat amFacutBonus care să întoarcă adevărat (este comentat în sursa dată).

În testele pentru bonus, lista Raw dată lui parse mai conține o structură antennas(L), în care lista L conține câte o listă pentru fiecare antenă din problemă. Fiecare listă corespunzătoare unei antene are pe prima poziție nodul în care este antena iar restul listei este formată din nodurile care sunt în raza de emisie a antenei.

Antenele nu vor fi niciodată una în raza alteia.

Notă: în soluție nu trebuie să apară legături de la antenă către alte noduri, doar legăturile care merg către antenă.

Se va lucra numai în fișierul transmission.pl.

Pentru a vă testa tema, folosiți predicatele:

• ttestAll – rulează toate testele, este predicatul folosit pe vmchecker.
• ttestOne(+TestID) – rulează testul identificat de TestID.
  • testele pot fi identificate în fișierul de testare ca fiind întoarse de predicatul tt(+TestID, -Raw).
• ttestOneA(+TestID) – rulează testul identificat , fără limită de timp.

Testele sunt detaliate în fișierul de testare în regulile predicatului tt. Înainte de regula pentru fiecare test, este dat și reprezentarea vizuală a testului, folosind simbolurile + pentru o unitate de lățime a unei surse, - pentru o unitate de lățime a unui receptor, = pentru o unitate de lățime a unui transmițător, și * pentru o antenă.

Membri echipei de PP nu promovează în scop comercial jocul Transmission. Proprietatea intelectuală asupra jocului, ideii, și elementelor de joc rămâne autorilor.

• Arhiva de pornire (Schelet și tester)

• Puteți găsi pe Youtube un mare număr de rezolvări (Walkthroughs) pentru nivelurile din Transmission în care puteți observa mecanica jocului și modul de rezolvare (e.g. căutați Transmission walkthrough 3-4).