Solution for the Practice Round of Google Hash Code 2020 - Score: 1,505,004,616

google_hash_code_pizza_2020.py

import sys
import time
from pathlib import Path
from functools import reduce


def get_previous_num(num, shift):
    last_part = num & (1 << shift) - 1
    first_part = num >> (shift * 2) << shift
    return last_part + first_part


def get_bit(num, position):
    return (num >> position) & 1


if __name__ == '__main__':
    start = time.time()

    INP_FILE = 'e_also_big.in'
    RES_FILE = 'e_res.txt'
    txt = Path(INP_FILE).read_text()
    lines = txt.split('\n')

    AIM = int(lines[0].split(' ')[0])
    PIZZ_TYPES = list(map(int, lines[1].split(' ')))
    MASK = (1 << AIM + 1) - 1

    print('Aim (pices):', AIM)
    print('Len of types', len(PIZZ_TYPES))
    print('Sum of types:', sum(PIZZ_TYPES))

    print('\nGetting shifts ...')
    final_num = reduce(lambda a, b: a | (a << b), PIZZ_TYPES, 1)
    print('Size of the final number in Mb:', sys.getsizeof(final_num) / 10 ** 6)

    print('\nGetting max sum ...')
    max_level = MASK + 1
    final_num_with_mask = final_num & MASK
    max_sum = final_num_with_mask.bit_length() - 1
    print('Max sum is:', max_sum)

    res = []
    curr_num = final_num
    curr_one_position = max_sum
    for i, pizz_type in reversed(list(enumerate(PIZZ_TYPES))):
        prev_num = get_previous_num(curr_num, pizz_type)
        if not get_bit(curr_num, curr_one_position):
            break
        if not get_bit(prev_num, curr_one_position):
            res.append(i)
            curr_one_position -= pizz_type
        if curr_one_position < 0:
            break
        curr_num = prev_num
    res.reverse()
    print('Result:', res)

    with open(RES_FILE, 'w') as resf:
        resf.writelines([str(len(res)) + '\n', ' '.join(str(el) for el in res)])

    print('\nFinished in:', time.time() - start)