Latest News

Wednesday, 25 April 2012

The traveling robot problem

I am currently between contracts and for first time in many years, I am requested to write some complex code from home so I took the liberties to share my result on my blog.

A startup based in London sent me this problem:

Problem:
A robot can be programmed to run 1, 2, 3, 5 and 10 kilometers and it takes 10, 5, 3, 2 and 1 minutes, respectively. Once it runs to programmed kilometers, it must be turned off for 2 minutes. After 2 minutes it can again be programmed to run for a further 1, 2, 3, 5 or 10 kilometers. How would you program this robot to go exactly 43 kilometers in minimum amount of time.

Please write a java program that solves the problem by finding the minimum time required to travel 43 kilometers. Your solution should print out the correct sequence of distances to be programmed into the robot: for example (10,5,10 and so on...)
When coding your solution please pay special attention to design, data structures, dynamic programming, faster execution time and creating generic solutions. (it should be fairly easy to change the parameters) Compute and provide Big O notation for main piece of your solution too.


END-OF-QUESTION

Before you look at my answers, it will be cool for you to try the exercise too so that we can share feedback in the comments section.

The question brought back memory of my Computer Sciences days, especially Data Structure and Algorithm lectures. At first glance, this looks like a simple problem but it goes deeper than that. Like artists, there are multiple ways to write code but once you look at someone else code, then it becomes difficult to be original ( IP patent law suit anyone?). Any experience developer can write code that would work perfectly for this problem, looking closely to what is being requested and you will notice that there is an extra requirement; dynamic programming. For those who needs more information about what dynamic programming is, I suggest the following wikipedia article. I had to spend sometimes reading the article to refresh my memories and off-I-went-hacking-away. Bear in mind that you could solve this problem by rewriting a recursive application but that is not a dynamic programming approach.

Anyway, here are my results ( the algorithm was inspired by a similar problem set).


I hope this helps someone in the future in any ways.


Happy Coding

You can download the source code this github https://github.com/armelnene/the-traveling-robot-problem

  • Blogger Comments
  • Facebook Comments

5 comments:

Post a Comment

Item Reviewed: The traveling robot problem Description: Rating: 5 Reviewed By: Armel Nene
Scroll to Top