hashcode2020

hashcode2020.py

from typing import List, Set, Dict, NamedTuple
import multiprocessing
import random


class Book(NamedTuple):
    id: int
    score: int


class LibPlan(NamedTuple):
    lib: 'Library'
    start_time: int
    books_planned: List[int]
    score: int


class Library:
    def __init__(self, id: int, books: List[Book], capacity: int, signup_time: int):
        self.id = id
        self.books = books
        self.capacity = capacity
        self.signup_time = signup_time

        self.books_set = set(map(lambda b: b.id, self.books))
        self.books_dict: Dict[int, Book] = {b.id: b for b in self.books}

    def score_for_book(self, id: int) -> int:
        return self.books_dict[id].score

    def __len__(self):
        return len(self.books)

    def plan(self,
             start_time: int,
             excluded_books: set,
             deadline: int,
             strategy: str = 'greedy') -> LibPlan:
        work_time = deadline - start_time - self.signup_time
        if work_time <= 0:
            return LibPlan(self, books_planned=[], score=0, start_time=start_time)

        books_available = list(self.books_set - excluded_books)

        if strategy == 'greedy':
            books_available = sorted(books_available, key=self.score_for_book, reverse=True)
        elif strategy == 'random':
            random.shuffle(books_available)

        books_available = books_available[:work_time*self.capacity]
        plan_score = sum(map(self.score_for_book, books_available))
        return LibPlan(self, books_planned=books_available, score=plan_score, start_time=start_time)


def generate(libraries: List[Library],
             deadline: int,
             lib_strategy: str = 'heuristic',
             book_strategy: str = 'greedy') -> List[LibPlan]:
    libs = libraries.copy()
    excluded = set()
    results = []
    t = 0

    if lib_strategy == 'random':
        random.shuffle(libs)
        for lib in libs:
            res = lib.plan(start_time=t, excluded_books=excluded, deadline=deadline, strategy=book_strategy)
            if res.books_planned:
                results.append(res)
                excluded = excluded.union(res.books_planned)
                t += lib.signup_time
    elif lib_strategy == 'greedy':
        libs = sorted(libs, key=lambda x: x.signup_time)

        for lib in libs:
            res = lib.plan(start_time=t, excluded_books=excluded, deadline=deadline, strategy=book_strategy)
            if res.books_planned:
                results.append(res)
                excluded = excluded.union(res.books_planned)
                t += lib.signup_time
    elif lib_strategy == 'heuristic':
        remaining_libs = libs
        for i in range(len(libs)):
            best_score = -1000
            best_lib = None
            best_lib_eval = None
            for lib in remaining_libs:
                lib_eval = lib.plan(t, excluded, deadline, strategy=book_strategy)
                if lib_eval.books_planned:
                    score = lib_eval.score / (lib.signup_time ** 0.9)
                    if score > best_score:
                        best_score = score
                        best_lib = lib
                        best_lib_eval = lib_eval

            if best_lib_eval:
                remaining_libs.remove(best_lib)
                excluded = excluded.union(best_lib_eval.books_planned)
                t += best_lib.signup_time
                results.append(best_lib_eval)
    return results


def find_best(n: int, libraries: List[Library], deadline: int) -> List[LibPlan]:
    best_score = 0
    lib_plans = None
    for i in range(n):
        lib_plans = generate(libraries, deadline)
        score = sum(map(lambda x: x.score, lib_plans))
        if score > best_score:
            lib_plans = lib_plans
            best_score = score
    return lib_plans


def find_best_multiproc(n: int, libraries: List[Library], deadline: int) -> List[LibPlan]:
    cpu_count = multiprocessing.cpu_count()
    pool = multiprocessing.Pool(cpu_count)
    handles = []
    for _ in range(cpu_count):
        handles.append(pool.apply_async(find_best, args=(n // cpu_count, libraries, deadline)))
    pool.close()
    pool.join()

    best_score = 0
    best_result = None
    for handle in handles:
        result = handle.get()
        score = sum(map(lambda x: x.score, result))
        if score > best_score:
            best_result = result
            best_score = score
    return best_result


def compute_score(lib_plans: List[LibPlan]):
    total_score = sum(map(lambda x: x.score, lib_plans))
    print(f'total_score: {total_score}')
    return total_score


def write_result(f_name, result: List[LibPlan]):
    with open(f_name, 'w') as f:
        f.write(f'{len(result)}\n')
        for r in result:
            f.write(f'{r.lib.id} {len(r.books_planned)}\n')
            planned = ' '.join(map(str, r.books_planned))
            f.write(f'{planned}\n')


def read_args(f):
    return list(map(int, f.readline().split(' ')))


def main(f_name):
    with open(f_name) as f:
        n_books, n_libs, deadline = read_args(f)
        books_list = list(map(lambda x: Book(id=x[0], score=x[1]), enumerate(read_args(f))))
        books_dict = {b.id: b for b in books_list}
        libraries = []
        for lib in range(n_libs):
            n_books_in_lib, signup_time, capacity = read_args(f)
            books = list(map(lambda x: books_dict[int(x)], f.readline().split(' ')))
            libraries.append(Library(id=lib, books=books, signup_time=signup_time, capacity=capacity))

        #result = find_best_multiproc(1, libraries, deadline)
        #result = find_best(100, libraries, deadline)
        result = find_best(1, libraries, deadline)
        compute_score(result)
        write_result(f_name + '.out', result)

        print(f'{f_name}')
        print(f'Possible top: {sum(map(lambda x: x.score, books_list))}')
        print('')

        """
        for i in range(100):
            explain(generate(libraries, deadline))
        """


if __name__ == '__main__':
    #main('a_example.txt')
    #main('b_read_on.txt')
    #main('c_incunabula.txt')
    #main('d_tough_choices.txt')
    main('e_so_many_books.txt')
    main('f_libraries_of_the_world.txt')