google hashcode 2020 online qualification

hashcode 2020 online qualification.py

# incomplete code by @robertkingNZ of team @perplexico_

import sys
import collections

Library = collections.namedtuple('Library', ['id', 'signup', 'per_day', 'bookids'])

def get_problem_from_file(f):
    lines = (line for line in f.read().splitlines())
    rows = (list(map(int, line.split())) for line in lines)

    B, L, D = next(rows) # num_books, num_libs, num_days
    books = next(rows) # Score 0, Score 1, ..
    libs = []
    for libid in range(L):
        N, T, M = next(rows) # lib_num_books, signup_time_days, scans_per_day
        lib_books = tuple(next(rows))
        lib = Library(libid, T, M, lib_books)
        libs.append(lib)
    return ((B, L, D), books, libs)

def get_problem(input_filename = None):
    if input_filename:
        return get_problem_from_file(open(input_filename))
    else:
        return get_problem_from_file(sys.stdin)


def dfs(book_pointers, lib_pointers, book_id, libid, is_lib, path, vb, vl):
    if is_lib:
        for book_id in lib_pointers[libid][1]: #shadows book_id
            if book_id in vb:
                continue
            vb.add(book_id)
            found = dfs(book_pointers, lib_pointers, book_id, libid, False, path, vb, vl)
            if found:
                path.append(book_id)
                return True
        return False
    else:
        if book_pointers[book_id][0] is None: # this book is free
            return True
        for libid in book_pointers[book_id][1]: #shadows libid
            if libid in vl:
                continue
            vl.add(libid)
            found = dfs(book_pointers, lib_pointers, book_id, libid, True, path, vb, vl)
            if found:
                path.append(libid)
                return True
        return False


def try_match_lib_to_another_book(book_pointers, lib_pointers, libid):
    path = []
    vb, vl = set(), set([libid])
    is_lib = True # alternates
    found = dfs(book_pointers, lib_pointers, None, libid, is_lib, path, vb, vl)
    #print(found)
    #print(path)
    if found:
        lib_pointers[libid][0].add(path[-1]) #library gets the last book in the path
    for a, b in zip(path, path[1:]):
        # todo: do swap
        pass

def add_lib(libid, days_left, M, lib_books, book_pointers, lib_pointers):
    capacity = days_left * M
    if capacity > len(lib_books):
        capacity = len(lib_books)
    if capacity <= 0:
        return

    # add to graph
    for book_id in lib_books:
        book_pointers[book_id][1].append(libid)
        lib_pointers[libid][1].append(book_id)

    for i in range(capacity):
        try_match_lib_to_another_book(book_pointers, lib_pointers, libid)



def score(days_left, books, sorted_book_ids, libs):
    book_pointers = [[None, []]] * len(books) # which libid that book points to
    lib_pointers = [[set(), []]] * len(libs) # which bookid(s) that lib points to

    for libid, T, M, lib_books in libs:
        days_left -= T
        add_lib(libid, days_left, M, lib_books, book_pointers, lib_pointers)

    used_books = [book_id for lp in lib_pointers for book_id in lp[0]]
    #print(book_pointers)
    score = sum(books[i] for i in used_books)
    return score




def reorder_libs(libs):
    libs[:] = libs[:]

def solve(input_filename):
    ((B, L, D), books, libs_in) = get_problem(input_filename)

    #pre process
    sorted_book_ids = sorted(range(len(books)), key=books.__getitem__, reverse=True)
    libs = []
    for libid, T, M, lib_books in libs_in:
        lib_books =  sorted(lib_books, key=books.__getitem__, reverse=True)
        libs.append((libid, T, M, lib_books))

    best = 0
    iterations = 1
    for iteration in range(iterations):
        reorder_libs(libs) # todo implement
        new_score = score(D, books, sorted_book_ids, libs)
        best = max(new_score, best)

    return best


def run():
    file_names = [
        'a_example.txt',
        'e_so_many_books.txt',
        'd_tough_choices.txt',
        'c_incunabula.txt',
        'b_read_on.txt',
        'f_libraries_of_the_world.txt',
    ]
    import os
    # for fn in os.listdir('input'):
    #     print("\'{}\',".format(fn))
    file_names = [os.path.join('input', fn) for fn in file_names]
    for file_name in file_names:
        print('running ', file_name)
        best = solve(file_name)
        print('best {}'.format(best))

if __name__ == '__main__':
    run()