首页 > itarticle > google hashcode 2016 比赛记

google hashcode 2016 比赛记

admin 11月 11, 2020 0

我的比赛代码

由于时间关系有许多优化没有做, 比如order优先级的计算, warehouse的选择以及多架无人机的安排. 在这个例子中我们使用了5架无人机来满负荷完成了所有的订单(order), 其实可以使用20架无人机依次执行任务, 等等.

废话不多说, talk is cheap, show me the code:

import math


row, cln, drones, T, payload = map(int, raw_input().split())
types = int(raw_input())
weights = map(int, raw_input().split())
warehouses = []
for i in xrange(int(raw_input())):
    warehouse = {}
    warehouse["position"] = map(int, raw_input().split())
    warehouse["items"] = map(int, raw_input().split())
    warehouses.append(warehouse)

orders = []
for i in xrange(int(raw_input())):
    order = {}
    order["position"] = map(int, raw_input().split())
    order["count"] = int(raw_input())
    order["items"] = map(int, raw_input().split())
    orders.append(order)


def (a, b):
    return int(math.ceil(math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)))

def count(results):
    totalNum = 0
    for drone in xrange(len(results)):
        result = results[drone]
        for eachOrder in result:
            for eachComm in eachOrder:
                totalNum += len(eachComm) * 2
    return totalNum

def translate(results):
    cnt = 0
    print count(results)
    for drone in xrange(len(results)):
        result = results[drone]
        for comms in result:
            for comm in comms:
                for key in comm:
                    print drone, 'L', 0, key, comm[key]
                for cle in comm:
                    print drone, 'D', cnt, cle, comm[cle]
            cnt += 1 # order number


# OK, let's go
# possible optimisation: decide which order to do in the first place
poids = 0
total = {}
total["totalCommands"] = []
total["turns"] = []
for order in orders:
    # first try 'mother of all warehouses' input file
    dest = order["position"]
    command = {} # for one Load-Delivery, init
    commands = []
    turns = 0
    orderItems = {}
    for x in order["items"]:
        if x not in orderItems:
            orderItems[x] = 1
        else:
            orderItems[x] += 1
    for i in xrange(types): # i is product type
        if i not in orderItems:
            continue
        lastIndex = max(orderItems.keys())
        nombre = orderItems[i] # consider each type delivary
        while nombre > 0:
            loadNum = (payload - poids) / weights[i] # load capacity
            if loadNum >= nombre:
                poids += nombre * weights[i]
                # write command
                command[i] = nombre
                if i == lastIndex:
                    commands.append(command)
                    turns += 2 * distance(warehouses[0]["position"], dest) + 2 * len(command)
                nombre = 0
            else:
                # poids += loadNum * weights[i]
                nombre -= loadNum
                poids = 0
                # write command
                if loadNum != 0:
                    command[i] = loadNum
                commands.append(command)
                # one warehouse case !!!
                turns += 2 * distance(warehouses[0]["position"], dest) + 2 * len(command)
                command = {}
    total["totalCommands"].append(commands)
    total["turns"].append(turns)
    turns = 0

#print len(total["totalCommands"])
result = []
results = []
temps = 0
for index in xrange(len(total["turns"])):
    if temps > T:
        results.append(result)
        result = []
        temps = 0
    temps += total["turns"][index]
    result.append(total["totalCommands"][index])

#print len(result)
translate(results)