A printer can can plot points provided to it in the form of
''x'' and
''y'' coordinates. The plotter hand can move horizontally or
vertically
only. Your program will be given a list of ''n'' coordinates in
the form
of {(x1,y1), (x2,y2} ... (xn,yn)}. My program must print a sorted list
of all ''n'' points that would represent the least cumulative
distance
for the plotter hand to plot all ''n'' points in that sorted
order.
Also, can we modify the program to provide the same output if the
plotter can also move diagonally?
Let me know how would you approach this problem.
Raj Man wrote:> A printer can can plot points provided to it in the form of ''x'' and > ''y'' coordinates. The plotter hand can move horizontally or vertically > only. Your program will be given a list of ''n'' coordinates in the form > of {(x1,y1), (x2,y2} ... (xn,yn)}. My program must print a sorted list > of all ''n'' points that would represent the least cumulative distance > for the plotter hand to plot all ''n'' points in that sorted order. > Also, can we modify the program to provide the same output if the > plotter can also move diagonally? > > Let me know how would you approach this problem.(wasn''t going to post, but I''m in that sort of mood...) 1. This is not Ruby on Rails. 2. This doesn''t even specify Ruby 3. Try doing your own homework? -- Posted via http://www.ruby-forum.com/.
I would go back to my Algorithms text book and do some reading... You probably should too. Ruby Forum -- A Homework Free Zone -- Posted via http://www.ruby-forum.com/.
On Jun 2, 2009, at 1:42 AM, RM wrote:> > A printer can can plot points provided to it in the form of ''x'' and > ''y'' coordinates. The plotter hand can move horizontally or vertically > only. Your program will be given a list of ''n'' coordinates in the form > of {(x1,y1), (x2,y2} ... (xn,yn)}. My program must print a sorted list > of all ''n'' points that would represent the least cumulative distance > for the plotter hand to plot all ''n'' points in that sorted order. > Also, can we modify the program to provide the same output if the > plotter can also move diagonally? > > Let me know how would you approach this problem.I''d pull my copy of "The Art of Computer Programing, Vol. 3 - Sorting and Searching" by Donald Knuth off the shelf and start reading particularly keen to look up the Traveling Salesman problem. Well, that''s what *I* would do. -Rob Rob Biedenharn http://agileconsultingllc.com Rob-xa9cJyRlE0mWcWVYNo9pwxS2lgjeYSpx@public.gmane.org