Re: Plotter problem



On Jun 1, 1:10 pm, dj3va...@xxxxxxxxxxxxxxxxxxxxxxxxxxx wrote:
In article <d9fc8a39-a9cc-4efc-bfad-debc73e3a...@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

Mensanator  <mensana...@xxxxxxx> wrote:
On Jun 1, 11:33 am, chandra.so...@xxxxxxxxx wrote:
Could someone help me with the below issue:

"You are given a plotter which 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)}. Your
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. If you are feeling adventurous -
modify the program to provide the same output if the plotter can also
move diagonally"

Wouldn't this be a minimum spanning tree?

Only if the print head can clone itself every time it gets to a node
with degree greater than 2.

Duh. That's what I get for trying to visualize it in my head.


It looks closer to the traveling salesman problem to me.

Too bad. An MST is at least easily solvable.


dave

--
Dave Vandervies                              dj3vande at eskimo dot com
I believe such a proof is beyond the capabilities of current compilers,
and is likely to remain so until I die and no longer care about it ...
                                           --Eric Sosman in comp.lang.c

.