-
Notifications
You must be signed in to change notification settings - Fork 1
/
hashcode_2.py
178 lines (141 loc) · 6.56 KB
/
hashcode_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
# -*- coding: utf-8 -*-
import math
import os
from time import time
from collections import OrderedDict
from pprint import pprint
def sort_by_second_value(original_dict):
ordered_dict = OrderedDict()
tuples = [(key, value) for key, value in original_dict.items()]
sorted_tuples = sorted(tuples, key=lambda tuple: tuple[1])
for tuple in sorted_tuples:
ordered_dict[tuple[0]] = tuple[1]
return ordered_dict
class Library(object):
def __init__(self, library_id, signup_time, books, books_per_day, global_book_scores):
self.library_id = library_id
self.signup_time = signup_time
# Sort books by score. We want the highest-scoring books to be first
self.books = list(reversed(sorted(books, key=lambda book: global_book_scores[book])))
self.book_amount = len(self.books)
self.books_per_day = books_per_day
self.global_book_scores = global_book_scores
self.book_scores = {book_id: global_book_scores[book_id] for book_id in self.books}
self.library_total_score = sum(self.book_scores.values())
def __repr__(self):
return 'Library: {} \n ' \
'Signup Time: {} \n ' \
'Amount of books: {} \n ' \
'Books per day: {} \n ' \
'Books: {} \n ' \
'Total score of books in library: {} \n' \
'Time to completion: {}'.format(
self.library_id, self.signup_time, self.book_amount, self.books_per_day, ', '.join(map(str,self.books)),
self.library_total_score, self.time_to_completion()
)
def time_to_completion(self, start_time=0):
return start_time + self.signup_time + math.ceil(self.book_amount / self.books_per_day)
def score_for_x_days(self, x_days, books_done):
not_done_books = [book for book in self.books if book not in books_done]
return sum([self.book_scores[book_id] for book_id in not_done_books[0:x_days * self.books_per_day]])
def books_for_days_left(self, days_left, books_done):
not_done_books = [book for book in self.books if book not in books_done]
possible_books = self.books_per_day * days_left
return not_done_books[:possible_books]
def average_score_for_books(self, books_done):
not_done_books = [book for book in self.books if book not in books_done]
len_not_done = len(not_done_books) or 1
total_scores = sum([self.book_scores[book] for book in not_done_books])
return total_scores/len_not_done
def can_send_entire_time(self, days_left, books_done):
not_done_books = [book for book in self.books if book not in books_done]
possible_amount = days_left * self.books_per_day
if possible_amount > len(not_done_books):
return 1
else:
return 0
def get_input(filename):
with open(filename, 'r') as f:
lines = f.readlines()
total_counts = lines[0]
amount_of_books, amount_of_libraries, days_for_scanning = map(int, total_counts.split(' '))
book_scores_line = lines[1]
book_scores = {}
for index, value in enumerate(map(int, book_scores_line.split(' '))):
book_scores[index] = value
book_scores = sort_by_second_value(book_scores)
libraries = []
for i in range(amount_of_libraries):
lib_stats = lines[2 + 2 * i]
lib_books = lines[2 + 2 * i + 1]
books_in_library, signup_time, shippings_per_day = map(int, lib_stats.split(' '))
books = list(map(int, lib_books.split(' ')))
libraries.append(Library(i, signup_time, books, shippings_per_day, book_scores))
# print('Book scores: ')
# pprint(book_scores)
# print('\n\n')
return libraries, days_for_scanning
def solve(libraries, days_for_scanning, out_file_name):
# do something
days_left = days_for_scanning
active_libraries = []
books_done = set()
original_amount_of_libraries = len(libraries)
while True:
# Sort libraries by highest score for days_left - signup time
libraries = sorted(libraries,
key=lambda library: library.score_for_x_days(days_left - library.signup_time,
[]) * library.can_send_entire_time(
days_left-library.signup_time, books_done),
reverse=True)
# Take the top 10 libraries, sort by avg score
# Sort by avg book score
# top_libraries = sorted(libraries[0:10], key=lambda library: library.average_score_for_books(books_done),
# reverse=True)
chosen_library = libraries[0]
days_left -= chosen_library.signup_time
# Books that we can scan from this library given we have days_left left
books_for_chosen_library = chosen_library.books_for_days_left(days_left, books_done)
active_libraries.append((chosen_library.library_id, len(books_for_chosen_library), books_for_chosen_library))
for book in books_for_chosen_library:
books_done.add(book)
libraries = libraries[1:]
if days_left <= 0 or len(libraries) == 0:
break
with open(out_file_name, 'w+') as out_file:
total_libraries = [tup for tup in active_libraries if tup[1] > 0]
out_file.write('{}\n'.format(len(total_libraries)))
for tup in active_libraries:
if (tup[1] > 0):
out_file.write('{} {}\n'.format(tup[0], tup[1]))
out_str = ''
for book_id in tup[2]:
out_str += str(book_id) + ' '
out_file.write(out_str.rstrip(' ') + '\n')
def purge_libraries(libraries, total_days):
new_libaries = []
for library in libraries:
if library.signup_time > total_days / 7:
pass
# print('PURGE')
else:
new_libaries.append(library)
return new_libaries
def main():
input_files = [
# 'a_example.txt',
# 'b_read_on.txt',
# 'c_incunabula.txt',
'd_tough_choices.txt',
# 'e_so_many_books.txt',
# 'f_libraries_of_the_world.txt'
]
for input_file in input_files:
start_time = time()
file, ext = input_file.split('.')
libraries, days_for_scanning = get_input(input_file)
libraries = purge_libraries(libraries, days_for_scanning)
solve(libraries, days_for_scanning, file + '_out.' + ext)
print('Done with file ', input_file, ' in time ', (time()-start_time))
if __name__ == "__main__":
main()