hashcode2016/reborn.py

#!/usr/bin/env python3

import sys
import math
import copy
import progressbar

DEBUG = False

outLines = []
differed = dict()

def log(*data):
    if DEBUG:
        print(*data)

def output(*values):
    global outLines
    outLines.append(' '.join([str(val) for val in values]))

def distance(A, B):
    return math.ceil(math.sqrt(pow(B[0] - A[0], 2) + pow(B[1] - A[1], 2)))

class Product:
    
    ALL = []

    def __init__(self, weight):
        self.id = len(self.ALL)
        self.ALL.append(self)

        self.weight = weight

    def totalWeight(items):
        s = 0
        for i in items:
            s += Product.get(i).weight
        return s

    def get(pid):
        return __class__.ALL[pid]

    def len():
        return len(__class__.ALL)

class Warehouse:
    
    ALL = []

    def __init__(self, pos, items):
        self.id = len(self.ALL)
        self.ALL.append(self)

        self.pos = pos
        self.items = items

        self.plannedItems = self.items.copy()
        self.clients = []

    def plan(self, items):
        for i in items:
            self.plannedItems.remove(i)

    def planRefill(self, items):
        for i in items:
            self.plannedNeeds.remove(i)

    def planUnload(self, items):
        for i in items:
            self.plannedItems.remove(i)
            self.plannedExtra.remove(i)

    def pack(self, payload=-1, rests=[]):
        if payload == -1:
            payload = Drone.PAYLOAD
        p = []
        load = 0
        rests = rests.copy()
        needs = []
        for need in self.plannedNeeds:
            if need in rests:
                needs.append(need)
                rests.remove(need)
        # # Sort occurences
        # occ = [(i, self.plannedNeeds.count(i)) for i in self.plannedNeeds]
        # occ.sort(key=lambda c: c[1])
        # # TODO Optimise for same product wanted more than once
        # Looks like it's not necessary for set 2, we'll see that later
        # Sort needs by weight
        couples = [(i, Product.get(i).weight) for i in needs]
        couples.sort(key=lambda c: c[1])
        for couple in couples:
            need, weight = couple
            if load + weight <= payload:
                p.append(need)
                load += weight
        return p

    # Set functions
    def near(pos):
        couples = []
        for el in __class__.ALL:
            couples.append([el, distance(el.pos, pos)])
        return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]

    def get(pid):
        return __class__.ALL[pid]

    def len():
        return len(__class__.ALL)

class Client:
    
    ALL = []
    UNSATISFIED = []

    def __init__(self, pos, needs):
        self.id = len(self.ALL)
        self.ALL.append(self)
        self.UNSATISFIED.append(self)

        self.pos = pos
        self.needs = needs

        self.plannedNeeds = self.needs.copy()
        self.warehouse = Warehouse.near(self.pos)[0]
        self.warehouse.clients.append(self)

    def plan(self, needs):
        for n in needs:
            self.plannedNeeds.remove(n)

    def satisfied(self):
        return len(self.needs) == 0

    def pack(self, payload=-1, rests=[]):
        if payload == -1:
            payload = Drone.PAYLOAD
        p = []
        load = 0
        rests = rests.copy()
        needs = []
        for need in self.plannedNeeds:
            if need in rests:
                needs.append(need)
                rests.remove(need)
        # # Sort occurences
        # occ = [(i, self.plannedNeeds.count(i)) for i in self.plannedNeeds]
        # occ.sort(key=lambda c: c[1])
        # # TODO Optimise for same product wanted more than once
        # Looks like it's not necessary for set 2, we'll see that later
        # Sort needs by weight
        couples = [(i, Product.get(i).weight) for i in needs]
        couples.sort(key=lambda c: c[1])
        for couple in couples:
            need, weight = couple
            if load + weight <= payload:
                p.append(need)
                load += weight
        return p

    # Set functions
    def near(pos):
        couples = []
        for el in __class__.UNSATISFIED:
            couples.append([el, distance(el.pos, pos)])
        return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]

    def get(pid):
        return __class__.ALL[pid]

    def len():
        return len(__class__.ALL)

class Drone:
    
    ALL = []
    PAYLOAD = 0

    def __init__(self):
        self.id = len(self.ALL)
        self.ALL.append(self)

        self.pos = Warehouse.get(0).pos
        self.items = []
        self.avail = 0

        self.tasks = []

    def addTask(self, *task):
        self.tasks.append(task)

    def executeTask(self):
        if self.available():
            if len(self.tasks):
                task = self.tasks[0]
                getattr(self, task[0])(*task[1:])
                self.tasks = self.tasks[1:]
            else:
                self.wait()

    def weight(self):
        return Product.totalWeight(self.items)

    def busyFor(self, time):
        self.avail += time 
        assert(self.avail < T)

    def available(self):
        return self.avail <= turn

    def load(self, warehouse, product, qt):
        assert(self.available())
        if (self.pos != warehouse.pos):
            self.busyFor(distance(self.pos, warehouse.pos))
            self.pos = warehouse.pos

        # Differed actions
        def diff():
            for q in range(qt):
                warehouse.items.remove(product.id)
                self.items.append(product.id)
        global differed
        if self.avail not in differed:
            differed[self.avail] = []
        differed[self.avail].append(diff)

        self.busyFor(1)
        assert(self.weight() <= __class__.PAYLOAD)
        log("Drone", self.id, "loads", qt, "of", product.id, "from warehouse", warehouse.id, "→", self.avail)
        output(self.id, 'L', warehouse.id, product.id, qt)        

    def unload(self, warehouse, product, qt):
        assert(self.available())
        if (self.pos != warehouse.pos):
            self.busyFor(distance(self.pos, warehouse.pos))
            self.pos = warehouse.pos

        # Differed actions
        def diff():
            for q in range(qt):
                self.items.remove(product.id)
                warehouse.items.append(product.id)
                warehouse.plannedItems.append(product.id)
        global differed
        if self.avail not in differed:
            differed[self.avail] = []
        differed[self.avail].append(diff)

        self.busyFor(1)
        log("Drone", self.id, "unloads", qt, "of", product.id, "to warehouse", warehouse.id, "→", self.avail)
        output(self.id, 'U', warehouse.id, product.id, qt)        

    def deliver(self, client, product, qt):
        assert(self.available())
        if (self.pos != client.pos):
            self.busyFor(distance(self.pos, client.pos))
            self.pos = client.pos
        for q in range(qt):
            self.items.remove(product.id)
            client.needs.remove(product.id)
        self.busyFor(1)
        log("Drone", self.id, "delivers", qt, "of", product.id, "to client", client.id, "→", self.avail)
        output(self.id, 'D', client.id, product.id, qt)        
        if client.satisfied():
            global score
            score += math.ceil((T-(self.avail+1))/T*100)
            Client.UNSATISFIED.remove(client)
            log("Client", client.id, "satisfied!", "New score:", score)

    def wait(self, turns=1):
        assert(self.available())
        self.busyFor(1)
        log("Drone", self.id, "waits", turns, "turn" + ('s' if turns >= 2 else ''), "→", self.avail)
        output(self.id, 'W', turns)

    # Set functions
    def near(pos):
        couples = []
        for el in __class__.ALL:
            couples.append([el, distance(el.pos, pos)])
        return [couple[0] for couple in sorted(couples, key=lambda c: c[1])]

    def get(pid):
        return __class__.ALL[pid]

    def len():
        return len(__class__.ALL)


X = 0 # Nb rows
Y = 0 # Nb columns
T = 0 # Deadline

turn = 0 # Turn
score = 0 # Score
done = False

def readFile(filename):
    global X, Y, T

    with open(filename, 'r') as f:
        # Parameters
        X, Y, D, T, Drone.PAYLOAD = [int(i) for i in f.readline().split(' ')]

        # Products
        P = int(f.readline())
        weights = [int(i) for i in f.readline().split(' ')]
        assert(len(weights) == P)
        for w in weights:
            Product(w)

        # Warehouses
        for i in range(0, int(f.readline())):
            pos = [int(i) for i in f.readline().split(' ')]
            qtItems = [int(i) for i in f.readline().split(' ')]
            assert(len(qtItems) == P)

            items = []
            for p in range(P):
                for i in range(qtItems[p]):
                    items.append(p)

            Warehouse(pos, items)

        # Clients
        for i in range(0, int(f.readline())):
            pos = [int(i) for i in f.readline().split(' ')]

            N = int(f.readline())

            needs = [int(i) for i in f.readline().split(' ')]
            assert(len(needs) == N)

            Client(pos, needs)

        # Create drones
        for d in range(D):
            Drone()

        # Find warehouse needs
        for warehouse in Warehouse.ALL:
            needs = []
            extra = warehouse.items.copy()
            for client in warehouse.clients:
                needs += client.needs
            warehouse.toDeliver = needs.copy()
            for item in needs:
                if item in extra:
                    extra.remove(item)
            for item in warehouse.items:
                if item in needs:
                    needs.remove(item)
            warehouse.needs = needs
            warehouse.extra = extra
            warehouse.plannedNeeds = warehouse.needs.copy()
            warehouse.plannedExtra = warehouse.extra.copy()
readFile(sys.argv[1])

def newTurn():
    global turn
    # Finishing turn
    for drone in Drone.ALL:
        drone.executeTask()
    if turn in differed:
        for diff in differed[turn]:
            diff()
    # New turn
    turn += 1
    log("--- Turn", turn)
    availableDrones = [str(drone.id) for drone in Drone.ALL if drone.available()]
    #log("Drones", ", ".join(availableDrones), "("+str(len(availableDrones))+")", "are available")

# Algorithm that only works for 1 warehouse

# Determined by trial and error. Not really reliable
CLIENT_TRIES = 3
CLIENT_TRIES = 100
def efficiency(pack, time):
    return Product.totalWeight(pack) / time
    #return len(pack) / time
    #return 1 / time

def route(roadmap):
    # Refill warehouse first
    # TODO Merge both (this is actually more for testing)
    remainingWarehouses = [w for w in Warehouse.near(roadmap['pos']) if w.plannedNeeds and w not in roadmap['clients'] and w != roadmap['warehouse']]
    for warehouse in remainingWarehouses[:CLIENT_TRIES]:
        pack = warehouse.pack(Drone.PAYLOAD - Product.totalWeight(roadmap['loads']), roadmap['warehouse'].plannedExtra)
        if not pack:
            continue
        roadmap['warehouse'].planUnload(pack)
        warehouse.planRefill(pack)
        roadmap['deliverTime'] += 42
        roadmap['pos'] = warehouse.pos
        roadmap['loads'] += pack
        roadmap['clients'].append(warehouse)
        roadmap['stops'].append((warehouse, pack))
        return roadmap


    # Find the nearest client that still has things to be delivered
    remainingClients = [c for c in Client.near(roadmap['pos']) if c.plannedNeeds and c not in roadmap['clients']]
    #for client in remainingClients:
    options = []
    for client in remainingClients[:CLIENT_TRIES]:
    #for client in remainingClients:
        # Create a pack to deliver
        pack = client.pack(Drone.PAYLOAD - Product.totalWeight(roadmap['loads']), roadmap['warehouse'].plannedItems)
        if not pack:
            continue

        # Calcultes the efficiency of adding a stop
        routeTime = distance(roadmap['pos'], client.pos) + len(list(set(pack)))
        routeEfficiency = efficiency(pack, routeTime)
        if roadmap['stops']:
            # Calculates the efficiency of coming back to warehouse and to the client again 
            backPack = client.pack(rests=roadmap['warehouse'].items)
            backTime = len(list(set(backPack))) + distance(roadmap['pos'], roadmap['warehouse'].pos) + distance(roadmap['warehouse'].pos, client.pos)
            backEfficiency = efficiency(backPack, backTime)
            if backEfficiency > routeEfficiency:
                continue
        options.append({
            'client': client,
            'efficiency': routeEfficiency,
            'routeTime': routeTime,
            'pack': pack
        })
        if not roadmap['stops']: # If it is the first stop, don't provide any alternative
            break

    if options:
        # Choose the best option (i.e. the max efficiency)
        #option = sorted(options, key=lambda c: c['efficiency'])[-1]
        option = options[0]
        # Plan the delivery
        roadmap['warehouse'].plan(option['pack'])
        option['client'].plan(option['pack'])
        roadmap['deliverTime'] += option['routeTime']
        roadmap['pos'] = option['client'].pos
        roadmap['loads'] += option['pack']
        roadmap['clients'].append(option['client'])
        roadmap['stops'].append((option['client'], option['pack']))
        return route(roadmap)
    else:
        return roadmap
    

def think():
    # For each drone that has nothing to do
    for drone in [d for d in Drone.ALL if d.available() and not d.tasks]:
        # Find the nearest warehouse 
        warehouse = Warehouse.near(drone.pos)[0]
        roadmap = route({
            'pos': warehouse.pos,
            'warehouse': warehouse,
            'deliverTime': 0,
            'loads': [],
            'clients': [],
            'stops': []
        })

        if not roadmap['stops']:
            global done
            done = True
            #if len(Client.UNSATISFIED) == 0:
            #        done = False
            if done:
                break

        loadOcc = dict((i, roadmap['loads'].count(i)) for i in roadmap['loads'])
        for i in loadOcc:
            drone.addTask('load', warehouse, Product.get(i), loadOcc[i])

        for client, items in roadmap['stops']:
            itemsOcc = dict((j, items.count(j)) for j in items)
            action = 'deliver' if type(client).__name__ is 'Client' else 'unload'
            for i in itemsOcc:
                drone.addTask(action, client, Product.get(i), itemsOcc[i])



if DEBUG:
    SIMULATION = 3000
else:
    SIMULATION = 8*T/10

try:
    if not DEBUG:
        bar = progressbar.ProgressBar(max_value=SIMULATION)
    while turn < SIMULATION and not done:
        think()
        newTurn()
        if not DEBUG:
            bar.update(turn)
    while turn < SIMULATION and [d for d in Drone.ALL if d.tasks]:
        newTurn()
        #if not DEBUG:
        #    bar.update(turn)
    if not DEBUG:
        bar.finish()


except KeyboardInterrupt:
    pass

with open(sys.argv[1] + 'o', 'w') as f:
    f.write(str(len(outLines)) + '\n' + '\n'.join(outLines) + '\n')
print("Turn:", turn)
print("Score:", score)