Programming Challenge 28 - An Optimization Problem

Deadline: October 31 2009

Your trucking company has been contracted to move a large amount of diesel fuel across a 1,000 mile desert. Each truck can carry 1,000 gallons of fuel and uses 1 gallon of its carried fuel per mile traveled. Whatever is left in the tank gets drained and deposited in the depot. I.e. if it does 250 miles then 750 gallons are moved but 250 are needed for the return journey so effectively 500 are moved. Wherever a truck starts from it must have enough fuel to complete its journey to the next depot. Trucks travel at 50 MPH.

You can set up depots with refueling facilities anywhere along the route but each costs $15,000.

Write a program to move 250,000 gallons of fuel as cheaply as possible across the thousand miles. Each truck costs $15,000 to buy and can do any number of journeys but the driver can only drive in 12 hours out of every 24.

Each journey of a loaded truck costs $100 in salary. I.e. It costs $100 to move an empty truck irrespective of distance so long as it has enough fuel to travel the distance. Every extra day it takes incurs a penalty cost of $10,000. You are supplied with the initial 250,000 gallons of fuel but each extra gallon of fuel needed costs $1. (Cheap!)

Summary of costs

• Trucks Cost $15,000. You start with no trucks.
• Each truck costs $100 no matter how far.
• Each mile traveled costs $1 for extra fuel. see Note 1.
• Each depot costs $15,000.
• Each day after the 7th incurs a penalty of $10,000.

Note 1. The extra fuel purchased is only available at the Start depot; you can move any amount from there.

The winner is the cheapest total cost (Trucks + Journeys + Extra Fuel + Depots plus any penalties) to move all 250,000 gallons from the start to the finish. The start and end depots are named S and E all other depots are numbered 1,2 etc.

Your Entry

Write an application that calculates and outputs a file results.csv in the same location as the exe. This should be a comma separated file with double quotes around strings "like this".

Each line in the file should be a cost and start with the letter "C",plus a cost description, the cost and a cumulative cost total or a rocket fuel move which starts with the letter "M" followed by the start and end depot codes, the amount of fuel moved, plus the cost and cumulative cost.

After every 100 lines of output please dump the depot stats and truck locations. For each depot output
"D" , "Location" is the depot Id S,1,2... "E", Distance is the distance from the start depot, Fuel is the total stored at each depot.

For each Truck output "T" followed by Truck number which is 1,2.. etc and then "Location", i.e. which depot it is currently located at. The comments I've added (everything after the ; ) are optional, you can output for debugging purposes or not as you choose. Please output as the last line of the output a "R" and the final cumulative cost figure.

Eg an output file will look something like this but many more lines!

"C","Buy Truck",15000,15000 ; Bought Truck for $15K total cost
"C","Build Depot 1 at 275 miles",15000,30000 ; Built a depot at 275 miles
"M","S","1",375,30375 ; Moved fuel from the start to dept 1 cost $275+100
"M","1","S",0,375,30750 ; Moved empty truck back to start (cost = 100 + 275= 375)
...
; After every 100 lines dump the depot and truck data
"D","S",0,250000 ; Depot S (Start) at 0 miles has 249,000 gallons
"D","1",275,250000 ; Depot 1 at 275 miles has 450 gallons (= 1000- 550 for two truck journeys S to 1 and 1 to S)
"D","E",1000,0 ; Depot E at 1000 miles has no fuel yet.
"T",1,"S" ;Truck 1 is at the start depot
"T",2,"2" ; Truck 2 is at depot 2
...
"R",456,000 ; Result = Last cumulative cost

Notes.

1. You must setup your depots before buying trucks!
2. Show costs to 0 decimal places. Round up so 21.49 is 21 but 21.50 is 22.
3. Number trucks and depots in ascending order. The first truck is 1, 2nd is 2 etc.
4. A truck going to a higher number depot will always carry fuel if there is enough at the start depot.
5. Trucks travel at a speed of 50 MPH.
6. A truck moving to a lower number depot will always be empty apart from the fuel needed for the journey
7. Every journey of a truck removes the fuel for that journey (if moving towards the start depot) or 1000 if going toward the end depot. (Less if there's not 1,000) from the depot it starts at.

I will run your program then run another on the output file to validate your costs

If it helps, think of the depots like this

S---1---2---3---4---- ... --E

Your program must work out the optimal number (and spacing of depots) and the minimum number of trucks (and journeys) to move the fuel from S to E.

In the case of a tie the fastest running code will win, so please include the following

• How To Time C Code.
• How To Time C++ Code.
• How To Time C# Code.

The Results

Congrats to Pedro Graca of Portugal; the only entry this time. technically his output file didn't work but I could see the results so he is the winner.

1. Pedro Graca (Portugal) - C Time ~ 3 seconds

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 Challenge 28 email address with the subject line Programming Challenge 28.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 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 October 31 2009.

The top ten entries will be listed, judged purely on speed. 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.

Have fun!