#!/usr/bin/env python3
import numpy as np

# Storage needed without normal storage and 1st level 20 great storage:
needed_storage = 600000
# Build slots dedicated to great storages beyond the 1st level 20 great storage:
n_storages     = 12

# initialize with worst case values
best_build_time = 1000000000
best_building_levels = [20] * n_storages

# Data for the great storage levels (w/o plus account)
# level, time*4 [minutes], storage capacity
build_times = np.array(
     [
     [0, 0, 0, 0],
     [1, 11, 3600, 11],
     [2, 16, 5100, 27],
     [3, 23, 6900, 50],
     [4, 34, 9300, 84],
     [5, 66, 12000, 150],
     [6, 140, 15000, 290],
     [7, 205, 18900, 495],
     [8, 275, 23100, 770],
     [9, 330, 28800, 1100],
     [10, 380, 36000, 1480],
     [11, 460, 43200, 1940],
     [12, 540, 54000, 2480],
     [13, 640, 66000, 3120],
     [14, 720, 78000, 3840],
     [15, 830, 96000, 4670],
     [16, 930, 114000, 5600],
     [17, 1110, 135000, 6710],
     [18, 1265, 165000, 7975],
     [19, 1460, 198000, 9435],
     [20, 1650, 240000, 11085]
     ]
     )

# capacity of the great storages with plus account (this is used)
plus_capacity = build_times[:,2] * 1.25
     
def get_cumulative_build_time(level=0):
    " Return the cumulative build time for a given level"
    return build_times[level,3]/4

def get_build_time(level=0):
    " Return the build time for a given level"
    return build_times[level,1]/4

def get_capacity(level=0):
    " Return the capacity for a certain level"
    return plus_capacity[level]

def add_storage(remaining_storages, building_levels, build_time, capacity):
    global best_build_time
    global best_building_levels
    global n_storages
    "Add the build time and capacity for an additional storage"
    if (capacity > needed_storage) and (build_time < best_build_time):
        best_build_time = build_time
        best_building_levels = building_levels
        print("Time: ", best_build_time, "; Storages: ", building_levels)
        # print("Storages: ", building_levels)
        return
    if remaining_storages == 0:
        return
    
    for level in range(0,21):
        if remaining_storages < n_storages:
            if building_levels[remaining_storages] < level:
                break
        building_levels[remaining_storages-1] = level
        add_storage(remaining_storages-1, building_levels, build_time+get_cumulative_build_time(level), capacity+get_capacity(level))

building_levels = [0] * n_storages
add_storage(n_storages, building_levels, 0, 0)