Hashcode Traffic promblem solution by nilesh raut solution 2021
The world’s first traffic light dates back t o 1868. It was installed in London t o control traffic for… horse-drawn vehicles! Today, traffic lights can b e found a t street intersections in almost every city in the world, making it safer f or vehicles t o g o through them.
google hashcode solution 2021
Traffic lights have a t l east two states, and use one color ( usually red) t o signal “stop”, and another (usually green) to signal that cars can proceed through. The very first
google hashcode solution 2021
traffic lights were manually controlled. Nowadays they are automatic, meaning that
they have to be carefully designed and timed in order to optimize the overall travel time for all the pafiicipants in traffic.
Task
Given the description of a city p lan a nd planned paths for a ll c ars i n t hat c ity, optimize the schedule of traffic lights to minimize the total amount of t ime spent in traffic, and help as many cars a s possible reach their destination b efore a given deadline.
Problem description
City plan
The city plan consists of one-way streets and intersections. Each street:
- is identified by a unique name,
- leads from one intersection to another,
- does not contain any intersections in between ( if two s treets need to cross outside an intersection, a bridge or tunnel is used),
- has a fixed amount o f time L it t akes a c ar to get from t he b eginning o f the street to the If i t takes L seconds to drive through a s treet and a car enters it at t ime T it will arrive at t he end o f the street precisely a t T +L, independently of how many cars are on the street.
-
Figure 1. A city plan with 4 intersections (0, 1, 2, and 3) and 7 streets (a, b,… ,
g-street). Intersections 0 and 2 are directly connected both ways through a-street and b-street. c-street uses a bridge over a-street and b-street and does not intersect with those two streets.
Note that while the streets are one-way, it is still possible to have two one-way streets connecting two i ntersections in o pposite directions ( see intersections 0 and 2 and a-street a nd b-street in Figure 1). However, there will never be two streets connecting two intersections in the same direction.
Each intersection:
- has a unique integer ID (for example 0, 1, 2 …),
- has at least one street that comes into it, and at least one s treet c oming o ut of
Traffic lights
There is a t raffic light a t the end of e very street ( just before t he intersection). Each traffic light has two states: a green light indicates that the cars from that street can cross the intersection and head towards any o ther street, while a red light indicates
that the cars f rom that street need to stop. At m
ost o ne traffic light w
ill b e g reen at
each intersection at any given time. While the light i s g reen for an incoming s treet, only cars from this street will be allowed to enter the intersection (and move to any outcoming street), all other cars have to wait.
Queuing up
When the light at the e nd of a street i s r ed, arriving cars queue up waiting for the
light to turn green. W hen t he light is g reen, one car can cross the intersection
every second. This means that if a g reen l ight for a given street l asts for Ti
seconds then only t he first Ti c ars f rom that s treet will c ontinue their travel (see
Figure 2). Others will need to wait for the following green light.
(a) (b) (c)
(d) (e) (f)
Figure 2. Consider an intersection with two incoming streets (a-street with 3 waiting cars and b-street with 2 waiting cars), and two outgoing streets (c-street and d-street). There are two traffic lights, one at the end of a-street with T 1 = 2s and one at the end of the
b-street with T 2 = 3 s. (a) Initially, the traffic light o f a -street is g reen, and the fi rst ( yellow) car stafis moving. (b) At T = 1s, t he n ext (green) car from a-street stafis moving. (c) At T = 2s, a-street has a red light, and t he last (red) car waiting there needs to stop. At the same
time, the traffic light of b-street turns green, and t he first (purple) car queued there stafis moving. (d), (e) At T = 3s and T = 4s, t he two (purple and blue) cars t hat were initially on
b-street have already passed the traffic light and continued their path. (f) At T = 5s, the light at a-street turns back to green and t he (red) car that was waiting there c an now move.
Schedule
For e ach intersection we can set a traffic light schedule. The traffic light schedule determines the order and duration of green light for the incoming streets of t he intersection and repeats itself until t he e nd of the simulation. The schedule is a list of pairs: incoming street and duration. Each street can appear at most once in
the schedule. The schedule can ignore some of the incoming streets – t hose will never get a green light.
The traffic light schedule is controlled by y our submissions. You don’t have to specify the schedule of all traffic lights. By default all lights o n all intersections are red ( yes, cars stuck there will have to wait until the end of simulation).
Example traffic light schedules
In the following example, an intersection has 3 streets leading to i t (a, b, a nd
c-street), and one leaving t he intersection (d-street). W example schedules for these traffic lights:
consider three different
google hashcode solution 2021
google hashcode solution 2021No traffic light schedule (default)
Figure 4 (a). I f no traffic light schedule is set for an
intersection, all of the traffic lights remain red
throughout the simulation. Any cars t hat are
scheduled to pass through a, b, or c-street will b e blocked and not reach their destination.
Schedule that covers only one street google hashcode solution 2021
Figure 4 (b). In this example the traffic light schedule covers only one incoming street (b-street). In this case b-street always has a green light. Αny cars coming f rom b-street will always go
through the intersection directly, while any cars
scheduled to pass through either a-street o r
c-street will be blocked and not reach their destination.
Figure 4 (c). In this example, the traffic l ight schedule covers all incoming streets (c-street, then a-street, then b-street). For each street we can define a different T i, meaning different duration during which that traffic light remains green.
Cars
Each car is d escribed by the path (a sequence of streets) it is going to drive through. The paths a re defined b y t he input datasets a nd can’t be altered. In the input datasets we guarantee that each car can go through a single intersection at most once.
Initially, all cars stafi a t the end o f the first street in their path, waiting for the green google hashcode solution 2021
light ( in case the traffic light is red), or ready to move ( if i t’s green). If two cars s tafi google hashcode solution 2021
at the end of the same street, the car l isted fi rst in the input file goes first. Each c ar then follows a given p ath, while obeying the traffic lights, and needs to reach t he end of the last street in that path. google hashcode solution 2021
Cars are queued up at t he end of each s treet. The first car in the q ueue c an cross the i ntersection immediately afler t he light turns green. There is no delay while a c ar passes through an intersection. Cars a fler that cross the intersection one afler another, o ne car every second.
When a car enters the l ast street of i ts path, it c ompletes its drive u ntil the end of the s treet and then is immediately removed f rom i t. This means that the c ar does not queue up at the end of the l ast s treet of its path a nd d oes n ot enter t he intersection at the end of it. google hashcode solution 2021
Figure 3. This figure shows the state of three cars at exactly T seconds, with the simulation stafiing at T = 0s and ending at T = 5s. The street has L = 3s, meaning that any car needs 3 seconds to go from its beginning to the end. The light turns green on the lefl intersection at T = 1s and turns red again 2 seconds later. The cars are queuing up at the end of the street, with yellow being the first one. At T = 1s, the fi rst (yellow) c ar immediately stafis moving
and reaches the end of the street 3 seconds later, at T = 4s. The s econd (red) car has to wait 1 second before it stafis moving and arrives at the end of the street 3 seconds later, at T = 5s. The t hird (purple) car did not have enough time to enter the street, as the light already turned red. Note that this figure only shows two streets for simplicity: when a traffic light is shown to be red, this means that another one in the same intersection has turned green.
Input data set
File format
Each input d ata set is provided in a plain text file. The file contains only ASCII characters with lines ending with a single ‘\n’ character (also called “UNIX-style” line endings). When multiple numbers are given in o ne line, they are separated b y a single space between each two numbers. google hashcode solution 2021
google hashcode solution 2021
- The first line contains five numbers:
- an integer D (1 ≤ D ≤ 1 04) – the duration of the simulation, in seconds,
- an i nteger I (2 ≤ I ≤ 105) – the n umber of intersections ( with IDs f rom 0 to I -1),
- an integer S (2 ≤ S ≤ 1 05) – the number of streets,
- an integer V (1 ≤ V ≤ 1 03) – the number of cars,
- an i nteger F (1 ≤ F ≤ 103) – the bonus p oints for each car that r eaches its destination before time D .
- The next S lines contain descriptions of Each line contains:
- two i ntegers B and E (0 ≤ B < I, 0 ≤ E < I) – the intersections a t t he s tafi and the end of the street, respectively,
- the street name (a string consisting of between 3 and 30 l owercase ASCII characters a -z and the character – ),
- an i nteger L (1 ≤ L ≤ D) – the time i t takes a car to get f rom t he beginning to the end of that google hashcode solution 2021
- The next V lines describe the paths of each Each line contains:
- an i nteger P (2 ≤ P ≤ 1 03) – the number of streets that the car wants to travel,
- followed by Pnames of t he streets: The car s tafis at t he end of the first street (i.e. it waits for the green light to move to the next street) and follows the path until t he end of the l ast The path o f a car is always valid, i.e. the streets will be connected by intersections. google hashcode solution 2021
Example
6 4 5 2 1000 The simulation lasts 6 seconds, there are 4 intersections, 5 streets, and 2 cars; and a car scores 1000 points for reaching the destination on time. 2 0 rue-de-londres 1 Street rue-de-londres starts at intersection 2, ends at 0, and it takes L=1 seconds to go from the beginning to the end. 0 1 rue-d-amsterdam 1 Street rue-d-amsterdam starts at intersection 0, ends at 1 and has L=1. 3 1 rue-d-athenes 1 Street rue-d-athenes starts at intersection 3, ends at 1 and has L=1. 2 3 rue-de-rome 2 Street rue-de-rome starts at intersection 2, ends at 3 and has L=2. 1 2 rue-de-moscou 3 Street rue-de-moscou starts at intersection 1, ends at 2, and has L=3. 4 rue-de-londres rue-d-amsterdam The first car starts at the end of rue-de-moscou rue-de-rome rue-de-londres and then follows the given path. 3 rue-d-athenes rue-de-moscou rue-de-londres The second car starts at the end of rue-d-athenes and then follows the given path.
Note that the input file does not contain any b lank lines. B lank l ines a nd line wrapping in the example above are added for clarity.
Figure 5. The streets and intersections, as given by the example input data set, as well as the two cars at their initial positions.
Submissions
Your submission describes the traffic l ight schedules you want to set for specific intersections.
File format
The first line must contain a single i nteger A ( 0 ≤ A ≤ I ), t he number o f i ntersections for which you specify the schedule.
Then, the s ubmission file must describe the intersection schedules, i n a ny order. Each schedule must be described by multiple lines:
- the first line containing a single integer i intersection,
(0 ≤ i < I ) – the ID of the
- the second line containing a single integer E i ( 0 < E i) – the number of incoming streets (of the intersection i ) covered by this schedule,
- Eilines d escribing the order a nd d uration of g reen lights. E ach of those lines must contain (separated by a single space):
- the street name,
- an integer T (1 ≤ T ≤ D ) – for how long each street will have a green
Each intersection can o nly be listed once in the submission file. And each street name can only be listed once per s chedule. I f the street n ame is n ot present in
intersection configuration it m eans its traffic light i s always red. If an i ntersection
configuration is not present in the submission file then all of i ts traffic lights a re always red.
Example
3 There are 3 intersections with traffic light schedules: 1 On intersection 1 the traffic lights are green for 2 2 different incoming streets, namely rue-d-athenes 2 rue-d-athenes for 2 seconds, then green for rue-d-amsterdam 1 rue-d-amsterdam for 1 second, then again rue-d-athenes. 0 On intersection 0 the traffic lights are green for 1 1 incoming street only, namely rue-de-londres 2 rue-de-londres for 2 seconds per cycle (it’s always green for rue-de-londres). 2 On intersection 2 the traffic lights are green for 1 1 incoming street only, namely rue-de-moscou 1 rue-de-moscou for 1 second per cycle (it’s always green for rue-de-moscou). Note t hat the input file does not c ontain any b lank l ines. Blank l ines and line wrapping in the e xample above are added for clarity. google hashcode solution 2021
Scoring
A s core i s awarded for each c ar that finishes i ts path before the end of the simulation. For a car t hat finishes its path at t ime T , the awarded score i s ( F ) points (fixed award for finishing t he path) a nd additionally ( D – T ): o ne point f or each second l efl when t he car finished the path. google hashcode solution 2021
google hashcode solution 2021
In o ther w ords: i f a car finishes a t time T i t s cores google hashcode solution 2021
- F + (D – T) p oints i f T ≤ D , google hashcode solution 2021
- or 0 points otherwise. google hashcode solution 2021
The score f or t he solution is the s um o f s cores for all cars. google hashcode solution 2021
Example
For instance, in the example above, the first car: google hashcode solution 2021
- T = 0s: c rosses immediately intersection 0, a s t he traffic light there is a lways green, google hashcode solution 2021
- T = 1s: one second l ater, it h as gone through r ue-d-amsterdam. H owever, google hashcode solution 2021
the t raffic light i s red (as for intersection 1, the s ubmission has set t he duration for r ue-d-athenes‘ s light to be green for 2 seconds), google hashcode solution 2021
- T = 2s: t he car now crosses the i ntersection a nd c ontinues to rue-de- moscou,
- T = 5s: the car has reached the end o f r ue-de-moscou, finds a g reen l ight a t intersection 2 , crosses it a nd continues to r ue-de-rome.
This first car would have r eached the end of r ue-de-rome at T = 7s, but this i s p ast the deadline of the run (defined i n the i nput data s et). Meaning that 0 points a re assigned to this car. google hashcode solution 2021
The second car: google hashcode solution 2021
- T = 0s: finds a green light at intersection 1 and continues to rue-de-moscou,
- T = 3s: reaches the end of rue-de-moscou, finds a green light at intersection 2 and no cars waiting, s o it immediately crosses t he intersection and heads towards r ue-de-londres, google hashcode solution 2021
- T = 4s: the car reaches the end of r ue-de-londres, which is its So the second car finishes before the d eadline, and gets a score o f 1 000 + (6 – 4 ) = 1002 points.
The final score for this submission is 1 002. google hashcode solution 2021
google hashcode solution 2021
Note that there are multiple data sets representing separate instances of the problem. The final s core for y our t eam will be the s um o f your best scores f or the individual data sets. google hashcode solution 2021
SOLUTION
0 Comments