HackerRank Coin on the Table Problem Solution

In this post, we will solve HackerRank Coin on the Table Problem Solution.

You have a rectangular board consisting of n rows, numbered from 1 to n. and m columns, numbered from 1 to m. The top left is (1, 1) and the bottom right is (n, m). Initially – at time 0- there is a coin on the top-left cell of your board. Each cell of your board contains one of these letters:
*: Exactly one of your cells has letter ***
U: If at time t the coin is on cell (i, j) and cell (i, j) has letter ‘U’, the coin will be on cell (i-1, j) at time t +1, if i > 1. Otherwise, there is no coin on your board at time t+1.
L: If at time t the coin is on cell (i, j) and cell (i, j) has letter ‘L’. the coin will be on cell (i, j 1) at time t + 1, if j> 1. Otherwise, there is no coin on your board at time t+1.
D: If at time t the coin is on cell (i, j) and cell (i, j) has letter ‘D’, the coin will be on cell (+1, j) at time t +1. if i<N. Otherwise, there is no coin on your board at time t +1.R: If at time t the coin is on cell (i, j) and cell (i, j) has letter ‘R’, the coin will be on cell (i, j + 1) at time t +1, if j < M. Otherwise, there is no coin on your board at time t+1.

When the coin reaches a cell that has letter*, it will stay there permanently. When you punch on your board, your timer starts and the coin moves between cells. Before starting the game, you can make operations to change the board, such that you are sure that at or before time & the coin will reach the cell having letter *. In each operation you can select a cell with some letter other than * and change the letter to “U”. ‘L’, ‘R’ or ‘D’. You need to carry out as few operations as possible in order to achieve your goal. Your task is to find the minimum number of operations.
For example, given a grid of n = 2 rows and m = 3 columns:
UDL RR*
the goal is to get from (1, 1) to (2, 3) in as few steps as possible. As the grid stands, it cannot be done because of the U in the cell at (1, 1). If (1, 1) is changed to D. the path (1, 1) (2, 1)→ (2, 2) (2, 3) is available. It could also be changed to R which would make the path (1, 1)→ (1, 2)→ (2, 2)→ (2, 3) available. Either choice takes 1 change operation, which is the value sought if k > 3. A lower value of k would result in a return value of -1 because the shortest path is 3 steps, starting from (1, 1).

Function Description

Complete the coinOnTheTable function in the editor below. It should return an integer that represents the minimum operations to achieve the goal, or -1 if it is not possible.

coinOnTheTable has the following parameters:

m: an integer, the number of columns on the board
k: an integer, the maximum time to reach the goal
board: an array of strings where each string represents a row of the board

Output Format

Print an integer which represents the minimum number of operations required to achieve your goal. If you cannot achieve your goal, print .

Sample Input

2 2 3  
RD  
*L

Sample output :

Sample input :

2 2 1  
RD  
*L

Sample output :

Explanation :

In the first example, a valid path exists without making any changes. In the second example, the letter of cell (1,1) must be changed to ‘D’ to make a valid path. In each example, a path length <K is available.

Table of Contents

Coin on the Table C Solution

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

#define MAX_N 51

int N, M;
char Cells[MAX_N][MAX_N];
short CellChanges[MAX_N][MAX_N];

static void traceback(const int i, const int j, const int changes, const int k)
{
    CellChanges[i][j] = changes;

    if (i == 0 && j == 0)
    {
        return;
    }

    if (k == 0)
    {
        return;
    }

    if (changes >= CellChanges[0][0])
    {
        return;
    }

    if (0 < i)
    {
        if (Cells[i - 1][j] == 'D')
        {
            if (CellChanges[i - 1][j] > changes)
            {
                traceback(i - 1, j, changes, k - 1);
            }
        }
        else
        {
            if (CellChanges[i - 1][j] > (changes + 1))
            {
                traceback(i - 1, j, changes + 1, k - 1);
            }
        }
    }

    if (i < N)
    {
        if (Cells[i + 1][j] == 'U')
        {
            if (CellChanges[i + 1][j] > changes)
            {
                traceback(i + 1, j, changes, k - 1);
            }
        }
        else
        {
            if (CellChanges[i + 1][j] > (changes + 1))
            {
                traceback(i + 1, j, changes + 1, k - 1);
            }
        }
    }

    if (0 < j)
    {
        if (Cells[i][j - 1] == 'R')
        {
            if (CellChanges[i][j - 1] > changes)
            {
                traceback(i, j - 1, changes, k - 1);
            }
        }
        else
        {
            if (CellChanges[i][j - 1] > (changes + 1))
            {
                traceback(i, j - 1, changes + 1, k - 1);
            }
        }
    }

    if (j < M)
    {
        if (Cells[i][j + 1] == 'L')
        {
            if (CellChanges[i][j + 1] > changes)
            {
                traceback(i, j + 1, changes, k - 1);
            }
        }
        else
        {
            if (CellChanges[i][j + 1] > (changes + 1))
            {
                traceback(i, j + 1, changes + 1, k - 1);
            }
        }
    }
}

int main()
{
    int K, i, j, ei, ej;

    scanf("%d %d %d\n", &N, &M, &K);

    ei = -1;
    for (i = 0; i < N; i++)
    {
        char * const row = Cells[i];
        fread(row, 1, M, stdin);
        getchar(); // newline

        if (ei == -1)
        {
            for (j = 0; j < M; j++)
            {
                if (row[j] == '*')
                {
                    ei = i;
                    ej = j;
                    break;
                }
            }
        }

        for (j = 0; j < M; j++)
        {
            CellChanges[i][j] = (K + 1);
        }
    }

    traceback(ei, ej, 0, K);
    printf("%d", (CellChanges[0][0] <= K ? CellChanges[0][0] : -1));

    return 0;
}

Coin on the Table C++ Solution

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, K;
int*** dp;

int solve(int n, int m, int k, string* map) {
    if(dp[n][m][k] != -2) {
        return dp[n][m][k];
    }
    if(map[n][m] == '*') {
        return 0;
    }
    if(k == 0) {
        return -1;
    }
    auto result = -1;
    if(n > 0) {
        auto t = solve(n - 1, m, k - 1, map);
        if(t != -1) {
            if(map[n][m] != 'U') {
                t++;
            }
            if(result == -1) {
                result = t;
            } else {
                result = min(result, t);
            }
        }
    }
    if(m > 0) {
        auto t = solve(n, m - 1, k - 1, map);
        if(t != -1) {
            if(map[n][m] != 'L') {
                t++;
            }
            if(result == -1) {
                result = t;
            } else {
                result = min(result, t);
            }
        }
    }
    if(n + 1 < N) {
        auto t = solve(n + 1, m, k - 1, map);
        if(t != -1) {
            if(map[n][m] != 'D') {
                t++;
            }
            if(result == -1) {
                result = t;
            } else {
                result = min(result, t);
            }
        }
    }
    if(m + 1 < M) {
        auto t = solve(n, m + 1, k - 1, map);
        if(t != -1) {
            if(map[n][m] != 'R') {
                t++;
            }
            if(result == -1) {
                result = t;
            } else {
                result = min(result, t);
            }
        }
    }
    dp[n][m][k] = result;
    return result;
}

int main() {
    cin >> N >> M >> K;
    string map[N];
    dp = new int**[N];
    for(auto i = 0; i < N; i++) {
        dp[i] = new int*[M];
        for(auto j = 0; j < M; j++) {
            dp[i][j] = new int[K + 1];
            fill(dp[i][j], dp[i][j] + K + 1, -2);
        }
    }
    for(auto i = 0; cin >> map[i]; i++) {
    }
    cout << solve(0, 0, K, map);
    return 0;
}

Coin on the Table C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    static int         n;
    static int         m;
    static int         time;
    static char[][]    board;
    static int[,,]    memo;
    
    static void Main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */
        int[]   inputs = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
        int     changes;
        
        n = inputs[0];
        m = inputs[1];
        time = inputs[2];
        board = buildBoard(n, m);
        
        InitializeMemo();
        
        if ((changes = GetMinChanges(0, 0, time)) == Int32.MaxValue)
            Console.WriteLine("-1");
        else
            Console.WriteLine(changes);
    }
    
    static int GetMinChanges(int posN, int posM, int currTime){
        int res = Int32.MaxValue;
        
        if (posN < 0 || posN >= n || posM < 0 || posM >= m)
            return res;
        else if (board[posN][posM] == '*')
            return 0;
        else if (currTime == 0)
            return res;
        else if (memo[posN, posM, currTime - 1] != -1)
            return memo[posN, posM, currTime - 1];
        
        res = Math.Min(res, GetChangesToEnd(posN - 1, posM, currTime - 1, 'U'));
        res = Math.Min(res, GetChangesToEnd(posN + 1, posM, currTime - 1, 'D'));
        res = Math.Min(res, GetChangesToEnd(posN, posM - 1, currTime - 1, 'L'));
        res = Math.Min(res, GetChangesToEnd(posN, posM + 1, currTime - 1, 'R'));;
        
        memo[posN, posM, currTime - 1] = res;
        
        return res;
    }
    
    static int GetChangesToEnd(int posN, int posM, int currTime, char cell){
        int moves = GetMinChanges(posN, posM, currTime);
        
        if (moves != Int32.MaxValue){
            switch (cell){
                case 'U':
                    if (board[posN + 1][posM] != cell)
                        moves++;
                    break;
                case 'D':
                    if (board[posN - 1][posM] != cell)
                        moves++;
                    break;
                case 'L':
                    if (board[posN][posM + 1] != cell)
                        moves++;
                    break;
                default:
                    if (board[posN][posM - 1] != cell)
                        moves++;
                    break;
            }
        }
        
        return moves;
    }
    
    static void InitializeMemo(){
        memo = new int[n, m, time];
        
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < time; k++)
                    memo[i, j, k] = -1;
    }
    
    static char[][] buildBoard(int n, int m){
        char[][]    res = InitializeCharArray(n, m);
        
        for (int i = 0; i < n; i++){
            String  line = Console.ReadLine();
            
            for (int j = 0; j < m; j++)
                res[i][j] = line[j];
        }
        
        return res;
    }
    
    static char[][] InitializeCharArray(int n, int m){
        char[][]    res = new char[n][];
        
        for (int i = 0; i < n; i++)
            res[i] = new char[m];
        
        return res;
    }
}

Coin on the Table Java Solution

import java.util.Arrays;
import java.util.Scanner;


/**
 * My solution to "Coin On The Table" on HackerRank. 
 *
 * Note: Don't forget to change the class name to "Solution" 
 * before you test this code on HackerRank.
 *
 * @date May 13, 2014
 * 
 * @author PiouseLeo (https://www.hackerrank.com/PiouseLeo)
 */
public class CoinOnTheTable {

    private static int k;

    private static char[][] board;

    private static int[][] costs;

    private static int solve() {
        dfs(0, 0, 0, 0);

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j] == '*') {
                    int minCost = costs[i][j];
                    return minCost == Integer.MAX_VALUE ? -1 : minCost;
                }
            }
        }

        return -1;
    }

    private static void dfs(int i, int j, int cost, int time) {

        if (!inBoard(i, j) || cost >= costs[i][j]) {
            return;
        }

        costs[i][j] = cost;

        if (board[i][j] == '*') {
            return;
        }
        if (time == k) {
            return;
        }

        dfs(i - 1, j, board[i][j] == 'U' ? cost : cost + 1, time + 1);

        dfs(i, j - 1, board[i][j] == 'L' ? cost : cost + 1, time + 1);

        dfs(i + 1, j, board[i][j] == 'D' ? cost : cost + 1, time + 1);

        dfs(i, j + 1, board[i][j] == 'R' ? cost : cost + 1, time + 1);
    }

    private static boolean inBoard(int i, int j) {
        return i >= 0 && i < board.length && j >= 0 && j < board[i].length;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int m = scanner.nextInt();
        k = scanner.nextInt();
        scanner.nextLine();
        board = new char[n][];

        for (int i = 0; i < n; i++) {
            board[i] = scanner.nextLine().toCharArray();
        }
        costs = new int[n][m];
        for (int i = 0; i < costs.length; i++) {
            Arrays.fill(costs[i], Integer.MAX_VALUE);
        }

        System.out.println(solve());
        
        scanner.close();
    }
}

Coin on the Table JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'coinOnTheTable' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER m
 *  2. INTEGER k
 *  3. STRING_ARRAY board
 */

function coinOnTheTable(m, k, board) {
    let n = board.length;
    let target = [-1, -1];
    let dp = Array.from({length: n}, () => Array.from({length: m}, () => Array(k + 1).fill(10001)));
    
    const directions = {
        'U': [-1, 0],
        'L': [0, -1],
        'D': [1, 0],
        'R': [0, 1],
    };

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (board[i][j] === '*') {
                target = [i, j];
            }
        }
    }

    dp[0][0][0] = 0;
    let queue = [{i: 0, j: 0, time: 0}];

    while (queue.length > 0) {
        const {i, j, time} = queue.shift();

        for (const dir in directions) {
            const [di, dj] = directions[dir];
            const ni = i + di;
            const nj = j + dj;
            const nextTime = time + 1;

            if (ni >= 0 && ni < n && nj >= 0 && nj < m && nextTime <= k) {
                const changeRequired = board[i][j] !== dir ? 1 : 0;
                const newOperations = dp[i][j][time] + changeRequired;

                if (newOperations < dp[ni][nj][nextTime]) {
                    dp[ni][nj][nextTime] = newOperations;
                    queue.push({i: ni, j: nj, time: nextTime});
                }
            }
        }
    }

    let result = 10001;
    for (let t = 0; t <= k; t++) {
        result = Math.min(result, dp[target[0]][target[1]][t]);
    }
    return result === 10001 ? -1 : result;
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const m = parseInt(firstMultipleInput[1], 10);

    const k = parseInt(firstMultipleInput[2], 10);

    let board = [];

    for (let i = 0; i < n; i++) {
        const boardItem = readLine();
        board.push(boardItem);
    }

    const result = coinOnTheTable(m, k, board);

    ws.write(result + '\n');

    ws.end();
}

Coin on the Table Python Solution

#!/usr/bin

def solve(arr,i,j,n,m,k):

	if i<0 or j<0 or i>n-1 or j>m-1 or k<0 or (k==0 and arr[i][j]!='*'):
		return 100000
	if arr[i][j]=='*':
		return 0
	if mem[i][j][k]!=-1:
		return mem[i][j][k]
	min_val=100000
	x=solve(arr,i,j+1,n,m,k-1)
	if x!=100000:
		x=x+(0 if arr[i][j]=='R' else 1)
	min_val=min(min_val,x)
	x=solve(arr,i,j-1,n,m,k-1)
	if x!=100000:
		x=x+(0 if arr[i][j]=='L' else 1)
	min_val=min(min_val,x)
	x=solve(arr,i-1,j,n,m,k-1)
	if x!=100000:
		x=x+(0 if arr[i][j]=='U' else 1)
	min_val=min(min_val,x)
	x=solve(arr,i+1,j,n,m,k-1)
	if x!=100000:
		x=x+(0 if arr[i][j]=='D' else 1)
	min_val=min(min_val,x)

	mem[i][j][k]=min_val
	return min_val

n,m,k=input().split()
n=int(n)
m=int(m)
k=int(k)
arr=[[' ' for j in range(m)] for i in range(n)]
for i in range(n):
	str=input()
	arr[i]=list(str)
mem=[[[-1 for i in range(200)] for j in range(200)] for l in range(1100)]
x=solve(arr,0,0,n,m,k)
print(x if x!=100000 else -1)