# "Bot saves princess" AI problem from Hackerrank

I’m trying to solve this problem in AI section of hackerrank, the link to the problem : https://www.hackerrank.com/challenges/saveprincess/problem

What I would like to know is what knowledge/topic I want to know to solve this problem efficiently apart from problem solving, please suggest any books, lectures? I would like to learn AI problem solving…

Here is the description of the problem

Princess Peach is trapped in one of the four corners of a square grid. You are in the center of the grid and can move one step at a time in any of the four directions. Can you rescue the princess?

Input format

The first line contains an odd integer N (3 <= N < 100) denoting the size of the grid. This is followed by an NxN grid. Each cell is denoted by ‘-’ (ascii value: 45). The bot position is denoted by ‘m’ and the princess position is denoted by ‘p’.

Grid is indexed using Matrix Convention

Output format

Print out the moves you will take to rescue the princess in one go. The moves must be separated by ‘\n’, a newline. The valid moves are LEFT or RIGHT or UP or DOWN.

Sample input

``````3
---
-m-
p--
``````

Sample output

``````DOWN
LEFT
``````

Complete the function displayPathtoPrincess which takes in two parameters - the integer N and the character array grid. The grid will be formatted exactly as you see it in the input, so for the sample input the princess is at grid[2][0]. The function shall output moves (LEFT, RIGHT, UP or DOWN) on consecutive lines to rescue/reach the princess. The goal is to reach the princess in as few moves as possible.

The above sample input is just to help you understand the format. The princess (‘p’) can be in any one of the four corners.

Scoring
Your score is calculated as follows : (NxN - number of moves made to rescue the princess)/10, where N is the size of the grid (3x3 in the sample testcase).

for a problem like this it is really just problem solving.

If you really want a source, maybe something about pathfinding algorithms?
probably you can find somewhere the explanation of the kind of algorithm you need here, it is not something that it is easy to invent on your own. I have honesty no idea tho, maybe it was when I was reading about simulations?

you need to do two things: individuate in which corner the bot needs to go, and then figure out the shortest way to there.

If you want some similar algorithms, you can do these ones on codingames.com:

try this:
you need to remember how to search in certain points of a string (or array, depending on how you want to proceed)

and then, once you have which corner it is, how would you reach it in the shortest possible way if it was you controlling the bot and had the four arrows as control?

1 Like

This is a fairly typical introductory problem in AI, and there are lots of potential solutions. Keep in mind that AI basically comes down to two things: 1) knowledge representation and 2) search, and if you screw up the first one, the second one gets a lot harder. For your purposes, though, it’s the second point that matters – all you really need here is a good search algorithm.

What you’re searching over is generally the space of possible moves given the current board state. Basic algorithms are breadth-first and depth-first search, but you’ll need to be careful about cycles. Because you’re looking for the optimal (shortest) route, you’ll also need to track path lengths. Once you’re doing that, you can do some pruning of the search tree, and you’ll end up with some form of branch-and-bound or A*.

Good references are the Wumpus World problem from Russell & Norvig’s textbook on Artificial Intelligence, path finding algorithms in general, shortest path algorithms in particular, and tree search algorithms.

Hackerrank problems tend to be underspecified, so don’t make the assumption that the princess is in a corner, or that you’ll start in the center of the board.

Good luck!

1 Like