HackerRank Java 1D Array (Part 2) problem solution

HackerRank Java 1D Array (Part 2) problem solution – In this HackerRank java Array (Part 2) problem in the java programming language. Let’s play a game on an array! You’re standing at index 0 of an n-element array named game. From some index i (where 0<=i<=n), you can perform one of the following moves:

Move Backward: If cell i-1 exists and contains a 0, you can walk back to cell i-1.

Move Forward: 

• If cell i+1 contains a zero, you can walk to cell i+1.
• If cell i+leap contains a zero, you can jump to cell i+leap.
• If you’re standing in cell n-1 or the value of i+leap>=n, you can walk or jump off the end of the array and win the game.

In other words, you can move from index i to index i+1, i-1, or i+leap as long as the destination index is a cell containing a 0. If the destination index is greater than n-1, you win the game.

HackerRank Java 1D Array (Part 2) problem solution.

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

public class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < t; i++) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            //System.out.println(n + " " + m);
            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = scanner.nextInt();
                //System.out.print(arr[j]);
            }
            //System.out.println();
            solve(n,m,arr);
        }
    }
    
    public static void solve(int n, int m, int[] arr) {
        if (solve(n,m,arr,new boolean[n],0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
    
    public static boolean solve(int n, int m, int[] arr, boolean[] visited, int curr) {
        if (curr + m >= n || curr + 1 == n) {
            return true;
        }
        
        boolean[] newVisited = new boolean[n];
        for (int i = 0; i < n; i++) {
            newVisited[i] = visited[i];
        }
        
        boolean s = false;
        if (!visited[curr+1] && arr[curr+1] == 0) {
            newVisited[curr+1] = true;
            s = solve(n,m,arr,newVisited,curr+1);
        }
        if (s) {
            return true;
        }
        if (m > 1 && arr[curr+m] == 0 && !visited[curr+m]) {
            newVisited[curr+m] = true;
            s = solve(n,m,arr,newVisited,curr+m);
        }
        if (s) {
            return true;
        }
        if (curr > 0 && arr[curr-1] == 0 && !visited[curr-1]) {
            newVisited[curr-1] = true;
            s = solve(n,m,arr,newVisited,curr-1); 
        }
        return s;
    }
}

Second solution in java8 programming.

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game) {
    VirtualPlayer v = new VirtualPlayer(leap, game);
    v.tick();
    return v.winnable;

}
static class VirtualPlayer {
    private int pos = 0; //pos-ition
    private int lp; //lp means leap
    private int[] map;
    boolean winnable = false;
    public VirtualPlayer(int lp, int[] map) {
        this.lp = lp; //gets the values from the canWin function
        this.map = map;

    }
    private void moveup() {
        if (map[pos + 1] == 0) {
            pos++;
            tick();
        }

    }

    private void movedown() {
        if ((pos - 1) >= 0 && map[pos - 1] == 0) {
            map[pos] = 1;
            pos--;
            tick();
        }

    }

    private void jump() {
        if ((pos + lp) < map.length) {
            if (map[pos + lp] == 0) {
                int posold = pos;
                pos = pos + lp;
                tick();
                pos = posold;
            }
        }

    }
    void tick() {
        //System.out.println("im at:"+pos);
        if (pos == (map.length - 1) || ((pos + lp) >= map.length)) {
            winnable = true;
        }
        else {
            this.moveup();
            if (lp != 0) {
                this.jump();
            } //cant jump 0 steps!
            this.movedown();
        }

    }

}

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int q = scan.nextInt();
        while (q-- > 0) {
            int n = scan.nextInt();
            int leap = scan.nextInt();
            
            int[] game = new int[n];
            for (int i = 0; i < n; i++) {
                game[i] = scan.nextInt();
            }

            System.out.println( (canWin(leap, game)) ? "YES" : "NO" );
        }
        scan.close();
    }
}

Third solution

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

public class Solution 
{
    public static void main(String[] args) 
    {
        Scanner scanner = new Scanner(System.in);
        int caseCount = scanner.nextInt();
        for(int ii=0; ii<caseCount; ++ii)
        {
            int arraySize = scanner.nextInt();
            int jumpSize = scanner.nextInt();
            int[] array = new int[arraySize];
            for(int jj=0; jj<arraySize; ++jj) array[jj] = scanner.nextInt();
            // --
            boolean solvableGame = solveGame(array, jumpSize, 0, new boolean[array.length]);
            System.out.println(solvableGame?"YES":"NO");
        }
    }
    public static boolean solveGame(int[] array, int jumpSize, int position, boolean[] testedPositions)
    {
        // System.out.println("solveGame:"+position);
        if(position < 0) return false;
        if(position >= array.length) return true;
        if(testedPositions[position]) return false;
        if(array[position]==1) return false;
        // --
        // -- test jump back case is pointless
        // -- which just repeat the last position
        // --
        testedPositions[position]=true;
        return solveGame(array, jumpSize, position+jumpSize, testedPositions)
            || solveGame(array, jumpSize, position+1, testedPositions) 
            || solveGame(array, jumpSize, position-1, testedPositions);
        
    }
}