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 hodnotu0.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ť pomocousrand(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é
-
Lethality
--lethality <float>
-
Infectivity
--infectivity <float>
-
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
-
id <int>
- nezáporný celočíselný unikátny identifikátor daného miesta -
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. -
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 a1
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:
-
Neostal žiadny živý agent
-
Vírus už nemá žiadneho hostiteľa, teda sú všetci agenti vyliečení
-
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:
-
Seed, ktorý bol použitý počas behu programu
-
Informáciu o každom kroku, ktorý začal
-
Výsledok simulácie
-
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
-
-
Miesto s najviac prenosmi vírusu.
-
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:
-
Step limit expired.
- v prípade, že simulácia neskončila do zadaného počtu krokov -
Population is extinct.
- všetci agenti zomreli -
Virus is extinct.
- aspoň jeden agent je živý a žiaden agent nie je nakazený
A <LOCATION>
je:
-
- <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. -
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