Posted 19 July 2017 - 02:27 AM

The shortest distance problem in CC.

Hey guys, just created a quick program that creates 6 random points (numbering them 1-6, 1 being the start point and the rest 2-6, based on their number in the data table) and then draws a line from the start point to each point.

The challenge? Design an algorithm that calculates the shortest distance taken to go around to each point once. You don't have to finish at the start point, just get to each point once in the shortest distance possible.

This algorithm doesn't necessarily have to be scalable (only so many pixels..), but could probably be scaled up to about 20 points (lines would be an issue, however ignore that for now).

Best way I've found with this algorithm (so far) is that if you can tell the program to do a spiral of the points you will get the shortest distance about 9 times out of 10, at least. The way to do this would be to compare the X/Y of each object relative to the bounds of the points, then make your way in by calculating how many points are left on the outside (til there are none). Generally this is the fastest way in our heads but putting that in an algorithm will be slightly harder.

Hey guys, just created a quick program that creates 6 random points (numbering them 1-6, 1 being the start point and the rest 2-6, based on their number in the data table) and then draws a line from the start point to each point.

The challenge? Design an algorithm that calculates the shortest distance taken to go around to each point once. You don't have to finish at the start point, just get to each point once in the shortest distance possible.

This algorithm doesn't necessarily have to be scalable (only so many pixels..), but could probably be scaled up to about 20 points (lines would be an issue, however ignore that for now).

Best way I've found with this algorithm (so far) is that if you can tell the program to do a spiral of the points you will get the shortest distance about 9 times out of 10, at least. The way to do this would be to compare the X/Y of each object relative to the bounds of the points, then make your way in by calculating how many points are left on the outside (til there are none). Generally this is the fastest way in our heads but putting that in an algorithm will be slightly harder.