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
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.
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
import java.util.Comparator;
ReplyDeleteimport java.util.TreeSet;
// i have no idea what i'm doing exactly, just messing around.... some kind of graph search, i guess...
class Test{
// distances including cooldown. ultimately we just get rid of the last two minutes.
final static int d[] = { 1, 2, 3,5,10};
final static int t[] = {12, 7, 5,4, 3};
public static void main( String[] args ){
TreeSet nodes = new TreeSet( new Comparator(){
@Override
public int compare( Node a, Node b ){
return a.t < b.t? -1 : a.t > b.t? 1 : ( b.d-a.d );
}
});
// throw in the original nodes ...
for( int i = 0; i < t.length; i++ )
nodes.add( new Node( null, d[i], t[i] ) );
// now search for a solution :)
while( true ){
Node cheapo = nodes.first();
// done?
if( cheapo.d == 43 ){
System.out.println( "HOLY SHIT, WE'RE DONE!" );
System.out.println( cheapo.toString() );
System.out.println( "Total time (excluding final cooldown): " + (cheapo.t - 2) + "min" );
break;
}
// expand the cheapest node ...
else{
nodes.remove( cheapo );
for( int i = 0; i < t.length; i++ )
nodes.add( new Node( cheapo, d[i], t[i] ) );
}
}
}
static class Node{
Node parent;
int d, myD, t, myT;
public Node( Node parent, int distance, int time ){
this.parent = parent;
this.d = ( parent != null? parent.d:0 ) + ( myD = distance );
this.t = ( parent != null? parent.t:0 ) + ( myT = time );
}
public String toString(){
String str = "Node[d=" + d + "km, t=" + t + "min, path=" + myD;
Node n = this.parent;
while( n != null ){
str += "," + n.myD;
n = n.parent;
}
return str + "]";
}
}
}
it outputs
HOLY SHIT, WE'RE DONE!
Node[d=43km, t=17min, path=3,10,10,10,10]
Total time (excluding final cooldown): 15min
oh, also i didn't read the post right and overlooked the "it has to be java" part, so here's my first solution in mathematica:
Minimize[{12 a + 7 b + 5 c + 4 d + 3 e,
a + 2 b + 3 c + 5 d + 10 e == 43 && # >= 0 & /@ {a, b, c, d,
e}}, {a, b, c, d, e}, Integers]
I used JavaScript instead of Java, since I do not like the overhead Java uses to juggle with arrays and collections. (In fact I do not care to understand most of them. :-P)
ReplyDeleteO(n*k) with n = number of distances and k = actual steps the robot needs to take
https://gist.github.com/4281820
I used prototypes to define the methods of the objects. If you are not familiar with prototypes: Think of them as classes that have their guts (methods) hanging outside instead of them tucked away in the inside.
I recently learned about the Silicon Valley Robotic Services and their innovative start-up, so if you want to learn more abut the Silicon Valley or you need some reliable and professional robotic services I suggest you to look at http://www.reuters.com/article/2014/06/10/idUSnGNX6C1r2L+1d1+GNW20140610
ReplyDeleteI conceive you have noted some very interesting points, regards for the post.
ReplyDeleteสล็อตเล่นง่าย แตกไว เว็บไหนดี
At this point you'll find out what is important, it all gives a url to the appealing page: Satta king 786
ReplyDeleteJava Training In Noida
ReplyDelete