Team: Doctor Cicero
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.

main.py 6.5KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286
  1. #!/usr/bin/env python3
  2. import math
  3. import sys
  4. def print(*a):
  5. return
  6. print("#hashcode2016")
  7. X = 0 # Nb rows
  8. Y = 0 # Nb columns
  9. D = 0 # Nb drones
  10. T = 0 # Deadline
  11. M = 0 # Maximum load
  12. P = 0 # Nb products
  13. W = 0 # Nb warehouses
  14. C = 0 # Nb customers
  15. t = 0 # Turn
  16. s = 0 # Score
  17. Dp = [] # Positions of drones
  18. # (x, y)
  19. Di = [] # Items of drones
  20. # {product number: qt}
  21. Dd = [] # Turn avaibility of drone
  22. # int
  23. Da = [] # Avaibles drones
  24. # bool
  25. Pw = [] # Weight of products
  26. # int
  27. Wp = [] # Positions of warehouses
  28. # (x, y)
  29. Wi = [] # Items of warehouses
  30. # {product number: qt}
  31. Cp = [] # Positions of customers
  32. # (x, y)
  33. Ci = [] # Needs of customers
  34. # {product number: qt}
  35. # Reading raw data
  36. f = open(sys.argv[1], 'r')
  37. line = f.readline()
  38. info = line.split(' ')
  39. GRILLE = (int(info[0]), int(info[1]))
  40. X, Y = GRILLE
  41. D = int(info[2])
  42. T = int(info[3])
  43. M = int(info[4])
  44. line = f.readline()
  45. P = int(line)
  46. line = f.readline()
  47. info = line.split(' ')
  48. for i in range(0, P):
  49. Pw.append(int(info[i]))
  50. line = f.readline()
  51. W = int(line)
  52. for i in range(0, W):
  53. line = f.readline()
  54. info = line.split(' ')
  55. Wp.append((int(info[0]), int(info[1])))
  56. line = f.readline()
  57. info = line.split(' ')
  58. productQ = {}
  59. for j in range(0, len(info)):
  60. productQ[j] = int(info[j])
  61. Wi.append(productQ)
  62. line = f.readline()
  63. C = int(line)
  64. for i in range(0, C):
  65. line = f.readline()
  66. info = line.split(' ')
  67. Cp.append((int(info[0]), int(info[1])))
  68. line = f.readline()
  69. nbP = int(line)
  70. line = f.readline()
  71. info = line.split(' ')
  72. orderQ = {}
  73. for k in range(0, P):
  74. orderQ[k] = 0
  75. for j in range(0, nbP):
  76. orderQ[int(info[j])] += -1
  77. Ci.append(orderQ)
  78. f.close()
  79. # Constituting data
  80. for d in range(D):
  81. Dp.append(Wp[0])
  82. Di.append(dict((p, 0) for p in range(P)))
  83. Dd.append(0)
  84. Da.append(True)
  85. Out = [] # Drones commands
  86. # Debug
  87. assert(len(Dp) == len(Di) == len(Dd) == len(Da) == D)
  88. assert(len(Pw) == P)
  89. assert(len(Wp) == len(Wi) == W)
  90. assert(len(Cp) == len(Ci) == C)
  91. #def droneInfos(d):
  92. # print("- Drone", d, "carries", ", ".join([p + ": " + q + "×" + Dw[p] for
  93. def showGrid():
  94. for y in range(Y):
  95. for x in range(X):
  96. if (x, y) in Wp:
  97. print("W", end="")
  98. if (x, y) in Cp:
  99. print("C", end="")
  100. else:
  101. print("·", end="")
  102. print()
  103. # Utilities
  104. def distance(A, B):
  105. return math.ceil(math.sqrt(pow(B[0] - A[0], 2) + pow(B[1] - A[1], 2)))
  106. def weight(d):
  107. return sum(Di[d][p]*Pw[p]for p in range(P))
  108. # Actions
  109. def load(d, w, p, q):
  110. # drone number, warehouse, product, qt
  111. assert(Da[d])
  112. if (Dp[d] != Wp[w]):
  113. Dd[d] += distance(Dp[d], Wp[w])
  114. Dp[d] = Wp[w]
  115. Wi[w][p] += -q
  116. Di[d][p] += +q
  117. assert(Wi[w][p] >= 0)
  118. assert(weight(d) <= M)
  119. assert(Dd[d] <= T)
  120. print("Drone", d, "loads", q, "of", p, "from warehouse", w, "→", Dd[d])
  121. Out.append(str(d) + ' L ' + str(w) + ' ' + str(p) + ' ' + str(q))
  122. def unload(d, w, p, q):
  123. # drone number, warehouse, product, qt
  124. assert(Da[d])
  125. if (Dp[d] != Wp[w]):
  126. Dd[d] += distance(Dp[d], Wp[w])
  127. Dp[d] = Wp[w]
  128. Wi[w][p] += +q
  129. Di[d][p] += -q
  130. assert(Dd[d] <= T)
  131. print("Drone", d, "unloads", q, "of", p, "from warehouse", w, "→", Dd[d])
  132. Out.append(str(d) + ' U ' + str(w) + ' ' + str(p) + ' ' + str(q))
  133. def deliver(d, c, p, q):
  134. # drone number, customer, product, qt
  135. assert(Da[d])
  136. if (Dp[d] != Cp[c]):
  137. Dd[d] += distance(Dp[d], Cp[c])
  138. Dp[d] = Cp[c]
  139. Ci[c][p] += +q
  140. Di[d][p] += -q
  141. Dd[d] += 1
  142. assert(Dd[d] <= T)
  143. print("Drone", d, "delivers", q, "of", p, "to client", c, "→", Dd[d])
  144. Out.append(str(d) + ' D ' + str(c) + ' ' + str(p) + ' ' + str(q))
  145. # Score
  146. if Ci[c][p] == 0:
  147. global s
  148. s += math.ceil((T-t)/T*100)
  149. def wait(d, w=1):
  150. global Dd, Da
  151. assert(Da[d])
  152. Dd[d] += w
  153. Da[d] = False
  154. print("Drone", d, "waits", w, "turn" + ('s' if w >= 2 else ''), "→", Dd[d])
  155. Out.append(str(d) + ' W ' + str(w))
  156. # Control
  157. def newTurn():
  158. global t
  159. # Finishing turn
  160. for d in [d for d in range(len(Da)) if Da[d]]:
  161. print(d)
  162. wait(d)
  163. assert(sum(Da) == 0)
  164. # New turn
  165. t += 1
  166. print("--- Turn", t)
  167. for d in range(D):
  168. if Dd[d] <= t:
  169. Da[d] = True
  170. print("Drones", ", ".join([str(d) for d in range(len(Da)) if Da[d]]), "(", len(Da), ")", "are avaible")
  171. def end():
  172. print("--- End!")
  173. # IA
  174. Dt = [[] for d in range(D)] # Drone tasks
  175. # (client, product)
  176. def nearestW(p, pos):
  177. minDist = math.inf
  178. selW = None
  179. for w in range(W):
  180. if Wi[w][p] > 0:
  181. dist = distance(Wp[w], pos)
  182. if dist < minDist:
  183. minDist = dist
  184. selW = w
  185. return selW
  186. def listItems(d):
  187. items = []
  188. for p in range(P):
  189. for cp in range(abs(Di[d][p])):
  190. items.append(p)
  191. return items
  192. N = [] # Needs
  193. # client, product
  194. for c in range(C):
  195. for p in range(P):
  196. for cp in range(abs(Ci[c][p])):
  197. N.append((c, p))
  198. try:
  199. while t < T-100:
  200. for d in [d for d in range(D) if Da[d]]:
  201. for tk in Dt[d]:
  202. c, p = tk
  203. deliver(d, c, p, 1)
  204. Dt[d].remove(tk)
  205. if len([d for d in range(D) if Da[d]]) > 1:
  206. for n in N:
  207. c, p = n
  208. w = nearestW(p, Cp[c])
  209. if w != None:
  210. minDist = math.inf;
  211. selD = None
  212. for d in [d for d in range(D) if Da[d] and len(listItems(d)) < 1]:
  213. dist = distance(Dp[d], Wp[w])
  214. if dist < minDist:
  215. minDist = dist
  216. print(d)
  217. selD = d
  218. print(244, selD)
  219. if selD != None:
  220. load(selD, w, p, 1)
  221. N.remove(n)
  222. Dt[selD].append((c, p))
  223. else:
  224. break
  225. newTurn()
  226. except KeyboardInterrupt:
  227. pass
  228. # Output
  229. f = open(sys.argv[1] + 'o', 'w')
  230. f.write(str(len(Out)) + '\n' + '\n'.join(Out) + '\n')
  231. f.close()
  232. def SortCustomer():
  233. CpSort = []
  234. for i in range(0, len(Cp)):
  235. CpSort.append((i, Cp[i], distance(Wp[0], Cp[i])))
  236. CpSort.sort(key=lambda tup: tup[2])
  237. def WarehouseHasItems(w, items):
  238. for i in range(0, len(items)):
  239. if Wi[w][items[i][0]] < items[i][1]:
  240. return False
  241. return True
  242. sys.stdout.write(str(s)+'\n')