Projekt: Šest stupňů odloučení

Vstupní soubor obsahuje položku trust, která vyjadřuje, jak moc osoba A důvěřuje osobě B na konkrétní platformě. Jedná se o celé číslo na intervalu <0; 100), kde nižší číslo vyjadřuje vyšší důvěru. Pro jedno spojení je potom důvěra nejnižší hodnota napříč všemi sociálními sítěmi. Tedy napříkad, pokud A má pro osobu B index důvěry na twitteru o hodnotě 80 a na facebooku o hodnotě 40 potom je přímá důvěra osoby A osobě B rovna 40.

Důvěryhodnost si můžeme definovat jako tranzitivní uzávěr důvěry, tedy jedná se o nejmenší hodnotu součtu všech možných propojení osoby A s osobou B. Jinými slovy pokud osoba A důvěřuje osobě B s hodnotou 30 a osobě C s hodnotou 3, osoba C důvěřuje osobě B s hodnotou 2, potom je důvěryhodnost osoby C pro osobu A rovna 3, a důvěryhodnost osoby B rovna 5 (důvěryhodnost je nižší - tedy lepší - než důvěra). Ovšem pozor, žádnou další důvěryhodnost z tohoto příkadu nevyčteme, pokud by pouze toto byl náš vstup, potom osoby B ani C nemají s osobou A vůbec žádný vztah a taková síť by byla brána za nesouvislou.

Stupeň odloučení osoby A od osoby B je roven počtu osob, které tvoří nejkratší řetězec propojení A a B.

Pokud A má přímou asociaci s B (tedy definuje pro něj trust), potom je jejich stupeň odloučení 1. Pokud A má asociaci s B a B s C, potom je stupeň odloučení A s C roven 2. Všimněte si, že pro určení stupně odloučení osob není atribut trust vůbec relevantní. Dále mějte na paměti, že podobně jako u důvěry to že platí A→B→C neznamená, že by zároveň platilo C→B→A. Může nastat situace, že C nemá žádnou vazbu na A.

Pokud bychom použili podobnou definici jako výše, potom stupeň odloučení osoby je tranzitivní uzávěr relace existujeDůvěra na množině osob.

CSV je velmi jednoduchý promát pro serializaci dat, jedná se o druh tabulky, kde jsou jednotlivé buňky řádku odděleny čárkami a jednotlive řádky tabulky jsou realizovány řádky v souboru (tedy ukončeny znakem \n). V obecném CSV jsou jako řídící znak použity i uvozovky ", které označují řetězec, v němž libovolný jiný znak (rozuměj primárně čárka) ztrácí řídící význam, tedy:

U našich vstupů se nicméně dvojité uvozovky nebudou vyskytovat, tedy tuto situaci nemusíte řešit.

První problém, který může při běhu nastat je nevalidní CSV soubor na vstupu, v tomto případě pouze vypište na standardní chybový výstup libovolnou zprávu, zastavte zpracování souboru a pokračujte dalším souborem. CSV soubor je nevalidní, pokud v hlavičce nejsou všechny povinné položky, situaci přeuspořádání sloupců nemusíte brát v úvahu.

Dalším druhem problému je situace nalezení neplatného řádku souboru. V takovém případě řádek přeskočte a pokračujte na další (bez zapisování chybové hlášky).

Neplatný řádek je takový, který neobsahuje všechny sloupce definované dle hlavičky souboru, má prázdný login nebo email nebo friend_login, případně takový řádek, jehož trust není celé číslo v rozmezí <0-100).

Pozor, i řádek, na kterém jsou vyplněny všechny povinné identifikační údaje, může být neplatný, například pokud neobsahuje všechny sloupce definované dle hlavičky.

Neprázdnost, či platnost, ostatních atributů (včetně real_name) nemusíte ověřovat.

Bohužel v některých souborech může nastat situace, kdy jsou vstupní data nekonzistentní, současná teorie je, že se jedná o halucinaci způsobenou zpětnovazebnou smyčkou do náhodného LLM (počet tokenů není neomezený). Takovým souborům bohužel nemůžeme věřit.

Pokud váš program při zpracování CSV souboru narazí na záznamy obsahující stejný email, a různé loginy, nebo naopak, pro stejný login různé emaily, potom vaše řešení musí označit celý soubor za neplatný (stejně jako výše), ukončit jeho zpracování a vypsat na standardní chybový výstup zprávu o chybě. Zároveň musí platit, že jakékoliv načtené záznamy z tohoto souboru musí být brány za neplatné.

V případě, že po zpracování vstupu nenaleznete email k přihlašovacímu jménu, potom takovou asociaci nesmíte brát při výpočtu v úvahu, tedy všechny takto přidané asociace jsou neplatné. Tato situace může nastat v případě, kdy pro libovolný login neexistuje žádná odchozí aosicace, tedy pro daný login nedokážete určit jeho email.

Funkční testování ověřuje váš program vzhledem ke specifikaci tohoto zadání, tedy testuje že pro daný vstup vracíte (vypisujete) korektní a očekávaný výstup.

Spouští se pouze v případě, že Váš program splnil funkční testy na 15 b. Tyto testy budou zkoušet poměrně velké instance problémů a extrémní situace a očekávají, že váš výpočet krom korektnosti splní i výkonostní požadavky.

Pro jejich splnění bude měřena jak časová, tak i paměťová náročnost vašich algoritmů a nesplnění kterékoliv z nich znamená neúspěch v testovacím případě.

Obecné parametry řešení:

Při návrhu algoritmů se můžete spolehnout, že počet lidí se stupněm odloučení větším než 6 bude logaritmický vzhledem k celkovému počtu osob - tedy pro 128 osob to bude maximálně 7, pro 1024 maximálně 10 a tak dále.