このリポジトリは2019-08-08にアーカイブされています。 ファイルの閲覧やリポジトリのクローンは可能ですが、プッシュしたり、イシューやプルリクエストを作成することはできません。
hashcode2016/main.py

287 行
6.5 KiB
Python
Raw パーマリンク Blame 履歴

このファイルには曖昧(ambiguous)なUnicode文字が含まれています!

このファイルには曖昧(ambiguous)なUnicode文字が含まれており、あなたが使用しているロケールにおいて他の文字と混同する可能性があります。 あなたのユースケースが意図的かつ正当な場合はこの警告を無視して構いません。 それらの文字をハイライトするにはエスケープボタンを使用します。

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