Grid walking algorithm code correction

Question

Grid Walking (Score 50 points): You are situated in an N dimensional grid at position (x_1,x2,...,x_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. (So there are always 2N possible different moves). In how many ways can you take M steps such that you do not leave the grid at any point? You leave the grid if you for any x_i, either x_i <= 0 or x_i > D_i.

Input: The first line contains the number of test cases T. T test cases follow. For each test case, the first line contains N and M, the second line contains x_1,x_2...,x_N and the 3rd line contains D_1,D_2,...,D_N.

So, in the above solution I'm trying to take one dimensional array. The website claims 38753340 to be the answer, but I'm not getting it.

public class GridWalking {

    /**
     * @param args
     */
    public static void main(String[] args) {

        try {

            long arr[] = new long[78];
            long pos = 44;
            long totake = 287;

            /*
             * Double arr[] = new Double[3]; Double pos = 0; Double totake = 5;
             */

            Double val = calculate(arr, pos, totake);
            System.out.println(val % 1000000007);

        } catch (Exception e) {
            System.out.println(e);
            e.printStackTrace();
        }

    }

    public static HashMap<String, Double> calculated = new HashMap<String, Double>();

    private static Double calculate(long[] arr, long pos, long totake) {

        if (calculated.containsKey(pos + "" + totake)) {
            return calculated.get(pos + "" + totake);
        }
        if (0 == totake) {

            calculated.put(pos + "" + totake, new Double(1));
            return new Double(1);
        }

        if (pos == arr.length - 1) {

            Double b = calculate(arr, pos - 1, totake - 1);

            Double ret = b;
            calculated.put(pos + "" + totake, new Double(ret));
            return ret;

        }
        if (pos == 0) {
            Double b = calculate(arr, pos + 1, totake - 1);

            Double ret = b;
            calculated.put(pos + "" + totake, new Double(ret));
            return ret;
        }

        Double a = calculate(arr, pos + 1, totake - 1);
        Double b = calculate(arr, pos - 1, totake - 1);

        Double ret = (a + b);
        calculated.put(pos + "" + totake, ret);
        return ret;
    }

}

Pasco

interviewstreet.com/challenges/dashboard/#problem/4e48bfab1bc3e – Pasco

I think it better fits codereview.SE – Swayback

Answer 1

You need to change key values as for pos + "_" + totake.

I have rewritten it but I'm not sure it working or not. It takes too much time to complete if ever.

    public class GridWalking {

      static long arr_length = 78;
      static long pos = 44;
      static long totake = 287;
      static long count = 0;

      /**
       * @param args
       */
      public static void main(String[] args) {
        try {
          calculate(pos, totake);
          System.out.println(count % 1000000007);
        } catch (Exception e) {
          System.out.println(e);
          e.printStackTrace();
        }
      }

      private static void calculate(long pos, long totake) {
        if (pos < 0 || pos > arr_length - 1)
          return;

        if (0 == totake) {
          count++;
          return;
        }

        calculate(pos + 1, totake - 1);
        calculate(pos - 1, totake - 1);
      }

    }

Jerricajerrie

Roman C, thanks a lot for trying this out.... really !! but its not even executing. My eclipse hung – Pasco

I said it's too slow, it counts slowly because to many variations. needed to test on not big numbers. 287 is too much combinations with repetitions. this is worst algorithm I've written ever. may be it needs to not use recursion. – Jerricajerrie

if arr_length = 9, pos = 5 and totake = 20 it will count to 450000. – Jerricajerrie

Answer 2

I have tried solving that Grid walking problem in Hackerrank. this is the code that had worked(in ecclipse atleast). but i donno why it does not match with given answers. Nut i think you can get the idea from it. Since it does not use recursion, no problem with execution time..

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

public class Solution {
    static int count=0;
    public static void main(String[] args) throws FileNotFoundException {
        String filename = "src/testcases.txt";//testcases is just a file containing input
        File file = new File(filename);
        Scanner in = new Scanner(file);
        //in.useDelimiter("[^0-9]+");
        //-----------------------------------------------------------------
        int T=in.nextInt();
        for(int t=0;t<1;t++){
            int N=in.nextInt();
            int M=in.nextInt();System.out.println("M="+M);
            int[] X=new int[N];
            long max=1000000007;
            int[] D=new int[N];
            for(int i=0;i<N;i++) X[i]=in.nextInt();
            for(int i=0;i<N;i++) D[i]=in.nextInt();
            int Dmax=D[0];
            int Dtotal=1;
            for(int i=0;i<N;i++) if(Dmax<D[i]) Dmax=D[i];
            for(int i=0;i<N;i++) X[i]--;
            for(int i=0;i<N;i++) Dtotal*=D[i];//total number of fields
            long[] mainarray= new long[Dtotal];
            long[] mainarraynext=new long[Dtotal];
            int[][] ways=new int[N][Dmax];
            set( X, mainarray,D, 1);
            int temp[]=new int[N];
            for(int h=0;h<10;h++){  

                for(int j=0;j<Dtotal;j++){
                    mainarraynext[j]=getsum(inverse(j,D),mainarray, D );
                }
                for(int j=0;j<Dtotal;j++){
                    mainarray[j]=mainarraynext[j];
                    mainarray[j]%=max;
                }
                System.out.println(Arrays.toString(mainarray));
            }
            long finalsum=0;
            for(int j=0;j<Dtotal;j++){  
                finalsum+=mainarray[j];
                //System.out.println(finalsum);

            }
            System.out.println(finalsum);
            //System.out.println(Arrays.toString(inverse(44,D)));
        }
    }
    public static long get(int[] x, long[] mainarray, int[] D){
        for(int i=0;i<x.length;i++){
            if(x[i]>=D[i]) return 0;
            if(x[i]<0) return 0;
        }
        int index=0;
        for(int i=0;i<D.length;i++){
            index=(index*D[i])+x[i];
        }
        return mainarray[index];
    }
    public static int[] inverse(int index,int[] D){
        int[] temp=new int[D.length];
        for(int i=D.length-1;i>=0;i--){
            temp[i]=index%D[i];
            index=index/D[i];
        }
        return temp;
    }
    public static void set(int[] x, long[] mainarray, int[] D, int value){
        int index=0;
        for(int i=0;i<D.length;i++){
            index=(index*D[i])+x[i];
        }
        mainarray[index]=value;
    }
    public static long getsum(int[] x,long[] mainarray, int[] D ){
        int[] temp=new int[x.length];
        long sum=0;
        //for 2n different sides
        for(int j=0;j<x.length;j++){//sum in each side
            temp[j]=x[j];
        }
        for(int j=0;j<x.length;j++){//sum in each side
            temp[j]--;
            sum+=get(temp,  mainarray, D);
            temp[j]+=2;
            sum+=get(temp,  mainarray, D);
            temp[j]--;
        }
        return sum;

    }
}

Jarib

Turns out my code was correct....! Just change print from (finalsum) to (finalsum%1000000007) – Jarib

It seems Dtotal can overflow when there are multiple dimensions. – Vella

@Jarib I am trying to solve this problem, I really need help xD – Pinnate

Answer 3

Here's a Java solution I've built for the original hackerrank problem. For big grids runs forever. Probably some smart math is needed.

long compute(int N, int M, int[] positions, int[] dimensions) {
    if (M == 0) {
        return 1;
    }
    long sum = 0;
    for (int i = 0; i < N; i++) {
        if (positions[i] < dimensions[i]) {
            positions[i]++;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]--;
        }
        if (positions[i] > 1) {
            positions[i]--;
            sum += compute(N, M - 1, positions, dimensions);
            positions[i]++;
        }
    }
    return sum % 1000000007;
}

Loats