Printer Algorithm

Rails
1

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.

2

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?
3

I would go back to my Algorithms text book and do some reading…

You probably should too.

Ruby Forum – A Homework Free Zone

4

On Jun 2, 2009, at 1:42 AM, RM wrote:

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 B. http://agileconsultingllc.com
[email protected]