Problems 133 and 155
Back to Problem Solutions forum
Hey. While solving problems 133 and 155 I have encountered some confusing problem desciptions, and I solved those problems
without including some parts of the problem definition.
Problem 133
Bouncing - Obviously the ball of the radius R could not have its Y position smaller than R in respect to this border.
So if after the step is calculated (as described above) and we found that new position has Ynew < R we should do two things:
change the sign of vertical component of the speed (i.e. Vy *= -1);
adjust the position of the ball as if it bounced from the line Y = R instead of crossing it.
In my solutions I just put the ball back to border - radius and it gave correct answers with dt=0.01
Problem 155
I solved the problem without even going through the recommended steps!
My solution in words:
1. add first node to seen, make node 0 as current
2. find all connections from current, the first unvisited connection is next node. answer for next is current
3. add next to seen and make it current repeat step 2
if step 2 does not yield a next go to node which the current came from and repeat step 2
exit then next==current and we have a loop
What do you guys think? Did any of you got a solution which follows the steps in Problem 155?
Hello there!
Thanks for good questions. If you don't mind I'll try to answer :)
On problem 133 - if we use time step which is really small than the difference between "just put the ball back to border - radius"
and more proper reflection implementation also becomes very small. That is why your approach works anyway. I think
it is general situation in modelling - we often can use simpler algorithm if we increment amount of steps. (I suspect
similar evolution was seen in missile tracking equipment over the years, haha)
On problem 155 you are right in that it is not necessarily to keep precise implementation with stack. The stack just helps the backtracking part. This can be done in different ways - e.g. reqursion, array etc.
Honestly I'm not sure I should write these implementation details in a statement. Probably I should add that it is "one of possible implementation"...
The only useful thing is that it helps to show how similar depth-search and breadth-search are - we only need to choose the structure for keeping nodes - either stack or queue.