[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionAnother 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 Background & TechniquesThis 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
Suggestions for Further ExplorationsA 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-2018, Gary Darby All rights reserved. |