## 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.

Helper Classes:

public class Route { public double Distance { get; set; } public List<Point> FinalRoute { get; set; } } public class Point { public double X { get; set; } public double Y { get; set; } }

Prototype Function:

public Route FindMinimumPath(Point startEndPoint, List<Point> points) { var finalRoute = new Route() {FinalRoute = new List<Point>()}; // Algorithm goes here return finalRoute; }

### Assumptions

Flat Earth

- Problem is 2 dimensional, only consider X and Y dimensions.
- No requirement to handle curvature of the earth effects.

## Requirements

- 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.

## Correct Response

The following is a good response as submitted by Matt Kent. It is approximate but fairly fast.

public static Route FindMinimumPath(Point origin, List<Point> points) { // This function uses the nearest neighbor algorithm for finding the path. // Nearest neighbor isn't good at finding the shortest path, but it is fast. var route = new Route(points.Count + 2); var visited = new bool[points.Count]; var pointsVisited = 0; route.FinalRoute.Add(origin); var closestDistance = double.PositiveInfinity; var closestIndex = 0; for (var i = 0; i < points.Count; i++) { var distance = CalculateDistance(origin, points[i]); if (distance < closestDistance) { closestDistance = distance; closestIndex = i; } } var currentPoint = points[closestIndex]; route.FinalRoute.Add(currentPoint); route.Distance += closestDistance; pointsVisited++; visited[closestIndex] = true; while (pointsVisited < points.Count) { closestDistance = double.PositiveInfinity; for (var i = 0; i < points.Count; i++) { if (visited[i]) { continue; } var distance = CalculateDistance(currentPoint, points[i]); if (distance < closestDistance) { closestDistance = distance; closestIndex = i; } } currentPoint = points[closestIndex]; visited[closestIndex] = true; route.Distance += closestDistance; route.FinalRoute.Add(currentPoint); pointsVisited++; } route.FinalRoute.Add(origin); route.Distance += CalculateDistance(currentPoint, origin); return route; } static double CalculateDistance(Point a, Point b) { var distance = Math.Sqrt(Math.Pow(b.X - a.X, 2) + Math.Pow(b.Y - a.Y, 2)); return distance; }

Here is a brute force method which is 100% accurate but is very time intensive.

public Route FindMinimumPath(Point startEndPoint, List<Point> points) { // Algorithm goes here // Find Number of Possible Routes var routeTemplate = new List<int>(); for(var i=0;i<points.Count;i++) { routeTemplate.Add(i); } var listOfRoutes = Permutations(routeTemplate); var finalRoute = FindShortestRoute(listOfRoutes, points, startEndPoint); return finalRoute; } private Route FindShortestRoute(List<List<int>> routes, List<Point> points, Point startEndPoint) { foreach (var route in routes) { var totalDistance = CalculateDistance(startEndPoint, points[route[0]]); for (int i = 0; i < route.Count-1; i++) { totalDistance += CalculateDistance(points[route[i]], points[route[i + 1]]); if (totalDistance > MinimumDistance) break; } totalDistance += CalculateDistance(points[route[route.Count - 1]], startEndPoint); if (totalDistance < MinimumDistance) { ShortestRoute.ShortestRoute = route; ShortestRoute.Distance = totalDistance; MinimumDistance = totalDistance; } } return ShortestRoute; } static double CalculateDistance(Point a, Point b) { var distance = Math.Sqrt(Math.Pow(b.X - a.X, 2) + Math.Pow(b.Y - a.Y, 2)); return distance; } public static List<List<T>> Permutations<T>(List<T> list) { var result = new List<List<T>>(); if (list.Count == 1) { // If only one possible permutation result.Add(list); // Add it and return it return result; } foreach (var element in list) { // For each element in that list var remainingList = new List<T>(list); remainingList.Remove(element); // Get a list containing everything except of chosen element foreach (var permutation in Permutations<T>(remainingList)) { // Get all possible sub-permutations permutation.Add(element); // Add that element result.Add(permutation); } } return result; }

## 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 |

Matt Kent | X | X |

Eric Axelrod | X |

## Monthly Programming Tidbits

### Validate the input “first”

Look at this code snippet:

public void Draw(Shape shape) { if (shape != null) { Console.WriteLine("Drawing " + shape.ToString()); Console.WriteLine("---"); } else { throw new ArgumentNullException("shape"); }

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:

public void Draw(Shape shape) { if (shape == null) { throw new ArgumentNullException("shape"); } else { Console.WriteLine("Drawing " + shape.ToString()); Console.WriteLine("---"); } }

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

https://programmingwithmosh.com/csharp/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.