import math
import time
import numpy as np
from itertools import groupby
from itertools import combinations, chain

# span =10
# h = 100
# events = [[11, 50, 30],
#           [12],
#           [13, 40, 20],
#           [14, 45, 40],
#           [15],
#           [16],
#           [18, 45, 20],
#           [21],
#           [22]]

#test case-2
span= 10
h= 50
events= [[1,50,25],
 [3,100,50],
 [4,50,25],
 [5],
 [6,200,50],
 [7,100,25],
 [8,100,25],
 [9],
 [10,101,25],
 [11,101,25],
 [12],
 [101,10,10],
 [102,25,25],
 [103,25,25],
 [104,15,15],
 [105,25,25],
 [106],
 [201,20,10],
 [202,20,15],
 [203,40,25],
 [204,40,25],
 [205,40,25],
 [206],
 [301,1,15],
 [302],
 [303,1,15],
 [304],
 [305,1,15],
 [306],
 [307,1,15],
 [308],
 [309,1,15],
 [310],
 [311,1,15],
 [312],
 [313,1,15],
 [314]]

# #test case-3
# span = 5
# h = 100
# events = [[2],
#  [3,10,50],
#  [4,11,50],
#  [9],
#  [10]]

# #test case-4
# span= 100
# h= 100
# events= [[12,44,405],
#  [13,39,614],
#  [20,5,841],
#  [23,89,129],
#  [28,18,918],
#  [30,44,325],
#  [32,91,184],
#  [35,26,773],
#  [43,6,591],
#  [44,87,955],
#  [59,43,83],
#  [60,8,198],
#  [61,49,805],
#  [68,29,623],
#  [70,47,344],
#  [85,23,341],
#  [88,6,811],
#  [92,31,662],
#  [95,21,306],
#  [98,27,445],
#  [118,9,466],
#  [122,59,283],
#  [124,63,638],
#  [125,37,601],
#  [136,80,900],
#  [144,72,469],
#  [150,82,132],
#  [168,95,934],
#  [171,100,164],
#  [173,97,900],
#  [179,14,774],
#  [194,96,191],
#  [199,85,467],
#  [212,85,91],
#  [220,37,543],
#  [227,57,446],
#  [228,88,419],
#  [229,73,349],
#  [230,37,10],
#  [236,88,343],
#  [238,14,302],
#  [246,56,322],
#  [271,22,600],
#  [276,12,940],
#  [277,6,668],
#  [281,51,128],
#  [282,21,659],
#  [287,70,423],
#  [302,31,82],
#  [306],
#  [307,73,973],
#  [314,86,626],
#  [316,41,300],
#  [318],
#  [325,99,714],
#  [328,91,525],
#  [336,20,582],
#  [337,56,733],
#  [341,80,5],
#  [351,77,274],
#  [354,61,256],
#  [363,85,580],
#  [365,22,206],
#  [366,14,505],
#  [368,27,755],
#  [369,3,945],
#  [371,85,507],
#  [374],
#  [379,29,869],
#  [380,9,873],
#  [384,37,499],
#  [387,49,754],
#  [394,34,334],
#  [396,55,891],
#  [400,69,747],
#  [404,47,501],
#  [408,50,798],
#  [414,34,304],
#  [422,54,498],
#  [427,26,687],
#  [429,76,997],
#  [430,30,158],
#  [433,15,461],
#  [435,5,461],
#  [438],
#  [445,3,557],
#  [452,100,698],
#  [457],
#  [482,1,404],
#  [489,39,648],
#  [492,36,152],
#  [493,93,340],
#  [498,5,128],
#  [501,65,50],
#  [504,44,430],
#  [506,1,178]]

result = [[50, 1],
          [135, 1, 2, 3],
          [135, 1, 2, 3],
          [140, 1, 3, 4],
          [130, 2, 3, 4]]

create_keys = lambda l: ", ".join(str(x) for x in l)
reload_events = [(elem[0], i) for i, elem in enumerate(events) if len(elem) == 1]
stories = [elem for elem in events if len(elem) != 1]
stories_dict = {create_keys(elem): i+1 for i, elem in enumerate(stories)}

print(reload_events)
print(stories)
print(stories_dict)
possible_solutions = []
best_score = 0.0

def powerset(ll: list):
    return chain.from_iterable(combinations(ll, r) for r in range(len(ll)+1))

def subset_sum(story_sets, height_limit, partial=[]):
    global best_score
    print(best_score, "; partial:", partial)
    height = sum([item[2] for item in partial])

    if height <= height_limit:
        score = sum([item[1] for item in partial])
        if score >= best_score:
            possible_solutions.append([score] + sorted([stories_dict[create_keys(x)] for x in partial]))
            best_score = score
    elif height > height_limit:
        return

    if len(partial) == 0:
        story_sets = sorted(story_sets, key=lambda x: x[2], reverse=True)
    for i in range(len(story_sets)):
        n = story_sets[i]
        remaining = story_sets[i + 1:]
        subset_sum(remaining, height_limit, partial + [n])

def subset_stories(height_limit, partial: list, best_score: float):
    height = sum([item[2] for item in partial])
    score = sum([item[1] for item in partial])

    if len(partial) == 0:
        pass
    elif height <= height_limit:
        if score != 0 and score >= best_score:
            best_score = score
            possible_solutions.append([score] + sorted([stories_dict[create_keys(x)] for x in partial]))
    return best_score

    # for i in range(len(partial)):
    #     subset_stories(height_limit, [x for x in partial if x is not partial[i]])


def find_best_story_set(story_sets: list):
    story_sets = np.array(story_sets)
    print(story_sets)
    max_score = max([item[0] for item in story_sets])
    best_story_indices = np.array([i for i, item in enumerate(story_sets) if item[0] == max_score])
    if len(best_story_indices) == 1:
        return story_sets[best_story_indices[0]]
    else:
        lowest_number_stories = min([len(item[1:]) for item in story_sets[best_story_indices]])
        stories_with_lowest_number_indices = [i for i, item in enumerate(story_sets[best_story_indices]) if len(item[1:]) == lowest_number_stories]
        if len(stories_with_lowest_number_indices) == 1:
            return story_sets[best_story_indices[stories_with_lowest_number_indices[0]]]
        else:
            return sorted(story_sets[best_story_indices[stories_with_lowest_number_indices]])[0]


solution = []
for each_reload in reload_events:
    relevant_stories = [item for item in events[:each_reload[1]] if each_reload[0]-item[0] <= span and len(item) != 1]
    relevant_stories = [item for item in relevant_stories if item[2] <= h]
    print(each_reload[0], "; relevant stories", relevant_stories)
    best_score = 0
    possible_solutions = []
    if len(relevant_stories) > 0:
        # possible_combinations = [list(x) for x in powerset(relevant_stories)]
        # for story_set in possible_combinations:
        #     new_best_score = subset_stories(h, story_set, best_score)
        #     best_score = new_best_score
        # print(possible_solutions)
        # if len(possible_solutions) > 0:
        #     solution.append(find_best_story_set(possible_solutions))
        subset_sum(relevant_stories, h)
        if len(possible_solutions) > 0:
            solution.append(find_best_story_set(possible_solutions))
        else:
            solution.append([0])
    else:
        solution.append([0])

print(solution)

# temp = [[13, 40, 20], [14, 45, 40], [18, 45, 20]]
# print(sorted(temp, key=lambda x: x[2], reverse=True))
# possible_solutions = []
# print(possible_solutions)
# subset_sum(temp, 50, 0)
# print(possible_solutions)

#
# import numpy as np
# def feedOptimizer(span, h, events):
#     create_keys = lambda l: ", ".join(str(x) for x in l)
#     reload_events = [(elem[0], i) for i, elem in enumerate(events) if len(elem) == 1]
#     stories = [elem for elem in events if len(elem) != 1]
#     stories_dict = {create_keys(elem): i+1 for i, elem in enumerate(stories)}
#
#     print(reload_events)
#     print(stories)
#     print(stories_dict)
#     possible_solutions = []
#
#
#     def subset_stories(stories, height_limit, partial=[]):
#         height = sum([item[2] for item in partial])
#         score = sum([item[1] for item in partial])
#
#         if height <= height_limit:
#             if score != 0:
#                 possible_solutions.append([score] + sorted([stories_dict[create_keys(x)] for x in partial]))
#         if height > height_limit:
#             return
#
#         for i in range(len(stories)):
#             n = stories[i]
#             remaining = stories[i + 1:]
#             subset_stories(remaining, height_limit, partial + [n])
#
#
#
#     def find_best_story_set(story_sets: list):
#         story_sets = np.array(story_sets)
#         max_score = max([item[0] for item in story_sets])
#         best_story_indices = np.array([i for i, item in enumerate(story_sets) if item[0] == max_score])
#         if len(best_story_indices) == 1:
#             return story_sets[best_story_indices[0]]
#         else:
#             lowest_number_stories = min([len(item[1:]) for item in story_sets[best_story_indices]])
#             stories_with_lowest_number_indices = [i for i, item in enumerate(story_sets[best_story_indices]) if len(item[1:]) == lowest_number_stories]
#             if len(stories_with_lowest_number_indices) == 1:
#                 return story_sets[best_story_indices[stories_with_lowest_number_indices[0]]]
#             else:
#                 return sorted(story_sets[best_story_indices[stories_with_lowest_number_indices]])[0]
#         pass
#
#
#     best_score = 0
#     solution = []
#     for each_reload in reload_events:
#         relevant_stories = [item for item in events[:each_reload[1]] if each_reload[0]-item[0] <= span and len(item) != 1]
#         print(each_reload[0], "; relevant stories", relevant_stories)
#         best_score = 0
#         possible_solutions = []
#         subset_stories(relevant_stories, h)
#         print(possible_solutions)
#         if len(possible_solutions) > 0:
#             solution.append(find_best_story_set(possible_solutions))
#         else:
#             solution.append([0])
#
#     print(solution)
#     return solution
#
