Source: Air Duct Spelunking

Part 1: Given a map of the form:

########### #0.1…..2# #.#######.# #4…….3# ###########

> Find the shortest route to visit each of the points, starting at `0`.




First, we want to take the map that we were given and simplify it. We know that we want to visit all of the points, so lets take the original map and turn it just into a map of distances between any two named points.

```python
walls = set()
name_to_point = {}
point_to_name = {}

# Load the input file into a set of walls and the location of points of interest
for y, line in enumerate(fileinput.input(args.files)):
    for x, c in enumerate(line.strip()):
        if c.isdigit():
            name_to_point[int(c)] = (x, y)
            point_to_name[(x, y)] = int(c)

        elif c == '#':
            walls.add((x, y))

# Dynamically fill a distance map to a given point
def distances_to(name):
    to_scan = queue.Queue()
    to_scan.put((name_to_point[name], 0))

    scanned = set()

    result = {}

    while not to_scan.empty():
        point, distance = to_scan.get()

        if point in point_to_name:
            name = point_to_name[point]
            if name not in result:
                result[name] = distance

        if point in scanned:
            continue
        else:
            scanned.add(point)

        x, y = point
        for xd, yd in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            neighbor = (x + xd, y + yd)
            if neighbor not in walls:
                to_scan.put((neighbor, distance + 1))

    return result

distances = {
    name: distances_to(name)
    for name in name_to_point
}
names = list(sorted(name_to_point.keys()))

The first part loads the map and the second part will flood fill out from each point. This will find the minimum distance from each named point to the given one, somewhat simplifying the problem.

Next, assume we have a list of points to visit in a given order. From that, we can add the distances between each pair to get the total distance:

def total_length(ordering):
    return sum(
        distances[p1][p2]
        for p1, p2 in zip(ordering, ordering[1:])
    )

Using that function, we can try all possible iterations using itertools.permutations . This is slightly complicated by having to start at point 0.

minimum_length = float("inf")
minimum_ordering = None

# Looks a bit funny since we have to start at 0
for ordering in itertools.permutations(names[1:], len(names) - 1):
    ordering = [0] + list(ordering)
    length = total_length(ordering)
    if not minimum_ordering or length < minimum_length:
        logging.info('New best ({} steps): {}'.format(length, ordering))
        minimum_length = length
        minimum_ordering = ordering

print('Best ordering ({} steps): {}'.format(minimum_length, minimum_ordering))

Part 2: Find the best route that also returns to the origin (point 0).

To do this, all we have to do is tweak our total_length function to include looping back to zero.

def total_length(ordering):
    # If we have to return back to the origin, the distance will from the last point to 0
    offset_ordering = ordering[1:]
    if args.must_return:
        offset_ordering += ordering[:1]

    return sum(
        distances[p1][p2]
        for p1, p2 in zip(ordering, offset_ordering)
    )

Then the same loop as above will find the best path using the new tweaked formula.