Mixing
Polite Near-Sighted Drunk Bot on a Minefield
Clash Royale CLAN TAG#URR8PPP
up vote
11
down vote
favorite
As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.
Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).
After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.
Challenge
You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.
Input: An natural number representing n.
Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.
Rules
- Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
- Your algorithm must be able to handle inputs of
n<20 (can be adjusted if too hard) in a reasonable time. - This is a code-golf challenge.
- Iterating over all possibilities for a given n will most definitely not be accepted as an answer.
Test Cases
1->0
2->3
4->39
6->135
8->7735
10->28287
Example Calculation for n=6
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).
Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.
Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.
Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had:
1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.
1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.
2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (1,1) is 300.
Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:
3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.
3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.
1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (0,0) is 400.
Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.
code-golf restricted-complexity
asked Aug 19 at 14:51
Rushabh Mehta
522119
 |Â
show 3 more comments
up vote
11
down vote
favorite
As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.
Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).
After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.
Challenge
You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.
Input: An natural number representing n.
Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.
Rules
- Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
- Your algorithm must be able to handle inputs of
n<20 (can be adjusted if too hard) in a reasonable time. - This is a code-golf challenge.
- Iterating over all possibilities for a given n will most definitely not be accepted as an answer.
Test Cases
1->0
2->3
4->39
6->135
8->7735
10->28287
Example Calculation for n=6
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).
Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.
Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.
Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had:
1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.
1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.
2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (1,1) is 300.
Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:
3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.
3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.
1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (0,0) is 400.
Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.
code-golf restricted-complexity
asked Aug 19 at 14:51
Rushabh Mehta
522119
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
2
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
1
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
1
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03
 |Â
show 3 more comments
up vote
11
down vote
favorite
up vote
11
down vote
favorite
As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.
Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).
After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.
Challenge
You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.
Input: An natural number representing n.
Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.
Rules
- Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
- Your algorithm must be able to handle inputs of
n<20 (can be adjusted if too hard) in a reasonable time. - This is a code-golf challenge.
- Iterating over all possibilities for a given n will most definitely not be accepted as an answer.
Test Cases
1->0
2->3
4->39
6->135
8->7735
10->28287
Example Calculation for n=6
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).
Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.
Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.
Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had:
1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.
1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.
2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (1,1) is 300.
Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:
3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.
3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.
1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (0,0) is 400.
Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.
code-golf restricted-complexity
asked Aug 19 at 14:51
Rushabh Mehta
522119
As the title may suggest, this problem is semi-inspired by the Polite Near-Sighted Drunk Bot by @N.P.
Our poor bot is placed on a cartesian grid at the origin, and after each minute, it moves 1 unit in one of four directions (Up, Down, Left, Right).
After n minutes, all of the latent mines on the grid activate, killing any poor bot that might find themselves over them. The mines are located at all integer coordinates satisfying the equation |y|=|x|.
Challenge
You will be provided n, the number of minutes before the mines blast, as an input, and as an output, you must find the probability that the bot is dead.
Input: An natural number representing n.
Output: Let the probability the bot is dead be p/q, where p and q are relatively prime whole numbers (q can't be 0, but p can). Output p.
Rules
- Your algorithm must not run in exponential or higher time. It ideally should run in polynomial time or less.
- Your algorithm must be able to handle inputs of
n<20 (can be adjusted if too hard) in a reasonable time. - This is a code-golf challenge.
- Iterating over all possibilities for a given n will most definitely not be accepted as an answer.
Test Cases
1->0
2->3
4->39
6->135
8->7735
10->28287
Example Calculation for n=6
We have 4 possible moves: U, D, R, and L. The total number of paths that could be taken is 4^6, or 4096. There are 4 possible cases that land along the line y = x: x,y = ±1; x,y = ±2; x,y = ±3; or x = y = 0. We will count the number of ways to end up at (1,1), (2,2), and (3,3), multiply them by 4 to account for the other quadrants, and add this to the number of ways to end up at (0,0).
Case 1: The bot ends at (3, 3). In order for the bot to end up here, it must have had 3 right moves, and 3 up moves. In other words, the total number of ways to get here is the ways to rearrange the letters in the sequence RRRUUU, which is 6 choose 3 = 20.
Case 2: The bot ends at (2,2). In order for the bot to end up here, it could have had 2 up moves, 3 right moves, and 1 left move; or 2 right moves, 3 up moves, and 1 down move. Thus, the total number of ways to get here is sum of the ways to rearrange the letters in the sequences RRRLUU and UUUDRR, both of which are (6 choose 1) * (5 choose 2) = 60, for a total of 120 possibilities.
Case 3: The bot ends at (1,1). In order for the bot to end up here, it could have had:
1 right move, 3 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RUUUDD is (6 choose 1)*(5 choose 2) = 60.
1 up move, 3 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence URRRLL is (6 choose 1)*(5 choose 2) = 60.
2 right moves, 1 left move, 2 up moves, and 1 down move. In this case, the number of ways to rearrange the letters in the sequence UUDRRL is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (1,1) is 300.
Case 4: The bot ends at (0,0). In order for the bot to end up here, it could have had:
3 right moves and 3 left moves. In this case, the number of ways to rearrange the letters in the sequence RRRLLL is (6 choose 3) = 20.
3 up moves and 3 down moves. In this case, the number of ways to rearrange the letters in the sequence UUUDDD is (6 choose 3) = 20.
1 right move, 1 left move, 2 up moves, and 2 down moves. In this case, the number of ways to rearrange the letters in the sequence RLUUDD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
1 up move, 1 down move, 2 right moves, and 2 left moves. In this case, the number of ways to rearrange the letters in the sequence RRLLUD is (6 choose 1)* (5 choose 1)*(4 choose 2) = 180.
Thus, the total number of ways to end up at (0,0) is 400.
Adding these cases together, we get that the total number of ways to end up on |y| = |x| is 4(20 + 120 + 300) + 400 = 2160. Thus, our probability is 2160/4096. When this fraction is fully reduced, it is 135/256, so our answer is 135.
code-golf restricted-complexity
asked Aug 19 at 14:51
Rushabh Mehta
522119
edited Aug 19 at 22:05
asked Aug 19 at 14:51
Rushabh Mehta
522119
asked Aug 19 at 14:51
Rushabh Mehta
522119
asked Aug 19 at 14:51
Rushabh Mehta
522119
522119
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
2
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
1
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
1
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03
 |Â
show 3 more comments
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
2
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
1
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
1
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
2
2
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
1
1
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
1
1
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
17
down vote
accepted
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$$ f(n) = 2s-s^2text, where s=frac12^nbinomnn/2$$
and the binomial is understood to equal $0$ when $n/2$ isn't whole.
We can reason like this. What's the probability that the bot lands on the $y=x$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin $n$ times and get as many tails as heads. You must choose $n/2$ flips to be heads of $n$ flips, which can be done in $binomnn/2$ ways, of $2^n$ possible sequences overall, giving probability
$$s=frac12^nbinomnn/2$$
The probability of landing the $y=-x$ line is also $s$. So, the probability of landing on either line is the sum of these or $2s$, except we're double-counting the probability of landing of $x=y=0$ in both lines, and must subtract it to compensate.
It turns out the probability of landing on $x=y=0$ is just $s^2$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on $x=y$ and likewise with "Up or Right" and "Down or Left" for $x=-y$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.
So, the probability of landing on $x=y$ or $x=-y$ is $2s-s^2$.
The code computes the binomial $binomnn/2$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.
The solution is golfed by writing $2s-s^2$ as $1-(1-s)^2$ so that $s$ is only referenced once, and working without the $1/2^n$ fractions to stay within the integers. The computation is polynomial-time in $n$ even with the funky way of computing binomials.
After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.
Let's keep track of the values of $a=x+y$ and $b=x-y$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of $a$ and $b$, with the four directions corresponding to the four combinations.
So, a random move is equivalent to randomly adding $pm 1$ to $a$ and independently $pm 1$ to $b$. This is equivalent to doing separate random walks on $a$ and $b$.
Now, the robot ends on the line $x=y$ or $x=-y$ exactly when $a=0$ or $b=0$. So, the probability of ending with $a=0$ is $s=frac12^nbinomnn/2$ and likewise for $b=0$. Since the walks are independent, the probability that $aneq 0$ and $bneq 0$ is $(1-s)^2$, so the probability that at least one is zero is the complement $1-(1-s)^2$.
answered Aug 19 at 18:32
xnor
86k16181427
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
17
down vote
accepted
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$$ f(n) = 2s-s^2text, where s=frac12^nbinomnn/2$$
and the binomial is understood to equal $0$ when $n/2$ isn't whole.
We can reason like this. What's the probability that the bot lands on the $y=x$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin $n$ times and get as many tails as heads. You must choose $n/2$ flips to be heads of $n$ flips, which can be done in $binomnn/2$ ways, of $2^n$ possible sequences overall, giving probability
$$s=frac12^nbinomnn/2$$
The probability of landing the $y=-x$ line is also $s$. So, the probability of landing on either line is the sum of these or $2s$, except we're double-counting the probability of landing of $x=y=0$ in both lines, and must subtract it to compensate.
It turns out the probability of landing on $x=y=0$ is just $s^2$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on $x=y$ and likewise with "Up or Right" and "Down or Left" for $x=-y$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.
So, the probability of landing on $x=y$ or $x=-y$ is $2s-s^2$.
The code computes the binomial $binomnn/2$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.
The solution is golfed by writing $2s-s^2$ as $1-(1-s)^2$ so that $s$ is only referenced once, and working without the $1/2^n$ fractions to stay within the integers. The computation is polynomial-time in $n$ even with the funky way of computing binomials.
After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.
Let's keep track of the values of $a=x+y$ and $b=x-y$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of $a$ and $b$, with the four directions corresponding to the four combinations.
So, a random move is equivalent to randomly adding $pm 1$ to $a$ and independently $pm 1$ to $b$. This is equivalent to doing separate random walks on $a$ and $b$.
Now, the robot ends on the line $x=y$ or $x=-y$ exactly when $a=0$ or $b=0$. So, the probability of ending with $a=0$ is $s=frac12^nbinomnn/2$ and likewise for $b=0$. Since the walks are independent, the probability that $aneq 0$ and $bneq 0$ is $(1-s)^2$, so the probability that at least one is zero is the complement $1-(1-s)^2$.
answered Aug 19 at 18:32
xnor
86k16181427
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
add a comment |Â
up vote
17
down vote
accepted
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$$ f(n) = 2s-s^2text, where s=frac12^nbinomnn/2$$
and the binomial is understood to equal $0$ when $n/2$ isn't whole.
We can reason like this. What's the probability that the bot lands on the $y=x$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin $n$ times and get as many tails as heads. You must choose $n/2$ flips to be heads of $n$ flips, which can be done in $binomnn/2$ ways, of $2^n$ possible sequences overall, giving probability
$$s=frac12^nbinomnn/2$$
The probability of landing the $y=-x$ line is also $s$. So, the probability of landing on either line is the sum of these or $2s$, except we're double-counting the probability of landing of $x=y=0$ in both lines, and must subtract it to compensate.
It turns out the probability of landing on $x=y=0$ is just $s^2$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on $x=y$ and likewise with "Up or Right" and "Down or Left" for $x=-y$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.
So, the probability of landing on $x=y$ or $x=-y$ is $2s-s^2$.
The code computes the binomial $binomnn/2$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.
The solution is golfed by writing $2s-s^2$ as $1-(1-s)^2$ so that $s$ is only referenced once, and working without the $1/2^n$ fractions to stay within the integers. The computation is polynomial-time in $n$ even with the funky way of computing binomials.
After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.
Let's keep track of the values of $a=x+y$ and $b=x-y$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of $a$ and $b$, with the four directions corresponding to the four combinations.
So, a random move is equivalent to randomly adding $pm 1$ to $a$ and independently $pm 1$ to $b$. This is equivalent to doing separate random walks on $a$ and $b$.
Now, the robot ends on the line $x=y$ or $x=-y$ exactly when $a=0$ or $b=0$. So, the probability of ending with $a=0$ is $s=frac12^nbinomnn/2$ and likewise for $b=0$. Since the walks are independent, the probability that $aneq 0$ and $bneq 0$ is $(1-s)^2$, so the probability that at least one is zero is the complement $1-(1-s)^2$.
answered Aug 19 at 18:32
xnor
86k16181427
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
add a comment |Â
up vote
17
down vote
accepted
up vote
17
down vote
accepted
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$$ f(n) = 2s-s^2text, where s=frac12^nbinomnn/2$$
and the binomial is understood to equal $0$ when $n/2$ isn't whole.
We can reason like this. What's the probability that the bot lands on the $y=x$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin $n$ times and get as many tails as heads. You must choose $n/2$ flips to be heads of $n$ flips, which can be done in $binomnn/2$ ways, of $2^n$ possible sequences overall, giving probability
$$s=frac12^nbinomnn/2$$
The probability of landing the $y=-x$ line is also $s$. So, the probability of landing on either line is the sum of these or $2s$, except we're double-counting the probability of landing of $x=y=0$ in both lines, and must subtract it to compensate.
It turns out the probability of landing on $x=y=0$ is just $s^2$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on $x=y$ and likewise with "Up or Right" and "Down or Left" for $x=-y$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.
So, the probability of landing on $x=y$ or $x=-y$ is $2s-s^2$.
The code computes the binomial $binomnn/2$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.
The solution is golfed by writing $2s-s^2$ as $1-(1-s)^2$ so that $s$ is only referenced once, and working without the $1/2^n$ fractions to stay within the integers. The computation is polynomial-time in $n$ even with the funky way of computing binomials.
After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.
Let's keep track of the values of $a=x+y$ and $b=x-y$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of $a$ and $b$, with the four directions corresponding to the four combinations.
So, a random move is equivalent to randomly adding $pm 1$ to $a$ and independently $pm 1$ to $b$. This is equivalent to doing separate random walks on $a$ and $b$.
Now, the robot ends on the line $x=y$ or $x=-y$ exactly when $a=0$ or $b=0$. So, the probability of ending with $a=0$ is $s=frac12^nbinomnn/2$ and likewise for $b=0$. Since the walks are independent, the probability that $aneq 0$ and $bneq 0$ is $(1-s)^2$, so the probability that at least one is zero is the complement $1-(1-s)^2$.
answered Aug 19 at 18:32
xnor
86k16181427
Python 2, 65 bytes
def p(n):b=2**n;r=b*b-((~b)**n/b**(n/2)%-b)**2;print~n%2*r/(r&-r)
Try it online!
The probability the bot is dead can be expressed as:
$$ f(n) = 2s-s^2text, where s=frac12^nbinomnn/2$$
and the binomial is understood to equal $0$ when $n/2$ isn't whole.
We can reason like this. What's the probability that the bot lands on the $y=x$ line? This happens if the total number of up and left moves equals the total number of down and right moves. This is the same probability that, say, you flip a coin $n$ times and get as many tails as heads. You must choose $n/2$ flips to be heads of $n$ flips, which can be done in $binomnn/2$ ways, of $2^n$ possible sequences overall, giving probability
$$s=frac12^nbinomnn/2$$
The probability of landing the $y=-x$ line is also $s$. So, the probability of landing on either line is the sum of these or $2s$, except we're double-counting the probability of landing of $x=y=0$ in both lines, and must subtract it to compensate.
It turns out the probability of landing on $x=y=0$ is just $s^2$, the product of the probability of landing on each line. We can argue the events are independent as follows: if we pick a random sequence of equal numbers of "Up or Left" and "Down or Right" to land on $x=y$ and likewise with "Up or Right" and "Down or Left" for $x=-y$, we can uniquely combine them into a sequence of Up, Down, Left, Right by taking the intersection of the pairs of directions at each position.
So, the probability of landing on $x=y$ or $x=-y$ is $2s-s^2$.
The code computes the binomial $binomnn/2$ using this expression as (b+1)**n/b**(n/2)%b with base b=2**n. To extract the numerator from the probability fraction, we note that the denominator is a power of 2, so we use the expression r/(r&-r) to divide out the maximal power of 2 is r, expressed as the classic bit trick r&-r.
The solution is golfed by writing $2s-s^2$ as $1-(1-s)^2$ so that $s$ is only referenced once, and working without the $1/2^n$ fractions to stay within the integers. The computation is polynomial-time in $n$ even with the funky way of computing binomials.
After writing the proof of the probability the bot dies, I found a possibly cleaner way to prove it and present it.
Let's keep track of the values of $a=x+y$ and $b=x-y$ after each move of the bot. Each of the four directions up, down, left, and right either increments or decrements each of $a$ and $b$, with the four directions corresponding to the four combinations.
So, a random move is equivalent to randomly adding $pm 1$ to $a$ and independently $pm 1$ to $b$. This is equivalent to doing separate random walks on $a$ and $b$.
Now, the robot ends on the line $x=y$ or $x=-y$ exactly when $a=0$ or $b=0$. So, the probability of ending with $a=0$ is $s=frac12^nbinomnn/2$ and likewise for $b=0$. Since the walks are independent, the probability that $aneq 0$ and $bneq 0$ is $(1-s)^2$, so the probability that at least one is zero is the complement $1-(1-s)^2$.
answered Aug 19 at 18:32
xnor
86k16181427
edited Aug 24 at 1:03
answered Aug 19 at 18:32
xnor
86k16181427
answered Aug 19 at 18:32
xnor
86k16181427
answered Aug 19 at 18:32
xnor
86k16181427
86k16181427
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
add a comment |Â
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
3
3
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
Fantastic! I was waiting for someone to derive this. I didn't imagine it being so fast. The downside now is that most of the other answers won't have to think too much :(. Excellent +1
– Rushabh Mehta
Aug 19 at 19:16
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
enjoy the small bounty (don't have much to give so sorry)
– Rushabh Mehta
Aug 22 at 21:56
1
1
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
@RushabhMehta Thank you, that's very kind of you! Your bounty motivated me to write up a cleaner proof I thought of afterward.
– xnor
Aug 24 at 1:03
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
The real inspiration for this problem was AIME I 2014 problem 11, if you want to check it out.
– Rushabh Mehta
Aug 24 at 1:04
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170865%2fpolite-near-sighted-drunk-bot-on-a-minefield%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
I like the challenge but I think it would benefit from including a worked example for one of the very small test cases (2 or 3) for instance.
– Mr. Xcoder
Aug 19 at 15:08
@Mr.Xcoder I will add one when I have time.
– Rushabh Mehta
Aug 19 at 15:20
2
Interesting challenge. Note that using the word "ideally" in a rule makes it not a rule. It would be useful to say definitely one way or the other.
– trichoplax
Aug 19 at 21:48
1
But nobody talks about First Gen Learning Algorithm?
– Redwolf Programs
Aug 20 at 2:40
1
@RedwolfPrograms ahaha yea but this bot has the cooler name
– Rushabh Mehta
Aug 20 at 3:03