Yuriy Netesov avatar Yuriy Netesov committed 9c0a034

solution to problem #3543

Comments (0)

Files changed (1)

+#!/usr/bin/python
+# http://community.topcoder.com/stat?c=problem_statement&pm=3543
+
+import math
+import itertools
+
+
+def points_distance(left_point, right_point):
+    return math.sqrt(pow(left_point[0] - right_point[0], 2) +
+                     pow(left_point[1] - right_point[1], 2))
+
+
+def cities_distance(left_city_stations, right_city_stations):
+    return min([(points_distance(left_station, right_station),
+                 left_station, right_station)
+                for (left_station, right_station) in
+                itertools.product(left_city_stations, right_city_stations)],
+               key=lambda x: x[0])[0]
+
+
+def parse_conditions(conditions):
+    def cords_from_line(line):
+        return [float(c) for c in line.strip('{').strip('}').split(',')]
+
+    lines = conditions.split('\n')
+    return (zip(cords_from_line(lines[1]), cords_from_line(lines[2])),
+            zip(cords_from_line(lines[3]), cords_from_line(lines[4])),
+            zip(cords_from_line(lines[5]), cords_from_line(lines[6])))
+
+
+def connect(conditions):
+    # parse conditions
+    [A_stations, B_stations, C_stations] = parse_conditions(conditions)
+
+    cities = [A_stations, B_stations, C_stations]
+
+    return \
+        min([cities_distance(a_city, b_city) + cities_distance(b_city, c_city)
+             for (a_city, b_city, c_city) in itertools.permutations(cities)])
+
+
+CONDITIONS1 = """
+{0,0,0}
+{0,1,2}
+{2,3}
+{1,1}
+{1,5}
+{3,28}
+"""
+
+CONDITIONS2 = """
+{-2,-1,0,1,2}
+{0,0,0,0,0}
+{-2,-1,0,1,2}
+{1,1,1,1,1}
+{-2,-1,0,1,2}
+{2,2,2,2,2}
+"""
+
+
+def main():
+    print connect(CONDITIONS2)
+
+
+main()
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.