Write the following functions by using python

1. regain(world, cityno). This function takes your world (list of cities) as the parameter world and an integer cityno specifying which city in the list has been regained from the enemy. So, to have city 2 be regained, you might use the function like this:

>>> my_world = set_up_cities() >>> regain(my_world, 2)

How do you “regain” a city? Well you have to set the “regained flag” for that city to True. In other words, set world[cityno][1] to True. The [cityno] indexes a particular city in the list of cities (world) and the following [1] indexes the second element (remember, the first element is [0]!) in the list that makes up that city description.

2. lose(world, cityno). The opposite of regain. Clear the regained flag for the city.

3. sim_step(world, p_regain, p_lose). This is the most important function in the assignment. This function will execute a single time step of your simulation. Depending on how fast you want to think of the operation continuing, that time step could be a day, an hour, a week, whatever. If you were modelling a real operation, you’d determine the size of your time step from some empirical data. Here is some English-language “pseudocode” for function. You’ll have to turn it into Python

for each city in world:   if the city is lost and numpy.random.rand() < p_regain:    regain the city!   if the city is lost and numpy.random.rand() < p_lose    randomly choose a *different* city connected along the enemy network (neighbouring cities)     (hint: use numpy.random.randint() and get_cityno() or is_connected())    lose the city! Make sure that city 0 is *always* regained (our stronghold). It can't be lost.

So, what’s going on there? Well, numpy.random.rand() isn’t so much pseudocode as actual Python code. It generates a random number between 0 and 1 every time you call it. Think of it like rolling dice. The parameter p_regain is the probability of regaining control of the city, and the parameter p_lose is the probability of losing a city to the enemy. For starters use values of 0.5 for p_regain and 0.0 for p_lose while you’re getting things working. We’ll play with these later.

Once you’ve done this, you now have a working Operation Save the World simulator! So spend some time testing it in the Python interpreter. Something like this:

>>> my_world = set_up_cities() >>> regain(my_world,0) >>> draw_world(my_world) >>> sim_step(my_world, 0.5, 0) >>> draw_world(my_world) >>> sim_step(my_world,0.5, 0) >>> draw_world(my_world) >>> sim_step(my_world, 0.5, 0)

The function draw_world() is one that’s already written for you. It graphically displays the state of your world. Cities are green circles if they are regained and red circles if they’re lost. If the enemy network connects two cities, there is a line drawn between the cities. If you update this display after each sim_step you can watch the operation happen! It’ll look something like this:

If you get tired of typing sim_step for every single step…you could always automate the process with a function that calls sim_step in a loop!

Once you’re convinced that your operation simulator works, move on to Part 2. If your simulator isn’t working yet GET IT WORKING BEFORE PROCEEDING.

Working now? Good. Make sure it’s commented and has function headers.

Coding, Part 2

As fun as it is to watch our operation being carried out, we’d like to gather some hard data on the results of our simulations. In particular, the leaders of the resistance force want to know how long it will take to regain all the cities in the world.

Write the following functions:

4. is_world_saved(world). Loop through all the cities in the list world. If all of them are regained, return True (victory!). Otherwise, return False.

5. time_to_save_world(world, p_regain, p_lose). Run a simulation, for specific values of p_regain and p_lose and count how long it takes to save the world (which you can now test with is_world_saved, of course). Some pseudocode for you:

reset the world (all cities are lost except city 0) initialize a "regained-world" counter       while the world hasn't been regained:               sim_step(world, p_regain, p_lose)               increment the regained-world counter       return the value of the regained-world counter

Now, after we have set up a world using

>>> my_world = set_up_cities()

to run an experiment to see how long it takes to save the world, all we have to do is:

>>> time_to_save_world(my_world,0.5,0)

We’ve got a problem though. Our simulation is stochastic: we are making use of random numbers to determine outcomes. We can’t just run our simulation once and count the number of steps until every city is regained. If you don’t believe me, just try it. Call the time_to_save_world function a few times. Do you get different values? Wildly different? Yeah.

We have to run our simulation many times to fairly sample the space of possible outcomes. In essence, simulation is a lot like experimentation; we have to do multiple experiments to get some statistical confidence in our answer.

So, write another function:

6. save_world_many_times(world, n, p_regain, p_lose). This function should initialize a list of results and then use a loop to run time_to_save_world(world, p_regain, p_lose) a total of n times. After each simulation, add the time it took to save the world to the list. Return a list of n “times to save the world”.