I received an email message from HackerRank inviting me to solve the Ice Cream Parlor challenge. It seems like I have already solved the challenge as illustrated in the Ice Cream Parlor – Part II post. On several occasions I have received invitations to solve challenges that I have already addressed. Perhaps HackerRank did not like my solutions ;o)
On this post I will address the Count Luck challenge from HackerRank. You can read in the discussions section how the challenge was initially given an easy difficulty level and then changed to medium. There is a reference to the Connected Cells in a Grid – Follow Up challenge which I have already solved in this blog. In retrospect, for me this challenge was harder than the one mentioned in the discussion.
In a future post (should not be committing because my plate is quite full with other topics) I will address this challenge a second time using what I consider a better approach.
Following is a screen dump from the console of the Eclipse IDE with the sample input, some sample data listed in the discussion section and some that I used while working on the solution:
20 3 6 *M.... .X.X.X XXX... 1 5 11 ..........* .XXXXXXXXXX ........... XXXXXXXXXX. M.......... 0 2 3 *.M .X. 1 4 11 .X.X......X .X*.X.XXX.X .XX.X.XM... ......XXXX. 3 4 11 .X.X......X .X*.X.XXX.X .XX.X.XM... ......XXXX. 4 3 6 *.M... .X.X.X XXX... 1 3 6 *..M.. .X.X.X XXX... 2 3 6 *....M .X.X.X XXX... 2 3 6 *..... .X.X.X XXX.M. 3 5 11 ..........* .XXXXXXXXXX ........... XXXXXXXXXX. M.......... 0 3 3 .X* .X. M.. 1 3 3 ..* X.X M.. 2 3 3 ..* .XX M.. 1 3 3 ..* .XX ..M 0 5 11 ..........* .XXXXXXXXX. ........... XXXXXXXXXX. M.......... 1 5 11 ..........* .XXXXXXXXX. ........... .XXXXXXXXX. M.......... 2 5 11 ..X.......* .XX.XXXXXXX .XX........ .XXXXXXXXX. M.......... 1 5 11 .X......X.* .X.XXXXXX.X .X......X.. .XXXXXXXXX. M.......... 1 5 11 ....X...X.* .XX...X...X ..XXXX.XXXX X.XX.X.XXX. M.......... 1 3 3 *.M .X. ..X 1 Impressed Impressed Impressed Impressed Oops! Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed Impressed
Only one of the test cases fails (Oops!).
I experimented with different approaches until I had enough. The core approach is to perform a breadth first search for the port on the matrix. The algorithm finds the port key (‘*’). That is quite straight forward. The trick is how to determine how many times the wand was waved. It is important to note that the wand only needs to be waved at forks and not at changes of direction. If there are no forks in the path (illustrated in the sample data) then there is no need to wave the wand.
Following is the test code and my solution written in Java 8:
import java.util.Scanner;
import java.util.Stack;
public class Soulution {
/**
*
*/
static class Point {
// **** ****
int r = -1;
int c = -1;
int f = 0;
/**
* Constructor
*/
public Point(int r, int c, int f) {
this.r = r;
this.c = c;
this.f = f;
}
/**
* Generate string representation.
*/
public String toString() {
return "(" + this.r + "," + c + "," + this.f +")";
}
}
// **** ****
static char[][] matrix = null;
static int rows = 0;
static int cols = 0;
static Stack<Point> bt = null;
/**
* Depth first search (recursive).
*/
static boolean dfs(int r, int c) {
boolean found = false;
// **** check if we found the port key ****
if (matrix[r][c] == '*') {
return true;
}
// **** flag that this cell as been visited ****
matrix[r][c] = 'V';
// **** to enable backtracking ****
bt.push(new Point(r, c, countForks(r, c)));
// **** UP ****
if ((r - 1 >= 0) && ((matrix[r - 1][c] == '.') || (matrix[r - 1][c] == '*'))) {
found = dfs(r - 1, c);
if (found) {
return true;
}
}
// **** RIGHT ****
if ((c + 1 < cols) && ((matrix[r][c + 1] == '.') || (matrix[r][c + 1] == '*'))) {
found = dfs(r, c + 1);
if (found) {
return true;
}
}
// **** DOWN ****
if ((r + 1 < rows) && ((matrix[r + 1][c] == '.') || (matrix[r + 1][c] == '*'))) { found = dfs(r + 1, c); if (found) { return true; } } // **** LEFT **** if ((c - 1 >= 0) && ((matrix[r][c - 1] == '.') || (matrix[r][c - 1] == '*'))) {
found = dfs (r, c - 1);
if (found) {
return true;
}
}
// **** ****
bt.pop();
// **** did not find the port key ****
return false;
}
/**
* Count forks at this point.
*/
static int countForks(int r, int c) {
int forks = 0;
// **** UP ****
if (r > 0 && (matrix[r - 1][c] == '.' || matrix[r - 1][c] == '*')) {
forks++;
}
// **** RIGHT ****
if (c + 1 < cols && (matrix[r][c + 1] == '.' || matrix[r][c + 1] == '*')) {
forks++;
}
// **** DOWN ****
if (r + 1 < rows && (matrix[r + 1][c] == '.' || matrix[r + 1][c] == '*')) { forks++; } // **** LEFT **** if (c > 0 && (matrix[r][c - 1] == '.' || matrix[r][c - 1] == '*')) {
forks++;
}
// **** return all possible forks ****
return forks;
}
/**
* Find the port key and count wand moves.
*/
static int findPortKey(int mr, int mc) {
bt = new Stack<Point>();
int count = 0;
// **** perform a depth first search ****
dfs(mr, mc);
// **** count the wand waves ****
while (!bt.isEmpty()) {
Point pt = bt.pop();
if (pt.f > 1) {
count++;
}
}
// **** return count of wand moves ****
return count;
}
/**
* Test code.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** get number of test cases ****
int T = sc.nextInt();
sc.nextLine();
// **** loop once per test case ****
for (int t = 0; t < T; t++) {
int mr = -1;
int mc = -1;
// **** read number of rows and columns ****
rows = sc.nextInt();
cols = sc.nextInt();
sc.nextLine();
// **** allocate matrix ****
matrix = new char[rows][cols];
// **** read and populate matrix ****
for (int r = 0; r < rows; r++) {
String line = sc.nextLine();
for (int c = 0; c < cols; c++) {
matrix[r][c] = line.charAt(c);
if (matrix[r][c] == 'M') {
mr = r;
mc = c;
}
}
}
// **** read prediction ****
int k = sc.nextInt();
// **** find port key ****
int directions = findPortKey(mr, mc);
// **** generate response ****
System.out.println(k == directions ? "Impressed" : "Oops!");
}
// **** close scanner ****
sc.close();
}
}
The Point class is used to keep track of what is going on when a fork is encountered. The coordinates and the number of paths are recorded. I removed the messages from the code but if you are interested in this challenge and would like to fully understand the solution here presented you could display information when a point is created and pushed into the stack. By looking at the console you should quickly be able to determine what to do to produce the results required (number of wand moves).
I though this challenge was very interesting and harder that what is posted. I do enjoy the HackerRank and the LeetCode challenges. They make you think, review and in some cases learn something new.
If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
Enjoy;
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa