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