Desafío
Debe crear un modelo simple de cómo la enfermedad se propaga alrededor de un grupo de personas.
Reglas y requisitos
El modelo debe ser una matriz 2D de 1000 por 1000 y cada elemento debe ser una persona diferente.
El usuario debe ingresar tres variables utilizando argv: la probabilidad de transmisión (la probabilidad de que alguien infecte a otra persona), la probabilidad de mutación y durante cuántos períodos debe ejecutarse la simulación.
En el primer período ( t=0
), cuatro personas deben ser elegidas al azar e infectadas con la enfermedad.
La forma en que se comporta la enfermedad se rige por las siguientes reglas:
- La enfermedad solo puede moverse verticalmente y horizontalmente, pasando a la persona de al lado.
- La infección dura 3 períodos en cada persona. No puede tener en cuenta las inmunodeficiencias.
- Después de que una persona ha sido infectada tres veces, es inmune y no puede volver a infectarse.
- La enfermedad está sujeta a mutaciones, lo que hace que las personas previamente inmunes sean vulnerables a esta nueva enfermedad mutada. La enfermedad mutada tiene exactamente los mismos rasgos y sigue las mismas reglas que la enfermedad original.
- Si se produce una mutación, toda la enfermedad no cambia, solo ese "paquete" particular tras la transmisión.
- Una vez que una persona ha sido infectada por un virus, no puede volver a infectarse hasta que pase la infección actual.
- Si una persona está infectada, es infecciosa desde el comienzo de su período de infección hasta su final.
- No hay niveles de inmunidad: una persona es inmune o no.
- Para detener la sobrecarga de memoria, hay un límite máximo de 800 mutaciones.
Al final del número especificado de períodos, debe generar los resultados.
Los resultados deben ser una cuadrícula de 1000 x 1000 que muestre qué personas están infectadas y cuáles no. Esto se puede generar como un archivo de texto, como un archivo de imagen o una salida gráfica (donde #FFFFFF es una persona sana y # 40FF00 es una persona infectada).
¿Puede incluir el nombre del idioma y un comando para ejecutarlo en su respuesta?
Victorioso
El código más rápido para ejecutar en mi computadora gana. Su tiempo se medirá con el siguiente código de Python:
import time, os
start = time.time()
os.system(command)
end = time.time()
print(end-start)
Tenga en cuenta que al ejecutar este script, usaré los siguientes valores predeterminados:
Probability of transmission = 1
Chance of mutation = 0.01
Number of periods = 1000
fuente
V
, el segundo contrae virusV'
. La contracción terminará en el mismo período. ¿El virus puedeV
infectar a la segunda persona? (O una pregunta más en blanco y negro: ¿es posible que una persona se infecte inmediatamente después de curarse, por lo que terminará con 6 períodos consecutivos de infección?)V
en personaA
, yV
nuevamente en personaB
. Cuando transmiten el virus, ¿pueden ambos mutar a la misma mutaciónV'
? ¿O tal vez de hecho deberían mutar a la misma cepa de virus? Si pueden mutar arbitrariamente, ¿cuál es la probabilidad de que dos virus muten a la misma cepa de virus?Respuestas:
Tenía curiosidad de cómo se vería, así que hice este truco rápido y sucio en JavaScript: http://jsfiddle.net/andrewmaxwell/r8m54t9c/
fuente
C ++ 11, 6-8 minutos
Mi ejecución de prueba tarda unos 6-8 minutos en mi máquina Fedora 19, i5. Pero debido a la aleatoriedad de la mutación, bien podría ser más rápido o tomar más tiempo que eso. Creo que los criterios de puntuación deben ser reorientados.
Imprime el resultado como texto al final de la finalización, persona sana indicada por punto (
.
), persona infectada por asterisco (*
), a menos queANIMATE
indicador se establezca en verdadero, en cuyo caso mostrará diferentes caracteres para las personas infectadas con una cepa de virus diferente.Aquí hay un GIF para 10x10, 200 períodos.
Comportamiento de mutación
Cada mutación dará una nueva cepa nunca antes vista (por lo que es posible que una persona infecte a las cuatro personas vecinas con 4 cepas distintas), a menos que se hayan generado 800 cepas, en cuyo caso ningún virus continuará con ninguna mutación.
El resultado de 8 minutos proviene del siguiente número de personas infectadas:
mientras que el resultado de 6 minutos proviene de lo siguiente:
Representación de la persona
Cada persona está representada en 205 bytes. Cuatro bytes para almacenar el tipo de virus que esta persona está contrayendo, un byte para almacenar cuánto tiempo ha estado infectada esta persona y 200 bytes para almacenar cuántas veces ha contraído cada cepa de virus (2 bits cada uno). Quizás haya una alineación de bytes adicional realizada por C ++, pero el tamaño total será de alrededor de 200 MB. Tengo dos cuadrículas para almacenar el siguiente paso, por lo que en total usa alrededor de 400 MB.
Guardo la ubicación de las personas infectadas en una cola, para reducir el tiempo requerido en los primeros períodos (que es realmente útil hasta períodos <400).
Tecnicismos del programa
Cada 100 pasos, este programa imprimirá el número de personas infectadas, a menos que la
ANIMATE
marca esté configuradatrue
, en cuyo caso imprimirá la cuadrícula completa cada 100 ms.Esto requiere bibliotecas C ++ 11 (compilar usando
-std=c++11
flag, o en Mac conclang++ -std=c++11 -stdlib=libc++ virus_spread.cpp -o virus_spread
).Ejecútelo sin argumentos para los valores predeterminados, o con argumentos como este:
./virus_spread 1 0.01 1000
fuente
C # 6-7 minutos
Editar 2
Finalmente (5 horas) generé una salida detallada durante cerca de 1000 períodos (solo 840 cuadros luego se bloqueó) a 1000x1000, cada 1 período, sin embargo, está cerca de 160 MB y requiere toda la memoria en mi sistema para visualizarse (IrfanView) , ni siquiera estoy seguro de que funcionaría en un navegador, puedo instalarlo más tarde.
EDITAR
He dedicado mucho tiempo a hacer esto más eficiente según la respuesta de "Beta Decay" que dice "Elija la cepa al azar". He elegido solo el método aleatorio para elegir quién infecta a quién por período, sin embargo, he cambiado la forma en que se calcula y enhebrando todo, he actualizado mis publicaciones con los nuevos detalles.
Codifiqué mi estimación más cercana a esto que pude, espero que siga todas las reglas, use una tonelada de memoria en mi sistema (aproximadamente 1.2 GB). El programa puede generar gifs animados (se ve genial, muy lento) o simplemente una imagen que coincida con las especificaciones de "Beta Decay". Esto es un poco reinventar la rueda, pero definitivamente se ve genial:
Resultados
(Nota: esto solo diferencia entre infectados y no infectados, es decir, no detallados)
1000 períodos, 1% de tasa de mutación, 100% de propagación:
Ejemplos (detallados)
De todos modos, usar el 100% de "Probabilidad de transmisión" en modo no detallado es algo aburrido, ya que siempre obtienes las mismas formas y no puedes ver las diferentes mutaciones, si ajustas los parámetros alrededor de un bit (y habilitas el modo detallado) obtienes un resultado atractivo (los GIF animados se muestran cada 10 cuadros):
Aleatorio - Tamaño de cuadrícula: 200, transmisión de prob: 100%, mutación de prob: 1%
Aleatorio - Tamaño de cuadrícula: 200, transmisión de prob: 20%, mutación de prob: 1%
Puntuación
Estoy de acuerdo con "solo" que los criterios de puntuación pueden no ser justos ya que cada carrera será diferente debido a la aleatoriedad de las mutaciones y la posición de los puntos de inicio aleatorios. Tal vez podríamos hacer un promedio de varias carreras o algo así ... bueno, de todos modos esto está en C #, así que recompensa para mí :( de todos modos.
Código
Asegúrese de incluir la biblioteca MagickImage (configurada para compilar x64 bit) de lo contrario no se compilará ( http://pastebin.com/vEmPF1PM ):
fuente