8000 HashCode 2020 BookScanning · GitHub
[go: up one dir, main page]
Skip to content

Instantly share code, notes, and snippets.

@nvshah

nvshah/BookScan_HashCode_2020.py

Last active June 17, 2020 15:11
Show Gist options
  • Save nvshah/6e06a953fec572e05b64fe2b4b26dc21 to your computer and use it in GitHub Desktop.
Save nvshah/6e06a953fec572e05b64fe2b4b26dc21 to your computer and use it in GitHub Desktop.
Download ZIP
HashCode 2020 BookScanning
Raw
BookScan_HashCode_2020.py
8000
### Global Variables -----------------------------------------------------------------------------------------------
scanUpDays = {-1:0} # track of first scanning day for each library
signUpDays = {} # track of signup day for each library
processingLibrary = -1 # track of library that have initiated signup process but not yet complete. it's always going to be one at a time
activeLibraries = [] # track of libraries that have started scanning process
completeLibraries = [] # track of libraries that have completed scanning of all unscanned books
bookHub = [] # global repo of scanned books
previousDayBooks = [] # temporary to keep track of books scanned previous day, inorder to update waiting queue by removing all books that are scanned
reSchedule = 0 # Use when waiting queue need to be jumble due to removal of some scanned books inorder to avoid those scanned books again to repo
Libraries = [] # Element Format -> [ (N,T,M), [b1, b2, ... bN] ]
libraryScores = {} # keep track of libraryScores of all waiting libraries
day = 0
### Functions -------------------------------------------------------------------------------------------------------
def libraryScoreFinder(lib_id):
'''
calculate score of library
'''
library = Libraries[lib_id]
bookPeak = bookThresold(library) # upper bound of book index which library can send utmost
selectedBooks = library[1][:bookPeak] # books which library can send to library withing deadline
scores = sum(bookScores[book] for book in selectedBooks) # calculating max score of books that can be send by library, accounting present day
speedFactor = library[0][2]/library[0][1] # Speed factor is ratio of Rate : SignupDays
return (0.5*scores + 0.5*speedFactor)
def libraryScheduler():
'''
Send next library from waiting queue to processing phase inorder to sign up process and
Send previous library that has completed signup process to active phase
'''
global processingLibrary
# For last library in processing phase i.e signup phase
if not waitingLibraries and day == scanUpDays[processingLibrary]:
activeLibraries.append(processingLibrary) # last library signup phase completes and sending book starts from here and now
processingLibrary = -2 # No library left to be processed
elif waitingLibraries and day == scanUpDays[processingLibrary]: # if signup of processinglibrary completes then give chance to next library from waiting queue
if processingLibrary >= 0: # No library in processing phase so cannot send to next phase (i.e Active phase)
activeLibraries.append(processingLibrary) # library that has recently completed it's signing process, can starts sending books from now onwards
preSignupProcess() # lucrative fixings & necessary calculation of ScanUpDay
processingLibrary = waitingLibraries.pop(0) # allow next waiting library to initiate signup process here & now
postSignupProcess() 8000 # remove the book that recently signed up library is going to send at hub
# ASA next waiting library initiates sign up process, it's no more waiting in queue
def preSignupProcess():
'''
Pick better suitable library from top
'''
# As we are gonna pick a library from waitinng queue so update the queue to get most suitable library
libraryScoreUpdater() # Updates the scores of each waiting library
# If two or more library has same Top score than check which library has min book so that it can complete it turn first
currTop = getLibraryScore(waitingLibraries[0])
topLibraries = [waitingLibraries[0], *list(filter(lambda l: getLibraryScore(l) == currTop, waitingLibraries[1:]))]
topLibraries.sort(key=lambda l: len(Libraries[l][1]))
waitingLibraries[:len(topLibraries)] = topLibraries
# Reshuffling among top Scorer libraries over
# Calculate scan up days for library standing first in queue before it can start it signup process
library_id = waitingLibraries[0]
signUpDays[library_id] = scanUpDays[processingLibrary]
scanUpDays[library_id] = signUpDays[library_id] + Libraries[library_id][0][1]
# Calculation Completes
def postSignupProcess():
'''
Remove the books that current processing library ( i.e recently signed up library ) is going to scanned at bookhub
'''
#Anticipation of books & removal books that the front library is going to scanned at hub
bookPeak = bookThresold(Libraries[processingLibrary])
anticipatedBooks = Libraries[processingLibrary][1][:bookPeak]
# Inorder to reduce redundancy & improve score, remove the anticipated books from all waiting libraries
removeAnticipatedBooks(anticipatedBooks)
def removeAnticipatedBooks(books):
'''
Remove anticipated books from libraries waiting in queue
'''
for library_id in waitingLibraries.copy():
library = Libraries[library_id]
for book in books:
if book in library[1]:
library[1].remove(book) # preventing library from sending anticipated books
if not library[1]:
waitingLibraries.remove(library_id) # No unscanned book left in library
completeLibraries.append(library_id) # So Move to Complete library list
def refreshWaitingQueue():
'''
Update the order of libraries in waiting queue
'''
waitingLibraries.sort(key=getLibraryScore, reverse=True) # Making Queue of library according to their score in Decreasing order
def libraryScoreUpdater():
'''
Updates libraries Scores & refresh Waiting Queue
'''
global libraryScores
libraryScores = {lib_id:libraryScoreFinder(lib_id) for lib_id in waitingLibraries} # calculate score of each library inorder to decide their position in Queue
refreshWaitingQueue() # Prepare Queue of libraries as of lucrative scheduling
#fetch the score of library
getLibraryScore = lambda library_id: libraryScores[library_id]
#get the upperIndex limit upto which paticular library can send books
bookThresold = lambda library: (D - library[0][1] - day) * library[0][2]
### Main Code Here-------------------------------------------------------------------------------------------------------------------
#Fetch Input from Files
with open(r'D:\snv_127\Hackathon\Pizza-HashCode\TC2.txt', "r") as input_file:
# Books, Libraries, Days
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split())) # Scores of each book
if len(bookScores) == B:
for _id in range(L):
data = tuple(map(int, input_file.readline().strip().split()))
books = sorted(map(int, input_file.readline().strip().split()), key=lambda score: bookScores[score], reverse=True)
Libraries.append([data, books])
del data,books # freeing local assisting variables
waitingLibraries = list(range(L)) # Initially all library are waiting to enter in active region # List_member -> (libraryId)
librariesBooksScanned = {i:[] for i in range(L)} # keep track of books scanned by each library
# Entire approach is premised upon day-wise task responsibility
for day in range(D):
if processingLibrary != -2: # signup of all libraries is not completed
libraryScheduler() # schedule library which is waiting front in Queue to initiate scanning process, if posssible
for library_id in activeLibraries.copy(): # send unscanned books from active libraries
library = Libraries[library_id]
for i in range(library[0][2]): # Send book at rate i.e M books/day
if not library[1]: # if remaining books are less than rate (i,e M)
break
book = library[1].pop(0) # fetch the book which is yet left to be scanned
while book in bookHub:
if not library[1]: # All books are scanned
break
book = library[1].pop(0)
else:
bookHub.append(book) # keep track of books scanned
previousDayBooks.append(book)
librariesBooksScanned[library_id].append(book) # keep track of scanned books for individual library
if not library[1]: # At the end of the day, if library completed with all it's books
completeLibraries.append(library_id)
activeLibraries.remove(library_id)
if len(completeLibraries) == L: # All libraries ends up scanning their books
break
# Outputs----------------------------------------------------------------------------------------------------------------------------
totalScanUps = len(list(filter(lambda scanUpDay: scanUpDay<=D-1, list(scanUpDays.values())))) - 1
actualCompleteLibraries = list(filter(lambda l: bool(librariesBooksScanned[l]), completeLibraries))
print(totalScanUps)
for library_id in actualCompleteLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
for library_id in activeLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
Raw
BookScanning_FirstApproach.py
#B, L, D = map(int, input().split())
#Library- N, T, M N - no of books, T - time for signup process, M- per day book can be shipped after signup process completed
def libraryScoreFinder(library):
return (library[0][2] + library[2])/library[0][1]
def activeRunningLibrary(currentDay):
if currentDay == libraryScanningMaidenDay[0][1] :
activeLibraries.append(libraryScanningMaidenDay[0][0])
del(libraryScanningMaidenDay[0])
Libraries = []
#Fetch Input from Files
with open(r'E:\Nipun(127)\Hackathon\hashCode\TC1.txt', "r") as input_file:
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split()))
if len(bookScores) == B:
for i in range(L):
Libraries.append([tuple(map(int, input_file.readline().strip().split())), set(map(int, input_file.readline().strip().split()))])
# print(B, L, D)
# print('bookScores', bookScores)
# for i in Libraries:
# print(i)
#Restructuring Library File According to Our Demand
for library in Libraries:
library.append(sum({bookScores[index] for index in library[1]}))
library[1] = sorted(library[1], key=lambda score: bookScores[score], reverse=True)
Libraries.sort(key=libraryScoreFinder, reverse=True)
print(B, L, D)
print('bookScores', bookScores)
for i in Libraries:
print(i)
libraryScanningMaidenDay = [0] #This will keep track of signig up day of each library, until last day i.e D-1
for i,library in enumerate(Libraries):
if library[0][1] + libraryScanningMaidenDay[-1] > D-1 :
break
libraryScanningMaidenDay.append(library[0][1] + libraryScanningMaidenDay[-1])
del(libraryScanningMaidenDay[0])
# List -> (libraryId, MaidenDayOfScanning)
libraryScanningMaidenDay = list(enumerate(libraryScanningMaidenDay))
print(libraryScanningMaidenDay)
activeLibraries = []
completeLibraries = []
bookHub = []
librariesBooksScanned = {i:[] for i in range(L)}
for day in range(D):
# runningLib = filter(lambda libNo, signupDay : day>=libraryScanningMaidenDay[li], libraryScanningMaidenDay)
# Not All library have initiated scanning process
if len(activeLibraries) != L:
activeRunningLibrary(day)
for index in activeLibraries.copy():
# sending left out books to be scanned from library
library = Libraries[index]
# Send book according to rate given for library i.e M books/day
for i in range(library[0][2]):
# if remaining books are less than rate (i,e M)
if len(library[1]) == 0:
break
# fetch the book which is yet left to be scanned
book = library[1].pop(0)
while book in bookHub:
# All books are scanned
if len(library[1]) == 0:
break
book = library[1].pop(0)
#1 This case is particularly set for situation when All book are scanned except last book
#2 This is condition is kept for scenario : When all books of library are already scanned to hub so in that case no need to add anymore
if book not in bookHub:
bookHub.append(book) # keep track of books scanned
8000 librariesBooksScanned[index].append(book) # keep track of scanned books for individual library
# At the end of the day for given library, no books are left to be scanned then just change the status of library from active to completed
if len(library[1]) == 0:
completeLibraries.append(index)
activeLibraries.remove(index)
Raw
BookScanning_GA_IV2.py
import logging
### Global Variables -----------------------------------------------------------------------------------------------
'''
What Does Values means ????
processingLibrary - { -1 : Not a single library initiated signup process, -2 : No library left for signUp process, +ve : libraryCurrentlybeingSignuped}
'''
scanUpDays = {-1:0} # track of first scanning day for each library
signUpDays = {} # track of signup day for each library
processingLibrary = -1 # track of library that have initiated signup process but not yet complete. it's always going to be one at a time
activeLibraries = [] # track of libraries that have started scanning process
completeLibraries = [] # track of libraries that have completed scanning of all unscanned books
bookHub = [] # global repo of scanned books
previousDayBooks = [] # temporary to keep track of books scanned previous day, inorder to update waiting queue by removing all books that are scanned
reSchedule = 0 # Use when waiting queue need to be jumble due to removal of some scanned books inorder to avoid those scanned books again to repo
Libraries = [] # Element Format -> [ (N,T,M), [b1, b2, ... bN] ]
libraryScores = {} # keep track of libraryScores of all waiting libraries
day = 0
### Functions -------------------------------------------------------------------------------------------------------
def libraryScoreFinder(lib_id):
'''
calculate score of library
depends on - Signup days, Rate of book/day, Book Scores
:param lib_id : id of library whose score need to be calculated
'''
library = Libraries[lib_id]
bookPeak = bookThresold(library) # upper bound of book index which library can send utmost
selectedBooks = library[1][:bookPeak] # books which library can send to library withing deadline
scores = sum(bookScores[book] for book in selectedBooks) # calculating max score of books that can be send by library, accounting present day
speedFactor = library[0][2]/library[0][1] # Speed factor is ratio of Rate : SignupDays
return (0.5*scores + 0.5*speedFactor)
def libraryScheduler():
'''
Send next library from waiting queue to processing phase inorder to sign up process and
Send previous library that has completed signup process to active phase
'''
global processingLibrary
# For last library in processing phase i.e signup phase
if not waitingLibraries and day == scanUpDays[processingLibrary]:
activeLibraries.append(processingLibrary) # last library signup phase completes and sending book starts from here and now
logging.info(f'Library {processingLibrary} initiated scannUp process')
processingLibrary = -2 # No library left to be processed
elif waitingLibraries and day == scanUpDays[processingLibrary]: # if signup of processinglibrary completes then give chance to next library from waiting queue
if processingLibrary >= 0: # No library in processing phase so cannot send to next phase (i.e Active phase)
activeLibraries.append(processingLibrary) # library that has recently completed it's signing process, can starts sending books from now onwards
logging.info(f'Library {processingLibrary} initiated scannUp process')
preSignupProcess() # lucrative fixings & necessary calculation of ScanUpDay
processingLibrary = waitingLibraries.pop(0) # allow next waiting library to initiate signup process here & now
logging.info(f'Library {processingLibrary} initiated signup process')
postSignupProcess() # remove the book that recently signed up library is going to send at hub
# ASA next waiting library initiates sign up process, it's no more waiting in queue
def preSignupProcess():
'''
Pick better suitable library from top,
Calculates Signup Day & ScanUp Day for that picked top library
NOTE : both signup & scannUp values of any library depend on same parameters of library left to it (i.e just ahead to it by 1 position) in waiting queue
for library standing in front of waiting queue, it's left library will be the one standing in processing phase
'''
# As we are gonna pick a library from waitinng queue so update the queue to get most suitable library
libraryScoreUpdater() # Updates the scores of each waiting library
# If two or more library has same Top score than check which library has min book so that it can complete it turn first
currTop = getLibraryScore(waitingLibraries[0])
topLibraries = [waitingLibraries[0], *list(filter(lambda l: getLibraryScore(l) == currTop, waitingLibraries[1:]))]
topLibraries.sort(key=lambda l: len(Libraries[l][1]))
waitingLibraries[:len(topLibraries)] = topLibraries
# Reshuffling among top Scorer libraries over
# Calculate scan up days for library standing first in queue before it can start it signup process
library_id = waitingLibraries[0]
signUpDays[library_id] = scanUpDays[processingLibrary]
scanUpDays[library_id] = signUpDays[library_id] + Libraries[library_id][0][1]
# Calculation Completes
logging.info(f'Pre Sign Up Process completes - Scannup & Signup Day calculated for front library { waitingLibraries[0] }')
def postSignupProcess():
'''
Remove the books that current processing library ( i.e recently signed up library ) is going to scanned at bookhub
'''
#Anticipation of books & removal books that the front library is going to scanned at hub
bookPeak = bookThresold(Libraries[processingLibrary])
anticipatedBooks = Libraries[processingLibrary][1][:bookPeak]
# Inorder to reduce redundancy & improve score, remove the anticipated books from all waiting libraries
removeAnticipatedBooks(anticipatedBooks)
def removeAnticipatedBooks(books):
'''
Remove anticipated books from libraries waiting in queue | performance Improvisation
:param books: list of books that need to be removed from waiting libraries
'''
for library_id in waitingLibraries.copy():
library = Libraries[library_id]
for book in books:
if book in library[1]:
library[1].remove(book) # preventing library from sending anticipated books
if not library[1]:
waitingLibraries.remove(library_id) # No unscanned book left in library
completeLibraries.append(library_id) # So Move to Complete library list
def refreshWaitingQueue():
'''
Update the order of libraries in waiting queue
'''
waitingLibraries.sort(key=getLibraryScore, reverse=True) # Making Queue of library according to their score in Decreasing order
logging.info('Waiting Queue Updated')
def libraryScoreUpdater():
'''
Updates libraries Scores & refresh Waiting Queue
'''
global libraryScores
libraryScores = {lib_id:libraryScoreFinder(lib_id) for lib_id in waitingLibraries} # calculate score of each library inorder to decide their position in Queue
refreshWaitingQueue() # Prepare Queue of libraries as of lucrative scheduling
#fetch the score of library
getLibraryScore = lambda library_id: libraryScores[library_id]
#get the upperIndex limit upto which paticular library can send books
bookThresold = lambda library: (D - library[0][1] - day) * library[0][2]
### Main Code Here-------------------------------------------------------------------------------------------------------------------
showLogs = input('\nDo you wanna display logs (for tracking) ? { y/n } : ')
while showLogs not in ('y', 'Y', 'n', 'N'):
showLogs = input('invalid input ! try again : ')
if showLogs in ('y', 'Y'):
print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
logging.basicConfig(level=logging.DEBUG)
else:
logging.disable(logging.CRITICAL)
logging.info('Task Started')
#Fetch Input from Files
with open(r'D:\snv_127\Hackathon\Pizza-HashCode\TC3.txt', "r") as input_file:
logging.info('Reading inputs initiated.....')
# Books, Libraries, Days
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split())) # Scores of each book
if len(bookScores) == B:
for _id in range(L):
data = tuple(map(int, input_file.readline().strip().split()))
books = sorted(map(int, input_file.readline().strip().split()), key=lambda score: bookScores[score], reverse=True)
Libraries.append([data, books])
del data,books # freeing local assisting variables
logging.info('Reading inputs completed')
waitingLibraries = list(range(L)) # Initially all library are waiting to enter in active region # List_member -> (libraryId)
librariesBooksScanned = {i:[] for i in range(L)} # keep track of books scanned by each library
# Entire approach is premised upon day-wise task responsibility
for day in range(D):
logging.info(f'Day {day} - ')
dayContributor = set() # track of libraries that send atleast 1 book on particular day
if processingLibrary != -2: # signup of all libraries is not completed
libraryScheduler() # schedule library which is waiting front in Queue to initiate scanning process, if posssible
for library_id in activeLibraries.copy(): # send unscanned books from active libraries
library = Libraries[library_id]
for i in range(library[0][2]): # Send book at rate i.e M books/day
if not library[1]: # if remaining books are less than rate (i,e M)
break
book = library[1].pop(0) # fetch the book which is yet left to be scanned
while book in bookHub:
if not library[1]: # All books are scanned
break
book = library[1].pop(0)
else:
bookHub.append(book) # keep track of books scanned
previousDayBooks.append(book)
librariesBooksScanned[library_id].append(book) # keep track of scanned books for individual library
dayContributor.add(library_id)
if not library[1]: # At the end of the day, if library completed with all it's books
completeLibraries.append(library_id)
activeLibraries.remove(library_id)
if dayContributor:
logging.info(f"contributor : {dayContributor}")
if len(completeLibraries) == L: # All libraries ends up scanning their books
break
logging.info("Task Finished")
# Outputs----------------------------------------------------------------------------------------------------------------------------
print('\n----------------------------------------------- Output ----------------------------------------------------------------\n')
totalSignUps = len(list(filter(lambda signupDay: signupDay<=D-1, list(signUpDays.values()))))
actualCompleteLibraries = list(filter(lambda l: bool(librariesBooksScanned[l]), completeLibraries))
print(f'Total number of books available globally : {B}')
print(f'max score possible : {sum(bookScores)}')
print(f'\nBooks scanned in bookhub : {len(bookHub)} books :- {bookHub}')
print(f'Total library signed up : {totalSignUps}\n')
for library_id in actualCompleteLibraries:
print(f'library {library_id} :- {len(librariesBooksScanned[library_id])} books scanned')
print(f"Books - {' '.join(map(str,librariesBooksScanned[library_id]))}")
for library_id in activeLibraries:
print(f'library {library_id} :- {len(librariesBooksScanned[library_id])} books scanned')
print(f"Books - {' '.join(map(str,librariesBooksScanned[library_id]))}")
if processingLibrary>=0:
print(f'library {processingLibrary} could not complete it\'s signup process')
print('\nSCORE :-', sum(list(map(lambda book: bookScores[book], bookHub))))
Raw
BookScanning_GA_V1.py
8000
import logging
### Global Variables -----------------------------------------------------------------------------------------------
'''
What Does Values means ????
processingLibrary - { -1 : Not a single library initiated signup process, -2 : No library left for signUp process, +ve : libraryCurrentlybeingSignuped}
'''
scanUpDays = {} # track of first scanning day for each library
signUpDays = {} # track of signup day for each library
processingLibrary = -1 # track of library that have initiated signup process but not yet complete. it's always going to be one at a time
activeLibraries = [] # track of libraries that have started scanning process
completeLibraries = [] # track of libraries that have completed scanning of all unscanned books
bookHub = [] # global repo of scanned books
previousDayBooks = [] # temporary to keep track of books scanned previous day, inorder to update waiting queue by removing all books that are scanned
reSchedule = 0 # Use when waiting queue need to be jumble due to removal of some scanned books inorder to avoid those scanned books again to repo
Libraries = [] # Element Format -> [ (N,T,M), [b1, b2, ... bN], totalMaxPossibleScore, Id ]
### Functions -------------------------------------------------------------------------------------------------------
def libraryScoreFinder(lib_id):
'''
calculate score of library
'''
library = Libraries[lib_id]
return (library[0][2] + library[2])/library[0][1]
def libraryScheduler():
'''
Send next library from waiting queue to processing phase to sign up process and previous library that has completed signup process to active phase
'''
global processingLibrary
# For last library in processing phase i.e signup phase
if len(waitingLibraries) == 0 and day == signUpDays[processingLibrary]+Libraries[processingLibrary][0][1]:
activeLibraries.append(processingLibrary) # last library signup phase completes and sending book starts from here and now
logging.info(f'Library {processingLibrary} initiated scannUp process')
processingLibrary = -2 # No library left to be processed
if len(waitingLibraries) != 0 and day == signUpDays[waitingLibraries[0]]: # For very first library in waiting queue when the Task initiated
if processingLibrary != -1: # No library in processing phase so cannot send to next phase (i.e Active phase)
activeLibraries.append(processingLibrary) # library that has recently completed it's signing process, can starts sending books from now onwards
logging.info(f'Library {processingLibrary} initiated scannUp process')
processingLibrary = waitingLibraries[0] # allow next waiting library to initiate signup process here & now
logging.info(f'Library {processingLibrary} initiated signup process')
del(waitingLibraries[0]) # ASA next waiting library initiates sign up process, it's no more waiting in queue
def refreshWaitingQueue():
'''
Updates waiting queue, signupDays, scanUpDays of waiting library
NOTE : both signup & scannUp values of any library depend on same parameters of library left to it (i.e just ahead to it by 1 position) in waiting queue
for library standing in front of waiting queue, it's left library will be the one standing in processing phase
'''
waitingLibraries.sort(key=getLibraryScore, reverse=True) # Making Queue of library according to their score
scanUpDays[-1] = 0 if len(waitingLibraries) == L else scanUpDays[processingLibrary] # As we using previous library scann up days to calculate next library's one
for schedule_position,library_id in enumerate(waitingLibraries): # schedule_position is new position library get in waiting queue, shirking what it was at time of reporting library details
library = Libraries[library_id] # fetch library from library repo
signUpDays[library_id] = scanUpDays[-1] if schedule_position == 0 else scanUpDays[waitingLibraries[schedule_position-1]] # calculate day at which library will initiate it's signing process
scanUpDays[library_id] = library[0][1] + signUpDays[library_id] # calculate day from which library will start sending it's book
logging.info('Waiting Queue Updated')
def removeScannedBooks():
'''
Remove scanned books from libraries waiting in queue & Reschedule inorder to improve efficiency & score
'''
global reSchedule
if len(previousDayBooks) > 0: # if atleast one book get scanned yesterday
for library_id in waitingLibraries:
library = Libraries[library_id]
prevScore = library[2]
for book in previousDayBooks:
if book in library[1]:
library[1].remove(book) # preventing library from sending scanned books
library[2] -= bookScores[book] # Updating total book Score of library
if library[2] != prevScore: # As Score Of any library varies only when it books are removed or added, hence bookScores varies
reSchedule = 1 # Even if atleast 1 library score changes we need to reschedule all
if library[2]:
libraryScores[library_id] = libraryScoreFinder(library_id) # Update libraryScore as some books are removed from library
else:
waitingLibraries.remove(library_id) # No unscanned book left in library
previousDayBooks.clear()
if reSchedule == 1: # reschedule requires for improving efficiency
refreshWaitingQueue()
reSchedule = 0
getLibraryScore = lambda library_id: libraryScores[library_id]
### Main Code Here-------------------------------------------------------------------------------------------------------------------
showLogs = input('\nDo you wanna display logs (for tracking) ? { y/n } : ')
while showLogs not in ('y', 'Y', 'n', 'N'):
showLogs = input('invalid input ! try again : ')
if showLogs in ('y', 'Y'):
print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
logging.basicConfig(level=logging.DEBUG)
else:
logging.disable(logging.CRITICAL)
logging.info('Task Started')
#Fetch Input from Files
with open(r'E:\Nipun(127)\Hackathon\hashCode\TC1.txt', "r") as input_file:
logging.info('Reading inputs initiated.....')
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split()))
if len(bookScores) == B:
for _id in range(L):
data = tuple(map(int, input_file.readline().strip().split()))
books = sorted(map(int, input_file.readline().strip().split()), key=lambda score: bookScores[score], reverse=True)
scores = sum(bookScores[book] for book in books)
Libraries.append([data, books, scores])
del data,books,scores # freeing local assisting variables
logging.info('Reading inputs completed')
libraryScores = {lib_id:libraryScoreFinder(lib_id) for lib_id in range(L)} # calculate score of each library inorder to decide their position in Queue
waitingLibraries = list(range(L)) # Initially all library are waiting to enter in active region # List_member -> (libraryId)
librariesBooksScanned = {i:[] for i in range(L)} # keep track of books scanned by each library
# Prepare Queue of libraries as of lucrative scheduling
refreshWaitingQueue()
# Entire approach is premised upon day-wise task responsibility
for day in range(D):
logging.info(f'Day {day} - ')
dayContributor = set() # track of libraries that send atleast 1 book on particular day
if len(waitingLibraries) != 0: # All libraries have'nt initiated scanning process
removeScannedBooks() # Remove scanned books from all waiting libraries
if processingLibrary != -2: # signup of all libraries is not completed
libraryScheduler() # schedule library which is waiting front in Queue to initiate scanning process, if posssible
for library_id in activeLibraries.copy(): # send unscanned books from active libraries
library = Libraries[library_id]
for i in range(library[0][2]): # Send book at rate i.e M books/day
if len(library[1]) == 0: # if remaining books are less than rate (i,e M)
break
book = library[1].pop(0) # fetch the book which is yet left to be scanned
while book in bookHub:
if len(library[1]) == 0: # All books are scanned
break
book = library[1].pop(0)
else:
bookHub.append(book) # keep track of books scanned
previousDayBooks.append(book)
librariesBooksScanned[library_id].append(book) # keep track of scanned books for individual library
dayContributor.add(library_id)
if len(library[1]) == 0: # At the end of the day, if library completed with all it's books
completeLibraries.append(library_id)
activeLibraries.remove(library_id)
if len(dayContributor) > 0:
logging.info(f"contributor : {dayContributor}")
if len(completeLibraries) == L: # All libraries ends up scanning their books
break
logging.info("Task Finished")
# Outputs----------------------------------------------------------------------------------------------------------------------------
print('\n----------------------------------------------- Output ----------------------------------------------------------------\n')
totalSignUps = len(list(filter(lambda signupDay: signupDay<=D-1, list(signUpDays.values()))))
print(totalSignUps)
for library_id in completeLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
for library_id in activeLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
if processingLibrary>=0:
print(processingLibrary, len(librariesBooksScanned[processingLibrary]))
print(' '.join(map(str,librariesBooksScanned[processingLibrary])))
print('\nSCORE :-', sum(list(map(lambda book: bookScores[book], bookHub))))
Raw
BookScanning_GA_V2.py
import logging
### Global Variables -----------------------------------------------------------------------------------------------
'''
What Does Values means ????
processingLibrary - { -1 : Not a single library initiated signup process, -2 : No library left for signUp process, +ve : libraryCurrentlybeingSignuped}
'''
scanUpDays = {-1:0} # track of first scanning day for each library
signUpDays = {} # track of signup day for each library
processingLibrary = -1 # track of library that have initiated signup process but not yet complete. it's always going to be one at a time
activeLibraries = [] # track of libraries that have started scanning process
completeLibraries = [] # track of libraries that have completed scanning of all unscanned books
bookHub = [] # global repo of scanned books
previousDayBooks = [] # temporary to keep track of books scanned previous day, inorder to update waiting queue by removing all books that are scanned
reSchedule = 0 # Use when waiting queue need to be jumble due to removal of some scanned books inorder to avoid those scanned books again to repo
Libraries = [] # Element Format -> [ (N,T,M), [b1, b2, ... bN] ]
libraryScores = {} # keep track of libraryScores of all waiting libraries
day = 0
### Functions -------------------------------------------------------------------------------------------------------
def libraryScoreFinder(lib_id):
'''
calculate score of library
depends on - Signup days, Rate of book/day, Book Scores
:param lib_id : id of library whose score need to be calculated
'''
library = Libraries[lib_id]
bookPeak = bookThresold(library) # upper bound of book index which library can send utmost
selectedBooks = library[1][:bookPeak] # books which library can send to library withing deadline
scores = sum(bookScores[book] for book in selectedBooks) # calculating max score of books that can be send by library, accounting present day
speedFactor = library[0][2]/library[0][1] # Speed factor is ratio of Rate : SignupDays
return (0.5*scores + 0.5*speedFactor)
def libraryScheduler():
'''
Send next library from waiting queue to processing phase inorder to sign up process and
Send previous library that has completed signup process to active phase
'''
global processingLibrary
# For last library in processing phase i.e signup phase
if not waitingLibraries and day == scanUpDays[processingLibrary]:
activeLibraries.append(processingLibrary) # last library signup phase completes and sending book starts from here and now
logging.info(f'Library {processingLibrary} initiated scannUp process')
processingLibrary = -2 # No library left to be processed
elif waitingLibraries and day == scanUpDays[processingLibrary]: # if signup of processinglibrary completes then give chance to next library from waiting queue
if processingLibrary >= 0: # No library in processing phase so cannot send to next phase (i.e Active phase)
activeLibraries.append(processingLibrary) # library that has recently completed it's signing process, can starts sending books from now onwards
logging.info(f'Library {processingLibrary} initiated scannUp process')
preSignupProcess() # lucrative fixings & necessary calculation of ScanUpDay
processingLibrary = waitingLibraries.pop(0) # allow next waiting library to initiate signup process here & now
logging.info(f'Library {processingLibrary} initiated signup process')
postSignupProcess() # remove the book that recently signed up library is going to send at hub
# ASA next waiting library initiates sign up process, it's no more waiting in queue
def preSignupProcess():
'''
Pick better suitable library from top,
Calculates Signup Day & ScanUp Day for that picked top library
NOTE : both signup & scannUp values of any library depend on same parameters of library left to it (i.e just ahead to it by 1 position) in waiting queue
for library standing in front of waiting queue, it's left library will be the one standing in processing phase
'''
# If two or more library has same Top score than check which library has min book so that it can complete it turn first
currTop = getLibraryScore(waitingLibraries[0])
topLibraries = [waitingLibraries[0], *list(filter(lambda l: getLibraryScore(l) == currTop, waitingLibraries[1:]))]
topLibraries.sort(key=lambda l: len(Libraries[l][1]))
waitingLibraries[:len(topLibraries)] = topLibraries
# Reshuffling among top Scorer libraries over
# Calculate scan up days for library standing first in queue before it can start it signup process
library_id = waitingLibraries[0]
signUpDays[library_id] = scanUpDays[processingLibrary]
scanUpDays[library_id] = signUpDays[library_id] + Libraries[library_id][0][1]
# Calculation Completes
logging.info(f'Pre Sign Up Process completes - Scannup & Signup Day calculated for front library { waitingLibraries[0] }')
def postSignupProcess():
'''
Remove the books that current processing library ( i.e recently signed up library ) is going to scanned at bookhub
'''
#Anticipation of books & removal books that the front library is going to scanned at hub
bookPeak = bookThresold(Libraries[processingLibrary])
anticipatedBooks = Libraries[processingLibrary][1][:bookPeak]
removeAnticipatedBooks(anticipatedBooks) # Inorder to reduce redundancy & improve score
def removeAnticipatedBooks(books):
'''
Remove anticipated books from libraries waiting in queue | performance Improvisation
:param books: list of books that need to be removed from waiting libraries
'''
for library_id in waitingLibraries.copy():
library = Libraries[library_id]
for book in books:
if book in library[1]:
library[1].remove(book) # preventing library from sending anticipated books
if not library[1]:
waitingLibraries.remove(library_id) # No unscanned book left in library
completeLibraries.append(library_id) # So Move to Complete library list
def refreshWaitingQueue():
'''
Update the order of libraries in waiting queue
'''
waitingLibraries.sort(key=getLibraryScore, reverse=True) # Making Queue of library according to their score in Decreasing order
logging.info('Waiting Queue Updated')
def libraryScoreUpdater():
'''
Updates libraries Scores & refresh Waiting Queue
'''
global libraryScores
libraryScores = {lib_id:libraryScoreFinder(lib_id) for lib_id in waitingLibraries} # calculate score of each library inorder to decide their position in Queue
refreshWaitingQueue() # Prepare Queue of libraries as of lucrative scheduling
#fetch the score of library
getLibraryScore = lambda library_id: libraryScores[library_id]
#get the upperIndex limit upto which paticular library can send books
bookThresold = lambda library: (D - library[0][1] - day) * library[0][2]
### Main Code Here-------------------------------------------------------------------------------------------------------------------
showLogs = input('\nDo you wanna display logs (for tracking) ? { y/n } : ')
while showLogs not in ('y', 'Y', 'n', 'N'):
showLogs = input('invalid input ! try again : ')
if showLogs in ('y', 'Y'):
print('\n------------------------------------------------ Logs -----------------------------------------------------------------')
logging.basicConfig(level=logging.DEBUG)
else:
logging.disable(logging.CRITICAL)
logging.info('Task Started')
#Fetch Input from Files
with open(r'D:\snv_127\Hackathon\Pizza-HashCode\TC3.txt', "r") as input_file:
logging.info('Reading inputs initiated.....')
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split()))
if len(bookScores) == B:
for _id in range(L):
data = tuple(map(int, input_file.readline().strip().split()))
books = sorted(map(int, input_file.readline().strip().split()), key=lambda score: bookScores[score], reverse=True)
Libraries.append([data, books])
del data,books # freeing local assisting variables
logging.info('Reading inputs completed')
waitingLibraries = list(range(L)) # Initially all library are waiting to enter in active region # List_member -> (libraryId)
librariesBooksScanned = {i:[] for i in range(L)} # keep track of books scanned by each library
# Entire approach is premised upon day-wise task responsibility
for day in range(D):
logging.info(f'Day {day} - ')
dayContributor = set() # track of libraries that send atleast 1 book on particular day
if waitingLibraries: # All libraries have'nt initiated signed up process
libraryScoreUpdater() # Updates the scores of each waiting library
if processingLibrary != -2: # signup of all libraries is not completed
libraryScheduler() # schedule library which is waiting front in Queue to initiate scanning process, if posssible
for library_id in activeLibraries.copy(): # send unscanned books from active libraries
library = Libraries[library_id]
for i in range(library[0][2]): # Send book at rate i.e M books/day
if not library[1]: # if remaining books are less than rate (i,e M)
break
book = library[1].pop(0) # fetch the book which is yet left to be scanned
while book in bookHub:
if not library[1]: # All books are scanned
break
book = library[1].pop(0)
else:
bookHub.append(book) # keep track of books scanned
previousDayBooks.append(book)
librariesBooksScanned[library_id].append(book) # keep track of scanned books for individual library
dayContributor.add(library_id)
if not library[1]: # At the end of the day, if library completed with all it's books
completeLibraries.append(library_id)
activeLibraries.remove(library_id)
if dayContributor:
logging.info(f"contributor : {dayContributor}")
if len(completeLibraries) == L: # All libraries ends up scanning their books
break
logging.info("Task Finished")
# Outputs----------------------------------------------------------------------------------------------------------------------------
print('\n----------------------------------------------- Output ----------------------------------------------------------------\n')
totalSignUps = len(list(filter(lambda signupDay: signupDay<=D-1, list(signUpDays.values()))))
actualCompleteLibraries = list(filter(lambda l: bool(librariesBooksScanned[l]), completeLibraries))
print(f'Total number of books available globally : {B}')
print(f'max score possible : {sum(bookScores)}')
print(f'\nBooks scanned in bookhub : {len(bookHub)} books :- {bookHub}')
print(f'Total library signed up : {totalSignUps}\n')
for library_id in actualCompleteLibraries:
print(f'library {library_id} :- {len(librariesBooksScanned[library_id])} books scanned')
print(f"Books - {' '.join(map(str,librariesBooksScanned[library_id]))}")
for library_id in activeLibraries:
print(f'library {library_id} :- {len(librariesBooksScanned[library_id])} books scanned')
print(f"Books - {' '.join(map(str,librariesBooksScanned[library_id]))}")
if processingLibrary>=0:
print(f'library {processingLibrary} :- {len(librariesBooksScanned[processingLibrary])} books scanned')
print(f"Books - {' '.join(map(str,librariesBooksScanned[processingLibrary]))}")
print('\nSCORE :-', sum(list(map(lambda book: bookScores[book], bookHub))))
Raw
BookScanning_HashCode2020.py
### Global Variables -----------------------------------------------------------------------------------------------
scanUpDays = {} # track of first scanning day for each library
signUpDays = {} # track of signup day for each library
processingLibrary = -1 # track of library that have initiated signup process but not yet complete. it's always going to be one at a time
activeLibraries = [] # track of libraries that have started scanning process
completeLibraries = [] # track of libraries that have completed scanning of all unscanned books
bookHub = [] # global repo of scanned books
previousDayBooks = [] # temporary to keep track of books scanned previous day, inorder to update waiting queue by removing all books that are scanned
reSchedule = 0 # Use when waiting queue need to be jumble due to removal of some scanned books inorder to avoid those scanned books again to repo
Libraries = [] # Element Format -> [ (N,T,M), [b1, b2, ... bN], totalMaxPossibleScore, Id ]
### Functions -------------------------------------------------------------------------------------------------------
def libraryScoreFinder(lib_id):
library = Libraries[lib_id]
return (library[0][2] + library[2])/library[0][1]
def libraryScheduler():
global processingLibrary
if len(waitingLibraries) == 0 and day == signUpDays[processingLibrary]+Libraries[processingLibrary][0][1]: # For last library in processing phase i.e signup phase
activeLibraries.append(processingLibrary) # last library signup phase completes and sending book starts from here and now
processingLibrary = -2 # No library left to be processed
if len(waitingLibraries) != 0 and day == signUpDays[waitingLibraries[0]]: # For very first library in waiting queue when the Task initiated
if processingLibrary != -1: # No library in processing phase so cannot send to next phase (i.e Active phase)
activeLibraries.append(processingLibrary) # library that has recently completed it's signing process, can starts sending books from now onwards
processingLibrary = waitingLibraries[0] # allow next waiting library to initiate signup process here & now
del(waitingLibraries[0]) # ASA next waiting library initiates sign up process, it's no more waiting in queue
def refreshWaitingQueue():
waitingLibraries.sort(key=getLibraryScore, reverse=True) # Making Queue of library according to their score
scanUpDays[-1] = 0 if len(waitingLibraries) == L else scanUpDays[processingLibrary] # As we using previous library scann up days to calculate next library's one
for schedule_position,library_id in enumerate(waitingLibraries): # schedule_position is new position library get in waiting queue, shirking what it was at time of reporting library details
library = Libraries[library_id] # fetch library from library repo
signUpDays[library_id] = scanUpDays[-1] if schedule_position == 0 else scanUpDays[waitingLibraries[schedule_position-1]] # calculate day at which library will initiate it's signing process
scanUpDays[library_id] = library[0][1] + signUpDays[library_id] # calculate day from which library will start sending it's book
def removeScannedBooks():
global reSchedule
if len(previousDayBooks) > 0: # if atleast one book get scanned yesterday
for library_id in waitingLibraries:
library = Libraries[library_id]
prevScore = library[2]
for book in previousDayBooks:
if book in library[1]:
library[1].remove(book) # preventing library from sending scanned books
library[2] -= bookScores[book] # Updating total book Score of library
if library[2] != prevScore: # As Score Of any library varies only when it books are removed or added, hence bookScores varies
reSchedule = 1 # Even if atleast 1 library score changes we need to reschedule all
if library[2]:
libraryScores[library_id] = libraryScoreFinder(library_id) # Update libraryScore as some books are removed from library
else:
waitingLibraries.remove(library_id) # No unscanned book left in library
previousDayBooks.clear()
if reSchedule == 1: # reschedule requires for improving efficiency
refreshWaitingQueue()
reSchedule = 0
getLibraryScore = lambda library_id: libraryScores[library_id]
### Main Code Here-------------------------------------------------------------------------------------------------------------------
with open(r'E:\Nipun(127)\Hackathon\hashCode\TC1.txt', "r") as input_file: # Fetch Input from Files
B,L,D = map(int, input_file.readline().strip().split())
bookScores = list(map(int, input_file.readline().strip().split()))
if len(bookScores) == B:
for _id in range(L):
data = tuple(map(int, input_file.readline().strip().split()))
books = sorted(map(int, input_file.readline().strip().split()), key=lambda score: bookScores[score], reverse=True)
scores = sum(bookScores[book] for book in books)
Libraries.append([data, books, scores])
del data,books,scores # freeing local assisting variables
libraryScores = {lib_id:libraryScoreFinder(lib_id) for lib_id in range(L)} # calculate score of each library inorder to decide their position in Queue
waitingLibraries = list(range(L)) # Initially all library are waiting to enter in active region # List_member -> (libraryId)
librariesBooksScanned = {i:[] for i in range(L)} # keep track of books scanned by each library
refreshWaitingQueue() # Prepare Queue of libraries as of lucrative scheduling
for day in range(D): # Entire approach is premised upon day-wise task responsibility
if len(waitingLibraries) != 0: # All libraries have'nt initiated scanning process
removeScannedBooks() # Remove scanned books from all waiting libraries
if processingLibrary != -2: # signup of all libraries is not completed
libraryScheduler() # schedule library which is waiting front in Queue to initiate scanning process, if posssible
for library_id in activeLibraries.copy(): # send unscanned books from active libraries
library = Libraries[library_id]
for i in range(library[0][2]): # Send book at rate i.e M books/day
if len(library[1]) == 0: # if remaining books are less than rate (i,e M)
break
book = library[1].pop(0) # fetch the book which is yet left to be scanned
while book in bookHub:
if len(library[1]) == 0: # All books are scanned
break
book = library[1].pop(0)
else:
bookHub.append(book) # keep track of books scanned
previousDayBooks.append(book)
librariesBooksScanned[library_id].append(book) # keep track of scanned books for individual library
if len(library[1]) == 0: # At the end of the day, if library completed with all it's books
completeLibraries.append(library_id)
activeLibraries.remove(library_id)
if len(completeLibraries) == L: # All libraries ends up scanning their books
break
# Outputs----------------------------------------------------------------------------------------------------------------------------
totalSignUps = len(list(filter(lambda signupDay: signupDay<=D-1, list(signUpDays.values()))))
print(totalSignUps)
for library_id in completeLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
for library_id in activeLibraries:
print(library_id, len(librariesBooksScanned[library_id]))
print(' '.join(map(str,librariesBooksScanned[library_id])))
if processingLibrary>=0:
print(processingLibrary, len(librariesBooksScanned[processingLibrary]))
print(' '.join(map(str,librariesBooksScanned[processingLibrary])))
#print('\nSCORE :-', sum(list(map(lambda book: bookScores[book], bookHub))))
Raw
Test Cases
TC1 :
---
Input ->
6 2 7
1 2 3 6 5 4
5 2 2
0 1 2 3 4
4 3 1
3 2 5 0
Score -> 21
TC2 :
---
Input ->
8 4 8
1 5 9 2 3 8 6 2
4 2 3
0 3 4 5
2 2 1
5 6
3 1 1
0 1 6
5 3 2
0 3 4 5 7
Score -> 27
TC3 :
----
Input ->
10 4 5
1 5 9 2 3 8 6 2 7 1
4 2 3
0 1 6 7
5 2 1
1 3 6 7 9
3 1 1
2 4 7
4 3 2
1 4 6 8
Score -> 30
@nvshah
Copy link
Author
nvshah commented Feb 28, 2020

For Que click here

@nvshah
Copy link
Author
nvshah commented Mar 6, 2020

BookScanning_Approach1 is not completed and it's not appropriate one

@nvshah
Copy link
Author
nvshah commented Jun 17, 2020

BookScanning_HashCode2020 -> is also depricated(old) version

BookScan_HashCode_2020 -> is the new & latest version of code

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
0