Hackathon2024/Level_1a.py at main · HariharanJB/Hackathon2024 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
import json
f = open("/content/level1a.json","r")
data = json.load(f)

dic = {}
dic['r0'] = {}
dic['r0']['order_quantity'] = 0
dic['r0']['distances'] = data['restaurants']['r0']['neighbourhood_distance']

for i in data['neighbourhoods'].keys():
    dic[i] = data['neighbourhoods'][i]
count = 1
for i in dic.keys():
    if i!='r0':
      dic[i]['distances'].insert(0,dic['r0']['distances'][count])
      count+= 1
    else:
      dic['r0']['distances'].insert(0,0)

path = []
keys = [i for i in dic.keys()]
capacity = 0
counter = 0
path.append([])
def travellingsalesman(c):
    global cost
    global capacity
    global counter
    adj_vertex = -1
    visited[c] = 1
    min_val = float('inf')
    path[counter].append(keys[c])
    for k in range(n):
        if (tsp_g[c][k] != 0) and (visited[k] == 0):
          if tsp_g[c][k] < min_val:
                min_val = tsp_g[c][k]
                adj_vertex = k
    if capacity + dic[keys[adj_vertex]]['order_quantity'] > 600:
        capacity = 0
        path[counter].append(keys[0])
        counter += 1
        path.append([])
        travellingsalesman(0)
    else:
        capacity += dic[keys[adj_vertex]]['order_quantity']
        if (min_val != float('inf')):
          cost = cost + min_val
        if adj_vertex == -1:
          adj_vertex = 0
          path[counter].append(keys[adj_vertex])
          cost = cost + tsp_g[c][adj_vertex]
          return
        travellingsalesman(adj_vertex)

n = len(keys)
cost = 0
visited = [0]*n
tsp_g = []
for i in dic.keys():
    tsp_g.append(dic[i]['distances'])
travellingsalesman(0)
path.pop()
print(path)
output = {}
output['v0'] = {}
counter = 0
for i in range(len(path)):
  output['v0']['path'+str(i)] =path[i]


outfile = open('level1a_output.json','w')
json.dump(output,outfile)
outfile.close()