Challenge Overview
Problem Statement  
You have just been hired as your city's new traffic control engineer. A city is represented as a grid, where northsouth streets run at x = 10, 20, 30, etc, and eastwest streets run at y = 10, 20, 30, etc. Points such as (30, 17) and (43, 20) are points along roads, while points such as (30, 40) and (20, 20) are at intersections. At every intersection there is a traffic light. (1, 1) is the northwest corner of the city, while (width, height) is the southeast corner. Based upon significant research done by your predecessor, you have detailed information about where many cars begin their commute, and the exact path they will take to get to their destination. Each traffic light is programmed so that a green light faces exactly one of the four cardinal directions at any given moment. Each traffic light will run its own timing sequence, and will loop through that sequence indefinitely. Each sequence can contain up to 20 directions. You are given the width and height of the city, and a String[] describing the commute path of each car that was studied. Each dimension of the city is congruent to 9 MOD 10. The number of intersections is (width / 10) * (height / 10), using integer division. Thus, a 59 x 49 city would have 5 * 4 = 20 intersections. The path of each car is given as the starting x,y location and a sequence of moves in one of the four cardinal directions, where each move means to move to the next intersection in that direction. After the final move, the car pulls into a parking garage at the final intersection, and is no longer on the road. For instance, if a path is described as "25,20 ENWS" (quotes for clarity), that means the car started at (25, 20), travelled east to (30, 20), turned left and travelled north to (30, 10), turned left again and travelled west to (20, 10), then turned left once more and travelled south to its final destination of (20, 20). During each unit of time, a car will attempt to move one unit in the direction it is currently travelling, provided that location is clear of any other car moving in the same direction. (Two cars travelling the same road in opposite directions, however, can occupy the same location.) When about to enter an intersection, a car will only do so if the entire intersection is clear (no cars moving in any direction), and there is a green light for that direction. The returned String[] should represent the traffic light timing string for each traffic light, starting with the one at (10, 10), and proceeding in rowmajor order. Each element should be formatted as a sequence of up to 20 'N', 'S', 'E', or 'W' characters, describing the sequence. For instance, the timing "NNEWS" would have a green light for northbound traffic at time 0 and 1, for eastbound at time 2, for westbound at time 3, for southbound at time 4, then repeating starting at time 5. Your score will be the number of units of time it takes for each car to reach its destination. You solution will be run for a maximum of 1,000 units of time, after which point you will be penalized an additional 50 units of time for each car not yet at its destination. Your total score for a full submission will be the sum of min_score / your_score for each test case, where min_score is the lowest score by any submission for that test case. Test Case GenerationThe width and height of the city will each be chosen as 49, 59, ..., 199 (uniformly at random). For each intersection, a set of proababilities will be chosen, defining the expected behavior of cars reaching that intersection. Five probabilities will be chosen: the probability of a car ending its trip at that intersection, or of continuing one block in any of the four directions. (All points in the 5simplex are equally likely.) The number of cars will be chosen between 200 and (height * width / 10), inclusive. The path of each car is then generated:
A visualizer is available for this problem.  
Definition  
 
Notes  
  The first few examples have fewer cars than normally allowed, to help facilitate testing.  
  There are 100 nonexample test cases.  
  Each test case is allowed 60 seconds to execute.  
  Memory limit is 1GB.  
Examples  
0)  
 
1)  
 
2)  
 
3)  
 
4)  
 
5)  
 
6)  
 
7)  
 
8)  
 
9)  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.