Hiking around HackerRank — 07

09/22/2020

Photo by Scott Elkins on Unsplash

Note:

1. All problems are published by HackerRank, credit to HackerRank
2. The solutions are coded by myself, and open source just for study.

Java 1D Array (Part 2)

Java 1D Array (Part 2), retrieved from https://www.hackerrank.com/challenges/java-1d-array/problem

It seems not difficult. I assume we just need to evaluate i+ leap, (i+1), and (i-1) elements in the array given in the statement. Let me give a try!

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game) {
        // Return true if you can win the game; otherwise, return false
        return solve(leap, game, 0);
    }

    private static boolean solve(int leap, int[] game, int i){
        if (i < 0 || game[i] == 1){
            return false;
        }
        else if (i>= game.length) {
            return true;
        }

        game[i] = 1;

        return solve(leap, game, i + leap) || solve(leap, game, i + 1) || solve(leap, game, i-1);
    }

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

Let’s runt it!
Hold on! It shows “Runtime Error”! What happened?

I assume we should not check the “False” condition before the “True” condition. See what will happen if we modify it:

import java.util.*;

public class Solution {

    public static boolean canWin(int leap, int[] game) {
        // Return true if you can win the game; otherwise, return false
        return solve(leap, game, 0);
    }

    private static boolean solve(int leap, int[] game, int i){
        if (i >= game.length) {
            return true;
        }
        else if (i < 0 || game[i] == 1) {
            return false;
        }

        game[i] = 1;

        return solve(leap, game, i + leap) || solve(leap, game, i + 1) || solve(leap, game, i-1);
    }

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

It worked!
It is a little bit difficult to understand the idea behind this code. Well, first, we want to evaluate elements at (i+ leap), (i+1), and (i-1). The “solve” method would help us to finish this job. As the programmer RodneyShag shared on HackerRank Forum, it is a recursion flow and you can refer to his original post here [1].

11/28/2020

Photo by Michiel Leunens on Unsplash

Java Regex2 — Duplicate Words

Java Regex2 — Duplicate Words, retrieved from https://www.hackerrank.com/challenges/duplicate-word/problem

The regular expression is not an easy topic. We can understand the idea of this problem: remove repeated words (but keep the first instance) and the extra spaces (which is doubtlessly accompanied with repeated words). So, how can we make it?

Let’s refer to this website: tutorialspoint. You may find this instruction is clear and straightforward enough. As mentioned: “\w” matches word characters, “\W” matches non-word characters, and “\b” matches the word boundaries when outside the boundaries [2].

The code is as below:

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class DuplicateWords {

    public static void main(String[] args) {

        String regex = "\\b(\\w+)(?:\\W+\\1\\b)+";;
        Pattern p = Pattern.compile(regex, Pattern.CASE_INSENSITIVE);

        Scanner in = new Scanner(System.in);
        int numSentences = Integer.parseInt(in.nextLine());

        while (numSentences-- > 0) {
            String input = in.nextLine();

            Matcher m = p.matcher(input);

            // Check for subsequences of input that match the compiled pattern
            while (m.find()) {
                input = input.replaceAll(m.group(), m.group(1));
            }

            // Prints the modified sentence.
            System.out.println(input);
        }

        in.close();
    }
}

Conclusion:

I’m not doing so well in these problems. I know, I’ve been occupied by all kinds of stuff recently, but it should not be an excuse. Hope I can keep making progress like I used to (and I have to do that, in fact).

This is my repo:

AndrewAct/HackerRank-Java-Practice

Hope it helps!

References:

[1] Java 1D Array (Part 2) retrieved from https://www.hackerrank.com/challenges/java-1d-array/forum

[2] Java-Regular Expressions, TutorialsPoint, retrieved from https://www.tutorialspoint.com/java/java_regular_expressions.htm