16
1
Given the size of the chess board and initial position of the knight, calculate the probability that after k
moves the knight will be inside the chess board.
Note:
The knight makes its all 8 possible moves with equal probability.
Once the knight is outside the chess board it cannot come back inside.
Input
Inputs are comma separated in the form:
l,k,x,y
where l
is the length and width of the chess board, k
is the number of moves the knight will make, x
is the x-position of the initial position of the knight, and y
is the y-position of the initial position of the knight. Note that 0,0
is the bottom-left corner of the board and l-1,l-1
is the top-right corner of the board.
Algorithm:
Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.
As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.
Credit
This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.
1@Edi - Can you clarify the input format and parameters a bit more ? Everything else looks okay imo. – Optimizer – 2015-05-25T09:53:59.897
14Why do you prescribe an exact algorithm? I'm not sure if there actually is a more elegant alternative, but requiring a specific algorithm could potentially prevent other clever approaches. Also, I don't think you need to specify the coordinate system in so much detail - it doesn't affect the probability at all. – Martin Ender – 2015-05-25T11:00:37.657
@MartinBüttner I actually edited in the entire Input section. I specified the coordinate system since I figured someone might ask about it if I left it missing. – absinthe – 2015-05-25T11:39:10.487
2"Inputs are comma separated in the form: l,k,x,y" - so the input is a string that we have to parse? Is it not acceptable to write a function that takes 4 parameters? – Cristian Lupascu – 2015-05-25T12:58:10.643
3@Edi Don't mark an answer as 'accepted' if there has been no time for other people to give it a try - marking something as accepted so is basically saying 'The challenge is over' - while most of the world has probably not even had time to look at it! – Sanchises – 2015-05-25T14:42:59.083
@w0lf that's what the currently accepted answer does. So it is 'yes' – edc65 – 2015-05-25T16:26:26.600
The title and first paragraph imply that we should be calculating probability, but the Algorithm section says to return either 0 or 1. Could you make it a bit more clear as to what we're supposed to end up with? – M. I. Wright – 2015-05-25T16:48:30.907
@M.I.Wright when stopping recursion you return 1 or 0, but the returned values are summed and multiplied by their probability (that is 1/8). You end up with a probability value between 0 and 1 indeed – edc65 – 2015-05-25T16:58:17.177
Can the knight leave the board, and come back on? – JNF – 2015-05-25T17:33:07.910
@JNF No:
Once the knight is outside the chess board it cannot come back inside.
– DLosc – 2015-05-25T17:48:58.893In the 5x5 square shown there are just 6 different positions, equivalent by symmetry. In a k x k square the number is ..... Each position has a probability of switching to one of the other positions. So there is a simple recursive formula. Or have I missed something? – John Bibby – 2015-05-25T18:52:38.280
@JohnBibby Nope, that's correct. Like it's written in the challenge post, there's a simple recursive algorithm. Your job is to implement the recursion in the least amount of chars. – Jakube – 2015-05-25T19:22:06.153
@sanchises okay. – Slim – 2015-05-26T01:53:31.003
3
@Edi Please stop posting random challenges you find on the web. Plagiarism is frowned on by our community. Challenges from ongoing programming competitions have no business here at all, since they may help someone winning this competition. And are challenges, which are discussed in a blog post, like this chess challenge (original source), will not be well-received here. One reason is, that the original source may have some sort of copyright.
– Jakube – 2015-05-26T08:22:41.4202@Edi For instance the source of this challenge allows copying and redistributing, but only if you give appropriate credit. – Jakube – 2015-05-26T08:23:58.327