Marathon Match 22 - Marathon Match 22

Problem Statement

You have just been hired as your city's new traffic control engineer. A city is represented as a grid, where north-south streets run at x = 10, 20, 30, etc, and east-west 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 row-major 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 north-bound traffic at time 0 and 1, for east-bound at time 2, for west-bound at time 3, for south-bound 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 Generation

The 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 5-simplex 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 starting point on any road, but not in an intersection, is chosen. If another car is already at that starting location, another location is chosen.
• An initial direction towards either adjacent intersection is chosen. (If the starting location is near the edge of the board, there may be only one possible initial direction.)
• The behavior of the car at this intersection is determined based upon the predefined probability for this intersection. (Going off the edge of the city, or making a u-turn are not permitted.) This step repeats until the car finally reaches a destination.

A visualizer is available for this problem.

Definition

Notes

Examples