1. Technology

Programming Challenge 65 - Taxi Scheduler

Starts December 1st- Completed

By

City Map

Your job is to devise a taxi scheduling and routing system that can move your automated fleet of ten computer controlled cars as quickly and profitably as possible around the city of Plusville for one day.

Unlike American cities, most European and British cities and towns tend to be laid out in a less than perfect grid. So this makes route finding "interesting". Plusville is a sort of hybrid!

The city is a 15 x 15 square grid numbered sequentially from 1-225 to the top left square is 1, the top right is 15 and the bottom right is 225. Each grid location is either a building or a road. All road locations are connected- there is a route from any road square to any other. For simplicity passengers are picked up and dropped off at road squares.

Central Zone

The city central zone is a 7 x 7 square located exactly dead central, so it runs from squares 65 (top left) to 71 (top right) and all squares in this zone down to 155 (bottom left) and 161 (bottom right). It appears in light gray in the image above. Traffic is slower in the central zone. The rest of the city is called the outer zone.

Passengers

The passengers phone in and request a taxi to pick them up at a time t, at location f to go to destination d, and have a boolean wait flag w (value T or F) included to indicate if the passenger will wait up to 30 minutes. If the flag is false then the taxi must arrive before t + 10 minutes then the passenger will walk and the job is lost. True means they'll wait until t + 30 minutes then walk.

A file of passenger bookings is provided, one booking per line, all values are comma separated. As these are all pre-booked you are free to read the entire file and pre-scan it to help optimize the journeys.

Times run from 0 (6:00 am) to midnight (1080) in steps of single minutes.

The Challenge

Process the passengers bookings and dispatch your ten cars to pick them up to optimize the income. All times are in minutes for simplicity and your cabs travel at the following speeds.

If unloaded, cars take 1 minute per outer zone and 2 minutes per central zone square. If loaded they take 2 minutes per outer zone and three minutes per central zone location. So a car at square 50 (in the outer zone) could move to square 56 (entering 6 squares) in 6 minutes if unloaded, 12 minutes if loaded.

A loaded car at 53 could move 3 squares south to 113 and would take nine minutes to get there as it enters three central roads squares.

Cars can only move along roads (r or c squares in the city.txt map) and can change to any direction allowed by the roads. A car at 49 can go north (34), east (50), south (64) or west (48).

Note. cars can move along the same roads in the same direction. There are no restrictions on their movement along roads except the speeds.

Input Files

Both files city.txt and bookings.txt will be located in the same location as your exe.

The file city.txt is 15 lines of 15 characters each x,r or c. Buildings are x, roads are r (outer zone) or c (central zone).

Bookings.txt is made up of many lines each holding a number of comma separated values in this order, one line per booking:

t,f,d,w

Where t is time (int) - value 0- 1079- the time the pickup is booked for, f is location to pick the passenger up from (int)- value 1-225, t is the destination for that passenger, also an int 1-255. W is a char 'T' or 'F' where 'T' means they will wait until T+ 30, F means T + 10.

The f and d values will be road locations (so r or c is the appropriate map.txt location).

Example line from bookings.txt

45,17,146,T

So at time 6:45 the passenger is to be picked up at 17 and dropped off at 146. The passenger will wait until 7:15 (T + 30) then the job is lost.

Output File

Output three lines into a file output.txt in the same location as your exe for each passenger. The first starts off as a repeat of the input line ie t,f,d,w but also has p (time picked up), e exit time when the passenger is dropped off, n vehicle number 1-10 and i = income (see below).

Entering the pickup location is not counted towards the time of the journey. If the car enters the pickup location at time 46 and takes ten minutes to reach the dropoff then the dropoff time is 56.

The second line should be a comma separated list of the locations your vehicle took including both f and d.

The third line should be a comma separated list of the locations your taxi moved to (plus its start location) when empty to reach the pickup.

If the passenger walked because no cab appeared use -1, -1, -1,0 for p,e,n,i and a single -1 for the 3rd line if no taxi was sent! There is no penalty for not sending a car except the lack of income.

Income

For a single journey the tariff is 10 + number of squares entered. Note. your journey must never re-enter a location it's been in and if the number of locations traveled in this journey is double or more the minimum journey path, the firm gets fined $500 per incident. Anything less than double is ok. Still a ripoff but ok!

Example Output

In this case using the example of input shown earlier, the nearest taxi was on 16 so only moved from 16 to 17 to do the pickup.

45,17,146,T,45,83,1,29
17,18,19,34,49,50,51,52,53,54,55,56,57,72,87,102,117,132,147,146
16,17

The journey started at time 45 in location 17, traveled 19 squares all in the outer zone and took 19 x 2 minutes = 38 so dropoff time = 45 + 38 = 83. Income was 10 + 19 = 29.

Taxi Start Locations

Taxis start at 16, 53, 30,150, 210,173, 213, 138, 78 and 113. Note once a car has dropped off and is empty, you can leave it where it dropped off or move it somewhere else. Your choice!

Results

There were two entries. Thanks guys. This was an entirely USA contest between Brian Duckworth and Mark Mammel. There were actually three entries (two from Brian Duckworth). I have to verify the results, which will take a day or two.

Based on the output, Brian wins with a gross income of 7168 versus Mark's 7019. Mark's entry ran 10 x faster than Brian's but this wasn't a time entry.

  1. Brian Duckworth(C#) Result=7168, Time = 0.76311842 (USA,49)
  2. Brian Duckworth(C#) Result=7115, Time = 0.73259241 (USA,49)
  3. Mark Mammel(C++) Result=7019, Time = 0.070362 (USA,)

Winning Criteria

The winner is the highest earnings total for the day. Please add one last line to the output.txt, a total of the income.

General Tips on Entering

Read this single page article with tips on things to do and not do when entering challenges. Please read it!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

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@aboutguide.com?subject=Programming Contest 65 email address with the subject line Programming Contest 65.

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, GCC/G++ and any Google Go compiler. 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 December 30, 2012.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest 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.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 65 - Taxi Scheduler

©2014 About.com. All rights reserved.