HackerRank Count Luck Problem Solution

In this post, we will solve HackerRank Count Luck Problem Solution.

Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they’ve managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.
Consider the forest as an N x M grid. Each cell is either empty (represented by .) or blocked by a tree (represented by X). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWN through empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character M, and the cell with the portkey is marked with a *. The upper-left corner is indexed as (0, 0).

.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.

In example above, Ron and Hermione are located at index (2, 7) and the portkey is at (1, 2). Each cell is indexed according to Matrix Conventions.
Hermione decides it’s time to find the portkey and leave. They start along the path and each time they have to choose a direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly k times. Can you determine if Ron’s guesses are correct?

.X.X.10000X
.X*0X0XXX0X
.XX0X0XM01.
...100XXXX.

There are three instances marked with 1 where Hermione must use her wand.

Note: It is guaranteed that there is only one path from the starting location to the portkey.

Function Description
Complete the countLuck function in the editor below. It should return a string, either Impressed if Ron is correct or Oops! if he is not.
countLuck has the following parameters:

matrix: a list of strings, each one represents a row of the matrix
k: an integer that represents Ron’s guess

Input Format
The first line contains an integer t, the number of test cases.
Each test case is described as follows:
The first line contains 2 space-separated integers n and m, the number of forest matrix rows and columns.
Each of the next n lines contains a string of length m describing a row of the forest matrix.
The last line contains an integer k, Ron’s guess as to how many times Hermione will wave her wand.

Output Format
On a new line for each test case, print Impressed if Ron impresses Hermione by guessing
correctly. Otherwise, print Oops!.

Sample Input

3
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

Sample Output

Impressed
Impressed
Oops!

Explanation
For each test case, count denotes the number of times Hermione waves her wand.
Case 0: Hermione waves her wand at (0, 2), giving us count = 1. Because
count = k = 1, we print Impressed on a new line.
Case 1: Hermione waves her wand at (2,9), (0,5), and (3, 3), giving us count = 3. =
Because count = k = 3, we print Impressed on a new line.
Case 2: Hermione waves her wand at (2,9), (0,5), and (3, 3), giving us count = 3.
Because count = 3 and k = 4. countk and we print Oops! on a new line.

Count Luck C Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE	100

char forest[MAX_SIZE][MAX_SIZE];
int path[MAX_SIZE][MAX_SIZE];
int N, M, K;

void find_start_pos(int *x, int *y)
{
	int i, j;

	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			if (forest[i][j] == 'M') {
				*x = i;
				*y = j;
			}
}

int is_marked(int i, int j)
{
	return path[i][j];
}

void mark(int i, int j)
{
	path[i][j] = 1;
}

int get_move_options(int i, int j, int *up, int *down, int *left, int *right)
{
	int count = 0;

	*up = 0;
	*down = 0;
	*left = 0;
	*right = 0;

	if (i > 0 && forest[i - 1][j] != 'X' && !is_marked(i - 1, j)) {
		count++;
		*up = 1;
	}
	if (i < N - 1 && forest[i + 1][j] != 'X' && !is_marked(i + 1, j)) {
		count++;
		*down = 1;
	}
	if (j > 0 && forest[i][j - 1] != 'X' && !is_marked(i, j - 1)) {
		count++;
		*left = 1;
	}
	if (j < M - 1 && forest[i][j + 1] != 'X' && !is_marked(i, j + 1)) {
		count++;
		*right = 1;
	}

	return count;
}

int waves_count(int i, int j, int count)
{
	int up, down, left, right;
	int up_ok, down_ok, left_ok, right_ok;
	int new_count;

	mark(i, j);

	/* too many waves */
	if (count > K)
		return -1;

	/* exit found */
	if (forest[i][j] == '*' && count == K)
		return count;

	/* we have to use the wand */
	new_count = count;
	if (get_move_options(i, j, &up_ok, &down_ok, &left_ok, &right_ok) > 1)
		new_count++;

	/* up */
	if (up_ok) {
		up = waves_count(i - 1, j, new_count);
		if (up != -1)
			return up;
	}

	/* down */
	if (down_ok) {
		down = waves_count(i + 1, j, new_count);
		if (down != -1)
			return down;
	}

	/* left */
	if (left_ok) {
		left = waves_count(i, j - 1, new_count);
		if (left != -1)
			return left;
	}

	/* right */
	if (right_ok) {
		right = waves_count(i, j + 1, new_count);
		if (right != -1)
			return right;
	}

	return -1;
}

int main()
{
	int T;
	int i, j, k;
	int x, y, count;

	scanf("%d", &T);
	for (i = 0; i < T; i++) {
		scanf("%d %d", &N, &M);
		for (j = 0; j < N; j++)
			for (k = 0; k < M; k++)
				scanf(" %c", &forest[j][k]);
		scanf("%d", &K);

		memset(path, 0, sizeof(path));
		find_start_pos(&x, &y);
		count = waves_count(x, y, 0);
		if (count == K)
			printf("Impressed\n");
		else
			printf("Oops!\n");
	}

	return 0;
}

Count Luck C++ Solution

#include <iostream>
#include <algorithm>
#include <vector>
#define checked 2
#define unchecked 1
#define cross 0

using namespace std;
int T,N,M,K;
vector< vector<char> > A;	
vector< vector<int> > check;	
typedef struct{
	int x,y;
}node;
int dfs(int x,int y,int now);
	
int main(){
	cin>>T;
	int X,Y;
	for(int q=1;q<=T;q++){
		A.clear();
		check.clear();
		cin>>N>>M;
		for(int i=0;i<N;i++){
			vector<char> temp(M);
			for(int j=0;j<M;j++){
				cin>>temp[j];
				if(temp[j] == 'M')		{ X=i;	Y=j;		}
			}
				
			A.push_back(temp);
		}
		cin>>K;
	for(int i=0;i<N;i++){
		vector<int > temp(M);
		for(int j=0;j<M;j++){
			if(A[i][j] == 'X')
				temp[j] = cross ;
			else
				temp[j] = unchecked;	
		}
		check.push_back(temp);	
	}
		
	if(dfs(X,Y,0) == K)
		cout<<"Impressed"<<endl;
	else
		cout<<"Oops!"<<endl;	
	}
	
	
	
	return 0;
}

int dfs(int x,int y,int now){
	if(A[x][y] == '*')
		return now;
	check[x][y] = checked;
	vector<node> temp2;
	if(x-1 >=0 && x-1<N && check[x-1][y] == unchecked){
		node zz;
		zz.x = x-1;
		zz.y = y;
		temp2.push_back(zz);
//		cout<<"up"<<endl;
	}
	if(x+1 >=0 && x+1<N && check[x+1][y] == unchecked){
		node zz;
		zz.x = x+1;
		zz.y = y;
		temp2.push_back(zz);
//		cout<<"down"<<endl;
	}
	if(y-1 >=0 && y-1<M && check[x][y-1] == unchecked){
		node zz;
		zz.x = x;
		zz.y = y-1;
		temp2.push_back(zz);
//		cout<<"left"<<endl;
	}
	if(y+1 >=0 && y+1<M && check[x][y+1] == unchecked){
		node zz;
		zz.x = x;
		zz.y = y+1;
		temp2.push_back(zz);
//		cout<<"right"<<endl;
	}
//	cout<<"temp2 size = "<<temp2.size()<<" when x="<<x<<" y="<<y<<" N="<<N<<" M="<<M<<" check[x][y+1] = "<<check[x][y+1]<<endl;
	if(temp2.size() == 0)
		return -1;
	else if(temp2.size() == 1)
		return dfs(temp2[0].x,temp2[0].y,now);	
	else{
		for(int a=0;a<temp2.size();a++){
			int xx=dfs(temp2[a].x,temp2[a].y,now+1);
			if( xx != -1  )
				return xx;
		
		}
		
	}
//cout<<"ERROR !!!  "<<x<<" "<<y<<"temp2.size = "<<temp2.size()<<endl;			
return -1;
}

Count Luck C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

struct PointState{
    public int X;
    public int Y;
    
    public int waves;
}

class Solution {
    
    static bool CanGoThere(int[,] map, int x, int y, int N, int M){
        if((x < 0) || (y<0) || (x >= M) || (y >= N)){
            return false;
        }
        
        if(map[x,y] == freeId || map[x,y] == destId){
            return true;
        }
        
        return false;
    }
    
    static void TryAddPoint(bool canGoThere, int X, int Y, int newWaves, Queue<PointState> q, int[,] map){
        if(!canGoThere){
            return;
        }
        
        if(map[X,Y] != destId){
            map[X,Y] = visitedId;
        }
        
        PointState p = new PointState();
        p.X = X;
        p.Y = Y;
        p.waves = newWaves;
        
        q.Enqueue(p);
    }
    
    static int GetMagicWaves(int[,] map, int startX, int startY, int N, int M){
        Queue<PointState> q = new Queue<PointState>();
        
        PointState start = new PointState();
        start.X = startX;
        start.Y = startY;
        start.waves = 0;
        
        q.Enqueue(start);
        
        while(q.Any()){
            
            var point = q.Dequeue();
            
            if(map[point.X,point.Y] == destId){
                return point.waves;
            }
            
            bool canGoSouth = CanGoThere(map, point.X, point.Y+1, N,M);
            bool canGoNorth = CanGoThere(map, point.X, point.Y-1, N,M);
            bool canGoWest = CanGoThere(map, point.X-1, point.Y, N,M);
            bool canGoEast = CanGoThere(map, point.X+1, point.Y, N,M);
            
            int optionsCount = (canGoSouth ? 1 : 0) + 
                (canGoNorth ? 1 : 0) +
                (canGoWest ? 1 : 0) +
                (canGoEast ? 1 : 0);
            
            int newWaves = point.waves;
            
            if(optionsCount > 1){
                newWaves ++;
            }
            
            TryAddPoint(canGoSouth, point.X, point.Y+1, newWaves, q, map);
            TryAddPoint(canGoNorth, point.X, point.Y-1, newWaves, q, map);
            TryAddPoint(canGoWest, point.X-1, point.Y, newWaves, q, map);
            TryAddPoint(canGoEast, point.X+1, point.Y, newWaves, q, map);
            
            
        }
        return -1;
    }
    
    const int freeId = 0;
    const int treeId = -1;
    const int startId = -2;
    const int destId = -3;
    const int visitedId = -4;
    
    static void Main(String[] args) {
        int T = int.Parse(Console.ReadLine());
        
        for(int t = 0; t<T; t++){
            int N,M,K;
            
            var splitted = Console.ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
            N = splitted[0];
            M = splitted[1];
            
            int startX = 0, startY = 0;
            int[,] map = new int[M,N];
            
            for(int y = 0;y<N; y++){
                string str = Console.ReadLine();
                for(int x = 0; x<M; x++){
                    if(str[x] == '.'){
                        map[x,y] = 0;
                    }
                    else if(str[x] == 'X'){
                        map[x,y] = treeId;
                    } else if(str[x] == 'M'){
                        map[x,y] = startId;
                        startX = x;
                        startY = y;
                    } else if(str[x] == '*'){
                        map[x,y] = destId;
                    }                    
                }
            }
            
            K = int.Parse(Console.ReadLine());
            
            int waves = GetMagicWaves(map, startX, startY, N, M);
            if(waves == K){
                Console.WriteLine("Impressed");
            } else{
                Console.WriteLine("Oops!");
            }
        }
    }
}

Count Luck Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {
    private static final int EMPTY_CELL = 1;
    private static final int TREE_CELL = 0;
    private static final int START_CELL = 3;
    private static final int FINAL_CELL = 4;

    private static int startRow = 0;
    private static int startCol = 0;
    /*
     * Complete the 'countLuck' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts following parameters:
     *  1. STRING_ARRAY matrix
     *  2. INTEGER k
     */

    public static String countLuck(List<String> matrix, int k) {
    // Write your code here
        int[][] map = parseMatrix(matrix);
        int guessing = countGuessing(map);

        return guessing == k ? "Impressed" : "Oops!";
    }

    private static int[][] parseMatrix(List<String> matrix) {
        int rows = matrix.size();
        int cols = matrix.get(0).length();
        int[][] map = new int[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char c = matrix.get(i).charAt(j);
                if (c == '.') {
                    map[i][j] = EMPTY_CELL;
                }
                else if (c == 'X') {
                    map[i][j] = TREE_CELL;
                }
                else if (c == 'M') {
                    map[i][j] = START_CELL;
                    startRow = i;
                    startCol = j;
                }
                else {
                    map[i][j] = FINAL_CELL;
                }
            }
        }

        return map;
    }

    private static int countGuessing(int[][] map) {
        int rows = map.length;
        int cols = map[0].length;
        boolean[][] visited = new boolean[rows][cols];


        visited[startRow][startCol] = true;
        LinkedList<Cell> queue = new LinkedList<>();
        queue.add(new Cell(startRow, startCol, 0));

        while (!queue.isEmpty()) {
            Cell currentCell = queue.removeFirst();
            int row = currentCell.row;
            int col = currentCell.col;
            int currentGuessing = currentCell.guessing;

            if (map[row][col] == FINAL_CELL) return currentGuessing;

            boolean needGuessing = checkGuessing(map, visited, row, col);
            if (needGuessing) currentGuessing++;

            visited[row][col] = true;
            
            if (isValid(map, row + 1, col) && !visited[row + 1][col] && map[row + 1][col] != TREE_CELL) queue.add(new Cell(row + 1, col, currentGuessing));
            if (isValid(map, row, col - 1) && !visited[row][col - 1] && map[row][col - 1] != TREE_CELL) queue.add(new Cell(row, col - 1, currentGuessing));
            if (isValid(map, row, col + 1) && !visited[row][col + 1] && map[row][col + 1] != TREE_CELL) queue.add(new Cell(row, col + 1, currentGuessing));
            if (isValid(map, row - 1, col) && !visited[row - 1][col] && map[row - 1][col] != TREE_CELL) queue.add(new Cell(row - 1, col, currentGuessing));

        }

        return 0;
    }
    
    private static boolean isValid(int[][] map, int row, int col) {
        int rows = map.length;
        int cols = map[0].length;

        if (row < 0 || row >= rows) return false;
        if (col < 0 || col >= cols) return false;

        return true;
    }

    private static boolean checkGuessing(int[][] map, boolean[][] visited, int row, int col) {
        int adjEmptyCells = 0;

        if (isValid(map, row + 1, col) && map[row + 1][col] != TREE_CELL && !visited[row + 1][col]) adjEmptyCells++;
        if (isValid(map, row, col - 1) && map[row][col - 1] != TREE_CELL && !visited[row][col - 1]) adjEmptyCells++;
        if (isValid(map, row, col + 1) && map[row][col + 1] != TREE_CELL && !visited[row][col + 1]) adjEmptyCells++;
        if (isValid(map, row - 1, col) && map[row - 1][col] != TREE_CELL && !visited[row - 1][col]) adjEmptyCells++;

        return adjEmptyCells > 1;
    }

    private static class Cell {
        int row;
        int col;
        int guessing;

        public Cell(int row, int col, int guessing) {
            this.row = row;
            this.col = col;
            this.guessing = guessing;
        }
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int t = Integer.parseInt(bufferedReader.readLine().trim());

        IntStream.range(0, t).forEach(tItr -> {
            try {
                String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

                int n = Integer.parseInt(firstMultipleInput[0]);

                int m = Integer.parseInt(firstMultipleInput[1]);

                List<String> matrix = IntStream.range(0, n).mapToObj(i -> {
                    try {
                        return bufferedReader.readLine();
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                })
                    .collect(toList());

                int k = Integer.parseInt(bufferedReader.readLine().trim());

                String result = Result.countLuck(matrix, k);

                bufferedWriter.write(result);
                bufferedWriter.newLine();
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        });

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Count Luck JavaScript Solution

var turns = []
var searched = []

function processData(input) {
    input = input.split('\n')
    var T = input.shift()
    var testStart = 0
    
    for (var test = 0; test < T; test++){
        var line = input[testStart].split(' ').map(Number)
        var N = line[0]
        var M = line[1]
        var K = Number(input[N+testStart+1])
                
        var forest = []
        
        var startR = -1
        var startC = -1
        var endR = -1
        var endC = -1
        
        for (var k = 0; k < N; k++){
            forest[k] = input[testStart+k+1].split('')
            var star = forest[k].indexOf('*')
            var m = forest[k].indexOf('M')
            
            if (star > -1){ endR = k; endC = star }
            if (m > -1){ startR = k; startC = m }
            
        }
        testStart += N+2
        
        for (var row = 0; row < N; row++){
            turns[row] = []
            searched[row] = []
            for (var col = 0; col < M; col++){
                turns[row][col] = 'X'
                searched[row][col] = false
            }
        }
        turns[startR][startC] = 0
        
        depthFirstSearch(forest,N,M,startR,startC,'','',endR,endC)
        
        
        if (K === turns[endR][endC]){
            console.log('Impressed')
        } else {
            console.log('Oops!')
        }
        
        //console.log(turns.join('\n')+ '\n')
        //console.log(turns[endR][endC])
        //console.log(K)
        
        
    }
    
} 



function depthFirstSearch(A,N,M,row,col,dir,lastDir,endR,endC){
    if (row >= N || row < 0 || col >= M || col < 0 || A[row][col]==='X' || searched[row][col]){ return }
    searched[row][col] = true
    
    
    switch (dir) {
        case 'D':
            turns[row][col] = turns[row-1][col]
            break;
        case 'L':
            turns[row][col] = turns[row][col+1]
            break;
        case 'R':
            turns[row][col] = turns[row][col-1]
            break;
        case 'U':
            turns[row][col] = turns[row+1][col]
            break;
        default:
            break;
    }
    
//    if (dir !== lastDir){
//       turns[row][col]++
//    }
    
    
    var D = true
    var L = true
    var R = true
    var U = true
    
    var possDir = 0
    // check left
    var newRow = row
    var newCol = col-1
    if ( newCol < 0 || A[newRow][newCol]==='X' || searched[newRow][newCol] ){
        L = false
    } else {
        L = true
        possDir++
        
    }
    
    // check right
    var newRow = row
    var newCol = col+1
    if ( newCol >= M || A[newRow][newCol]==='X' || searched[newRow][newCol] ){
        R = false
    } else {
        R = true
        possDir++
        
    }
    
    // check down
    var newRow = row+1
    var newCol = col
    if ( newRow >= N || A[newRow][newCol]==='X' || searched[newRow][newCol] ){
        D = false
    } else {
        D = true
        possDir++
        
    }
    
    // check up
    var newRow = row-1
    var newCol = col
    if ( newRow < 0 || A[newRow][newCol]==='X' || searched[newRow][newCol] ){
        R = false
    } else {
        R = true
        possDir++

    }
    
    
    if (possDir > 1 && !(row === endR && col === endC)){ turns[row][col]++}
    
    depthFirstSearch(A,N,M,row,col-1,'L',dir,endR,endC)
    depthFirstSearch(A,N,M,row,col+1,'R',dir,endR,endC)
    depthFirstSearch(A,N,M,row+1,col,'D',dir,endR,endC)
    depthFirstSearch(A,N,M,row-1,col,'U',dir,endR,endC)
    return
} 



process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

Count Luck Python Solution

import sys

def getLength():
    return sys.stdin.readline().split()

def getBoard(times):
    board = []
    for x in range(times):
        board.append(list(sys.stdin.readline()))
    return board

def findHermione(board):
    for row, rData in enumerate(board):
        try:
            column = rData.index('M')
        except ValueError:
            continue
        return [row, column]
    return -1

def makeMoves(curPos, pastPos=None, waves=0):
    positions.append(curPos)
    moves = []
    y = curPos[0]
    x = curPos[1]
    herms = board[y][x]
    pastY = pastPos[0] if pastPos else curPos[0]
    pastX = pastPos[1] if pastPos else curPos[1]
    
    for move in range(-1,2,2):
        if ((x+move) in range(0, columns)) & ((x+move) != pastX):
            if board[y][x+move] == '.' or board[y][x+move] == '*':
                moves.append([y,x+move])
        if ((y+move) in range(0, rows)) & ((y+move) != pastY):
            if board[y+move][x] == '.' or board[y+move][x] == '*':
                moves.append([y+move,x])

    checkWin(herms, waves)

    if len(moves) == 0:
        positions.remove(curPos)
    elif len(moves) == 1:
        makeMoves(moves[0], curPos, waves)
    else:
        waves += 1
        for move in moves:
            makeMoves(move, curPos, waves)

def checkWin(herms, waves):
    if herms == '*':
        print('Impressed' if waves == k else 'Oops!')
    
testCases = int(sys.stdin.readline())
for times in range(0, testCases):
    length = getLength()
    rows = int(length[0])
    columns = int(length[1])
    board = getBoard(rows)
    k = int(sys.stdin.readline())
    positions = []
    makeMoves(findHermione(board))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python