This blog post is a write-up of Frog in Maze on HackerRank.

Problem Statement

Input

A map like the one below.

Output

The probability that Alef will exit the dungeon.

Rules

Alef

Alef moves in any of the four directions (up, down, left, and right) at the same probability.

Tunnel

If Alef moves to one of the ends of a tunnel, he will warp to the other end.

Blockage

Alef cannot go into a cell with a blockage.

Mine

Alef dies when he moves to a cell with a mine.

Insights

Each cell has a different probability of life

Alef in the left map will safely exit from the dungeon at the probability of 3/4 in the first move. Even if he goes to the right in the first move, he may come back and exit in the successive moves. On the other hand, Alef on the right map will die at the probability of 1/4 in the first move. So, each cell has a different probability of life.

Calculate the Probability of Life for Each Cell

Let $p_{i, j}$ be the probability of life at the cell $(i, j)$, meaning the probability that Alef will exit safely starting his move from that cell. $p_{i, j}$ can be computed as follows:$(i, j)$ is an exit cell: $p_{i, j} = 1$

• $(i, j)$ is a mine cell: $p_{i, j} = 0$
• $(i, j)$ is an empty cell: $p_{i, j} = \sum_{\text{adjacent cells}} p_{\text{adjacent cell}}$.

We can obtain $p_{1,1}$ and $p{1, 2}$ from the following simultaneous equations:

$$
\left\{
\begin{aligned}
p_{1,1} &= \frac{3}{4} + \frac{1}{4}p_{1, 2}\\
p_{1,2} &= \frac{1}{4}p_{1,1}
\end{aligned}
\right.
$$

$p_{1,1} = \frac{4}{5}, p_{1,2} = \frac{1}{5}$. Notice that we do not have to include unreachable cells into the simultaneous equations.

Tunnels

We know that Alef will escape from the dungeon below with the probability of 1. By thinking about it, we can conclude that when you calculate the probability of a cell with an entrance to a tunnel, you should consider the adjacent cells of the other end.

So, the simultaneous equations will be as follows:

$$
\left\{
\begin{aligned}
p_{0, 0} &= p_{1, 0}\\
p_{1, 0} &= 1
\end{aligned}
\right.
$$

Here is the maze after calculating the probabilities.

Gaussian Elimination

To calculate the answer to the system of linear equations, you can use Gaussian elimination.