[Home]   [Projects]    [Delphi Techniques]   [Math Topics]   [Library]   [Utilities]

Problem Description

Another ACM Programming Contest problem.  Here it is just the way the contestants saw it:

Why did the chicken cross the road? Well, that is not our concern. We only seek
to make sure that it gets across safely.

The chicken will cross several roads (anything from Farm-to-Market roads to interstate
highways including access roads). For each road to cross, the chicken looks
to see how many lanes there are to cross and what traffic there is on each lane.
The chicken then starts waiting for traffic to clear so it can cross safely. In order to
maintain the timing between steps and his head-bobbing, the chicken will only start
walking on 1 second intervals. However, this chicken is particularly impatient and
will start walking whether it is safe or not after waiting only 60 seconds and it
may be time to break out the barbeque sauce.

When the chicken does cross the road, it will start walking on a path perpendicular
to the lanes (all lanes are parallel) at a constant rate of 10 feet/second and will not
stop until reaching the other side. All lanes are 15 feet wide and there is no room
between the lanes. Each vehicle description includes a width in feet of the vehicle
(0<W<=15 feet), the length of the vehicle (0<L<=40 feet), a constant speed of the
vehicle in feet/second (0<S<=100 feet/second), and the time (in seconds) which
the vehicle will cross the line which the chicken will attempt to walk along.
Second zero is the first opportunity for the chicken to start across the road. Vehicles
always drive down the exact center of the lane they occupy (no drunk drivers here!).

Information for each crossing will be formatted in the input file as follows.
The first line for each crossing will contain the number of lanes (1<=L<=20) to be crossed
(direction does not matter here). The second line contains the number of vehicles
(0<=N<=100) involved in the crossing. Each of the subsequent N lines contains the
description of the vehicles in no particular order. The first value of the line
is an integer which identifies the lane number (1 to L) the vehicle occupies
(lane 1 is closest to the chicken). The second through fifth values are floating
point numbers which identify the width, length and speed of the vehicle and the
time (in seconds) that the vehicle will cross the line the chicken will walk
along. You must read to the end-of-file.

You may assume that there are no lane changes; collisions between vehicles are
irrelevant; and sufficient safety margin has been included in the dimensions of the
vehicle to treat the chicken as a single point. It is time to get the barbeque
sauce if at any time any part of the vehicle and the single point of the chicken intersect.

For each road to cross, you must output the crossing number (start counting at
one) and an integer representing the earliest second (0 to 60) the chicken should start
to cross such that it can cross safely. If the chicken cannot cross safely, you
must print the message "Bar-B-Q time!" instead of the crossing start time. Your output
should be formatted similar to that in the examples below.

Sample Input:
2
8
2 5.0 6.3 12.0 47.7
1 14.5 39.6 66.0 29.3
2 14.8 40.0 9.0 4.8
1 11.1 40.0 100.0 24.3
1 9.0 14.2 83.6 2.1
1 9.0 15.0 88.0 1.1
2 12.6 29.9 80.67 19.25
1 3.0 6.0 40.0 10.6
6
1
4 15.0 40.0 0.1 4.4
6
1
2 15.0 40.0 0.1 4.4

Sample Output:
Crossing 1 should start at 8.
Crossing 2 Bar-B-Q time!
Crossing 3 should start at 0.

Background & Techniques

This problem is from the 1993 Southeastern Regional ACM Programming Contest.   I decided to solve this as a console application mainly because I had never written one before and secondarily because that's the way all ACM Programming Contest programs must be written.  The easiest way to create a console program is to click on the Delphi menu option File/New/Console Application.   Console apps have no form and no corresponding unit, only the .dpr member is generated.  Main program code lies between  Begin and End. statements.  Readln and Writeln functions can be used to read and write lines to the console.     A Readln function with no parameters is commonly used at the end of a program to force it to pause while the user reads the output screen until the user presses the Enter key.  

For this problem, the total number of lanes information seems redundant.   Here's how I approached the problem.    A TTruck class was created to contain lane number, length, width, speed and time of arrival (toa) fields for each truck.  An additional  time of departure (tod) field was calculated based on time of arrival plus time for the truck to pass, based on its length and speed.   tod=toa + length/speed;   

To find a valid start time we'll just try all possible start times from 0 through 60 seconds.  For each start time,  for each truck, we'll check whether the chicken and the truck try to occupy the same space at the same time.  If, for a particular start time, we check all trucks and find no conflicts, that time  is the solution.  If they do conflict, we'll try the next start time. If all times are tried without finding a clear path, display the "Bar-B-Q" message.   To check for conflicts, compute time of chicken arrival (toca) and time of chicken departure (tocd) for each truck.  Since the chicken travels at a constant speed, and the truck travels down the center of its lane, distance to the near  and far sides of the truck divided by the chickens speed will give us the desired times.  The equations are:  toca:=starttime + ((lane-1)+(lanewidth/2-truckwidth/2))/chickenspeed;      tocd:=toca+truckwidth / chickenspeed;   If the chicken leaves the truck spaces before the truck arrives (tocd<toa) or the chicken arrives at he truck space after the truck has departed (toca>tod), then he is safe.  If there's a conflict (i.e. both of the above test are false), we'll stop checking this time and try the next.  If we check all the trucks for a particular time without finding a conflict, that is the solution.      

Running/Exploring the Program 

• Browse source extract
• Download source

Suggestions for Further Explorations

A visual animated version that showed the trucks moving  and the chicken crossing would be cool and and not very difficult to do.    

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2008, Gary Darby    All rights reserved.