Tantangan
Anda harus membuat model sederhana tentang bagaimana penyakit menyebar di sekitar sekelompok orang.
Aturan dan Persyaratan
Model harus berupa larik 1000 kali 1000 2D dengan setiap elemen menjadi orang yang berbeda.
Pengguna harus memasukkan tiga variabel menggunakan argv: probabilitas penularan (seberapa besar kemungkinan seseorang akan menginfeksi orang lain), peluang mutasi dan berapa periode simulasi yang harus dijalankan.
Pada periode pertama ( t=0
), empat orang harus dipilih secara acak dan terinfeksi penyakit ini.
Cara penyakit berperilaku diatur oleh aturan berikut:
- Penyakit ini hanya dapat bergerak secara vertikal dan horizontal, pindah ke orang di sebelahnya.
- Infeksi berlangsung selama 3 periode pada setiap orang. Anda tidak boleh memasukkan faktor imunodefisiensi.
- Setelah seseorang terinfeksi tiga kali, mereka kebal dan tidak dapat terinfeksi lagi.
- Penyakit ini tunduk pada mutasi yang membuat orang yang sebelumnya kebal rentan terhadap penyakit mutasi baru ini. Penyakit yang bermutasi memiliki sifat yang persis sama dan mengikuti aturan yang sama dengan penyakit aslinya.
- Jika terjadi mutasi, seluruh penyakit tidak berubah, hanya 'paket' tertentu pada saat transmisi.
- Sekali seseorang telah terinfeksi oleh satu virus, mereka tidak dapat terinfeksi lagi sampai infeksi saat ini lewat.
- Jika seseorang terinfeksi, mereka menular dari awal masa infeksi hingga akhir.
- Tidak ada tingkat kekebalan - seseorang kebal atau tidak.
- Untuk menghentikan kelebihan memori, ada batas maksimum 800 mutasi.
Pada akhir jumlah periode yang ditentukan, Anda harus menampilkan hasilnya.
Hasilnya harus berupa kisi 1000 x 1000 yang menunjukkan orang yang terinfeksi dan mana yang tidak. Ini bisa berupa output sebagai file teks, sebagai file gambar atau output grafis (di mana #FFFFFF adalah orang yang sehat dan # 40FF00 adalah orang yang terinfeksi).
Anda dapat memasukkan nama bahasa dan perintah untuk menjalankannya dalam jawaban Anda.
Kemenangan
Kode tercepat untuk dijalankan di komputer saya menang. Waktunya akan diukur dengan potongan kode Python berikut:
import time, os
start = time.time()
os.system(command)
end = time.time()
print(end-start)
Perhatikan bahwa saat menjalankan skrip ini, saya akan menggunakan default berikut:
Probability of transmission = 1
Chance of mutation = 0.01
Number of periods = 1000
sumber
V
, virus kontrak keduaV'
. Kontraksi keduanya akan berakhir pada periode yang sama. Bisakah virusV
menginfeksi orang kedua? (Atau pertanyaan yang lebih hitam-putih: mungkinkah seseorang terinfeksi segera setelah dia sembuh, sehingga dia akan berakhir dengan 6 periode infeksi berturut-turut?)V
secara langsungA
, danV
lagi secara langsungB
. Ketika mereka menularkan virus, bisakah mereka bermutasi ke mutasi yang samaV'
? Atau mungkin mereka sebenarnya harus bermutasi ke strain virus yang sama? Jika mereka dapat bermutasi secara sewenang-wenang, berapakah probabilitas dua virus bermutasi ke jenis virus yang sama?Jawaban:
Saya ingin tahu seperti apa ini sehingga saya membuat peretasan yang cepat dan kotor ini dalam JavaScript: http://jsfiddle.net/andrewmaxwell/r8m54t9c/
sumber
C ++ 11, 6-8 menit
Uji coba saya memakan waktu 6-8 menit di mesin Fedora 19, i5 saya. Tetapi karena keacakan mutasi, mungkin lebih cepat atau lebih lama dari itu. Saya pikir kriteria penilaian perlu disusun kembali.
Mencetak hasilnya sebagai teks pada akhir penyelesaian, orang sehat dilambangkan dengan titik (
.
), orang yang terinfeksi oleh asterisk (*
), kecuali jikaANIMATE
flag disetel ke true, dalam hal ini akan menampilkan karakter yang berbeda untuk orang yang terinfeksi dengan strain virus yang berbeda.Berikut adalah GIF untuk 10x10, 200 periode.
Perilaku mutasi
Setiap mutasi akan memberikan galur baru yang tidak pernah terlihat sebelumnya (jadi mungkin satu orang menginfeksi empat orang tetangga dengan 4 galur berbeda), kecuali 800 galur telah dihasilkan, dalam hal ini tidak ada virus yang akan mengalami mutasi lebih lanjut.
Hasil 8 menit berasal dari jumlah orang yang terinfeksi berikut:
sedangkan hasil 6 menit berasal dari yang berikut:
Representasi orang
Setiap orang diwakili dalam 205 byte. Empat byte untuk menyimpan jenis virus yang dikontrak oleh orang ini, satu byte untuk menyimpan berapa lama orang ini telah terinfeksi, dan 200 byte untuk menyimpan berapa kali ia telah mengontrak setiap jenis virus (masing-masing 2 bit). Mungkin ada beberapa byte-alignment yang dilakukan oleh C ++, tetapi ukuran totalnya sekitar 200MB. Saya memiliki dua kotak untuk menyimpan langkah selanjutnya, jadi totalnya menggunakan sekitar 400MB.
Saya menyimpan lokasi orang yang terinfeksi dalam antrian, untuk memotong waktu yang diperlukan pada periode awal (yang benar-benar berguna hingga periode <400).
Teknis program
Setiap 100 langkah program ini akan mencetak jumlah orang yang terinfeksi, kecuali jika
ANIMATE
flag ditetapkantrue
, dalam hal ini akan mencetak seluruh grid setiap 100 ms.Ini membutuhkan pustaka C ++ 11 (kompilasi menggunakan
-std=c++11
flag, atau di Mac withclang++ -std=c++11 -stdlib=libc++ virus_spread.cpp -o virus_spread
).Jalankan tanpa argumen untuk nilai default, atau dengan argumen seperti ini:
./virus_spread 1 0.01 1000
sumber
C # 6-7 Menit
Edit 2
Saya akhirnya (5 jam) menghasilkan output verbose untuk hampir 1000 periode (hanya 840 frame kemudian macet) pada 1000x1000, setiap 1 periode, namun hampir 160MB dan membutuhkan semua memori pada sistem saya untuk ditampilkan (IrfanView) , bahkan tidak yakin itu akan berfungsi di browser, mungkin saya akan memasangnya nanti.
EDIT
Saya telah menghabiskan banyak waktu untuk membuat ini lebih efisien per "Beta Decay" s jawaban yang menyatakan "Pilih strain secara acak" Saya hanya memilih metode acak untuk memilih siapa yang menginfeksi siapa per periode, namun saya telah mengubah cara yang dihitung dan utas segala hal, saya telah memperbarui posting saya dengan detail baru.
Kode estimasi terdekat saya untuk ini saya bisa, saya harap ini mengikuti semua aturan, menggunakan banyak memori pada sistem saya (sekitar 1.2GB). Program ini dapat menampilkan gif animasi (terlihat keren, sangat lambat) atau hanya gambar yang cocok dengan spesifikasi "Peluruhan Beta". Ini sedikit menciptakan kembali roda, tetapi jelas terlihat keren:
Hasil
(Catatan: ini hanya membedakan antara yang terinfeksi dan yang tidak terinfeksi, yaitu non-verbose)
1000 Periode, Tingkat Mutasi 1%, Penyebaran 100%:
Contoh (Verbose)
Pokoknya menggunakan 100% "Probabilitas transmisi" dalam mode non-verbose agak membosankan karena Anda selalu mendapatkan bentuk yang sama dan Anda tidak dapat melihat mutasi yang berbeda, jika Anda mengubah parameter sekitar a-bit (dan mengaktifkan mode verbose) Anda mendapatkan beberapa output keren (tampilan GIF animasi setiap frame 10):
Acak - Ukuran Kotak: 200, ProbTransmission: 100%, ProbMutation: 1%
Acak - Ukuran Kotak: 200, ProbTransmisi: 20%, ProbMutasi: 1%
Mencetak gol
Saya setuju dengan "justhalf" bahwa kriteria penilaian mungkin tidak adil karena setiap putaran akan berbeda karena keacakan mutasi dan posisi titik awal acak. Mungkin kita bisa melakukan rata-rata beberapa kali berjalan atau semacamnya ..., yah bagaimanapun ini ada di C # jadi hadiah bagi saya :( pokoknya.
Kode
Pastikan untuk menyertakan pustaka MagickImage (atur untuk mengkompilasi bit x64) jika tidak, pustaka itu tidak akan dibuat ( http://pastebin.com/vEmPF1PM ):
sumber