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
Task
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
thank you, your answer is helpful!
Thank you Millar, you’ve given me some direction, I’ll also read your mentioned book by Russell & Norvig on Artificial Intelligence.