Using Python. Write a program that takes as input an $88$ matrix where each element could be $\text{'}s\text{'}($a space$)$ or $\text{'}w\text{'}($a wall$),$ and

exactly one element is $\text{'}$o$\text{'}($the origin$),$ and exactly one element is $\text{'}$d$\text{'}($the destination$),$ and does the following:

$($a$)$ Assuming the grid is numbered $1-64($starting left to right, top to bottom in sequence$),$ creates a vector of

states.

$($b$)$ Generates $4$ transition matrices, one for each direction of movement. Movements are possible only between

spaces. Note that any action that moves across a wall or out of the grid would result in no movement $($staying

in the same space$).$

$($c$)$ For a policy that randomly chooses each direction with equal likelihood, computes the average number of steps

it takes to move from the origin to the destination.

$($d$)($extra credit$)$ Add as inputs to your code, a policy $p=(p_u,p_d,p_r,p_t)$ where $p_u$ is the probability by which

$\text{'}$up$\text{'}$ is the action, $p_d$ probability of moving one step down, $p_l$ probability of moving one step to the left, and

$p_r$ the probability of moving one step to the right, and compute the average number of steps to get from the

origin to the destination.

Execute your code for the following maze grid:

In a written report, describe clearly and mathematically how you developed the Markov chain for the problem and

explain using an example executed using your code.