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.

reborn.py 15KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511
  1. #!/usr/bin/env python3
  2. import sys
  3. import math
  4. import copy
  5. import progressbar
  6. DEBUG = False
  7. outLines = []
  8. differed = dict()
  9. def log(*data):
  10. if DEBUG:
  11. print(*data)
  12. def output(*values):
  13. global outLines
  14. outLines.append(' '.join([str(val) for val in values]))
  15. def distance(A, B):
  16. return math.ceil(math.sqrt(pow(B[0] - A[0], 2) + pow(B[1] - A[1], 2)))
  17. class Product:
  18. ALL = []
  19. def __init__(self, weight):
  20. self.id = len(self.ALL)
  21. self.ALL.append(self)
  22. self.weight = weight
  23. def totalWeight(items):
  24. s = 0
  25. for i in items:
  26. s += Product.get(i).weight
  27. return s
  28. def get(pid):
  29. return __class__.ALL[pid]
  30. def len():
  31. return len(__class__.ALL)
  32. class Warehouse:
  33. ALL = []
  34. def __init__(self, pos, items):
  35. self.id = len(self.ALL)
  36. self.ALL.append(self)
  37. self.pos = pos
  38. self.items = items
  39. self.plannedItems = self.items.copy()
  40. self.clients = []
  41. def plan(self, items):
  42. for i in items:
  43. self.plannedItems.remove(i)
  44. def planRefill(self, items):
  45. for i in items:
  46. self.plannedNeeds.remove(i)
  47. def planUnload(self, items):
  48. for i in items:
  49. self.plannedItems.remove(i)
  50. self.plannedExtra.remove(i)
  51. def pack(self, payload=-1, rests=[]):
  52. if payload == -1:
  53. payload = Drone.PAYLOAD
  54. p = []
  55. load = 0
  56. rests = rests.copy()
  57. needs = []
  58. for need in self.plannedNeeds:
  59. if need in rests:
  60. needs.append(need)
  61. rests.remove(need)
  62. # # Sort occurences
  63. # occ = [(i, self.plannedNeeds.count(i)) for i in self.plannedNeeds]
  64. # occ.sort(key=lambda c: c[1])
  65. # # TODO Optimise for same product wanted more than once
  66. # Looks like it's not necessary for set 2, we'll see that later
  67. # Sort needs by weight
  68. couples = [(i, Product.get(i).weight) for i in needs]
  69. couples.sort(key=lambda c: c[1])
  70. for couple in couples:
  71. need, weight = couple
  72. if load + weight <= payload:
  73. p.append(need)
  74. load += weight
  75. return p
  76. # Set functions
  77. def near(pos):
  78. couples = []
  79. for el in __class__.ALL:
  80. couples.append([el, distance(el.pos, pos)])
  81. return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]
  82. def get(pid):
  83. return __class__.ALL[pid]
  84. def len():
  85. return len(__class__.ALL)
  86. class Client:
  87. ALL = []
  88. UNSATISFIED = []
  89. def __init__(self, pos, needs):
  90. self.id = len(self.ALL)
  91. self.ALL.append(self)
  92. self.UNSATISFIED.append(self)
  93. self.pos = pos
  94. self.needs = needs
  95. self.plannedNeeds = self.needs.copy()
  96. self.warehouse = Warehouse.near(self.pos)[0]
  97. self.warehouse.clients.append(self)
  98. def plan(self, needs):
  99. for n in needs:
  100. self.plannedNeeds.remove(n)
  101. def satisfied(self):
  102. return len(self.needs) == 0
  103. def pack(self, payload=-1, rests=[]):
  104. if payload == -1:
  105. payload = Drone.PAYLOAD
  106. p = []
  107. load = 0
  108. rests = rests.copy()
  109. needs = []
  110. for need in self.plannedNeeds:
  111. if need in rests:
  112. needs.append(need)
  113. rests.remove(need)
  114. # # Sort occurences
  115. # occ = [(i, self.plannedNeeds.count(i)) for i in self.plannedNeeds]
  116. # occ.sort(key=lambda c: c[1])
  117. # # TODO Optimise for same product wanted more than once
  118. # Looks like it's not necessary for set 2, we'll see that later
  119. # Sort needs by weight
  120. couples = [(i, Product.get(i).weight) for i in needs]
  121. couples.sort(key=lambda c: c[1])
  122. for couple in couples:
  123. need, weight = couple
  124. if load + weight <= payload:
  125. p.append(need)
  126. load += weight
  127. return p
  128. # Set functions
  129. def near(pos):
  130. couples = []
  131. for el in __class__.UNSATISFIED:
  132. couples.append([el, distance(el.pos, pos)])
  133. return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]
  134. def get(pid):
  135. return __class__.ALL[pid]
  136. def len():
  137. return len(__class__.ALL)
  138. class Drone:
  139. ALL = []
  140. PAYLOAD = 0
  141. def __init__(self):
  142. self.id = len(self.ALL)
  143. self.ALL.append(self)
  144. self.pos = Warehouse.get(0).pos
  145. self.items = []
  146. self.avail = 0
  147. self.tasks = []
  148. def addTask(self, *task):
  149. self.tasks.append(task)
  150. def executeTask(self):
  151. if self.available():
  152. if len(self.tasks):
  153. task = self.tasks[0]
  154. getattr(self, task[0])(*task[1:])
  155. self.tasks = self.tasks[1:]
  156. else:
  157. self.wait()
  158. def weight(self):
  159. return Product.totalWeight(self.items)
  160. def busyFor(self, time):
  161. self.avail += time
  162. assert(self.avail < T)
  163. def available(self):
  164. return self.avail <= turn
  165. def load(self, warehouse, product, qt):
  166. assert(self.available())
  167. if (self.pos != warehouse.pos):
  168. self.busyFor(distance(self.pos, warehouse.pos))
  169. self.pos = warehouse.pos
  170. # Differed actions
  171. def diff():
  172. for q in range(qt):
  173. warehouse.items.remove(product.id)
  174. self.items.append(product.id)
  175. global differed
  176. if self.avail not in differed:
  177. differed[self.avail] = []
  178. differed[self.avail].append(diff)
  179. self.busyFor(1)
  180. assert(self.weight() <= __class__.PAYLOAD)
  181. log("Drone", self.id, "loads", qt, "of", product.id, "from warehouse", warehouse.id, "→", self.avail)
  182. output(self.id, 'L', warehouse.id, product.id, qt)
  183. def unload(self, warehouse, product, qt):
  184. assert(self.available())
  185. if (self.pos != warehouse.pos):
  186. self.busyFor(distance(self.pos, warehouse.pos))
  187. self.pos = warehouse.pos
  188. # Differed actions
  189. def diff():
  190. for q in range(qt):
  191. self.items.remove(product.id)
  192. warehouse.items.append(product.id)
  193. warehouse.plannedItems.append(product.id)
  194. global differed
  195. if self.avail not in differed:
  196. differed[self.avail] = []
  197. differed[self.avail].append(diff)
  198. self.busyFor(1)
  199. log("Drone", self.id, "unloads", qt, "of", product.id, "to warehouse", warehouse.id, "→", self.avail)
  200. output(self.id, 'U', warehouse.id, product.id, qt)
  201. def deliver(self, client, product, qt):
  202. assert(self.available())
  203. if (self.pos != client.pos):
  204. self.busyFor(distance(self.pos, client.pos))
  205. self.pos = client.pos
  206. for q in range(qt):
  207. self.items.remove(product.id)
  208. client.needs.remove(product.id)
  209. self.busyFor(1)
  210. log("Drone", self.id, "delivers", qt, "of", product.id, "to client", client.id, "→", self.avail)
  211. output(self.id, 'D', client.id, product.id, qt)
  212. if client.satisfied():
  213. global score
  214. score += math.ceil((T-(self.avail+1))/T*100)
  215. Client.UNSATISFIED.remove(client)
  216. log("Client", client.id, "satisfied!", "New score:", score)
  217. def wait(self, turns=1):
  218. assert(self.available())
  219. self.busyFor(1)
  220. log("Drone", self.id, "waits", turns, "turn" + ('s' if turns >= 2 else ''), "→", self.avail)
  221. output(self.id, 'W', turns)
  222. # Set functions
  223. def near(pos):
  224. couples = []
  225. for el in __class__.ALL:
  226. couples.append([el, distance(el.pos, pos)])
  227. return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]
  228. def get(pid):
  229. return __class__.ALL[pid]
  230. def len():
  231. return len(__class__.ALL)
  232. X = 0 # Nb rows
  233. Y = 0 # Nb columns
  234. T = 0 # Deadline
  235. turn = 0 # Turn
  236. score = 0 # Score
  237. done = False
  238. def readFile(filename):
  239. global X, Y, T
  240. with open(filename, 'r') as f:
  241. # Parameters
  242. X, Y, D, T, Drone.PAYLOAD = [int(i) for i in f.readline().split(' ')]
  243. # Products
  244. P = int(f.readline())
  245. weights = [int(i) for i in f.readline().split(' ')]
  246. assert(len(weights) == P)
  247. for w in weights:
  248. Product(w)
  249. # Warehouses
  250. for i in range(0, int(f.readline())):
  251. pos = [int(i) for i in f.readline().split(' ')]
  252. qtItems = [int(i) for i in f.readline().split(' ')]
  253. assert(len(qtItems) == P)
  254. items = []
  255. for p in range(P):
  256. for i in range(qtItems[p]):
  257. items.append(p)
  258. Warehouse(pos, items)
  259. # Clients
  260. for i in range(0, int(f.readline())):
  261. pos = [int(i) for i in f.readline().split(' ')]
  262. N = int(f.readline())
  263. needs = [int(i) for i in f.readline().split(' ')]
  264. assert(len(needs) == N)
  265. Client(pos, needs)
  266. # Create drones
  267. for d in range(D):
  268. Drone()
  269. # Find warehouse needs
  270. for warehouse in Warehouse.ALL:
  271. needs = []
  272. extra = warehouse.items.copy()
  273. for client in warehouse.clients:
  274. needs += client.needs
  275. warehouse.toDeliver = needs.copy()
  276. for item in needs:
  277. if item in extra:
  278. extra.remove(item)
  279. for item in warehouse.items:
  280. if item in needs:
  281. needs.remove(item)
  282. warehouse.needs = needs
  283. warehouse.extra = extra
  284. warehouse.plannedNeeds = warehouse.needs.copy()
  285. warehouse.plannedExtra = warehouse.extra.copy()
  286. readFile(sys.argv[1])
  287. def newTurn():
  288. global turn
  289. # Finishing turn
  290. for drone in Drone.ALL:
  291. drone.executeTask()
  292. if turn in differed:
  293. for diff in differed[turn]:
  294. diff()
  295. # New turn
  296. turn += 1
  297. log("--- Turn", turn)
  298. availableDrones = [str(drone.id) for drone in Drone.ALL if drone.available()]
  299. #log("Drones", ", ".join(availableDrones), "("+str(len(availableDrones))+")", "are available")
  300. # Algorithm that only works for 1 warehouse
  301. # Determined by trial and error. Not really reliable
  302. CLIENT_TRIES = 3
  303. CLIENT_TRIES = 100
  304. def efficiency(pack, time):
  305. return Product.totalWeight(pack) / time
  306. #return len(pack) / time
  307. #return 1 / time
  308. def route(roadmap):
  309. # Refill warehouse first
  310. # TODO Merge both (this is actually more for testing)
  311. remainingWarehouses = [w for w in Warehouse.near(roadmap['pos']) if w.plannedNeeds and w not in roadmap['clients'] and w != roadmap['warehouse']]
  312. for warehouse in remainingWarehouses[:CLIENT_TRIES]:
  313. pack = warehouse.pack(Drone.PAYLOAD - Product.totalWeight(roadmap['loads']), roadmap['warehouse'].plannedExtra)
  314. if not pack:
  315. continue
  316. roadmap['warehouse'].planUnload(pack)
  317. warehouse.planRefill(pack)
  318. roadmap['deliverTime'] += 42
  319. roadmap['pos'] = warehouse.pos
  320. roadmap['loads'] += pack
  321. roadmap['clients'].append(warehouse)
  322. roadmap['stops'].append((warehouse, pack))
  323. return roadmap
  324. # Find the nearest client that still has things to be delivered
  325. remainingClients = [c for c in Client.near(roadmap['pos']) if c.plannedNeeds and c not in roadmap['clients']]
  326. #for client in remainingClients:
  327. options = []
  328. for client in remainingClients[:CLIENT_TRIES]:
  329. #for client in remainingClients:
  330. # Create a pack to deliver
  331. pack = client.pack(Drone.PAYLOAD - Product.totalWeight(roadmap['loads']), roadmap['warehouse'].plannedItems)
  332. if not pack:
  333. continue
  334. # Calcultes the efficiency of adding a stop
  335. routeTime = distance(roadmap['pos'], client.pos) + len(list(set(pack)))
  336. routeEfficiency = efficiency(pack, routeTime)
  337. if roadmap['stops']:
  338. # Calculates the efficiency of coming back to warehouse and to the client again
  339. backPack = client.pack(rests=roadmap['warehouse'].items)
  340. backTime = len(list(set(backPack))) + distance(roadmap['pos'], roadmap['warehouse'].pos) + distance(roadmap['warehouse'].pos, client.pos)
  341. backEfficiency = efficiency(backPack, backTime)
  342. if backEfficiency > routeEfficiency:
  343. continue
  344. options.append({
  345. 'client': client,
  346. 'efficiency': routeEfficiency,
  347. 'routeTime': routeTime,
  348. 'pack': pack
  349. })
  350. if not roadmap['stops']: # If it is the first stop, don't provide any alternative
  351. break
  352. if options:
  353. # Choose the best option (i.e. the max efficiency)
  354. #option = sorted(options, key=lambda c: c['efficiency'])[-1]
  355. option = options[0]
  356. # Plan the delivery
  357. roadmap['warehouse'].plan(option['pack'])
  358. option['client'].plan(option['pack'])
  359. roadmap['deliverTime'] += option['routeTime']
  360. roadmap['pos'] = option['client'].pos
  361. roadmap['loads'] += option['pack']
  362. roadmap['clients'].append(option['client'])
  363. roadmap['stops'].append((option['client'], option['pack']))
  364. return route(roadmap)
  365. else:
  366. return roadmap
  367. def think():
  368. # For each drone that has nothing to do
  369. for drone in [d for d in Drone.ALL if d.available() and not d.tasks]:
  370. # Find the nearest warehouse
  371. warehouse = Warehouse.near(drone.pos)[0]
  372. roadmap = route({
  373. 'pos': warehouse.pos,
  374. 'warehouse': warehouse,
  375. 'deliverTime': 0,
  376. 'loads': [],
  377. 'clients': [],
  378. 'stops': []
  379. })
  380. if not roadmap['stops']:
  381. global done
  382. done = True
  383. #if len(Client.UNSATISFIED) == 0:
  384. # done = False
  385. if done:
  386. break
  387. loadOcc = dict((i, roadmap['loads'].count(i)) for i in roadmap['loads'])
  388. for i in loadOcc:
  389. drone.addTask('load', warehouse, Product.get(i), loadOcc[i])
  390. for client, items in roadmap['stops']:
  391. itemsOcc = dict((j, items.count(j)) for j in items)
  392. action = 'deliver' if type(client).__name__ is 'Client' else 'unload'
  393. for i in itemsOcc:
  394. drone.addTask(action, client, Product.get(i), itemsOcc[i])
  395. if DEBUG:
  396. SIMULATION = 3000
  397. else:
  398. SIMULATION = 8*T/10
  399. try:
  400. if not DEBUG:
  401. bar = progressbar.ProgressBar(max_value=SIMULATION)
  402. while turn < SIMULATION and not done:
  403. think()
  404. newTurn()
  405. if not DEBUG:
  406. bar.update(turn)
  407. while turn < SIMULATION and [d for d in Drone.ALL if d.tasks]:
  408. newTurn()
  409. #if not DEBUG:
  410. # bar.update(turn)
  411. if not DEBUG:
  412. bar.finish()
  413. except KeyboardInterrupt:
  414. pass
  415. with open(sys.argv[1] + 'o', 'w') as f:
  416. f.write(str(len(outLines)) + '\n' + '\n'.join(outLines) + '\n')
  417. print("Turn:", turn)
  418. print("Score:", score)