Widgets are the cornerstone of modern industry and Rainbow Widgets Inc (founded 1878) was one of the first Widget manufacturers. Modernization has recently led to them installing the latest model EWMak (Electronic Widget Maker) machine from Yamhituki Heavy Industries.
EWMak can make every one of the seven colored Widgets that Rainbow Widgets makes in three sizes: small, standard and large. As production manager, it is your scheduling activities that will maintain Rainbow Widgets profitability and #1 position for quality and rapid dispatching of Widgets to the thousands of customers who rely on Rainbow Widgets.
Your task is to code an algorithm in C, C++ or C# that inputs a file of orders and turns it into a production schedule and delivery schedule optimized for profitability and reliability.
You are given an order file orders.csv with seven items on each row.
- Customer Number. An int, range 1-100,000. e.g. 456
- Order Number. Int range 1- 2,000,000,000, e.g. 456,789.
- Order Time Hours. int (hours from Sunday Midnight am to Friday Midnight). 0-120. Eg 56 (56 hours).
- Order Time Minutes. int 0-59. e.g. 32
- Order Quantity. int. Range 1-50. e.g. 45
- Widget Type. 2 Chars. First is one char of ROYGBIV, 2nd is one char of 123. E.g. Y2.
- Urgent or Non Urgent. 1 Char, Either U or N. EG N.
Widgets come in the seven colors of the rainbow (Red, Orange, Yellow, Green, Blue, Indigo and Violet) and in three sizes (small =1, standard = 2, large = 3). So in the example line customer 123 ordered with order #1432, at 9:00 hours ten x R1 (small red) widgets in a non-urgent order.
So long as EWMak is maintained (next para), it will make the highest quality Widgets at these rates: small is one widget takes a minute, standard is one widget takes two minutes and large takes three minutes for each one. But EWMak can only make one type of Widget at a time, one color in one size. To change Widget size takes ten minutes and costs $5. During this ten minutes EWMak is not making any widgets.
Likewise changing Widget color requires one hour of EWMak downtime and costs $20. So optimization means trying to keep EWMak making the same thing and as few changes as possible. After every 20 changes of any type, EWMak needs a further 30 minutes servicing and that costs $100.
The gross profit from every small widget is $5, every standard widget $7.50 and every large widget $10. If an order of 15 small widgets requires a size change first (-$5) then the order net profit is 15*5-5= $70. If it needed a color and size change then net profit would be (5*15)-5-20=$50. If it also needed a maintenance and the two other changes then it would be a loss -$50.
Urgent orders and Dispatch Costs
All orders must be dispatched within 24 hours. I.e. if an order arrives at 10:25 it must dispatch no later than 34:25. With EWMak, Rainbow can now offer fast Widgets for urgent orders, within 8 hours of the order time. This adds $50 to the order's profit. E.g. 10 Large widgets brings in $100 for normal dispatch, $150 for urgent. If an urgent order can't be dispatched within eight hours then you just get the normal profit.
Every order dispatched incurs a $25 cost per batch. If a customer has five separate orders and they can be dispatched together (all must be within their time frame, urgent and non urgent) then there is only one $25 cost not five * $25 = $125. There can be any number of orders dispatched in a batch.
The orders file (orders.csv) is in the same folder as your exe:
- Download orders.csv
Your program must read in orders.csv then generate the files schedule.csv and dispatch.csv. All files orders.csv, dispatch.csv and schedule.csv will be in the same location as your exe.
Each line contains a batch of orders to one customer.
- Time of dispatch Hours. int e.g. 45 is 45 hours since Sunday midnight.
- Dispatch Time Minutes. e.g. 30 minutes
- Customer number. Same as in orders.csv. e.g. 345.
- Order number (as in orders.csv)
- Net Profit for this order.
There should be a pair (Order, Profit) for every order in a batch to a customer. So if there are three orders numbers 10,25 and 50 to customer 345 at time 56:30 it might look like this:
Where 120 is the net profit for order 10, 250 for order 25 and 475 for order 50. Do not count the dispatch cost $25 in these net profits. Instead, the last line in the file should be the total of all profits minus $25 for each batch line before it. If there are 100 batch lines then deduct $2500.
Format of Schedule.csv
This file consists of multiple lines with three csv items. Each line has a time (hour,minute) and an order number or the words "Downtime Color Change", "Downtime Size Change", "Downtime Maintenance". After every 20 color or size changes there must be a maintenance change. The times should be consistent. In this case order 123 took 30 minutes.
- 9,30,"Downtime Size Change"
- 12,20,"Downtime Color Change"
The highest total profit wins.
RulesThis is for glory only. About.com does not permit prizes to be given.
Please submit your source code and the output file to the email@example.com?subject=Programming Contest 50 email address with the subject line Programming Contest 50.
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 September 30 2011.
The top ten entries will be listed, judged purely on points. 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