HackerRank Grid Walking problem solution

YASH PAL,

In this HackerRank Grid Walking problem solution, you are situated in an n-dimensional grid at position (x1, x2,….,xn). the dimensions of the grid are (D1, D2,…., Dn). 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?

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
  • x: an integer array where each xi represents a coordinate in the ith dimension where 1 <= i <= n
  • D: an integer array where each Di represents the upper limit of the axis in the ith dimension
HackerRank Grid Walking problem solution

HackerRank Grid Walking problem solution in Python.

#!/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)

Grid Walking problem solution in Java.

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();
    }
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <stdint.h>

using namespace::std;

#define MOD 1000000007

main()
{
	int **binom = new int*[301];
	for (int i = 0; i <= 300; i++)
		binom[i] = new int[301];

	for (int i = 1; i <= 300; i++)
		binom[i][0] = binom[i][i] = 1;

	for (int i = 2; i <= 300; i++)
	{
		for (int j = 1; j < i; j++)
		{
			uint64_t x = ((uint64_t) binom[i - 1][j] + (uint64_t) binom[i - 1][j - 1]) % MOD;
			binom[i][j] = x;
		}
	}

	int ***num_ways = new int**[101];
	for (int i = 0; i <= 100; i++)
		num_ways[i] = new int*[101];

	for (int i = 0; i <= 100; i++)
		for (int j = 0; j <= 100; j++)
			num_ways[i][j] = new int[301];

	num_ways[1][1][0] = 1;
	for (int i = 1; i <= 300; i++)
		num_ways[1][1][i] = 0;

	for (int i = 2; i <= 100; i++)
	{
		for (int j = 1; j <= 100; j++)
			num_ways[i][j][0] = 1;

		for (int k = 1; k <= 300; k++)
		{
			for (int j = 1; j <= i; j++)
			{
				if (j == 1)
				{
					num_ways[i][j][k] = num_ways[i][j + 1][k - 1];
					continue;
				}

				if (j == i)
				{
					num_ways[i][j][k] = num_ways[i][j - 1][k - 1];
					continue;
				}

				num_ways[i][j][k] = ((uint64_t) num_ways[i][j - 1][k - 1] + (uint64_t) num_ways[i][j + 1][k - 1]) % MOD;
			}
		}
	}

	int T;
	cin >> T;

	for (int t = 0; t < T; t++)
	{
		int N, M;
		cin >> N >> M;

		int *a = new int[N];
		int *b = new int[N];

		for (int i = 0; i < N; i++)
			cin >> a[i];

		for (int i = 0; i < N; i++)
			cin >> b[i];

		int **P = new int*[N];
		for (int i = 0; i < N; i++)
			P[i] = new int[1 + M];

		for (int i = 0; i <= M; i++)
			P[0][i] = num_ways[b[0]][a[0]][i];

		for (int i = 1; i < N; i++)
		{
			P[i][0] = 1;
			for (int j = 1; j <= M; j++)
			{
				uint64_t s = 0;
				for (int k = 0; k <= j; k++)
				{
					uint64_t x = ((uint64_t) binom[j][k] * (uint64_t) num_ways[b[i]][a[i]][k]) % MOD;
					uint64_t y = (x * (uint64_t) P[i - 1][j - k]) % MOD;
					s = (s + y) % MOD;
				}

				P[i][j] = s;
			}
		}

		std::cout << P[N - 1][M] << std::endl;

		delete[] a;
		delete[] b;
		delete[] P;
	}

	delete[] binom;
	delete[] num_ways;
}

Problem solution in C.

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

#define MAX_N 10
#define MAX_M 300
#define MAX_D 100
#define MODULUS 1000000007

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int T;
    scanf("%d", &T);
    
    // precompute number of ways for one dimension
    int count[MAX_M + 1][MAX_D + 1][MAX_D + 1];
    for (int above = 0; above <= MAX_D; above++) {
        for (int below = 0; below <= MAX_D; below++) {
            count[0][above][below] = 1;
        }
    }
    for (int m = 1; m <= MAX_M; m++) {
        for (int above = 0; above <= MAX_D; above++) {
            for (int below = 0; below <= MAX_D; below++) {
                int c = 0;
                if (above == 0 && below == 0) {
                    c = 0;
                } else if (above == 0) {
                    c = count[m - 1][above + 1][below - 1];
                } else if (below == 0) {
                    c = count[m - 1][above - 1][below + 1];
                } else {
                    c = count[m - 1][above + 1][below - 1] + count[m - 1][above - 1][below + 1];
                }
                count[m][above][below] = c % MODULUS;
            }
        }
    }
    
    int combination[MAX_M + 1][MAX_M + 1];
    combination[0][0] = 1;
    for (int i = 1; i <= MAX_M; i++) {
        combination[i][0] = combination[i][i] = 1;
        for (int j = 1; j < i; j++) {
            combination[i][j] = (combination[i - 1][j] + combination[i - 1][j - 1]) % MODULUS;
        }
    }
    
    int x[MAX_N], D[MAX_N];
    long long d[MAX_M + 1][MAX_N];
    for (int t = 1; t <= T; t++) {
        int N, M;
        scanf("%d %d", &N, &M);
        for (int i = 0; i < N; i++) {
            scanf("%d", &x[i]);
        }
        for (int i = 0; i < N; i++) {
            scanf("%d", &D[i]);
            d[0][i] = 1;
        }
        
        for (int m = 1; m <= M; m++) {
            d[m][0] = count[m][D[0] - x[0]][x[0] - 1];
            for (int i = 1; i < N; i++) {
                d[m][i] = 0;
                for (int j = 0; j <= m; j++) {
                    long long c = count[j][D[i] - x[i]][x[i] - 1];
                    d[m][i] += (((d[m - j][i - 1] * c) % MODULUS) * combination[m][j]) % MODULUS;
                    d[m][i] %= MODULUS;
                }
                // printf("%d %d: %lldn", m, i, d[m][i]);
            }
        }
        
        printf("%lldn", d[M][N - 1]);
    }
    return 0;
}

Algorithms coding problems solutions