HackerRank Frog in Maze problem solution YASH PAL, 31 July 2024 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 Topics we are covering Toggle Problem solution in Python.Problem solution in Java.Problem solution in C++.Problem solution in C. 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} Algorithms coding problems solutions