A python program needs to be written on random walk and timer. Basically a person starts at a certain location and that point is given a probability of 1. They need to make it to the exit point. So only 50% can leave it.

input is a dict where each key is a location in the woods and the values are path options that lead to the next possible location.

The input for the first walk is like this:

{0:[1,2], 1:[0,2], 2:[0,1]} 

Everyone starts at 0 end the exit is alway the max(woods.keys())-->the biggest key.

So 100 % (1.00) of the initial population starts at location 0: --> they are all trying to get out of the woods since they are lost. Every walk is equal to 1 minute and a walk is defined as moving from location A to location B.

run 1:

So at location 0 we have 2 path options either we can go to location 1 or to location 2 (the exit)

there is a 50% (1.00x1/2=0.50) chance we choose the most optimal path.

So 50% of the people were able to get out of the forest in 1 walk so in 1 min.

run 2:

Since 50% were able to get out there are still 50% of the people that are still lost and the are at location 1.

From the individuals the portion of people still lost the other 50% they have 2 path otptions. (0 or 2)

They have 50% chance of choosing the most optimal one so half of this group will be able to get out and the other half will still be lost.

run 3:

now 1/4 of the initial group that are still lost and at location 0.

...

We repeat these steps 1000 times, and compute the average time it takes for everyone to get out.

from typing import Dict, List

def lost(woods: Dict[int, List[int]]) -> float:

'''return the expected value of the number of minutes it will take a lost personto get out of the woods represented by the dictionary woods

>>>print(lost({0:[1,2], 1:[0,2], 2:[0,1]}))

>>>2.0

>>>print(lost({0:[1,2], 1:[0,3], 2:[0,4], 3:[1,4], 4:[2,3]}))

>>>6.0

>>>print(lost({0:[1,2,3], 1:[0,2], 2:[0,1,4], 3:[0,4], 4:[2,3]}))

>>>6.727273

>>>print(lost({0:[1,2,3], 1:[0,3], 2:[0], 3:[0,1]}))

>>>3.333333

'''

HINTS

Use 2 lists:

main_storage=[]

update=[]

The first represent the starting stats of the problem. The index at which the element is placed represents the amount of people that are at the location of that index.

Then apply all the changes that you store in update.

Finally just update main_storage=update.copy()

ex : at the start for walk 1:

population: [1,0,0]

location :0 1 2

population us the main_storage

so then you apply all changes to update

update:[0,0.5,0.5]

location :012

youu remove the amount of people who got out.

update:[0,0.5,0]

finally you store everything

main_storage =update.copy()

and you can clear update of 1