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
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])
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;
}
}
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("%lf\n", get_ans(i+1));
}
printf("%lf\n", get_ans(limit));
}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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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] = '\0';
}
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;
}
![HackerRank Swap Nodes [Algo] problem solution](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgjGi7Fstz7Lqye8x4O35woHbqY83IFxLWWoAcFKWtcVUFpaHsa36W_s_jsIQw-vD4s-J3t2MfQN6Cn8t0M5JtvDTFX75PloaEQsdzJImQLqzAtA1_z_2ktw9UsJ-Le4MYkHQZrHz3q2-c/w100/hackerrank-interview-preparation-kit-swap-nodes-algo-solution.png)
0 Comments