英文:
Probability of moving on a cartesian plane
问题
我正在处理以下编程问题,看起来更像是一个概率问题而不是一个编程问题。
平台由5个顶点组成。这些顶点的坐标分别是:(-1,0), (0,-1), (0,0), (0,1), (1,0)。
你从顶点(xs,ys)开始,并随机向左(即x坐标减1)、向右(即x坐标加1)、向上或向下移动。后续移动的方向是独立的。
在掉出平台之前,你到达顶点(xe,ye)的概率是多少?
约束条件:
(xs, ys)在[(-1,0), (0,-1), (0,0), (0,1), (1,0)]范围内
(xe, ye)在[(-1,0), (0,-1), (0,0), (0,1), (1,0)]范围内
xs != xe 或 ys != ye
以下是我实现的代码,对于我分享的案例有效,但对于所有其他情况都失败了
def calculate_probability(xs, ys, xe, ye):
edges = [[-1, 0], [0, -1], [0, 1], [1, 0]]
if [xs, ys] in edges:
if xe == 0 and ye == 0:
return 0.25
elif xs == xe and ys == ye:
return 1.0
elif [xe, ye] in edges:
return 0.075
if xs == 0 and ys == 0:
if [xe, ye] in edges:
return 0.3
elif xe == 0 and ye == 0:
return 1
return 0
英文:
I am working on the below coding problem which looks more like a probability question rather than a coding problem
platform consisting of 5 vertices. The coordinates of the vertices are: (-1,0), (0.-1). (0,0), (0.1). (1.0).
You start at vertex (xs,ys)
and keep moving randomly either left (i.e., x coordinate decreases by 1), right (i.e., x coordinate increases by 1), up, or
down. The direction of subsequent moves is independent.
What is the probability that you reach vertex (xe, ye)
before falling off the platform?
Constraints:
(xs, ys) in [(-1.0), (0.-1), (0.0), (0.1), (1,0)]
(xe, ye) in [(-1,0), (0.-1), (0,0), (0,1), (1.0)]
xs != xend or ys != yend
below is what I implemented which works for the case I shared but fails for all other cases
def calculate_probability(xs, ys, xe, ye):
edges = [[-1, 0], [0, -1], [0, 1], [1, 0]]
if [xs, ys] in edges:
if xe == 0 and ye == 0:
return 0.25
elif xs == xe and ys == ye:
return 1.0
elif [xe, ye] in edges:
return 0.075
if xs == 0 and ys == 0:
if [xe, ye] in edges:
return 0.3
elif xe == 0 and ye == 0:
return 1
return 0
答案1
得分: 7
If we handle the edge cases where you start at your destination, or you start at an edge and the destination is the center, we're left with a simple scenario: find your way to the center, and then to the destination. Getting to the origin is a flat 0.25
probability, and then it's just a matter of getting to the right edge. If you randomly walk in the wrong direction, you can always backtrack with 0.25
probability of success. This can repeat any number of times before walking in the correct direction (to the destination).
This means from the origin, we have a 1/4 chance of picking the right direction, and a 3/4 chance of picking the wrong direction. If we pick the right direction, we're done, if we pick the wrong direction, we have to pick the opposite direction to get back to the origin and avoid falling off, which is a 1/4 chance. Combining these into one, we have a 1/4 of being right the first time, and 3/16 chance at a second chance. Continuing this repeatedly, we end up with a formula like:
1/4 + 1/4 * (3/16) + 1/4 * (3/16)^2 + 1/4 * (3/16)^3 + ...
= 1/4 * (1 + (3/16) + (3/16)^2 + (3/16)^3 + ...)
= 1/4 * (16/13)
= 4/13
So from the origin, we have a 4/13
chance of walking to the correct edge tile without falling off.
In code:
def solve(xs, ys, xe, ye):
# already at destination
if xs == xe and ys == ye:
return 1
# if destination is the origin, the probability is a flat 0.25
if xe == 0 and ye == 0:
return 0.25
# first move must take you to the origin if not already there
prob = 0.25 if xs != 0 or ys != 0 else 1
# multiply by probability of walking from origin to destination
return prob * 4 / 13
Update: I have an alternative and possibly simpler way of approaching the math in the section above.
Take P
to represent the probability of successfully walking from the origin to the destination without falling off. Ignore the edge case where the origin is the destination- that's already handled above. We now have two cases to handle:
- The first move takes is to the destination. This has a 1/4 chance of happening.
- The first move takes us in one of the other 3 directions (3/4 chance). We then have to return to the origin, with a 1/4 chance of not falling off. We then repeat the process recursively, with a
P
chance of success (by definition ofP
). This gives3/16 * P
chance for this scenario.
This means we have algebraically:
P = 1/4 + 3/16 * P
13/16 * P = 1/4
P = 4/13
We arrive at the same probability of 4/13
as before.
英文:
If we handle the edge cases where you start at your destination, or you start at an edge and the destination is the center, we're left with a simple scenario: find you way to the center, and then to the destination. Getting to the origin is a flat 0.25
probability, and then its just a matter of getting to the right edge. If you randomly walk in the wrong direction, you can always backtrack with 0.25
probability of success. This can repeat any number of times before walking in the correct direction (to the destination).
This means from the origin, we have a 1/4 chance of picking the right direction, and a 3/4 chance of picking the wrong direction. If we pick the right direction, we're done, if we pick the wrong direction, we have to pick the opposite direction to get back to the origin and avoid falling off, which is a 1/4 chance. Combining these into one, we have a 1/4 of being right the first time, and 3/16 chance at a second chance. Continuing this repeatedly, we end up with a formula like:
1/4 + 1/4 * (3/16) + 1/4 * (3/16)^2 + 1/4 * (3/16)^3 + ...
= 1/4 * (1 + (3/16) + (3/16)^2 + (3/16)^3 + ...)
= 1/4 * (16/13)
= 4/13
So from the origin, we have a 4/13
chance of walking to the correct edge tile without falling off.
In code:
def solve(xs, ys, xe, ye):
# already at destination
if xs == xe and ys == ye:
return 1
# if destination is the origin, the probability is a flat 0.25
if xe == 0 and ye == 0:
return 0.25
# first move must take you to the origin if not already there
prob = 0.25 if xs != 0 or ys != 0 else 1
# multiply by probability of walking from origin to destination
return prob * 4 / 13
Update: I have an alternative and possibly simpler way of approaching the math in the section above.
Take P
to represent the probability of successfully walking from the origin to the destination without falling off. Ignore the edge case where the origin is the destination- that's already handled above. We know have two cases to handle:
- The first move takes is to the destination. This has a 1/4 chance of happening.
- The first move takes us in one of the other 3 directions (3/4 chance). We then have to return to the origin, with a 1/4 chance of not falling off. We then repeat the process recursively, with a
P
chance of success (by definition ofP
). This gives3/16 * P
chance for this scenario.
This means we have algebraically:
P = 1/4 + 3/16 * P
13/16 * P = 1/4
P = 4/13
We arrive at the same probability of 4/13
as before.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论