I
t is another warm Tuesday morning in the Twin Cities of Minneapolis and St. Paul. When the COVID-19 pandemic started my wife and I stopped walking on a daily schedule. A couple weeks ago we started walking. Slowly we are trying to get to 10,000 steps a day. Currently we are around 6,500 steps. In addition after every 2-hour block of work I get on a stationary bike and pedal fast and furious for 5 minutes. I tend to get 4 to 5 short sessions per day. My wife decided to skip the bike. That said; we both are starting to feel the benefits of exercising once again. We love it!
On a separate note my best friend sent me a message that he was starting to test ProtonMail for personal and potentially commercial use. I replied that I have been experimenting with it on my defunct Pixel 4 cell phone. After it died with less than two years of use a couple weeks ago, I switched for the first time to an iPhone. I am still installing applications. Today I will install ProtonMail and will continue testing the service. About three months ago I mentioned ProtonMail on my post Largest Triple Products – Revisited. I like the encryption and the fact that they do not use or sell your personal information.
In this post we will cover the HackerRank problem Red John is back. If interested please visit the HackerRank site and get the requirements directly from them.
There is a wall of size 4 x n in the victim's house. The victim has an infinite supply of bricks of size 4 x 1 and 1 x 4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks. First we must calculate the total number of ways in which the bricks can be arranged so that the entire wall is covered. There is one more step to the puzzle. Call the number of possible arrangements M. Patrick must calculate the number of prime numbers P in the inclusive range 0 - M. Constraints: 1 <= t <= 20 1 <= n <= 40
The description is somewhat convoluted. I guess there could be other problems that deal with Red John. We are first asked to calculate the number of ways in which 1 x 4 and 4 x 1 bricks can be used to tile a wall. That seems to be a self contained problem.
Then we need to determine the number of prime numbers in the specified range. Note that the upper limit for the range is the number of ways in which the bricks can be arranged in the wall that we obtained by solving the first part of this problem.
This is a dynamic programming problem. We first need to come up with a recursive function to compute the number of combinations for the tiles and then probably we will need to memorized it in order to pass all test cases. More on this as we go through the implementations.
I did a lot of research and experimentation while solving the problem. After I had an accepted version I wanted to read the editorial to get additional insights. The entire idea is to learn. I was surprised that HackerRank would discount the 65 points from this problem if I would read the editorial. I did and it was not that interesting.
Wondering in the Internet I ran into Red John is back explained; how recursion is formulated by Lin Myat Ko. His article describes how you can arrive to the formula: f(n) = f(n – 1) + f(n – 4) which is the recursive part of the recursive call we need to generate. The short article does provide an explanation.
I also ran into the article: Find the number of ways to fill an `N × 4` matrix with `1 × 4` tiles which describes in more depth what appears to be a different but similar problem. You will later see that it is exactly what was requested in the first part of our convoluted problem.
I also read the article Recurrence relation in Wikipedia. Perhaps too long but you might find it of interest.
We can convert the first part of the problem into a recurrence relation i.e. F(N) = F(N - 1) + F(N - 4) with the base case : F(0) = F(1) = F(2) = F(3) = 1. Here, F(N) represents the number of ways of tiling the 4xN rectangle with 4x1 and 1x4 tiles.
This explains the approach that we can take to solve this problem.
We are going to solve the problem using the Java programming language and the VSCode IDE on a Windows 10 computer. You can use the same language and IDE on a different platform. As a matter of fact you can use any other IDE. Lately I have been using VSCode as the only IDE in this blog. It is free but it has several issues when compared to the full and paid version of Visual Studio Enterprise Edition.
public static int redJohn(int n) {
// Write your code here
}
The signature for the function of interest is quite simple. We receive a an integer `n` and have to return a count of primes. Go figure.
1 40 main <<< t: 1 main <<< n: 40 redJohn <<< m: 217286 main <<< ans: 19385 1 7 main <<< t: 1 main <<< n: 7 redJohn <<< m: 5 main <<< ans: 3 2 1 7 main <<< t: 2 main <<< n: 1 redJohn <<< m: 1 main <<< ans: 0 main <<< n: 7 redJohn <<< m: 5 main <<< ans: 3 3 3 5 8 main <<< t: 3 main <<< n: 3 redJohn <<< m: 1 main <<< ans: 0 main <<< n: 5 redJohn <<< m: 3 main <<< ans: 2 main <<< n: 8 redJohn <<< m: 7 main <<< ans: 4 20 34 3 31 35 10 38 18 27 15 3 38 14 18 4 5 23 9 31 10 25 main <<< t: 20 main <<< n: 34 redJohn <<< m: 31422 main <<< ans: 3385 main <<< n: 3 redJohn <<< m: 1 main <<< ans: 0 main <<< n: 31 redJohn <<< m: 11949 main <<< ans: 1432 main <<< n: 35 redJohn <<< m: 43371 main <<< ans: 4522 main <<< n: 10 redJohn <<< m: 14 main <<< ans: 6 main <<< n: 38 redJohn <<< m: 114051 main <<< ans: 10794 main <<< n: 18 redJohn <<< m: 181 main <<< ans: 42 main <<< n: 27 redJohn <<< m: 3292 main <<< ans: 462 main <<< n: 15 redJohn <<< m: 69 main <<< ans: 19 main <<< n: 3 redJohn <<< m: 1 main <<< ans: 0 main <<< n: 38 redJohn <<< m: 114051 main <<< ans: 10794 main <<< n: 14 redJohn <<< m: 50 main <<< ans: 15 main <<< n: 18 redJohn <<< m: 181 main <<< ans: 42 main <<< n: 4 redJohn <<< m: 2 main <<< ans: 1 main <<< n: 5 redJohn <<< m: 3 main <<< ans: 2 main <<< n: 23 redJohn <<< m: 907 main <<< ans: 155 main <<< n: 9 redJohn <<< m: 10 main <<< ans: 4 main <<< n: 31 redJohn <<< m: 11949 main <<< ans: 1432 main <<< n: 10 redJohn <<< m: 14 main <<< ans: 6 main <<< n: 25 redJohn <<< m: 1728 main <<< ans: 269
HackerRank provides a test scaffold. To be honest with you I did not pay attention to it. I just wrote a simple piece of code that seems to match the expected input for the test cases.
The first input line contains the number of test cases.
The following line(s) contain the value(s) for ‘n’.
The first test case was used to determine the upper limit for the prime numbers. This is based on the second constrain provide in the problem description.
As usual we display the arguments and the result for each test case. Note that we also display the intermediate value of `m`. This was done to verify the operation of the code.
All the test cases came from HackerRank with the exception of the first one.
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read number of test cases `t` ****
int t = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< t: " + t);
// **** loop once per test case ****
for (int i = 0; i < t; i++) {
// **** read `n` for the wall size ****
int n = Integer.parseInt(br.readLine().trim());
// ???? ????
System.out.println("main <<< n: " + n);
// ???? ????
// System.out.println("main <<< findTotalWays(" + n + "): " + findTotalWays(n));
// **** call and display result for this test case ****
System.out.println("main <<< ans: " + redJohn(n));
// ???? ????
// System.out.println("main <<< memo: " + Arrays.toString(memo));
}
// **** close buffered reader ****
br.close();
}
This is the test code for this problem. It seems to match very closely to the task at hand. It reads the number of test cases and then loops once per test case reading the value of `n`. The result is then computed and displayed.
Note that there is the findTotalWays() function that we call with the value of `n`. We have that code commented out. We will use this function to compute the number of combinations of bricks for the wall.
// **** global variables ****
static long memo[];
static HashSet<Integer> hs;
We are going to use the array for memoization and the hash set to keep track of the prime numbers for the second part of the problem.
/**
* Populate hash map with prime numbers.
* Auxiliary function.
*/
static void setPrimes() {
// **** ****
for (int i = 2; i <= 217286; i++) {
if (isPrime(i))
hs.add(i);
}
}
This function is used to generate a prime numbers and store them in the hash set. It uses the isPrime() auxiliary function to determine if the current number is a prime.
Note the value 217286. Please go back to the test cases and look at the first one. The number represents the largest prime we will encounter in this problem.
/**
* Determine if this number is a prime.
* Auxiliary function.
*/
static boolean isPrime (int num) {
// **** ****
for (int i = 2; (i * i) <= num; i++){
// **** check if not a prime ****
if (num % i == 0)
return false;
}
// **** num is a prime ****
return true;
}
This function is used to determine if a number is or is not a prime. It uses the Sieve of Eratosthenes algorithm.
/**
* There is a wall of size 4 x n in the victim's house.
* The victim has an infinite supply of bricks of size 4 x 1 and 1 x 4 in her house.
* There is a hidden safe which can only be opened by a particular configuration of bricks.
*
* First we must calculate the total number of ways in which the bricks can be arranged
* so that the entire wall is covered.
*
* There is one more step to the puzzle.
* Call the number of possible arrangements M.
* Patrick must calculate the number of prime numbers P in the inclusive range 0 - M.
*
* The time complexity of the first part of the problem is O(n)
* since we can calculate M using Dynamic Programming.
*
* The time complexity of the second part is O(n log log n).
*
* Hence, the overall time complexity for the problem becomes O(n log log n).
*/
static int redJohn(int n) {
// **** set global variables ****
hs = new HashSet<Integer>();
memo = new long[41];
Arrays.fill(memo, -1);
// **** initialization ****
int ans = 0;
long m = 0;
// **** fill the wall (number of ways) (first problem) ****
// m = f(n); // uses memoization
m = findTotalWays(n); // not using memoization
// ???? ????
System.out.println("redJohn <<< m: " + m);
// System.out.println("redJohn <<< memo: " + Arrays.toString(memo));
// System.out.println("redJohn <<< findTotalWays(" + n + "): " + findTotalWays(n));
// **** populate hash set with primes (second problem) ****
setPrimes();
// **** calculate the number of prime numbers in the inclusive range 0 - m ****
for (int i = 2; i <= m; i++) {
// **** count this prime (if needed) ****
if (hs.contains(i))
ans++;
}
// **** return number of prime numbers in range 0 - m ****
return ans;
}
This function is used to get the values to the two problems that are required to generate the answer.
We start by initializing the hash set and the memo.
The key of this problem is to compute how many ways we can arrange the 1 x n tiles. Such value is computed by f() which as you can see has been commented out. We will see this function shortly.
The value for `m` is computed by the findTotalWays() function which we saw in the main procedure. Note that f() uses memoization and findTotalWays() does not. Both implementations were accepted by HackerRank.
After we have the number of combinations we determine how many primes are in the specified range. This is done by counting the number of prime numbers that are found in the hash set between the specified range.
The result is returned.
/**
* Compute combinations of times.
* Recursive call.
* Uses memoization.
*/
static long f(int n) {
// **** check if in memo ****
if (memo[n] != -1) return memo[n];
// **** initialization ****
long ans = 1;
// **** recursive call (if needed) ****
if (n > 3)
ans = f(n - 1) + f(n - 4);
// **** memoize answer ****
memo[n] = ans;
// ???? ????
// System.out.println("f <<< n: " + n + " ans: " + ans);
// **** return answer ****
return ans;
}
This is the memorized recursive call used to generate the number of combinations of tiles 1 x 4 and 4 x 1. The key is the way we recursively call f(n – 1) + f(n – 4) as we have already seen in the references.
/**
* Given a n x 4 matrix where n is a positive number,
* find the number of ways to fill the matrix with 1 x 4 tiles.
*
* Recursive call.
*
* Find the number of ways to fill an `N × 4` matrix with `1 × 4` tiles
* https://www.techiedelight.com/find-ways-fill-n-x-4-matrix-with-1-x-4-tiles/
*/
public static int findTotalWays(int n) {
// **** base case(s) ****
if (n < 1) return 0;
if (n < 4) return 1;
if (n == 4) return 2;
// **** combine the results of placing 1 tile horizontally
// and placing 4 tiles vertically ****
return findTotalWays(n - 1) + findTotalWays(n - 4);
}
This is the recursive call that is used to solve a different but similar problem. The information is in the comment section.
We have three conditions in the base case section.
If they are all passed we just perform the recursive calls in a similar fashion as we did in the f() implementation.
Note that this call does not make use of memoization. Both implementations (with and without memoization) were accepted by HackerRank.
I would say that this was a very educational experience. I did enjoy working on it. Perhaps the description could be simpler. At least I like the name given to the villain (Red John).
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John