This repository has been archived on 2019-08-08. You can view files and clone it, but cannot push or open issues/pull-requests.
hashcode2016/main.py

287 lines
6.5 KiB
Python
Raw Permalink Blame History

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#!/usr/bin/env python3
import math
import sys
def print(*a):
return
print("#hashcode2016")
X = 0 # Nb rows
Y = 0 # Nb columns
D = 0 # Nb drones
T = 0 # Deadline
M = 0 # Maximum load
P = 0 # Nb products
W = 0 # Nb warehouses
C = 0 # Nb customers
t = 0 # Turn
s = 0 # Score
Dp = [] # Positions of drones
# (x, y)
Di = [] # Items of drones
# {product number: qt}
Dd = [] # Turn avaibility of drone
# int
Da = [] # Avaibles drones
# bool
Pw = [] # Weight of products
# int
Wp = [] # Positions of warehouses
# (x, y)
Wi = [] # Items of warehouses
# {product number: qt}
Cp = [] # Positions of customers
# (x, y)
Ci = [] # Needs of customers
# {product number: qt}
# Reading raw data
f = open(sys.argv[1], 'r')
line = f.readline()
info = line.split(' ')
GRILLE = (int(info[0]), int(info[1]))
X, Y = GRILLE
D = int(info[2])
T = int(info[3])
M = int(info[4])
line = f.readline()
P = int(line)
line = f.readline()
info = line.split(' ')
for i in range(0, P):
Pw.append(int(info[i]))
line = f.readline()
W = int(line)
for i in range(0, W):
line = f.readline()
info = line.split(' ')
Wp.append((int(info[0]), int(info[1])))
line = f.readline()
info = line.split(' ')
productQ = {}
for j in range(0, len(info)):
productQ[j] = int(info[j])
Wi.append(productQ)
line = f.readline()
C = int(line)
for i in range(0, C):
line = f.readline()
info = line.split(' ')
Cp.append((int(info[0]), int(info[1])))
line = f.readline()
nbP = int(line)
line = f.readline()
info = line.split(' ')
orderQ = {}
for k in range(0, P):
orderQ[k] = 0
for j in range(0, nbP):
orderQ[int(info[j])] += -1
Ci.append(orderQ)
f.close()
# Constituting data
for d in range(D):
Dp.append(Wp[0])
Di.append(dict((p, 0) for p in range(P)))
Dd.append(0)
Da.append(True)
Out = [] # Drones commands
# Debug
assert(len(Dp) == len(Di) == len(Dd) == len(Da) == D)
assert(len(Pw) == P)
assert(len(Wp) == len(Wi) == W)
assert(len(Cp) == len(Ci) == C)
#def droneInfos(d):
# print("- Drone", d, "carries", ", ".join([p + ": " + q + "×" + Dw[p] for
def showGrid():
for y in range(Y):
for x in range(X):
if (x, y) in Wp:
print("W", end="")
if (x, y) in Cp:
print("C", end="")
else:
print("·", end="")
print()
# Utilities
def distance(A, B):
return math.ceil(math.sqrt(pow(B[0] - A[0], 2) + pow(B[1] - A[1], 2)))
def weight(d):
return sum(Di[d][p]*Pw[p]for p in range(P))
# Actions
def load(d, w, p, q):
# drone number, warehouse, product, qt
assert(Da[d])
if (Dp[d] != Wp[w]):
Dd[d] += distance(Dp[d], Wp[w])
Dp[d] = Wp[w]
Wi[w][p] += -q
Di[d][p] += +q
assert(Wi[w][p] >= 0)
assert(weight(d) <= M)
assert(Dd[d] <= T)
print("Drone", d, "loads", q, "of", p, "from warehouse", w, "", Dd[d])
Out.append(str(d) + ' L ' + str(w) + ' ' + str(p) + ' ' + str(q))
def unload(d, w, p, q):
# drone number, warehouse, product, qt
assert(Da[d])
if (Dp[d] != Wp[w]):
Dd[d] += distance(Dp[d], Wp[w])
Dp[d] = Wp[w]
Wi[w][p] += +q
Di[d][p] += -q
assert(Dd[d] <= T)
print("Drone", d, "unloads", q, "of", p, "from warehouse", w, "", Dd[d])
Out.append(str(d) + ' U ' + str(w) + ' ' + str(p) + ' ' + str(q))
def deliver(d, c, p, q):
# drone number, customer, product, qt
assert(Da[d])
if (Dp[d] != Cp[c]):
Dd[d] += distance(Dp[d], Cp[c])
Dp[d] = Cp[c]
Ci[c][p] += +q
Di[d][p] += -q
Dd[d] += 1
assert(Dd[d] <= T)
print("Drone", d, "delivers", q, "of", p, "to client", c, "", Dd[d])
Out.append(str(d) + ' D ' + str(c) + ' ' + str(p) + ' ' + str(q))
# Score
if Ci[c][p] == 0:
global s
s += math.ceil((T-t)/T*100)
def wait(d, w=1):
global Dd, Da
assert(Da[d])
Dd[d] += w
Da[d] = False
print("Drone", d, "waits", w, "turn" + ('s' if w >= 2 else ''), "", Dd[d])
Out.append(str(d) + ' W ' + str(w))
# Control
def newTurn():
global t
# Finishing turn
for d in [d for d in range(len(Da)) if Da[d]]:
print(d)
wait(d)
assert(sum(Da) == 0)
# New turn
t += 1
print("--- Turn", t)
for d in range(D):
if Dd[d] <= t:
Da[d] = True
print("Drones", ", ".join([str(d) for d in range(len(Da)) if Da[d]]), "(", len(Da), ")", "are avaible")
def end():
print("--- End!")
# IA
Dt = [[] for d in range(D)] # Drone tasks
# (client, product)
def nearestW(p, pos):
minDist = math.inf
selW = None
for w in range(W):
if Wi[w][p] > 0:
dist = distance(Wp[w], pos)
if dist < minDist:
minDist = dist
selW = w
return selW
def listItems(d):
items = []
for p in range(P):
for cp in range(abs(Di[d][p])):
items.append(p)
return items
N = [] # Needs
# client, product
for c in range(C):
for p in range(P):
for cp in range(abs(Ci[c][p])):
N.append((c, p))
try:
while t < T-100:
for d in [d for d in range(D) if Da[d]]:
for tk in Dt[d]:
c, p = tk
deliver(d, c, p, 1)
Dt[d].remove(tk)
if len([d for d in range(D) if Da[d]]) > 1:
for n in N:
c, p = n
w = nearestW(p, Cp[c])
if w != None:
minDist = math.inf;
selD = None
for d in [d for d in range(D) if Da[d] and len(listItems(d)) < 1]:
dist = distance(Dp[d], Wp[w])
if dist < minDist:
minDist = dist
print(d)
selD = d
print(244, selD)
if selD != None:
load(selD, w, p, 1)
N.remove(n)
Dt[selD].append((c, p))
else:
break
newTurn()
except KeyboardInterrupt:
pass
# Output
f = open(sys.argv[1] + 'o', 'w')
f.write(str(len(Out)) + '\n' + '\n'.join(Out) + '\n')
f.close()
def SortCustomer():
CpSort = []
for i in range(0, len(Cp)):
CpSort.append((i, Cp[i], distance(Wp[0], Cp[i])))
CpSort.sort(key=lambda tup: tup[2])
def WarehouseHasItems(w, items):
for i in range(0, len(items)):
if Wi[w][items[i][0]] < items[i][1]:
return False
return True
sys.stdout.write(str(s)+'\n')