Mad Robot
An interesting test question asked recently in Graviton
Before we begin this week’s puzzle, we wanted to wish all of you guys good luck for the upcoming placement tests. The hiring season is in full swing and we gladly wish that you get placed in your dream firms and have all that this world has in store for you 🤞🏻
Now for this week’s crazy question :
A mad robot sets off towards the North East on a journey from the point (0,0) in a coordinate system. It travels in stages by moving forward and then rotating on the spot. It follows these pseudo-code instructions:
SUB JOURNEY
DISTANCE = 1000
WHILE (DISTANCE > 0.001)
MOVE DISTANCE
STOP
ROTATE(90, DEGREES, CLOCKWISE)
DISTANCE = DISTANCE / 2
END WHILE
EXPLODE
END SUB
Where does the robot explode?
Try to solve this problem yourself before moving on to the solution below
.
.
.
.
.
.
Solution
First we find the number of forward turns, noting that the WHILE(DISTANCE > 0.001) condition is evaluated after each halving.
The forward motion, if it occurs, following the th turn will be of distance . This will occur for each for which
![\[ 1000\times 2^{-n} > 0.001. \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F1d4e187b-4c2b-4368-a14a-34826663bc99_142x13.png "\[ 1000\times 2^{-n} > 0.001. \]")
Taking logs gives
![\[ \log {1000}-n\log {2}>\log {0.001} \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fbf1f6642-faa7-470c-9521-188340b11f7c_206x16.png "\[ \log {1000}-n\log {2}>\log {0.001} \]")
Rearranging gives
![\[ n<\frac{\log {1000}-\log {0.001}}{\log {2}} = \frac{\log {1000000}}{\log {2}} \approx 19.93. \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F9e70a2a7-735d-4487-9e0a-9940725a931c_346x38.png "\[ n<\frac{\log {1000}-\log {0.001}}{\log {2}} = \frac{\log {1000000}}{\log {2}} \approx 19.93. \]")
This first becomes invalid after 20 turns. Thus, the path of the robot is determined by 20 motions. The directions that the robot travels in these 20 motions are alternately NE, SE, SW, NW, .... Since there are 20 motions in total there are 5 motions in each of these directions.
Let be the total distance travelled NE. Then
![\[ T=1000\left(\frac{1}{2^0}+\frac{1}{2^4}+\frac{1}{2^8}+\frac{1}{2^{12}}+\frac{1}{2^{16}}\right). \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2Fa6c62d6f-99a4-4a57-865b-5f6a80902fa6_294x40.png "\[ T=1000\left(\frac{1}{2^0}+\frac{1}{2^4}+\frac{1}{2^8}+\frac{1}{2^{12}}+\frac{1}{2^{16}}\right). \]")
The NE motion contributes a component travelled in the direction and the same component travelled in the direction. By Pythagoras’ theorem we have
![\[ 2d^2=T^2, \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F64f74087-5afc-4d79-b15a-cd775402fdbb_70x19.png "\[ 2d^2=T^2, \]")
so
![\[ d=\frac{T}{\sqrt{2}}. \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F862743f4-e43c-47dc-ac74-b35ae71f6ee1_60x38.png "\[ d=\frac{T}{\sqrt{2}}. \]")
Note that the distance SE will be half of T, since each motion is half the length of the preceding NE motion. Similarly, the total distance SW will be one quarter of ; total distance NW will be one eighth of . Each of these motions contributes the same component in the -direction as in the -direction. The NE direction counts positively towards both and directions, the SE direction counts positively in the direction and negatively in the direction, SW counts negatively in both and directions and NW counts negatively in the and positively in the direction. The final coordinates are therefore
![\[ (x,y)=\left(\frac{T}{\sqrt{2}}\left(1+\frac{1}{2}-\frac{1}{4}-\frac{1}{8}\right),\frac{T}{\sqrt{2}}\left(1-\frac{1}{2}-\frac{1}{4}+\frac{1}{8}\right)\right)=\left(\frac{9T}{8\sqrt{2}},\frac{3T}{8\sqrt{2}}\right) \]](https://substackcdn.com/image/fetch/f_auto,q_auto:good,fl_progressive:steep/https%3A%2F%2Fsubstack-post-media.s3.amazonaws.com%2Fpublic%2Fimages%2F3ed99bc7-1516-4cb2-a7f5-470c67550efc_532x40.png "\[ (x,y)=\left(\frac{T}{\sqrt{2}}\left(1+\frac{1}{2}-\frac{1}{4}-\frac{1}{8}\right),\frac{T}{\sqrt{2}}\left(1-\frac{1}{2}-\frac{1}{4}+\frac{1}{8}\right)\right)=\left(\frac{9T}{8\sqrt{2}},\frac{3T}{8\sqrt{2}}\right) \]")
.
.
😃 Over to you: Were you able to solve this?
👉 If you liked this post, don’t forget to leave a like ❤️. It helps more people discover this newsletter on Substack and tells us that you appreciate solving these weekly questions. The button is located towards the bottom of this email.
👉 If you love reading this newsletter, feel free to share it with friends!