Alex the Truck Driver

Question

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!

Answer 1

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.

Answer 2

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";}

Answer 3

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.

Answer 4

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!)

Answer 5

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