Wyzwanie
Musisz stworzyć prosty model rozprzestrzeniania się choroby wśród grupy ludzi.
Zasady i wymagania
Model musi być tablicą 2D o wymiarach 1000 na 1000, przy czym każdy element jest inną osobą.
Użytkownik musi wprowadzić trzy zmienne za pomocą argv: prawdopodobieństwo przeniesienia (prawdopodobieństwo, że ktoś zarazi kogoś innego), prawdopodobieństwo mutacji i liczbę okresów, przez które symulacja powinna zostać uruchomiona.
W pierwszym okresie ( t=0
) cztery osoby powinny zostać wybrane losowo i zakażone chorobą.
Zachowanie się choroby regulują następujące zasady:
- Choroba może poruszać się tylko pionowo i poziomo, przenosząc się na osobę obok.
- Zakażenie trwa 3 okresy u każdej osoby. Nie możesz brać pod uwagę niedoborów odporności.
- Po trzykrotnym zarażeniu osoba jest odporna i nie można jej ponownie zainfekować.
- Choroba podlega mutacji, dzięki czemu osoby uprzednio odporne są podatne na tę nową zmutowaną chorobę. Zmutowana choroba ma dokładnie te same cechy i podlega tym samym zasadom, co pierwotna choroba.
- Jeśli dojdzie do mutacji, cała choroba się nie zmienia, tylko ten konkretny „pakiet” po przeniesieniu.
- Gdy dana osoba zostanie zainfekowana jednym wirusem, nie można jej ponownie zainfekować, dopóki nie minie bieżąca infekcja.
- Jeśli dana osoba jest zarażona, jest zakaźna od początku okresu zakażenia do jego końca.
- Nie ma poziomów odporności - osoba jest albo odporna, albo nie.
- Aby zatrzymać przeciążenie pamięci, istnieje maksymalny limit 800 mutacji.
Pod koniec określonej liczby okresów należy wyświetlić wyniki.
Wynikiem musi być siatka 1000 x 1000 pokazująca, które osoby są zainfekowane, a które nie. Może to być wyprowadzane jako plik tekstowy, jako plik obrazu lub wyjście graficzne (gdzie #FFFFFF to zdrowa osoba, a # 40FF00 to osoba zarażona).
Czy możesz podać nazwę języka i polecenie uruchomienia go w swojej odpowiedzi.
Zwycięski
Wygrywa najszybszy kod do uruchomienia na moim komputerze. Jego czas będzie mierzony za pomocą następującego fragmentu kodu Python:
import time, os
start = time.time()
os.system(command)
end = time.time()
print(end-start)
Pamiętaj, że podczas uruchamiania tego skryptu użyję następujących ustawień domyślnych:
Probability of transmission = 1
Chance of mutation = 0.01
Number of periods = 1000
źródło
V
, drugi zaraża wirusemV'
. Oba skurcze zakończą się w tym samym okresie. Czy wirus możeV
zarazić drugą osobę? (Lub bardziej czarno-białe pytanie: czy jest możliwe, że dana osoba zostanie zarażona natychmiast po wyleczeniu, więc skończy się 6 kolejnymiV
osobiścieA
iV
znowu osobiścieB
. Czy po przeniesieniu wirusa oba mutują się w tej samej mutacjiV'
? A może faktycznie powinni mutować do tego samego szczepu wirusa? Jeśli potrafią mutować dowolnie, jakie jest prawdopodobieństwo mutacji dwóch wirusów na ten sam szczep wirusa?Odpowiedzi:
Byłem ciekawy, jak to będzie wyglądać, więc zrobiłem ten szybki i brudny hack w JavaScript: http://jsfiddle.net/andrewmaxwell/r8m54t9c/
źródło
C ++ 11, 6-8 minut
Mój test trwa około 6-8 minut na moim komputerze Fedora 19, i5. Ale z powodu losowości mutacji, równie dobrze może ona być szybsza lub potrwać dłużej. Myślę, że kryteria punktacji wymagają ponownego sformułowania.
Drukuje wynik jako tekst na końcu zakończenia, zdrowa osoba oznaczona kropką (
.
), zainfekowana osoba gwiazdką (*
), chyba żeANIMATE
flaga jest ustawiona na true, w takim przypadku wyświetla różne znaki dla osób zainfekowanych różnymi szczepami wirusów.Oto GIF na 10x10, 200 okresów.
Zachowanie mutacyjne
Każda mutacja da nowy szczep, którego nigdy wcześniej nie widziano (więc możliwe jest, że jedna osoba zaraża czterech sąsiadujących ludzi 4 różnymi szczepami), chyba że wytworzono 800 szczepów, w którym to przypadku żaden wirus nie przejdzie na żadną dalszą mutację.
8-minutowy wynik pochodzi z następującej liczby zainfekowanych osób:
podczas gdy wynik 6 minut pochodzi z:
Reprezentacja osoby
Każda osoba jest reprezentowana w 205 bajtach. Cztery bajty do przechowywania typu wirusa, który ta osoba się zaraża, jeden bajt do przechowywania informacji o tym, jak długo ta osoba została zainfekowana, oraz 200 bajtów do przechowywania informacji o tym, ile razy zarażał każdy szczep wirusa (2 bity każdy). Być może C ++ wykonuje dodatkowe wyrównanie bajtów, ale całkowity rozmiar wyniesie około 200 MB. Mam dwie siatki do przechowywania następnego kroku, więc w sumie zużywa około 400 MB.
Przechowuję lokalizację zainfekowanych osób w kolejce, aby skrócić czas wymagany we wczesnych okresach (co jest naprawdę przydatne do okresów <400).
Dane techniczne programu
Co 100 kroków ten program wypisze liczbę zainfekowanych osób, chyba że
ANIMATE
ustawiono flagętrue
, w którym to przypadku drukuje całą siatkę co 100 ms.Wymaga to bibliotek C ++ 11 (kompilacja przy użyciu
-std=c++11
flagi lub w systemie Mac zclang++ -std=c++11 -stdlib=libc++ virus_spread.cpp -o virus_spread
).Uruchom go bez argumentów dla wartości domyślnych lub z argumentami takimi jak ten:
./virus_spread 1 0.01 1000
źródło
C # 6-7 minut
Edytuj 2
W końcu (5 godzin) wygenerowałem wyczerpujący wynik dla prawie 1000 okresów (tylko 840 klatek, a następnie rozbił się) przy 1000 x 1000, co 1 okres, jednak jest to prawie 160 MB i wymaga wyświetlenia całej pamięci w moim systemie (IrfanView) , nawet nie jestem pewien, czy to zadziała w przeglądarce, pozwól mi to później.
EDYTOWAĆ
Spędziłem dużo czasu, aby uczynić to bardziej wydajnym zgodnie z odpowiedzią na „Rozpad Beta” stwierdzającą: „Wybierz szczep losowo”. Mam tylko losową metodę wyboru, kto zaraża, kogo na okres, jednak zmieniłem sposób, który jest obliczany i wszystko załatwiłem, zaktualizowałem swoje posty o nowe szczegóły.
Zakodowałem moje najbliższe oszacowanie do tego, co mogłem, mam nadzieję, że przestrzega wszystkich zasad, wykorzystuje mnóstwo pamięci w moim systemie (około 1,2 GB). Program może wyświetlać animowane gify (wygląda fajnie, naprawdę wolno) lub po prostu obraz pasujący do specyfikacji „Beta Decay”. To trochę nowa koncepcja koła, ale zdecydowanie wygląda świetnie:
Wyniki
(Uwaga: rozróżnia to tylko między zarażonym i niezainfekowanym, tj. Nie gadatliwym)
1000 okresów, 1% wskaźnik mutacji, 100% spread:
Przykłady (pełne)
W każdym razie użycie 100% „prawdopodobieństwa transmisji” w trybie nieokreślonym jest nudne, ponieważ zawsze dostajesz te same kształty i nie widzisz różnych mutacji, jeśli poprawisz parametry wokół nieco (i włączysz tryb szczegółowy) masz fajnie wyglądający wynik (animowane pliki GIF są wyświetlane co 10 klatek):
Losowo - Rozmiar siatki: 200, Prob Transmisja: 100%, ProbMutacja: 1%
Losowo - Rozmiar siatki: 200, Prob Transmisja: 20%, ProbMutacja: 1%
Punktacja
Zgadzam się z „justhalf”, że kryteria punktacji mogą być niesprawiedliwe, ponieważ każdy bieg będzie się różnić z powodu losowości mutacji i pozycji losowych punktów początkowych. Może moglibyśmy zrobić średnio kilka biegów lub coś w tym stylu ... Cóż, w każdym razie jest to w C #, więc dla mnie nagroda :( w każdym razie.
Kod
Pamiętaj, aby dołączyć bibliotekę MagickImage (ustawioną na kompilację bitów x64), w przeciwnym razie nie zostanie ona zbudowana ( http://pastebin.com/vEmPF1PM ):
źródło