17
\$\begingroup\$

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

\$\endgroup\$
  • 4
    \$\begingroup\$ But how do you say someone's code is O(n!) but not O(sqrt(n)*n^n/e^n) nor O(n!/100000000000000000000)? \$\endgroup\$ – jimmy23013 Jun 16 '14 at 22:09
  • 1
    \$\begingroup\$ @user23013 One solution is to say the only options are O(n!) and O(b^n*n^a*ln(n)^k), and all bounds must be as tight as possible given that notation. OP should clarify, though. \$\endgroup\$ – isaacg Jun 16 '14 at 22:50
  • 2
    \$\begingroup\$ @Geobits As shown in the comic, the dynamic programing solution is O(n^2*2^n), which is much less than O(n!) for large n. \$\endgroup\$ – isaacg Jun 16 '14 at 22:52
  • \$\begingroup\$ @proud haskeller okay (it's actually been out for a while and i just wanted to accept it because it was the best despite having nearly no votes, but if you get something better go ahead.) \$\endgroup\$ – PyRulez Sep 25 '14 at 22:12
  • \$\begingroup\$ @PyRulez well whatever I try I convince myself it has complexity of O(n!)... it's complex \$\endgroup\$ – proud haskeller Sep 25 '14 at 23:16
5
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ it's been a while, but is there a 'non-minified' (perhaps annotated) version available? I'm curious how you solved this issue with Haskell. \$\endgroup\$ – Henk Mollema Oct 10 '16 at 19:05
5
\$\begingroup\$

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)))
\$\endgroup\$
  • \$\begingroup\$ from itertools import* would be shorter. \$\endgroup\$ – seequ Jun 17 '14 at 20:20
  • \$\begingroup\$ Oh, good idea..! \$\endgroup\$ – Greg Hewgill Jun 17 '14 at 20:20
  • \$\begingroup\$ I can't test now, so I'm just throwing ideas. Is the set necessary? \$\endgroup\$ – seequ Jun 17 '14 at 20:37
  • \$\begingroup\$ The set is used to eliminate duplicates in the list of cities. Since the input does not contain entries like ("a", "a", 0), there would need to be extra logic somewhere to skip zero-length edges. (And if you're on the web, you can always test with something like codepad.org.) \$\endgroup\$ – Greg Hewgill Jun 17 '14 at 20:39
  • \$\begingroup\$ I don't know much about Python, but apparently you have called sum on each item of a permutation. Wouldn't that be O(n!*n)? \$\endgroup\$ – jimmy23013 Jun 20 '14 at 17:15
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Called sum on each item of a permutation. Wouldn't that be O(n!*n)? \$\endgroup\$ – jimmy23013 Jun 20 '14 at 17:16
  • \$\begingroup\$ Yeah I think you're right. \$\endgroup\$ – gggg Jun 20 '14 at 20:11
2
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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