HackerRank Frog in Maze problem solution

In this HackerRank Frog in Maze problem solution Alef, the Frog is in an n x m two-dimensional maze represented as a table. each cell can be free or can contain an obstacle, an exit, or a mine. any two cells in the table are considered adjacent if they share a side. the maze is surrounded by a solid wall made of obstacles. some pairs of free cells are connected by a bidirectional tunnel. we need to write a program that calculates and prints a probability that Alef escapes the maze

HackerRank Frog in Maze problem solution

Problem solution in Python.

#!/bin/python3

import sys

from collections import deque

def ismine(char):
  return char == '*'

def isexit(char):
  return char == '%'

def isopen(char):
  return char == 'A' or char == 'O'

def isobstacle(char):
  return char == '#'

def probability(node):
  if ismine(node): # mine
    return 0.0
  if isexit(node): # exit
    return 1.0
  # if tunnel(node) != None: # tunnel

def getneighbs(node):
  # print("Getting neighbs for",node)
  global n,m,tunnels
  i0,j0 = node
  dirs = [(0,1),(1,0),(-1,0),(0,-1)]
  out = []
  for di, dj in dirs:
    i,j = i0+di, j0+dj
    if i < 0 or i >= n:
      continue
    if j < 0 or j >= m:
      continue
    if (i,j) in tunnels:
      i,j = tunnels[(i,j)]
    ch = mat[i][j]
    if isobstacle(ch):
      continue
    out.append(mapping[(i,j)])
  return out

def matmult(m, times): # m is square
  if times == 0:
    return m
  n = len(m)
  newm = [[sum(a*b for a,b in zip(X_row,Y_col) if a != 0 and b!= 0) for Y_col in zip(*m)] for X_row in m]
  return matmult(newm, times - 1)

n, m, k = map(int,input().strip().split(' '))
mat = [[None for _ in range(m)] for _ in range(n)]
mapping = {} # maps (i,j) to a row/col in our move matrix
reversemapping = {} # maps a node to (i,j)
MAP_MINE = -2
MAP_EXIT = -1
MAP_START = 0
next_open = 1

def pmat(m):
  return True
  print("---")
  for r in m:
    print(" ".join(["%0.2f"%v for v in r]))

def mygauss(m):
    #eliminate columns
    for col in range(len(m[0])):
        for row in range(col+1, len(m)):
            r = [(rowValue * (-(m[row][col] / m[col][col]))) for rowValue in m[col]]
            m[row] = [sum(pair) for pair in zip(m[row], r)]
    #now backsolve by substitution
    ans = []
    m.reverse() #makes it easier to backsolve
    for sol in range(len(m)):
            if sol == 0:
                ans.append(m[sol][-1] / m[sol][-2])
            else:
                inner = 0
                #substitute in all known coefficients
                for x in range(sol):
                    inner += (ans[x]*m[sol][-2-x])
                #the equation is now reduced to ax + b = c form
                #solve with (c - b) / a
                ans.append((m[sol][-1]-inner)/m[sol][-sol-2])
    ans.reverse()
    return ans
  
for i in range(n):
    row = input().strip()
    for j, char in enumerate(row):
      mat[i][j] = char
      if isobstacle(char):
        continue
      if char == 'A':
        node = MAP_START
        reversemapping[node] = (i,j)
      elif ismine(char):
        node = MAP_MINE
      elif isexit(char):
        node = MAP_EXIT
      else: # open
        node = next_open
        reversemapping[node] = (i,j)
        next_open += 1
      mapping[(i,j)] = node
#print(mapping)
tunnels = {}
for a0 in range(k):
    i1, j1, i2, j2 = map(lambda x: int(x) - 1, input().strip().split(' '))
    tunnels[(i1,j1)] = (i2,j2)
    tunnels[(i2,j2)] = (i1,j1)
nodes = next_open + 2
transitions = [[0 for _ in range(nodes)] for _ in range(nodes)] # transitions[i][j] is probability of ending up at j from i
transitions[MAP_MINE][MAP_MINE] = 1 # try zero to make it disappear from probailities
transitions[MAP_EXIT][MAP_EXIT] = 1
for i in range(nodes - 2):
  neighbs = getneighbs(reversemapping[i])
  opts = len(neighbs)
  if opts == 0:
    # leave at zero to make it disappear from the probabilities
    # transitions[i][i] = 1
    continue
  for j in neighbs:
    transitions[i][j] += 1 / opts
# make the transitions matrix all in upper-right quadrant (drive to the end)
for i in range(nodes):
  for j in range(nodes):
    if j < i: # back-transition, substitute that row here
      p = transitions[i][j]
      if p > 0:
        # print(i,j)
        transitions[i][j] = 0
        transitions[i] = [transitions[i][k] + p*transitions[j][k] for k in range(nodes)]
    if j == i and i < nodes-2: # move on, except end goals
      p = transitions[i][j]
      if p > 0: # if we get back to here, distribute that among the other probs
        transitions[i][j] = 0
        for k in range(j+1,nodes):
          if transitions[i][k] > 0:
            transitions[i][k] /= (1-p)
pmat(transitions)
# now fully cancel out row 0 except for endpoints
for i in range(1,nodes-2):
  p = transitions[0][i]
  if p > 0:
        transitions[0][i] = 0
        for k in range(i+1,nodes):
          transitions[0][k] += p*transitions[i][k]
    
# transitions = mygauss(transitions)
pmat(transitions)
print(transitions[0][MAP_EXIT])

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

import java.util.Arrays;

public class Solution002 {
        static final int EXIT = Integer.MAX_VALUE;
        public static void main(String[] args) {
                java.util.Scanner sc = new java.util.Scanner(System.in);
                int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
                sc.nextLine();
                int[][] nextAry2 = new int[n + 2][m + 2];
                int[][] ids = new int[n + 2][m + 2];
                int ax = -1, ay = -1, id = 0;
                for (int i = 1; i <= n; ++i) {
                        char[] typeLine = sc.nextLine().toCharArray();
                        for (int j = 1; j <= m; ++j) {
                                switch (typeLine[j - 1]) {
                                case '*':
                                        nextAry2[i][j] = 1;
                                        break;                                        
                                case '#':
                                        nextAry2[i][j] = 0;
                                        break;
                                case '%':
                                        nextAry2[i][j] = EXIT;
                                        break;
                                case 'A':
                                        ax = i;
                                        ay = j;
                                default:
                                        nextAry2[i][j] = (i << 16) | j;
                                }
                        }
                }
                for (int i = 0; i < k; ++i) {
                        int x0 = sc.nextInt(), y0 = sc.nextInt(), x1 = sc.nextInt(), y1 = sc.nextInt();
                        nextAry2[x0][y0] = (x1 << 16) | y1;
                        nextAry2[x1][y1] = (x0 << 16) | y0;
                }
                for (int i = 1; i <= n; ++i)
                        for (int j = 1; j <= m; ++j) 
                                ids[i][j] = nextAry2[i][j] > 1 ? id++ : -1;
                                
                double[][] T = new double[id][id];
                for (int i = 1; i <= n; ++i) {
                        int[] nextAry2i = nextAry2[i];
                        int[] idi = ids[i];
                        for (int j = 1; j <= m; ++j) {
                                int cid = idi[j];
                                if (idi[j] < 0) continue;
                                int v = nextAry2i[j];
                                if (v != EXIT) {
                                        int a=v>>16,b=v&0xffff;
                                        if(a!=i || b!=j) {
                                                a = i;
                                                b = j;
                                        }                                                
                                        int w0 = nextAry2[a][b - 1], w1 = nextAry2[a - 1][b], w2 = nextAry2[a][b + 1],w3 = nextAry2[a + 1][b];
                                        int c = (w0 > 0 ? 1 : 0) + (w1 > 0 ? 1 : 0) + (w2 > 0 ? 1 : 0) + (w3 > 0 ? 1 : 0);
                                        if (c == 0) continue;
                                        double c1 = 1.0 / c;
                                        if(w0==EXIT) T[cid][ids[a][b-1]] = c1; else if(w0 > 1) T[cid][ids[w0 >> 16][w0 & 0xffff]] = c1;
                                        if(w1==EXIT) T[cid][ids[a-1][b]] = c1; else if (w1 > 1) T[cid][ids[w1 >> 16][w1 & 0xffff]] = c1;
                                        if(w2==EXIT) T[cid][ids[a][b+1]] = c1; else if (w2 > 1) T[cid][ids[w2 >> 16][w2 & 0xffff]] = c1;
                                        if(w3==EXIT) T[cid][ids[a+1][b]] = c1; else if (w3 > 1) T[cid][ids[w3 >> 16][w3 & 0xffff]] = c1;
                                        continue;
                                }
                                T[cid][cid] = 1.0;
                        }
                }
        //        print(T);        
                double[][] TP = pow(T, id, 0x10000L);
                int ida = ids[ax][ay];
                double rs = 0;
                for (int i = 1; i <= n; ++i)
                        for (int j = 1; j <= m; ++j)
                                if (nextAry2[i][j] == EXIT) rs += TP[ida][ids[i][j]];
        //        print(TP);
                System.out.println(rs);
        }
        public static void print(double[][] x) {
                System.out.println("[");
                for(int i=0;i<x.length;++i) {
                        if(i!=0) {
                                System.out.print(",");
                        }
                        System.out.println(Arrays.toString(x[i]));
                }
                System.out.println("]");
                
                for (int i = 0; i < x.length; ++i) {
                        if (i > 0) {
                                System.out.println("n");
                        }
                        for (int j = 0; j < x[i].length; ++j) {
                                if (j > 0) {
                                        System.out.print(' ');
                                }
                                System.out.print(String.format("%.20f", x[i][j]));
                        }
                }

                System.out.println();
                System.out.println("----------------");
                System.out.println();
        }
        
        static void print(Object...args) {
                System.out.println(Arrays.toString(args));
        }
        
        static void mul(double[][] A, double[][] B, double[][] R, int n) {
                for (int i = 0,k=0; i < n; i++) {
                        double[] Ri = R[i],Ai = A[i];
                        for (int j = 0; j < n; j++)
                                for (k =0, Ri[j]=0; k < n; k++) Ri[j] += Ai[k] * B[k][j];
                }
        }
        static double[][] pow(double[][] A, int n, long p) {
                double[][] C = new double[n][n],R = new double[n][n], t = null;
                for (int i = 0; i < n; i++) R[i][i] = 1;
                while (p != 0) {
                        if (p % 2 == 1) {
                                mul(A, R, C, n);
                                t = C;
                                C = R;
                                R = t;
                        }
                        mul(A, A, C, n);
                        t = C;
                        C = A;
                        A = t;
                        p >>= 1;
                }
                return R;
        }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#include<cstdio>

char M[25][25]; // map
int T[25][25][2]; // tunnels
double P[2][25][25];

const int D[4][2] = {{-1,0}, {1, 0}, {0,-1}, {0,1}};
int h,w,t;

void calc(int in, int out) {
    for(int x=0;x<w;x++)
        for(int y=0;y<h;y++) {
            if(M[y][x] == '*' || M[y][x] == '#')
                P[out][y][x] = 0.0;
            if(M[y][x] == '%')
                P[out][y][x] = 1.0;
            if(M[y][x] == 'O' || M[y][x] == 'A') {
                int count = 0; double suma = 0.0;
                int px=x, py=y;
                if(T[y][x][0] != -1) {px = T[y][x][0]; py = T[y][x][1];}
                
                for(int i=0;i<4;i++) {
                    int x2 = px+D[i][0], y2 = py + D[i][1];
                    if(x2 < 0 || x2 >= w || y2 < 0 || y2 >= h)continue;
                    if(M[y2][x2] == '#')continue;
                    suma += P[in][y2][x2];
                    count++;
                }
                if(count == 0)
                    P[out][y][x] = 0.0;
                else P[out][y][x] = suma / count;
            }
        }
}

double get_ans(int p) {
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            if(M[i][j] == 'A')
                return P[p%2][i][j];
    return -1.0;
}

int main() {
    scanf("%d%d%d", &h, &w, &t);
    
    for(int i=0;i<h;i++)
        scanf("%s", M[i]);
    
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            T[i][j][0] = T[i][j][1] = -1;
    
    for(int i=0;i<t;i++){
        int x0, y0, x1, y1;
        scanf("%d%d%d%d", &y0, &x0, &y1, &x1);
        x0--;y0--;x1--;y1--;
        T[y0][x0][0] = x1;
        T[y0][x0][1] = y1;
        T[y1][x1][0] = x0;
        T[y1][x1][1] = y0;
    }

    const int limit = 80000;
    
    for(int i=0;i<limit;i++) {
        calc(i%2, (i+1)%2);
        // for(int y=0;y<h;y++){
        //     for(int x=0;x<w;x++)printf("%.3lf|", P[(i+1)%2][y][x]);
        //     printf("n");
        // } printf("n");
        //printf("%lfn", get_ans(i+1));
    }
    printf("%lfn", get_ans(limit));
    
    
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DOUBLES 10
#define REPS 100

char* readline();
char** split_string(char*);

struct room{
    bool isexit;
};

double escapeMaze(int n, int m, char** maze, int k, int** tunnels){
    double transmat[n][m][n][m];
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            for(int c = 0; c < n; c++){
                for(int d = 0; d < m; d++){
                    transmat[a][b][c][d] = 0;
                }
            }
        }
    }

    double prob[REPS + 1][n][m];
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            prob[0][a][b] = 0;
            if(maze[a][b] == 'A'){
                prob[0][a][b] = 1;
            }
            if(maze[a][b] == '%'){
                transmat[a][b][a][b] = 1;
            }
            else if(maze[a][b] != '*'){
                int numdirs = 0;
                if(a > 0 && maze[a - 1][b] != '#'){
                    numdirs++;
                }
                if(a < n - 1 && maze[a + 1][b] != '#'){
                    numdirs++;
                }
                if(b > 0 && maze[a][b - 1] != '#'){
                    numdirs++;
                }
                if(b < m - 1 && maze[a][b + 1] != '#'){
                    numdirs++;
                }

                if(numdirs > 0){
                    double prob = ((double)1)/numdirs;
                    if(a > 0 && maze[a - 1][b] != '#'){
                        transmat[a][b][a - 1][b] = prob;
                    }
                    if(a < n - 1 && maze[a + 1][b] != '#'){
                        transmat[a][b][a + 1][b] = prob;
                    }
                    if(b > 0 && maze[a][b - 1] != '#'){
                        transmat[a][b][a][b - 1] = prob;
                    }
                    if(b < m - 1 && maze[a][b + 1] != '#'){
                        transmat[a][b][a][b + 1] = prob;
                    }
                }
            }
        }
    }

    for(int i = 0; i < k; i++){
        int i1 = tunnels[i][0] - 1;
        int j1 = tunnels[i][1] - 1;
        int i2 = tunnels[i][2] - 1;
        int j2 = tunnels[i][3] - 1;
        double temp;
        for(int a = 0; a < n; a++){
            for(int b = 0; b < m; b++){
                temp  = transmat[i1][j1][a][b];
                transmat[i1][j1][a][b] = transmat[i2][j2][a][b];
                transmat[i2][j2][a][b] = temp;
            }
        }
    }

    double transpow[DOUBLES + 1][n][m][n][m];
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            for(int c = 0; c < n; c++){
                for(int d = 0; d < m; d++){
                    transpow[0][a][b][c][d] = transmat[a][b][c][d];
                }
            }
        }
    }

    for(int i = 0; i < DOUBLES; i++){
        for(int a = 0; a < n; a++){
            for(int b = 0; b < m; b++){
                if(maze[a][b] == 'A' || maze[a][b] == 'O'){
                    for(int c = 0; c < n; c++){
                        for(int d = 0; d < m; d++){
                            transpow[i + 1][a][b][c][d] = 0;
                            for(int e = 0; e < n; e++){
                                for(int f = 0; f < m; f++){
                                    transpow[i + 1][a][b][c][d] += transpow[i][a][b][e][f] * transpow[i][e][f][c][d];
                                }
                            }
                        }
                    }
                }
                else if(maze[a][b] == '#'){
                    for(int c = 0; c < n; c++){
                        for(int d = 0; d < m; d++){
                            transpow[i + 1][a][b][c][d] = 0;
                        }
                    }
                }
                else if(maze[a][b] == '%' || maze[a][b] == '*'){
                    for(int c = 0; c < n; c++){
                        for(int d = 0; d < m; d++){
                            transpow[i + 1][a][b][c][d] = 0;
                        }
                    }
                    transpow[i + 1][a][b][a][b] = 1;
                }
            }
        }
    }

    for(int i = 0; i < REPS; i++){
        for(int a = 0; a < n; a++){
            for(int b = 0; b < m; b++){
                prob[i + 1][a][b] = 0;
                for(int c = 0; c < n; c++){
                    for(int d = 0; d < m; d++){
                        prob[i + 1][a][b] += transpow[DOUBLES][c][d][a][b] * prob[i][c][d];
                    }
                }
            }
        }
    }

    double toprint = 0;
    for(int a = 0; a < n; a++){
        for(int b = 0; b < m; b++){
            if(maze[a][b] == '%'){
                toprint += prob[REPS][a][b];
            }
        }
    }
    return toprint;
}

int main()
{
    char** nmk = split_string(readline());

    char* n_endptr;
    char* n_str = nmk[0];
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

    char* m_endptr;
    char* m_str = nmk[1];
    int m = strtol(m_str, &m_endptr, 10);

    if (m_endptr == m_str || *m_endptr != '') { exit(EXIT_FAILURE); }

    char* k_endptr;
    char* k_str = nmk[2];
    int k = strtol(k_str, &k_endptr, 10);

    if (k_endptr == k_str || *k_endptr != '') { exit(EXIT_FAILURE); }

    char** maze = malloc(n*sizeof(char*));

    for (int n_itr = 0; n_itr < n; n_itr++) {
        char* row = readline();

        maze[n_itr] = row;
    }

    int** tunnels = malloc(k*sizeof(int*));
    for (int k_itr = 0; k_itr < k; k_itr++) {
        char** i1J1I2J2 = split_string(readline());

        char* i1_endptr;
        char* i1_str = i1J1I2J2[0];
        int i1 = strtol(i1_str, &i1_endptr, 10);

        if (i1_endptr == i1_str || *i1_endptr != '') { exit(EXIT_FAILURE); }

        char* j1_endptr;
        char* j1_str = i1J1I2J2[1];
        int j1 = strtol(j1_str, &j1_endptr, 10);

        if (j1_endptr == j1_str || *j1_endptr != '') { exit(EXIT_FAILURE); }

        char* i2_endptr;
        char* i2_str = i1J1I2J2[2];
        int i2 = strtol(i2_str, &i2_endptr, 10);

        if (i2_endptr == i2_str || *i2_endptr != '') { exit(EXIT_FAILURE); }

        char* j2_endptr;
        char* j2_str = i1J1I2J2[3];
        int j2 = strtol(j2_str, &j2_endptr, 10);

        if (j2_endptr == j2_str || *j2_endptr != '') { exit(EXIT_FAILURE); }

        tunnels[k_itr] = malloc(4*sizeof(int));
        tunnels[k_itr][0] = i1;
        tunnels[k_itr][1] = j1;
        tunnels[k_itr][2] = i2;
        tunnels[k_itr][3] = j2;
    }
    printf("%f", escapeMaze(n, m, maze, k, tunnels));

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

{“mode”:”full”,”isActive”:false}