HW06: Pandémia s.r.o.

Odevzdávání úkolu je ukončeno.
Autoři zadání Radoslav Sabol Matej Focko Martin Krebs
Odevzdávané soubory src/main.c src/*.c src/*.h
Začátek odevzdávání viz diskusní fórum
Bonus za brzké odevzdání neurčeno
Konec odevzdání 2022-07-08 24:00
Vzorová implementace /home/kontr/pb071/hw06/pandemic
Opravy v zadání 2022-06-29 10:54 8

Predstavenie úlohy

Modelovanie a simulácie sú veľmi efektívny nástroj, ako pomocou vhodnej úrovne abstrakcie modelovať a skúmať aj veľmi zložité systémy. Jednou z najpoužívanejších oblastí je takzvaný Agent-based modeling.

Ide o výpočetný model, ktorý sleduje akcie a interakcie jednotlivých agentov. Na to, aby sme mohli nejaký jav skúmať pomocou takejto simulácie, si však musíme najprv vytvoriť vhodné prostredie.

Mnohí z vás určite poznajú hru Plague Inc., v ktorej hráte na strane vírusu a snažíte sa vyhubiť ľudstvo. My si v tejto domácej úlohe naprogramujeme zjednodušenú verziu a viac, ako koniec ľudstva, nás bude zaujímať spôsob, akým sa vírus šíri a čo všetko ovplyvňuje jeho nákazlivosť.

Zadanie

Napíšte program, ktorý z príkazového riadku a súborov načíta informácie o víruse, agentoch a svete, v ktorom bude simulácia prebiehať. Následne simuláciu spustite a na textový výstup vypíšte informácie o jej priebehu.

Použitie výsledného programu bude vyzerať takto:

./pandemic [OPTIONS] agents.csv world.csv

Kde [OPTIONS] sú voliteľné prepínače programu, world.csv je súbor popisujúci svet a agents.csv je súbor s agentmi (Detailný popis v príslušnom odstavci).

Prepínače

--lethality <float>

Prepínač popisujúci smrteľnosť vírusu, používa sa vo vzorci pre výpočet úmrtí agentov. Ak prepínač nie je špecifikovaný, lethality bude nastavené na hodnotu 0.5. Hodnota musí byť z rozsahu [0, 1].

--infectivity <float>

Infekčnosť vírusu, používa sa vo vzorci pre výpočet prenášania vírusu medzi agentmi. V prípade, že prepínač nie je špecifikovaný, nastavte hodnotu na 0.5. Hodnota musí byť z rozsahu [0, 1].

--duration <float>

Doba infekčnosti, používa sa vo vzorci pre výpočet, či sa daný agent vylieči alebo nie. Ak nie je špecifikovaná, očakávaná hodnota je 0.5. Hodnota musí byť z rozsahu [0, 1].

--vaccine-modifier <float>

Reálne nezáporné číslo, ktoré reprezentuje účinnosť vakcíny, ktorou sú všetci agenti zaočkovaní. Predvolná hodnota je 1.2.

--max-steps <int>

Nezáporné celé číslo popisujúce počet kôl simulácie. Ak nie toto číslo špecifikované, očakáva sa, že vaša simulácia bude bežať až do chvíle, kým nie sú všetci agenti zdraví alebo mŕtvi.

--random-seed <int>

Seed, ktorý potrebujeme byť schopní nastaviť pre účely testovania. V prípade, že prepínač nie je špecifikovaný, predvolená hodnota je time(NULL). Nezabudnite tento seed nastaviť pomocou srand(3) pred samotným spustením simulácie.

V prípade, že porovnávate správanie referenčnej implementácie voči tej vašej, nezabudnite tento prepínač nastaviť na rovnakú hodnotu pre oba programy.
--verbose

V prípade, že je zvolený tento prepínač, požaduje sa, aby váš program vypisoval informáciu o jednotlivých kolách. Bude nás zaujímať, kto koho nakazil, kto sa vyliečil a kto zomrel. Detailný formát výpisu je v časti o vyhodnotení priebehu.

Vírus

Rovnako ako občas v skutočnom svete, aj v tejto úlohe bude pre nás vírus akousi záhadnou entitou, o ktorej toho veľa nevieme. Všetky informácie týkajúce sa vírusu sa zadávajú ako prepínače na príkazovom riadku. Pre vírus sú relevantné

  1. Lethality --lethality <float>

  2. Infectivity --infectivity <float>

  3. Duration --duration <float>

Ako ovplyvňujú priebeh samotnej simulácie sa dočítate v časti o jej priebehu.

Svet

Svet budeme reprezentovať ako úplný graf, ktorého vrcholy predstavujú miesta, v ktorých sa združujú agenti.

Súbor bude vo formáte CSV, kde každý riadok bude reprezentovať jeden vrchol nášho grafu. Každý validný riadok bude mať nasledujúce stĺpce:

id;name;exposure
  1. id <int> - nezáporný celočíselný unikátny identifikátor daného miesta

  2. name <reťazec> - názov daného miesta, používať ho budeme pri výpise informácií o simulácii. Implementácia musí podporovať reťazec s dĺžkou aspoň 16 ASCII znakov.

  3. exposure <float> - nezáporné reálne číslo, ktoré ovplyvňuje šírenie vírusu v danom vrchole grafu.

Príklad súboru so svetom:

$ cat Bratislava.csv
1;Robota;0.7
2;Kostol;0.0
3;Krčma;1.0
4;Cintorín;0.0
5;Domov;0.4
Formát CSV nie je úplne štandardizovaný, vo väčšine prípadov obsahuje prvý riadok názvy jednotlivých stĺpcov. V celom zadaní predpokladáme, že vstupný súbor takýto riadok neobsahuje.

V prípade, že vášmu programu bude dodaná cesta ku súboru so svetom, bude to vždy posledný argument volania programu.

V prípade, že vás článok o úplnom grafe viac zmiatol než obohatil, stačí ak rozumiete, že medzi každým vrcholom vedie hrana. V praxi to znamená, že agenti sa môžu (a budú) pohybovať medzi ľubovoľnými dvoma vrcholmi, podľa toho ako to majú špecifikované vo svojom chovaní.

Overte, že pre každý riadok kontrolujete správny počet stĺpcov. Predovšetkým id;;hocičo alebo id;name;exposure;eyecolor nie sú validné riadky.
Pri načítaní súboru by sa vám mohla zísť funkcia strtok(3). Ak ste zabudli, ako sa s ňou pracuje, pripomenúť si to môžete v cvičení 5.

Agenti

Podobne ako svet, aj súbor s agentmi bude vo formáte CSV. Jeden riadok zodpovedá jednému agentovi, význam jednotlivých stĺpcov je nasledujúci:

id;route;is_vaccinated;immunity;is_infected
id <int>

Nezáporný celočíselný unikátny identifikátor agenta

route <reťazec>

Agentova cesta svetom, čísla zodpovedajú identifikátorom jednotlivých miest v grafe. Z posledného vrcholu sa agent vracia na prvý. Cesta je zadaná ako postupnosť identifikátorov miest oddelených znakom -. Všetky vrcholy cesty musia vo svete existovať. Implementácia musí podporovať cesty s aspoň 256 vrcholmi.

is_vaccinated <bool>

Reprezentuje zaočkovanosť agenta, používa sa v priebehu simulácie. Akceptované hodnoty sú 0 pre nezaočkovaného agenta a 1 pre zaočkovaného.

immunity <float>

Agentova prirodzená imunita, rovnako ju budeme využívať pri výpočtoch v jednotlivých kolách simulácie. Akceptované sú hodnoty z intervalu [0, 1].

is_infected <bool>

Číslo udávajúce počiatočný stav agenta, 0 znamená, že agent je zdravý, 1 značí, že u neho bola zistená prítomnosť vírusu.

Príklad súboru s agentmi:

$ cat agents.txt
1;4-1-3;1;0.5;0
2;5-1-3;1;0.5;0
3;5;1;0.2;0
4;4;0;0.2;1
5;5-2-3-1-3;0;0.5;1

Tak ako v prípade súboru so svetom si dajte pozor, aby bol dodržaný správny počet stĺpcov.

Priebeh simulácie

Naša simulácia bude pozostávať z jednotlivých iterácií a končí jedným z možných scenárov:

  1. Neostal žiadny živý agent

  2. Vírus už nemá žiadneho hostiteľa, teda sú všetci agenti vyliečení

  3. Počet iterácií presiahne vopred stanovené číslo dodané prepínačom --max-steps.

Vo všetkých prípadoch je simulácia ukončená a po vašom programe sa očakáva, že vypíše výslednú štatistiku.

Priebeh iterácie

Fáza presunu

Agenti sa presúvajú z miesta na miesto určené ich cestou zo vstupného súboru. V tomto prípade je jedno, aké poradie presunu agentov zvolíte. Po vašom programe sa očákava, že po skončení tejto fázy sú všetci agenti na mieste, do ktorého sa podľa svojej cesty mali presunúť.

Fáza pokroku ochorenia

Priebeh nákazy u jednotlivca - jednotlivec zomrie, vylieči sa, alebo ostane nakazený.

Vzorec pre úmrtie agenta prebieha podľa vzorca:

roll = (double) rand() / RAND_MAX;
dead = roll < lethality;

V prípade, že je agent zaočkovaný, tak sa hodnota roll násobí príslušnou hodnotou vaccine_modifier.

Vzorec pre vyliečenie agenta

roll = (double) rand() / RAND_MAX;
cured = roll > duration;

Najprv vyhodnocujeme či agent prežil, až potom či sa vyliečil.

roll pre úmrtie a roll pre uzdravenie sú dve nezávislé hodnoty.

Táto fáza prebieha postupne v jednotlivých miestach podľa ich číselného identifikátora vzostupne od toho najnižšieho. V jednom mieste sa rovnakým spôsobom vyhodnocujú jednotliví agenti, t.j. vzostupne od agenta s najnižším id. V prípade, že agent v tejto fáze zomrie, tak sa v ďalšej fáze neberie do úvahy.

Fáza šírenia nákazy

Šírenie nákazy v aktuálnom mieste pobytu agentov, nákaza sa šíri spôsobom každý s každým - t.j. ak agenta nakazí iný agent, agent je nakazený a ďalej do priebehu nákazy nevstupuje. V prípade, že agenta nenakazí ani jeden zo zvyšných agentov, tak agent ostáva zdravý. Medzi agentmi, ktorí do tejto fázy prišli už nakazení, sa nákaza ďalej nešíri. Vírus sa šíri v prípade, že

roll = (double) rand() / RAND_MAX;
infected = exposure * roll * infectivity > immunity;

Ak je agent zaočkovaný, tak sa immunity násobí príslušnou hodnotou vaccine_modifier.

Aby sme vedeli vašu implementáciu otestovať, je dôležité, aby sa táto fáza vyhodnocovala rovnako, ako v referenčnej implementácii. Šírenie začína v mieste s najnižším číselným identifikátorom a pokračuje vzostupne, rovnako ako v predošlej fáze.

V jednotlivých miestach je poradie agentov jasne dané ich identifikátormi, iteruje sa vzostupne od agenta s najnižším identifikátorom.

Agenta môže nakaziť len agent, ktorý je sám nakazený. Nákaza sa šíri atomicky, takže v prípade, že sa agent nakazí v tomto kole a predtým bol zdravý, tak v tomto kole nákazu nešíri. Rovnako ho po nakazení už neskúšajú nakaziť ostatní infikovaní agenti.

V prípade, že sa v jednom mieste nachádzajú agenti s identifikátormi 1, 5, 12, 42 a 1337, a agenti 5 a 1337 sú nakazení, poradie vzájomnej výmeny vírusu je nasledovné.

5 -> 1
5 -> 12 \\ infected
5 -> 42
1337 -> 1
1337 -> 42

Vyhodnotenie

Po skončení simulácie (jedným z troch vyššie uvedených spôsobov) váš program na štandardný výstup vypíšte nasledujúce informácie:

  1. Seed, ktorý bol použitý počas behu programu

  2. Informáciu o každom kroku, ktorý začal

  3. Výsledok simulácie

  4. Kumulatívnu štatistiku o prebehnutej simulácii:

    • celkový počet prenosov vírusu

    • počet obetí vírusu

    • počet živých ľudí po skončení simulácie

  5. Miesto s najviac prenosmi vírusu.

  6. Celkový počet krokov simulácie

Formát je nasledujúci:

Random seed: 1337
<VERBOSE INFO>
<RESULT>
Statistics:
	Total infections: A
	Total deaths: B
	Number of survivors: C
Most infectious location:
	<LOCATION>
Simulation terminated after N steps.
V prípade odsadenia vždy odsadzujte jedným znakom tabulátora.

Kde <RESULT> je jeden z možných scenárov:

  1. Step limit expired. - v prípade, že simulácia neskončila do zadaného počtu krokov

  2. Population is extinct. - všetci agenti zomreli

  3. Virus is extinct. - aspoň jeden agent je živý a žiaden agent nie je nakazený

A <LOCATION> je:

  1. - <PLACE_NAME>: <NUMBER_OF_INFECTED> infections - ak existuje práve jedno mesto s najväčším počtom novo-nakazených agentov počas celého behu simulácie, t.j. miesto kde sa nákaza najviac šírila.

  2. Multiple: v prípade, že najväčší počet nakazených zďieľajú aspoň dve miesta

V prípade, že je špecifikovaný prepínač --verbose, od vašej implementácie sa očakáva, že bude v každom kole vypisovať nasledujúce informácie v mieste <VERBOSE INFO>:

  • Zmenu stavu agenta, t.j. nakazený agent zomrel, alebo sa nakazený agent vyliečil

  • Informáciu, ktorý agent koho nakazil.

Pre iterácie S a S + 1 vyzerá výstup nasledovne:

*** STEP S ***
Agent 1 has died at Hospital.
Agent 3 has recovered at Bar.
Agent 2 has infected agent 4 at School.
Agent 2 has infected agent 3 at School.
Agent 8 has infected agent 6 at Office.

*** STEP S + 1 ***
Agent 8 has infected agent 17 at Office.

V prípade, že váš program bol spustený bez prepínača --verbose, nevypisujte na mieste <VERBOSE INFO> nič.

Požiadavky

Od vášho programu sa očakáva, že v prípade chyby korektne uvoľní všetky alokované zdroje a skončí s nenulovým návratovým kódom a príslušnou chybovou hláškou.

V prípade, že simulácia prebehne v poriadku, na konci vypíše súhrnnú štatistiku o jej priebehu a skončí s nulovým návratovým kódom. V prípade spustenia s prepínačom --verbose sa takisto očakávajú informácie o jej priebehu v jednotlivých krokoch.

Váš program vypisuje všetky informácie na štandardný textový (prípadne chybový) výstup. V prípade, že si chcete správanie otestovať proti referenčnej implementácii, odporúčame si výstupy presmerovať do súborov, a tieto súbory potom porovnať pomocou príkazu diff(1).

Opravy v zadání

Add locations to death/recovery

07af5c4 2022-06-29 10:54 Matej Focko
 -387,4 +387,4  Pre iterácie `S` a `S + 1` vyzerá výstup nasledovne:
 *** STEP S ***
-Agent 1 has died.
-Agent 3 has recovered.
+Agent 1 has died at Hospital.
+Agent 3 has recovered at Bar.
 Agent 2 has infected agent 4 at School.

Postpone deadline

8610d2a 2022-06-28 22:13 Roman Lacko
 -7,3 +7,3  publish: now
 deadline-early: ~
-deadline-final: 2022-06-20 24:00
+deadline-final: 2022-07-08 24:00
 authors:

Reformat the steps

da4f096 2022-06-08 22:13 Matej Focko
 -386,3 +386,3  Pre iterácie `S` a `S + 1` vyzerá výstup nasledovne:
 ----
-STEP S
+*** STEP S ***
 Agent 1 has died.
 -392,3 +392,4  Agent 2 has infected agent 3 at School.
 Agent 8 has infected agent 6 at Office.
-STEP S + 1
+
+*** STEP S + 1 ***
 Agent 8 has infected agent 17 at Office.

Make periods consistent

a28053a 2022-06-08 22:11 Matej Focko
 -363,6 +363,6  Kde `` je jeden z možných scenárov:
 
-1. `Step limit expired` - v prípade, že simulácia neskončila do zadaného počtu
+1. `Step limit expired.` - v prípade, že simulácia neskončila do zadaného počtu
    krokov
-2. `Population is extinct` - všetci agenti zomreli
-3. `Virus is extinct` - aspoň jeden agent je živý a žiaden agent nie je nakazený
+2. `Population is extinct.` - všetci agenti zomreli
+3. `Virus is extinct.` - aspoň jeden agent je živý a žiaden agent nie je nakazený
 
 -387,9 +387,9  Pre iterácie `S` a `S + 1` vyzerá výstup nasledovne:
 STEP S
-Agent 1 has died
-Agent 3 has recovered
-Agent 2 has infected Agent 4 at School
-Agent 2 has infected Agent 3 at School
-Agent 8 has infected Agent 6 at Office
+Agent 1 has died.
+Agent 3 has recovered.
+Agent 2 has infected agent 4 at School.
+Agent 2 has infected agent 3 at School.
+Agent 8 has infected agent 6 at Office.
 STEP S + 1
-Agent 8 has infected Agent 17 at Office
+Agent 8 has infected agent 17 at Office.
 ----

Fix `--max-steps`

5d40b69 2022-06-05 22:32 Matej Focko
 -72,3 +72,3  agenti zaočkovaní. Predvolná hodnota je `1.2`.
 
-`--max-iterations `::
+`--max-steps `::
 Nezáporné celé číslo popisujúce počet kôl simulácie. Ak nie toto číslo
 -232,3 +232,3  scenárov:
 3. Počet iterácií presiahne vopred stanovené číslo dodané prepínačom
-   `--max-iterations`.
+   `--max-steps`.
 

Use tabs instead of spaces

2c26755 2022-06-05 22:25 Matej Focko
 -350,7 +350,7  Random seed: 1337
 Statistics:
-    Total infections: A
-    Total deaths: B
-    Number of survivors: C
+	Total infections: A
+	Total deaths: B
+	Number of survivors: C
 Most infectious location:
-    
+	
 Simulation terminated after N steps.

Fix order of input files

d04ac29 2022-06-05 21:59 Matej Focko
 -43,3 +43,3  Použitie výsledného programu bude vyzerať takto:
 ----
-./pandemic [OPTIONS] world.csv agents.csv
+./pandemic [OPTIONS] agents.csv world.csv
 ----
 -153,3 +153,3  takýto riadok neobsahuje.
 V prípade, že vášmu programu bude dodaná cesta ku súboru so svetom, bude to vždy
-predposledný argument volania programu.
+posledný argument volania programu.
 

Fix typos

12c62ae 2022-05-16 15:48 Juraj Fiala
 -126,3 +126,3  id;name;exposure
 2. `name ` - názov daného miesta, používať ho budeme pri výpise
-   informácií o simulácii. Implementácia musí podporovať cestu s dĺžkou
+   informácií o simulácii. Implementácia musí podporovať reťazec s dĺžkou
    aspoň 16 ASCII znakov.
 -148,3 +148,3  $ cat Bratislava.csv
 [TIP]
-Formát CSV nie je úplne štandardizovaný, vo väčšie prípadov obsahuje prvý riadok
+Formát CSV nie je úplne štandardizovaný, vo väčšine prípadov obsahuje prvý riadok
 názvy jednotlivých stĺpcov. V celom zadaní predpokladáme, že vstupný súbor