hashcode2018_saygen.py

#!/usr/bin/env python3
#-*- coding:utf8 -*-


import numpy as np
from itertools import count


class Position:
    def __init__(self, row, column):
        self.row = row
        self.column = column

    def distance(self, other):
        return abs(self.row - other.row) + abs(self.column - other.column)

class Ride:

    def __init__(self, position_start, position_end, time_start, time_end):
        self.position_start = position_start
        self.position_end = position_end
        self.time_start = time_start
        self.time_end = time_end



class Vehicule:

    def __init__(self, position, rides, max_time, bonus):
        self.position = position
        self.max_time = max_time
        self.score = 0
        self.time = 0
        self.rides = rides
        self.bonus = bonus

    def do_ride(self, ride):
        if self.time >= self.max_time:
            return

        # arrive at picking point
        time_to_pickup = self.position.distance(ride.position_start)
        self.time += time_to_pickup
        self.position = ride.position_start

        if self.time < ride.time_start:
            self.time = ride.time_start

        if self.time == ride.time_start:
            self.score += self.bonus

        # doing the ride
        distance = self.position.distance(ride.position_end)
        self.time += distance
        self.position = ride.position_end

        # check the score
        if self.time < ride.time_end:
            self.score += distance

    def do_rides(self):
        for ride in self.rides:
            self.do_ride(ride)


    def __repr__(self):
        score = 'score ' + str(self.score)
        rides = 'total rides: ' + str(len(self.rides))
        time = 'total time: ' + str(self.time)

        return '\n'.join([score, rides, time])

if __name__ == '__main__':


    def parse_input(fpath):
        with open(fpath, 'r') as f:
            lines = f.readlines()


            return dict(ride_array = np.asarray([map(int, o.split()) for o in lines[1:]]),
                 ttl_vehicules  = int(lines[0].split()[2]),
                 ttl_rides = int(lines[0].split()[3]),
                 bonus = int(lines[0].split()[4]),
                 steps = int(lines[0].split()[5]))




    arg = parse_input('e_high_bonus.in')

    import random

#     # parsing
#     ttl_rides = 3
#     ttl_vehicules = 2
#     bonus = 2
#     max_time = 10
#     ride_array = np.asarray([[0, 0, 1, 3, 2, 9],
#                              [1, 2, 1, 0, 0, 9],
#                              [2, 0, 2, 2, 0, 9]])
#



    bonus = arg['bonus']
    max_time = arg['steps']


    ttl_rides = arg['ttl_rides']
    ttl_vehicules = arg['ttl_vehicules']
    ride_array = arg['ride_array']





    def get_shuffle(ttl_vehicules, ttl_rides):
        l = [x for x in range(ttl_rides)] + (ttl_rides * ttl_vehicules - ttl_rides) * [-1]

        random.shuffle(l)
        a = np.asarray(l)
        a = a.reshape(ttl_vehicules, ttl_rides)
        return a


    def f_score(vehicule_array):
        rides = []
        for idx in vehicule_array:
            if idx == -1:
                continue
            r = Ride(position_start = Position(ride_array[idx][0], ride_array[idx][1]),
                     position_end = Position(ride_array[idx][2], ride_array[idx][3]),
                     time_start = ride_array[idx][4],
                     time_end = ride_array[idx][5])

            rides.append(r)
        vehicule = Vehicule(position=Position(0, 0), rides=rides, max_time=max_time, bonus=bonus)
        vehicule.do_rides()
        return vehicule.score

    global_score = 0
    candidate = None
    max_iter = 10
    for c in count():
        vehicule_ride_matrix = get_shuffle(ttl_vehicules, ttl_rides)
        score = 0
        if c > max_iter:
            break

        for vehicule_array in vehicule_ride_matrix:
            score += f_score(vehicule_array)
            if score >= global_score:
                global_score = score
                candidate = vehicule_ride_matrix


    def print_candidate(candidate):
        result = []
        for row in candidate:
            r = [o for o in row if o != -1]
            result.append(str(len(r)) + ' ' + ' '.join([str(o) for o in r]))

        return '\n'.join(result)


    print(print_candidate(candidate))
    print(global_score)