hashcode2016/main.py

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