Alex the Truck Driver

Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the quickest way to deliver goods to them.

Input

The first line of input gives the number of cities Alex needs to deliver goods to. Every line that follows gives the distance between the cities. The second line of input is always the distance between the first and second cities. If there is a third city, the third line of input is the distance between the first and third city. When to distance to the first city has been given for all cities, the next lines of input gives the distance between the the second city and every other city (except the first, as that information as already been given). This continues until every combination has been given. Sample inputs:

//Number of cities
4
//A -> B
2
//A -> C
4
//A -> D
3
//B -> C
5
//B -> D
1
//C -> D
3

3
6
4
2


Output

The output should print the quickest way to deliver goods to every destination in the form A -> C -> D -> C -> A (For every output, the reverse of will also work. You only need to print one solution). Alex ALWAYS starts at A and must always return to A at the end (as A is where he lives). Here are the outputs for the sample inputs above:

A -> B -> D -> C -> A

A -> C -> B -> A


Rules

The shortest code wins.

Happy Golfing!

• In short: solve travelling salesman for integer distances? Apr 15 '13 at 16:24
• Looks like. +100 bounty if you can prove that no polynomial-time solution exists? Apr 15 '13 at 19:15
• Can I change the input to comma separated distances only? IE, input: 2,4,3,5,1,3 detection: 4 cities detected. How flexible are you willing to be on the input format? Apr 26 '13 at 17:48
• @histocrat, I think a polynomial-time solution would deserve the bounty, too. May 2 '13 at 5:47
• So the graph of the cities is completely connected? Or should we interpret negative distances as not being connected? May 3 '13 at 9:30

Python 2, 210 205

from itertools import*
r=range(input())
d={t:input()for t in combinations(r,2)}
n=0,
print" -> ".join(chr(65+c)for c in n+min(permutations(r[1:]),key=lambda p:sum(d[min(t),max(t)]for t in zip(n+p,p+n)))+n)


Edit: Shortened according to Volatility's suggestion. I'm amazed that it gets more readable and Pythonic the shorter it gets.

• Change d={(i,j):input()for i in r for j in r[i+1:]} to d={t:input()for t in combinations(r,2)} to save 5 chars May 5 '13 at 0:49

C++ - 380

#include<iostream>
#include<algorithm>
#define I new int[n]
#define f for(i=0;i<n;++i)
using namespace std;int main(){int*a,**d,*s,n,i,j,t,b=2e9;cin>>n;d=new
int*[n];a=I;s=I;f{a[i]=i;d[i]=I;}f
for(j=i+1;j<n;++j){cin>>d[i][j];d[j][i]=d[i][j];}do{t=0;f
t+=d[a[i]][a[(i+1)%n]];if(t<b){b=t;copy(a,a+n,s);}}while(next_permutation(a+1,a+n));f
cout<<(char)(65+s[i])<<" -> ";cout<<"A\n";}


This a commentary rather than an entry.

If I am not mistaken, the sample data appear to correspond to an impossible set of distances between cities located in the plane.

The inter-city distances might be represented by a matrix

or, perhaps more conveniently, by a graph in which the edge labels are distances. (Note: The graph is not a geographical map.)

The figure below arbitrarily sets A at the origin of a coordinate plane. The distances from A to B, C, and D constrain the latter three cities to positions on circles with center at A and radii of 2, 4, and 3 units. We may arbitrarily place B at (0,2) and continue. Now, because D is one unit away from B and 3 units away from A, it must lie at (0, 3).

But there would appear to exist no position in the plane that is simultaneously 4, 5, and 3 units away from A, B, and D respectively.

The impossibility of the data would not detected by most approaches, although I suspect that a multidimensional scaling analysis would return a stress value that should raise a flag.

• Holds only if you interpret "distance" with "euclidean distance" which most often isn't the case if we are talking about cities and streets between them. May 5 '13 at 9:11
• @Howard Good point. May 5 '13 at 13:35
• @Howard with any metric, the triangle inequality must hold. We should be promised the distances form a metric. Here, BCD disobeys the triangle inequality. May 5 '13 at 19:05
• Is there a case where the triangle inequality holds for a tetrahedron but the tetrahedron is still impossible (not just degenerate) in E^3 or, equivalently, in any euclidean space? What about impossibility in "any (continuous) space with any induced metric"? What about general hypertetrahedra in their respective spaces and euclidean spaces? May 5 '13 at 19:20
• @JanDvorak can you write a shorter program if the distances obey the triangle inequality than if they don't? May 6 '13 at 6:29

Ruby, 242 characters

s,a,c,i=gets.to_i-1,[],[],0
0.upto(s){|x|x.upto(s){|y|a[y]||=[];a[x][y]=a[y][x]=x==y ?0:gets.to_f}}
(0..s).to_a.permutation{|x|x[0]<1&&c<<[(0..s).reduce(0){|y,z|y+a[x[z]][x[z-1]]},x]}
puts c.min_by{|x|x[0]}[1].map{|x|(x+65).chr+" -> "}*""+"A"


This finds the shortest path that never visits the same city twice. If triangle inequality is satisfied, no city should be visited twice. If the triangle inequality is broken, visiting the same city twice may be beneficial. If there are negative cycles, no optimal solution exists, as you can keep driving along the cycle to travel back in time. In practice, triangle inequality (and thus non-negativity) is safe to assume.

The algorithm itself is brute-force and inefficient. Don't use for maps with more than 10 or 12 cities. Three words: O(n!)

GolfScript, 118 108 characters

~](:€,{.€-~:§2$>\)[0]*@§<+}%€.?,{€base}%{$€,1>=},{[0].@+\+.0\{.@[\]$~\5$==@+\}*;[\]}%\$\;0=1={65+}%""+" -> "*


A quite clumsy (i.e. really slow) 118 characters GolfScript program.

Example:

> 4 2 4 3 5 1 3
A -> B -> D -> C -> A

> 3 6 4 2
A -> B -> C -> A