geoffrey
/
hashcode2016
Arşivlenmiş
1
0
Çatalla 0
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 satır
6.5 KiB
Python
Ham Kalıcı Bağlantı Suçlama Geçmiş

Bu dosya muğlak Evrensel Kodlu karakter içeriyor!

Bu dosya, aşağıda görünenden farklı bir şekilde işlenebilecek muğlak Evrensel Kodlu karakter içeriyor. Eğer bunu kasıtlı ve meşru olarak yaptıysanız bu uyarıyı yok sayabilirsiniz. Bu karakterleri göstermek için Kaçış düğmesine tıklayın.

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