A Busy supermarket has about 4,000 shoppers arrive during its 12 hour day, roughly one shopper hits the tills every 16 seconds. Shoppers buy between 2 and 20 items and each item takes 8 seconds to scan and pack at the till. The supermarket opens at 8:00 am and stays open for 12 hours until 8:00 pm.
You as store manager have 10 checkout staff available and 10 tills each with a packer. Staff get paid extra to work on checkout tills so keeping the number of tills open saves the store money.
It's your job as manager to decide every 10 minutes during the day how many tills to keep open. Too few and the customers won't tolerate long queues and will dump their shopping and walk away. Too many and the senior management will dump you and ask you to walk away as the staffing costs go through the roof.
Each customer reaches the tills at a certain time (in seconds from the start of the day), approximately one every 16 seconds. There is obviously a queue at each till and the shopper will go on the end of the queue with the fewest items left to process. If that queue is more than 8 minutes long (ie there are 60 items or more left to process in each of the available tills) then the customer will leave their shopping down and just exit the store. That's bad!
To keep it simple, the arrival times and number of items of every customer have been put into a csv file with one line per customer, so there are just under 4,000 lines in shoppers.txt each of the form:
seconds, number of items
Seconds is number of seconds since 8:00 a.m.
e.g.
30,2
35,4
42,3
...
- Download the shoppers.txt file.
Your Task
You must write a program that reads shoppers.txt then constructs an array with 72 values in it and output it to tills.txt, one value per line, where value is an int number saying how many tills are open for that particular ten minutes. That is 12 hours of 6 values per hour (every ten minutes). It must track a queue for each open till and every ten minutes (simulation minutes), calculate whether to open or close more tills. The minimum open is 1, the maximum 10.
Closing a Till
Once the program decides to close one or more tills, no more items can be added to those closing till queues but the existing items in those queues must still be processed. Your program is free to open or close any of the tills in any order.
Scoring Your Entry
Add up the total number of tills used, i.e. all 72 values. For every shopper who leaves add 1. That is your score. I'll be running a program I wrote to read shoppers.txt and tills.txt to calculate the score.
Winning Criteria
Lowest score wins.
The Results
Subject to verification (my program isn't quite ready), but based on the tills.txt output, it's congratulations to John Settlemyer whose C program got a total of 381, just pipping Tavis Bohne's 406. Thank you to all three entrants.
- John Settlemyer C, Score = 381 (USA,21)
- Tavis Bohne C++, Score = 406 (USA)
- Li-Der Chang C++, Score = 517
General Tips on Entering
This is a single page article with tips on things to do and not do when entering challenges. Please read it!
Rules
This is for glory only. About.com does not permit prizes to be given.Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Contest 55 email address with the subject line Programming Contest 55.
It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is February 29, 2012.
The top ten entries in each challenge will be listed, judged on lowest number of moves and in the case of a draw, the lowest time. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
- An index of Every Past Programming Contest on this site
