3
\$\begingroup\$

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!

\$\endgroup\$
7
  • 12
    \$\begingroup\$ In short: solve travelling salesman for integer distances? \$\endgroup\$
    – Howard
    Apr 15, 2013 at 16:24
  • 10
    \$\begingroup\$ Looks like. +100 bounty if you can prove that no polynomial-time solution exists? \$\endgroup\$
    – histocrat
    Apr 15, 2013 at 19:15
  • \$\begingroup\$ 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? \$\endgroup\$ Apr 26, 2013 at 17:48
  • 6
    \$\begingroup\$ @histocrat, I think a polynomial-time solution would deserve the bounty, too. \$\endgroup\$
    – boothby
    May 2, 2013 at 5:47
  • \$\begingroup\$ So the graph of the cities is completely connected? Or should we interpret negative distances as not being connected? \$\endgroup\$ May 3, 2013 at 9:30

5 Answers 5

2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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 \$\endgroup\$
    – Volatility
    May 5, 2013 at 0:49
0
\$\begingroup\$

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";}
\$\endgroup\$
0
\$\begingroup\$

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

matrix

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

distances

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.

where is C


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.

\$\endgroup\$
9
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Howard
    May 5, 2013 at 9:11
  • \$\begingroup\$ @Howard Good point. \$\endgroup\$
    – DavidC
    May 5, 2013 at 13:35
  • \$\begingroup\$ @Howard with any metric, the triangle inequality must hold. We should be promised the distances form a metric. Here, BCD disobeys the triangle inequality. \$\endgroup\$ May 5, 2013 at 19:05
  • \$\begingroup\$ 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? \$\endgroup\$ May 5, 2013 at 19:20
  • 1
    \$\begingroup\$ @JanDvorak can you write a shorter program if the distances obey the triangle inequality than if they don't? \$\endgroup\$ May 6, 2013 at 6:29
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.