HackerRank Grid Walking Problem Solution

HackerRank Grid Walking Problem Solution

Yashwant Parihar,

In this Post, we will solve HackerRank Grid Walking Problem Solution.

You are situated in an n dimensional grid at position (x[1], [2], …, [n]). The dimensions of the grid are (D[1], D[2],… D[n]). In one step, you can walk one step ahead or behind in any one of the n dimensions. This implies that there are always 2 x n possible moves if movements are unconstrained by grid boundaries. How many ways can you take m steps without leaving the grid at any point? You leave the grid if at any point [i], either [i] < 0 or x[i]> D[i].
For example, you start off in a 3 dimensional grid at position = [2, 2, 2]. The dimensions of the grid are D = [3, 3, 3], so each of your axes will be numbered from 1 to 3. If you want to move m = 1 step, you can move to the following coordinates: {[1, 2, 2], [2, 1, 2], [2, 2, 1], [3, 2, 2], [2, 3, 2], [2, 2, 3]}.

If we started at x = [1, 1, 1] in the same grid, our new paths would lead to {[1, 1, 2], [1, 2, 1], [2, 1, 1]}. Other moves are constrained by a[i] 0.
Function Description
Complete the gridWalking function in the editor below. It should return an integer that represents the number of possible moves, modulo (109 + 7). gridWalking has the following parameter(s):
m: an integer that represents the number of steps

Input Format
The first line contains an integer t, the number of test cases.
Each of the next t sets of lines is as follows:

  • The first line contains two space-separated integers, n and m
  • The next line contains n space-separated integers a[i].
  • The third line of each test contains n space-separated integers D[i].

Sample Input

1
2 3
1 1
2 3

Sample Output

12
HackerRank Grid Walking Problem Solution
HackerRank Grid Walking Problem Solution

Grid Walking C Solution



#include<stdio.h>
#include<stdlib.h>

//using namespace std;

typedef long long int ll;


ll invr(ll x) {
  ll M=1000000007;
  ll a = 1, b = x;
  while (b != 1) {
    ll c = M / b;
    a *= c; a %= M;
    b *= c; b %= M;
    if (b > M/2) { a = M - a; b = M - b; }
  }
  return a;
}

int main(){
	ll cases,ww,i,j,k,l,m,n;
	ll *** a;
	a=(ll ***)malloc(11*sizeof(ll **));
	for(i=0;i<11;i++){
		a[i]=(ll **)malloc(101*sizeof(ll *));
		for(j=0;j<101;j++){
			a[i][j]=(ll *)malloc(301*sizeof(ll));
		}
	}
	ll ** b;
	b=(ll **)malloc(301*sizeof(ll *));
	for(i=0;i<301;i++){
		b[i]=(ll *)malloc(11*sizeof(ll));
	}
	ll *x;
	x=(ll *)malloc(11*sizeof(ll));
	ll *d;
	d=(ll *)malloc(11*sizeof(ll));
	ll * fact;
	fact=(ll *)malloc(301*sizeof(ll));
	ll * inv;
	inv=(ll *)malloc(301*sizeof(ll));

	fact[1]=1;
	for(i=2;i<=300;i++){
		fact[i]=(i*fact[i-1])%1000000007;
	}
	for(i=1;i<=300;i++){
		inv[i]=invr(fact[i]);
	}

	scanf("%lld",&cases);

	for(ww=0;ww<cases;ww++){
		scanf("%lld",&n);
		scanf("%lld",&m);
		for(i=1;i<=n;i++){
			scanf("%lld",&x[i]);
		}
		for(i=1;i<=n;i++){
			scanf("%lld",&d[i]);
		}

		for(i=1;i<=n;i++){
			for(j=1;j<=d[i];j++){
				if(j==1 || j==d[i]){
					if(d[i]==1)a[i][j][1]=0;
					else a[i][j][1]=1;
				}
				else{
					a[i][j][1]=2;
				}
			}
		}

		for(k=2;k<=m;k++){
			for(i=1;i<=n;i++){
				for(j=1;j<=d[i];j++){
					if(j==1){
						if(d[i]==1)a[i][j][k]=0;
						else a[i][j][k]=a[i][2][k-1];
					}
					else if(j==d[i]){
						a[i][j][k]=a[i][j-1][k-1];
					}
					else{
						a[i][j][k]=(a[i][j-1][k-1]+a[i][j+1][k-1])%1000000007;
					}
				}
			}
		}
		//printf("hello\n");

		for(k=1;k<=m;k++){
			for(i=1;i<=n;i++){//printf("hello\n");
				if(k==1){
					if(i==1){
						b[k][i]=a[1][x[1]][1];
					}
					else{
						b[k][i]=(a[i][x[i]][1]+b[k][i-1])%1000000007;
					}
				}
				else{
					if(i==1){
						b[k][i]=a[1][x[1]][k];
					}
					else{
						int s;
						s=x[i];
						b[k][i]=(a[i][s][k]+b[k][i-1])%1000000007;
						//if(k==5 && i==2)break;
						for(l=1;l<k;l++){
							b[k][i]=(b[k][i]+((a[i][s][l]*((b[k-l][i-1]*((fact[k]*((inv[l]*inv[k-l])%1000000007))%1000000007))%1000000007))%1000000007))%1000000007;
							/*if(k==5 && i==2 && l==2){
								printf("%lld\n",fact[k]);
								printf("%lld\n",fact[k]*((inv[l]*inv[k-l])%1000000007));
								printf("%lld\n",inv[k-l]);
								printf("%lld\n",(fact[k]*(inv[l]*inv[k-l])%1000000007)%1000000007);
								//break;
							}*/
						}
					}
				}
			}
		}
		//printf("hello\n");
		/*for(i=1;i<=8;i++){
			for(j=1;j<=2;j++){
				printf("%lld ",b[i][j]);
			}
			printf("\n");
		}*/
		printf("%lld\n",b[m][n]);
	}
//printf("%lld",(6*(ll)inv[2])%1000000007);

return 0;
}

Grid Walking C++ Solution

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <map>
//#include <unordered_map>

using namespace std;

typedef long long int ll;

const int max_N = 11, max_S = 101, max_M = 301;
const ll modulo = 1000*1000*1000+7;

ll D[max_N+1], X[max_N+1];
int n, m;

ll CC[max_M][max_M];

ll C(int n, int k) {
    if (n<k) return 0LL;
    if (CC[n][k] == 0) {
        if (n == 0 || k == 0)
            CC[n][k] = 1LL;
        else
            CC[n][k] = (C(n-1, k-1) + C(n-1, k)) % modulo;
    }
    return CC[n][k];
}

vector<ll> count_dimension(int d, int m) {
    vector<ll> p(D[d], 0LL);
    vector<ll> upd(D[d], 0LL);
    vector<ll> res(m+1, 0LL);
    res[0] = 1;
    p[X[d]] = 1;
    
    for(int steps=1; steps<=m; ++steps) {
        for(int i=1; i<D[d]-1; ++i)
            upd[i] = (p[i-1]+p[i+1]) % modulo;
        upd[0] = (D[d] > 1) ? p[1] : 0;
        upd[D[d]-1] = (D[d] > 1) ? p[D[d]-2] : 0;
        for(int i=0; i<D[d]; ++i) {
            res[steps] = (res[steps] + upd[i]) % modulo;
            p[i] = upd[i];
        }
        //res[steps] = (1LL * res[steps] * C(m, steps)) % modulo;
    }
    
    return res;
}


int main() {
    //cout << C(3,2) << endl;
    int t;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for(int i=0; i<n; ++i) {
            cin >> X[i];
            X[i]--;
        }
        for(int i=0; i<n; ++i) { 
            cin >> D[i];
            //D[i]--;
        }
        vector<vector<ll>> pathes(n);
        for(int i=0; i<n; ++i) {
            pathes[i] = std::move(count_dimension(i, m));
            //for(int j=0; j<=m; ++j)
            //    cout << pathes[i][j] << ' ';
            //cout << endl;
        }
        vector<ll> A(pathes[0]);
        vector<ll> next_A(m+1);
        next_A[0] = 1;
        for(int i=1; i<n; ++i) {
            for(int j=1; j<=m; ++j) {
                ll v = 0;
                for(int k=0; k<=j; ++k)
                    v = (v + (C(j, k)*((A[k]*pathes[i][j-k] % modulo)) % modulo) ) % modulo;
                next_A[j] = v;
            }
            for(int j=0; j<=m; ++j)
                A[j] = next_A[j];
        }
        cout << A[m] << endl;     
    }
    
    return 0;
}

Grid Walking C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{
    public static int GridWalking(int numSteps, List<int> coords, List<int> dims)
    {
        var m = 1000000007;
        
        var numWaysPerDim = new long[dims.Count, numSteps + 1];
        
        for (var i = 0; i < dims.Count; ++i) {
            var numWays = new long[dims[i], numSteps + 1];
            
            numWays[coords[i] - 1, 0] = 1;
            numWaysPerDim[i, 0] = 1;
            
            for (var j = 1; j <= numSteps; ++j) {
                for (var k = 0; k < dims[i]; ++k) {
                    numWays[k, j] = (
                        (k - 1 >= 0 ? numWays[k - 1, j - 1] : 0) +
                        (k + 1 < dims[i] ? numWays[k + 1, j - 1] : 0)
                    ) % m;
                    
                    numWaysPerDim[i, j] = (numWaysPerDim[i, j] + numWays[k, j]) % m;
                }
            }
        }
        
        var coefs = CalculateBinomialCoefficients(numSteps, m);
        var numWaysCombined = new long[dims.Count, numSteps + 1];
        
        for (var i = 0; i <= numSteps; ++i) {
            numWaysCombined[0, i] = numWaysPerDim[0, i];
        }
        
        for (var i = 1; i < dims.Count; ++i) {
            for (var j = 0; j <= numSteps; ++j) {
                for (var k = 0; k <= j; ++k) {
                    numWaysCombined[i, j] = (numWaysCombined[i, j] +
                        ((((numWaysCombined[i - 1, k] * numWaysPerDim[i, j - k]) % m) * coefs[j, k]) % m)) % m;
                }
            }
        }
        
        return (int)numWaysCombined[dims.Count - 1, numSteps];
    }
    
    private static long[,] CalculateBinomialCoefficients(long n, long m) {
        var coefs = new long[n + 1, n + 1];
        
        coefs[0, 0] = 1;
        
        for (var i = 1; i <= n; ++i) {
            coefs[i, 0] = 1;
            
            for (var j = 1; j < n; ++j) {
                coefs[i, j] = (coefs[i - 1, j - 1] + coefs[i - 1, j]) % m;
            }
            
            coefs[i, n] = 1;
        }
        
        return coefs;
    }
}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int t = Convert.ToInt32(Console.ReadLine().Trim());

        for (int tItr = 0; tItr < t; tItr++)
        {
            string[] firstMultipleInput = Console.ReadLine().TrimEnd().Split(' ');

            int n = Convert.ToInt32(firstMultipleInput[0]);

            int m = Convert.ToInt32(firstMultipleInput[1]);

            List<int> x = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(xTemp => Convert.ToInt32(xTemp)).ToList();

            List<int> D = Console.ReadLine().TrimEnd().Split(' ').ToList().Select(DTemp => Convert.ToInt32(DTemp)).ToList();

            int result = Result.GridWalking(m, x, D);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Grid Walking Java Solution

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    /*
     * Complete the gridWalking function below.
     */
    static long[][] c;
    
    static void initBinomials(long mod, int m) {
        c = new long[m + 1][m + 1];
        c[0][0] = 1;
        for (int i = 0; i <= m; i++) {
            c[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
            }
        }
    }
    
    public static long[] ways(long mod, int x, int d, int m) {
        long[] w = new long[m + 1];
        long[] p = new long[d];
        p[x - 1] = 1;
        w[0] = 1;
        for (int t = 1; t <= m; t++) {
            long[] p1 = new long[d];
            for (int i = 0; i < p1.length; i++) {
                if (i > 0) p1[i] = (p1[i] + p[i - 1]) % mod;
                if (i + 1 < d) p1[i] = (p1[i] + p[i + 1]) % mod;
            }
            p = p1;
            for (int i = 0; i < d; i++) w[t] = (w[t] + p[i]) % mod;
        }        
        return w;
    }

    static long[] apply(long mod, long[] W, long[] w) {
        long[] R = new long[W.length];
        for (int i = 0; i < W.length; i++) {
            for (int j = 0; i + j < W.length; j++) {
                long p = (w[i] * W[j]) % mod;
                R[i + j] = (R[i + j] + p * c[i + j][i]) % mod;
            }
        }
        return R;
    }

    static int gridWalking(int m, int[] x, int[] D) {
        long mod = 1000_000_007;
        initBinomials(mod, m);
        long[] W = ways(mod, x[0], D[0], m);
        for (int i = 1; i < D.length; i++) {
            long[] w = ways(mod, x[i], D[i], m);
            W = apply(mod, W, w);
        }
        return (int)W[m];
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String[] nm = scanner.nextLine().split(" ");

            int n = Integer.parseInt(nm[0].trim());

            int m = Integer.parseInt(nm[1].trim());

            int[] x = new int[n];

            String[] xItems = scanner.nextLine().split(" ");

            for (int xItr = 0; xItr < n; xItr++) {
                int xItem = Integer.parseInt(xItems[xItr].trim());
                x[xItr] = xItem;
            }

            int[] D = new int[n];

            String[] DItems = scanner.nextLine().split(" ");

            for (int DItr = 0; DItr < n; DItr++) {
                int DItem = Integer.parseInt(DItems[DItr].trim());
                D[DItr] = DItem;
            }

            int result = gridWalking(m, x, D);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Grid Walking JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function gridWalking(m, x, D) {
    const MOD = BigInt(1e9 + 7);
    const add = (a, b) => (BigInt(a) + BigInt(b)) % MOD;
    const mul = (a, b, c = 1) => (((BigInt(a) * BigInt(b)) % MOD) * BigInt(c)) % MOD;

    const binom = new Array(m + 1);
    for (let i = 0; i <= m; i += 1) {
        binom[i] = new Array(m + 1).fill(0);
        binom[i][0] = 1;
        binom[i][i] = 1;
        for (let j = 1; j < i; j += 1) {
            binom[i][j] = add(binom[i - 1][j - 1], binom[i - 1][j]);
        }
    }

    const paths = new Array(D.length);
    const dp = new Array(D.length);

    for (let i = 0; i < dp.length; i += 1) {
        paths[i] = new Array(m + 1).fill(0);
        dp[i] = new Array(m + 1);
        for (let j = 0; j <= m; j += 1) {
            dp[i][j] = new Array(D[i] + 2).fill(0);
            for (let k = 1; k <= D[i]; k += 1) {
                if (j === 0) {
                    dp[i][j][k] = Number(k === x[i]);
                } else {
                    dp[i][j][k] = add(dp[i][j - 1][k - 1], dp[i][j - 1][k + 1]);
                }
                paths[i][j] = add(paths[i][j], dp[i][j][k]);
            }
        }
    }

    const acc = new Array(D.length);
    acc[0] = paths[0];
    for (let i = 1; i < D.length; i += 1) {
        acc[i] = new Array(m + 1).fill(0);
        for (let j = 0; j <= m; j += 1) {
            for (let k = 0; k <= j; k += 1) {
                const current = mul(acc[i - 1][k], binom[j][k], paths[i][j - k]);
                acc[i][j] = add(acc[i][j], current);
            }
        }
    }

    return acc[D.length - 1][m];
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const t = parseInt(readLine(), 10);

    for (let tItr = 0; tItr < t; tItr++) {
        const nm = readLine().split(' ');

        const n = parseInt(nm[0], 10);

        const m = parseInt(nm[1], 10);

        const x = readLine().split(' ').map(xTemp => parseInt(xTemp, 10));

        const D = readLine().split(' ').map(DTemp => parseInt(DTemp, 10));

        let result = gridWalking(m, x, D);

        ws.write(result + "\n");
    }

    ws.end();
}

Grid Walking Python Solution

#!/usr/bin/env python

import sys


MOD = 1000000007


def choose(n, k):
    if k < 0 or k > n:
        return 0
    
    else:
         p, q = 1, 1
         
         for i in range(1, min(k, n - k) + 1):
            p *= n
            q *= i
            n -= 1
         
         return p // q


def count_ways(N, M, D):
    ways = [[[0] * D[i] for _ in range(M + 1)] for i in range(N)]
    
    # Find all possible ways for all points and steps
    for i in range(N):
        # Initial counting of zeroth and first steps
        for j in range(D[i]):
            ways[i][0][j] = 1
            
            if j > 0:
                ways[i][1][j] += 1
            if j < D[i] - 1:
                ways[i][1][j] += 1
        
        # Higher steps
        for s in range(2, M + 1):
            for j in range(D[i]):
                if j > 0:
                    ways[i][s][j] += ways[i][s - 1][j - 1]
                if j < D[i] - 1:
                    ways[i][s][j] += ways[i][s - 1][j + 1]
    
    # Return total ways
    return ways


if __name__ == '__main__':
    T = int(sys.stdin.readline())
    c = {}
    
    for _ in range(T):
        N, M = list(map(int, sys.stdin.readline().split()))
        X = list(map(int, sys.stdin.readline().split()))
        D = list(map(int, sys.stdin.readline().split()))
        
        # Count the possible ways for each individual dimension
        ways = count_ways(N, M, D)
        
        # Compute totals
        total = [ways[0][i][X[0] - 1] for i in range(M + 1)]
        
        for i in range(1, N):
            for j in reversed(range(1, M + 1)):
                k = j
                
                while k >= 0 and (j, k) not in c:
                    c[(j, k)] = choose(j, k)
                    k -= 1
                
                total[j] = sum(total[k] * c[(j, k)] * ways[i][j - k][X[i] - 1] for k in range(j + 1))
        
        print(total[M] % MOD)
c C# C++ HackerRank Solutions java javascript python