taxi.py

import math

# Read file
input = open("input.txt")
rows = []
for line in input.readlines():
    rows.append(line[0: -1])
input.close()

# for row in rows:
    # print row

# Distance
    # List Comprehension
distance = [[0 for column in range(0, int(rows[0])+1)] for row in range(0, int(rows[0])+1)]
for i in range(1, int(rows[0])+1):
    for j in range(1, int(rows[0])+1):
        #print i, j
        x1 = float(rows[i].split(" ")[0])
        y1 = float(rows[i].split(" ")[1])
        x2 = float(rows[j].split(" ")[0])
        y2 = float(rows[j].split(" ")[1])
        # print x1, " ", y1, " ", x2, " ", y2
        distance[i][j] = math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) 
        # print distance[i][j]

# Dynamic Program
decision = [0] # append rows[0] letter(a, b)
decision.append("a")
cost = [[0 for column in range(0, int(rows[0])+1)] for row in range(0, int(rows[0])+1)]
# cost[1][1] = 0
taxi = [[0 for column in range(0, int(rows[0])+1)] for row in range(0, int(rows[0])+1)]
taxi[1][1] = "a"

for i in range(2, int(rows[0])+1):
    for j in range(1, i):
        # print "(", i, ",", j, ")"
        # print taxi
        # print "(", i, ",", j, ")", " "
        if i > j + 1: # (3,1)
            cost[i][j] = cost[i-1][j] + distance[i-1][i]
            # print cost[i][j]
            taxi[i][j] = taxi[i-1][j]
        elif i == j + 1: # (2,1) (3,2)
            # (2,1) special
            if i == 2 and j == 1:
                cost[2][1] = distance[1][2]
                # print cost[i][j]
                taxi[2][1] = taxi[1][1]
            # overall situation 
            else:
                min = cost[j][1]
                min_t = 1
                for t in range(1, j):
                    if cost[j][t] < min:
                        min = cost[j][t]
                        min_t = t
                cost[i][j] = min + distance[min_t][i]
                if taxi[i-1][min_t] == "a":
                    taxi[i][j] = "b"
                else:
                    taxi[i][j] = "a"
        # print taxi
        # print cost
    min_cost = cost[i][1]
    min_j = 1
    for m in range(1, i):
        if cost[i][m] < min_cost:
            min_cost = cost[i][m]
            min_j = m 
    if i == 2 and j == 1:
        decision.append("a")
    elif i == min_j + 1:
        decision.append(taxi[i][min_j])
    elif i > min_j + 1:
        decision.append(taxi[i][min_j])
# Find max from the
# print decision        
# print "The Best Solution Is: "
print decision
a = [1, 2]
b = []
for i in range(3, len(decision)):
    if decision[i] == "a":
        a.append(i)
    else:
        b.append(i)

print a
print b
output = open("output.txt", "w")
for i in range(0, len(a)):
    output.write(str(a[i]))
    output.write(" ")
output.write("\n\n")
for j in range(0, len(b)):
    output.write(str(b[j]))
    output.write(" ")
output.close()