Travelling Salesman

Question

You are given, as a list or vector or whatever, a bunch of 3-tuples or whatever, where the first two things are strings, and the third thing is a number. The strings are cities, and the number is the distance between them. The order of the cities in the tuple is arbitrary (i.e. it doesn't matter which comes first and which comes second) since it is the same distance each way. Also, there is exactly one tuple for each pair of connected cites. Not all cities may be connected. Also, the distance is always positive (not 0). You do not need to check these conditions, you may assume input will be well formed. Your job is to return the cities in a cyclic sequence, such that, if you start at any one city, and go around the sequence back to the same city, the total of the distances between the cities will be minimum (exactly and in all cases.) You may assume a solution exists. For example, let us say you are given

[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]

You could output any of the following (but you only need to output one):

["Detroit","Hong Kong","Dillsburg","New York"]
["Hong Kong","Dillsburg","New York","Detroit"]
["Dillsburg","New York","Detroit","Hong Kong"]
["New York","Detroit","Hong Kong","Dillsburg"]
["Dillsburg","Hong Kong","Detroit","New York"]
["New York","Dillsburg","Hong Kong","Detroit"]
["Detroit","New York","Dillsburg","Hong Kong"]
["Hong Kong","Detroit","New York","Dillsburg"]

because it is the shortest trip: 13.9

but not

["Dillburg","Detroit","New York","Hong Kong"]

because it is not the shortest.

See en.wikipedia.org/wiki/Travelling_salesman_problem

Scoring

This is where it gets interesting. You take the number of characters you have, and then plug them into the bare worst case O-notation formula. For example, let us say you write a brute force program that is 42 characters. As we all know, the worst case is n! where n is the number of cities. 42!=1405006117752879898543142606244511569936384000000000, so that is your score. The lowest score wins.

Note: I relieved this afterwards too, but wasn't sure how to solve it and hoped that no one would notice. People did, so I will go with issacg's suggestion:

the only options are O(n!) and O(b^nn^aln(n)^k), and all bounds must be as tight as possible given that notation

Answer 1

Haskell, 259

I thought I would be able to get it shorter. maybe I will.
this has time complexity of O(n^2*2^n)* so score is about 6.2e82

_{*i'm not actually sure, but if there is any "addition" to the complexity it's not more than polynomial, so this shouldn't change the score much.}

import Data.List
g e=tail$snd$minimum[r|r@(_,b)<-iterate(\l->nubBy((.f).(==).f)$sort[(b+d,c:a)|(b,a)<-l,c<-h\\init a,d<-a!!0%c])[(0,[h!!0])]!!length h,b!!0==h!!0]where h=sort$nub$e>>= \(a,b,_)->[a,b];a%b=[z|(x,y,z)<-e,x==a&&y==b||x==b&&y==a]
f(_,x:b)=x:sort b

Answer 2

Python 2, 237 231 228 225 characters

Since this is a naive algorithm, its score is probably about 225! ≈ 1.26e433.

from itertools import*
a=input()
n=lambda*a:tuple(sorted(a))
d=dict((n(*x[:2]),x[2])for x in a)
print min(permutations(set(chain(*[x[:2]for x in a]))),key=lambda x:sum(d.get(n(x[i],x[i+1]),1e400)for i in range(-1,len(x)-1)))

Answer 3

Julia, 213 chars

Probably goes like n!n, so ~2e407.

a=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
f(a)=(
d(x,y)=(r=filter(z->x in z&&y in z,a);r==[]?Inf:r[1][3]);
m=Inf;
q=0;
c=unique([[z[1] for z=a],[z[2] for z=a]]);
n=length(c);
for p=permutations(c);
    x=sum([d(p[i],p[mod1(i+1,n)]) for i=1:n]);
    x<m&&(m=x;q=p);
end;
q)
f(a)

For readability and to demonstrate use I left in some unscored newlines and tabs as well as example input and a call to the function. Also I used an algorithm that requires n! time, but not n! memory, its slightly more feasible to run.

Answer 4

Python 3 - 491

I did not count the length of the input graph variable g. This solution uses dynamic programming, and has a complexity of n^2 * 2^n, for a total score of ~6.39e147. I am still pretty new to golfing, so please chime in if you see a big waste of code somewhere!

g=[("New York", "Detroit", 2.2), ("New York", "Dillsburg", 3.7), ("Hong Kong", "Dillsburg", 4), ("Hong Kong", "Detroit", 4), ("Dillsburg", "Detroit", 9000.1), ("New York", "Hong Kong", 9000.01)]
s=''
c={s:1}
D={}
for t in g:c[t[0]]=1;c[t[1]]=1;D[(t[0],t[1])]=t[2];D[(t[1],t[0])]=t[2];D[('',t[0])]=0;D['',t[1]]=0
V={}
y=[x for x in c.keys() if x!='']
f=''
def n(z,p):
 if(len(p)==len(y)-1):
  global f;f=z
 if(0==len(p)):
  return (D[(z,f)] if (z,f) in D else float('inf'))
 Y=[(float('inf'),'')]
 for P in p:
  if((z,P) in D):
   Y.append((D[(z,P)] + n(P,[m for m in p if m!=P]), P))
 V[(z,tuple(p))]=min(Y)
 return min(Y)[0]
n('',y)
for i in range(len(c)-1):
 N=V[(s,tuple(y))][1]
 print(N)
 s=N
 y.remove(N)

Answer 5

Mathematica, 66 bytes

Most@Last@FindShortestTour@Graph[#<->#2&@@@#,EdgeWeight->Last/@#]&

No idea on the complexity, so the score is somewhere between 10^23 and 10^93.

Answer 6

Ruby, 198 180 bytes

G=eval(gets.tr("()","[]"))
C=G.map{|t|[t[0],t[1]]}.flatten.uniq
D=Hash.new(+1.0/0)
G.map{|p|D[[p[0],p[1]]]=D[[p[1],p[0]]]=p[2]}
p C.permutation.map{|l|d=0;p=l[-1];l.map{|c|d+=D[[p,c]];p=c};[d,l]}.sort[0][1]

The first line that reads the input is unscored, as that seems to be what everyone else is doing. Also, there is no final newline needed for ruby.

It just dumbly generates all permutations of cities, so put me down for O(n!*n). Actually, on second thoughts, it's slower even than that, because it sorts all O(n!) paths rather than keeping track of the best so far.