Geek Answers Handbook

Smoothing algorithm code correction

Walk on the grid (score 50 points): You are in the N-dimensional grid in position (x_1,x2,...,x_N) . Grid sizes (D_1,D_2,...D_N) . In one step, you can go one step forward or backward in any of the N dimensions. (Thus, there are always 2N possible different moves). How many ways can you take M steps so that you do not leave the grid at any point? You leave the grid if you are for any x_i , or 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 third line contains D_1,D_2,...,D_N .

So, in the solution above, I'm trying to take one dimensional array. The website claims 38753340 is the answer, but I am 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; } }
0
source share
3 answers

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

I rewrote it, but I'm not sure if it works or not. It takes too much time to complete.

  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); } }
+1
source

I tried to solve this grid problem in Hackerrank. this is the code that worked (in ecclipse atleast). but I do not know why this does not correspond to the given answers. Walnut, I think you can get this idea. Since it does not use recursion, there is no problem with runtime.

 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; } }
+1
source

Here's the Java solution I created for the original hackerrank problem. For large grids, it works forever. Perhaps you need smart math.

 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; }
0
source

More articles:


All Articles