Challenge #37 – Find the shortest route between my house and all my neighbors
Challenge #37 involved creating a function and an algorithm (e.g. FindMinimumPath() ) that will calculate the minimum distance between a start / end point and a series of mid points.
A person wants to leave his home and visit his neighbors who live a fixed distance from him. He wants to visit all his neighbors, and take the shortest total path. Given a specific start point and end point (his home), and a list of mid points (his neighbors) find the shortest route.
For example, one possible route is Start to 1, 1→2, 2→ 3, 3→7, 7→6, 6→9, 9→4, 4→5, 5→8, 8→End.
- Problem is 2 dimensional, only consider X and Y dimensions.
- No requirement to handle curvature of the earth effects.
- Define a function and algorithm (through a code sample) that will find the shortest route from a start / end point through a series of mid points.
- Any programming language may be used as long as it correctly finds the shortest route.
- Function that correctly finds the shortest distance in the fastest amount of processing time will be the winner.
The following is a good response as submitted by Matt Kent. It is approximate but fairly fast.
Here is a brute force method which is 100% accurate but is very time intensive.
Winners (out of approximately 10 respondents)
Thanks to everybody for your responses to SCS Coding Challenge #37!!!
Congratulations to Matt Kent for his fine effort to come up with a workable algorithm.
|Name||Prize Winner||Good Answer|
Monthly Programming Tidbits
Validate the input “first”
Look at this code snippet:
We have to read all this code to find the last line that throws an exception if the argument is null. By convention, we often validate the input first. This tells the reader of the code how a given method should be used.
So, let’s reverse the order of if and else here:
Now, you can immediately tell what is a valid argument for this method. You don’t have to scroll down to the end of the body of the method to figure that out.
Reference: 5 Tips for Junior C# Developers to Write Cleaner C# Code
Coding Challenge #38
Please stay tuned, SCS Coding Challenge #38 will be published this week. Details will follow. The winner will be awarded based upon the best approach.