Šis repozitorijs tika arhivēts 2019-08-08. Ir iespējams aplūkot tā failus un to konēt, bet nav iespējams iesūtīt izmaiņas, kā arī atvērt jaunas problēmas vai izmaiņu pieprasījumus.
hashcode2016/main.py

287 rindas
6.5 KiB
Python

Šis fails satur neviennozīmīgus unikoda simbolus!

Šis fails satur nevienozīmīgus unikoda simbolus, kas var būt mulsinoši un grūti atšķirami. Ja tie ir izmantoti ar pamatotu nodumu, tad varat ignorēt šo brīdinājumu. Izmantojiet Kodēt pogu, lai parādītu šos neredzamos simbolus.

#!/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')