Let’s say you are living in a controlled economy where there is a baker in town, and every day he bakes a random number of loaves of bread (sometimes the oven breaks, or he has less ingredients). The people in the town queue up to buy a loaf of bread (you can only buy one loaf) based on a pre-assigned ticketing system. Your position in the queue is constant every single day.
There are more people in the queue than loaves of bread available. The bread is ready at different times each day, and some people in the queue need to be at work. If the bread isn’t ready before they have to leave for work, they leave the queue and the next person in line takes their place. But they still have their original queue ticket. The values in the people list are the number of hours before the person in the queue has to leave for work
I want to know what is the number on the last ticket given to the baker each day before he runs out of loaves of bread.
I can get my existing code to work for relatively small numbers of people, but if there are millions of people, lots of days (planned economies plan for 5 years ahead), you get the picture.
def BakerQueue(loaves, people, bake_time): got_some_bread = () for b in bake_time: counter = 0 for p in range(len(people)): if people(p) >= b: counter += 1 if counter == loaves: got_some_bread.append(p + 1) counter = 0 break elif p == len(people) - 1: got_some_bread.append(0) break elif counter < loaves and p == len(people) - 1: got_some_bread.append(0) counter = 0 return got_some_bread
So I thought about implementing a priority queue using the heapq library, however, I need to maintain the original ticket order, so I thought to create a list of tuples with the values and the index and convert to a heap and pop the top person off of the heap if they have gone to work or if they have gotten a loaf of bread and there are still loaves available. This is the point where I begin to fail. I only care which ticket number got the last loaf of bread each day