Back
Close

Pedestrian Traffic

Statement

 Goal

Pedestrians are walking on a path of length n that is separated into an upper and lower lane. The upper lane is for people moving to the right and the lower lane is for people moving to the left. However, due to people walking next to their friend or being distracted by their phone, not everyone is in their correct lane.

People are differentiated by the direction in which they are moving:

People moving toward the right: R
People moving toward the left: L
Open spaces on the path: o

              o o o o o --> Right exit
Left exit <-- o o o o o

Each second, everyone moves according to the following rules:

1. People will prioritize trying to move to their lane. If this is not possible or they are already in their correct lane, they will try to move forward
2. If two people both want to move forward to the same space, the one who is in their correct lane takes priority
3. If a lane switcher and forward mover want to move to the same space, the forward mover takes priority
4. People can exit from the edges of the path
5. People can move to unoccupied spaces
6. People can move to a space that was opened up due to someone else moving during the current second (for example, two people directly above and below each other can swap lanes)
7. An exception to rule 6 is that two people in the same lane cannot walk past (swap places with) each other

Your task is to determine whether the path becomes clogged so that not everyone can exit, and if everyone is able to exit, how many seconds it takes.

Example:

o o R L o
o L R o o

o o R R o
L o o L o

o o o R R
o o L o o

o o o o R
o L o o o

o o o o o
L o o o o

o o o o o
o o o o o

It takes 5 seconds for everyone to exit.
Input
Line 1: An integer n for the length of the path
Lines 2 & 3: String of length n consisting of R, L, and o
Output
The number of seconds it takes for everyone to exit the path.
If not everyone can exit, print "Congestion".
Constraints
0 < n < 1000
Example
Input
4
RoLo
oooo
Output
4

Tags
Loops

Difficulty
Hard

Test cases
Crossing Paths Test
Input
4 RoLo oooo
Output
4

Validator 1 Validator
Input
6 oooooo ooRoLo
Output
5

One Way Stampede Test
Input
10 RRRRRRRRRR RRRRRRRRRR
Output
11

Validator 2 Validator
Input
9 LLLLLLLLL LLLLLLLLL
Output
10

Simple Dependency Test
Input
3 oLo oRo
Output
3

Validator 3 Validator
Input
6 oLoooL oRoooo
Output
7

More Dependencies Test
Input
5 ooRLo oLRoo
Output
5

Validator 4 Validator
Input
5 RRRLo ooRoo
Output
6

Complex Dependencies Test
Input
5 RooLo oRoLL
Output
Congestion

Validator 5 Validator
Input
3 RLL RRL
Output
Congestion

Temporary Blockage Test
Input
7 oRRLLLo LLLLLLL
Output
11

Validator 6 Validator
Input
6 RLRLLL LLLLLL
Output
13

Ring Around the Rosie Test
Input
9 oRRRRRRLo oRLLLLLLo
Output
9

Validator 7 Validator
Input
8 oRLooLRo oRLooLRo
Output
8

Empty Path Test
Input
12 oooooooooooo oooooooooooo
Output
0

Validator 8 Validator
Input
15 ooooooooooooooo ooooooooooooooo
Output
0

Group Collision Test
Input
9 RRoooooLL RRoooooLL
Output
Congestion

Validator 9 Validator
Input
13 RRRoooooooLLL RRoooooooooLL
Output
Congestion

Long Path Test
Input
30 oooRRLoLRoooooLooRLoRLRooRoooo ooooLoooooLoRLLoLoooooRRoLRLoo
Output
29

Validator 10 Validator
Input
30 oLRRoLRRoRoLooRoooooLRLLoLoooR RooLoLoooRLRoLoRooRooooooRoRoo
Output
31

Longer Path Test
Input
100 oRRooooLoRRRoLLLLoooRoLRLRRoRooLoooooRLoooLoooLoRRoooRLoooooRRoLLoRRRLoRLRRLRRoRoooRLooooLoRooLooooR RoRoLoooRRoooooLooooooRoRRRLRooRLLRRLoLooRooooRRoLooRooooLoooRRRoooLLLRoooLoooRoLooooooooRoRoLLoLooR
Output
101

Validator 11 Validator
Input
100 oLooLRRoLoLooRRooRoLoooRoooooRLLoooRRooRLLooLoooLRLooLRLRLoooLooLoLLLoooooRoLoRRooRooooooooLLooooooo ooRLooooooLLoooRoooooLLLLoRooooooRoooLoooooRoLLRoLoooRRooLoLRoRoooLLoooRoRLLooLoooooRLRooooLooLLoLLo
Output
99

Longest Path Test
Input
999 ooooooooooooRooooLoooooooooooRoooooooLooLLoooRooooRooRoooooooooooLooooRoooooooRooooooooooooooLLoooooRooLLoRLooooRoooLooooLoooRoooooooRoooLooooooRooLoooLoooRoRoooRooLoRoooRRoooooooooooooRooLooLoooooRooRooooLoooLoooooooooooLLoRoLoRoRoooooRoooRoooLoooRoRLLoooooooooooooLRooooRooooooRLRooooRoooLooLoooooooooRooooLRoooLoLLoooRoooooLoRoooooooRoLoooooooooooooooooLooLooRooooooooLoooooRoooooLooooooRooLoooooRoooooooRoooRoLoooRoooooRooooooooooooooRRoooRooooooooooRoooRooLoooLooLooooooooooooLRoooooRoooooooooLRoooRooooRLoRoooLoooLoooooooooRoooooooRooooooooooLooRoLLoLoooLRooooRoooooooooooooooooRoooooRoRooooooooooooooRoooooooooooooooLooLooLooLoRRoLooooRoooooooRooooooRooRLoooRoooLooooooLRLRooLLRooooooooooooooLoooooLRoooooRooRooooooRooooooLooLoooRoRoRoooLooooLLoooLooooRRooooooooooooLoRooooRoRooooooooooRoooRLLLoooooRoooooooRoooooooooooRoooRoRoRoLooRoRoooooRoRoooooooLooLoooRoooRoRooooooooooooooRooRooRoooRRoooooRooooooooooooooooRoRLoooooooLoRoRoooLoooooooRoRRooooooRLLoooooooooooooooRoRoRoRLooooooooLoRoooooo ooRooRoooooRLooRooooRooooooooooLooooooRoooLooRooLLooooooooooooooooLooooLRooLoooRooooooooRooooooooRooRRoRoRoLooooooRooooooRoLooooooooooLoooLoooooLooLLoooRooLoooRoRoooRooRoooLoooooooLooooooooLooooRoooRoooooLooooLoLoRooooooooooLoooRoooRooooooooooRooLooooooooooooooRRoooooLoLRoooooooLooooooooooLooRoooooooooLLoLoooLoooooooooLoooooooooooooooooooooooRoooooooooRoooooooooooooLooLooRoooRLoooooooLoLoRoooooooooLRRoooooooRRoooooooLRoooooRoLoooRoooLoooooLoooLoRRoooLoooooooooooLooLooooRoooRoooRoLooooooooooooLoRoooooooLoooooooLRoLoooooooLoLoooooRLooooooooLoooRRooooooooooLooooooRooooLoooRooooooLLoooooooooooooLoooooooRLoooooooRooooooLoooooooooooooooooooooRooooRooRRRoooooooRLoooooooLoooooooRoooooLooLooLooooooooRoooooooooooooRooRooLooRooooooRoooRoooLooooRoooooooooooooooooRooRooLooooRooRoRoLooooLRooLooooooRoooooRoooooLoLooooooooRLoLRoooLLooooooooLoRooooooooooooRooooooLoRooooooooooRoooooooooooooRoRoooRoooLooLooRoooooooRoRoRooooooRooooooLoooooooLooRLoooooooooLoooRoLoooooooLLooooooRRooLoRoooLooooLoRLooooooooo
Output
998

Validator 12 Validator
Input
999 oooLoooLRooooooooooLooooooRRooRooooRooooooooLooooooooRoooRLooooooooooLRooooooLoooooLoRoooLoLooooLoRRoooooooooRooooRLRoooooRRoLoooooooLooooRooLooRLLoRooRooooRoRoooooooooLoooLoRLooLoooLoLoooooooooooRRoooooooooooooRoLoooooooooLRooLooooRoooRooooooLoooooLoRoLooooRoRoooRoooRRoLooooooooooooooooooooLRooRooooooLooLooooooooooooRoooooooLooRooooooooooooRoooooooooooooooLooooooooooooLoRooooooooooRoooooooRoRoooRRRooRRoooooooooooRoooRRooRoooLooRooooooooLoooooooooooooooooooLRoRRoooooooooooooLoooooRooooooooooooooooooooooooRooLRoooooLooRLoRooLoLooRooRLooRLoRRoooooooooooLRoRoRooooooooRooooRRoooooRooooooRLooooRRRooooRRoLooooooooooooooooooRoooRooooooooRoooLooooooLLooRRoRooooooooooooooooooooooooLooooooooooLoooRooooRLoooooooooLoooooooRRoLooooLooRoRooLoooRooooLooRoLLooooRRoLoooLRooooRRoooLoLooRooLoooLooLooRoRoooooooooooooooLooLooLRRLLoooooooooooLooLooLooooooLoooooooooooooooLoooLoooooLooooRoooRLLoooooLoLRoooooRoooooooRooRooooooLoLooooLRoooooooooLLoooooooLooooooooooRooooooooLoooooooRooLoooooooooooRRoRRooooooLoL ooooooLooRooRooooLooRoRRooooooooooooooooooLoRoooooooooooLRoooooLLoooooRRoooooooLooLoooooooooooooooooRRoooRooooLoRooooooLoooooRooooRooRoooLooooLooooooRoRLoooooLoRoLoRooRoooooooooooooLoooLoLooRRooRoooooRooooooLRoooLoooLLooooooLoooooooooooooLRoooRLooooRRRooooooooooooRooLoooooooRooooooooooooLRooooooooooooooooooooooooooooRRLoRoooooooooRooooooRooooRooRooooooLoLoooLRoooLooLoRoRRoooooRooRRoLoLoooLLooooRooLoooooRooooooRLoooooRoooooLoRooooooLRoooooLoRRRooRLooRoooooRoooLoLoooooooRooooooRoooooLooRooooRooRRoRoRoooLoRoooooLooRLoRoooooRooooooooooooooLooLooooooooooRoLRooooLoooRRoLooRRooooooooooRoooLRLoooooRoooooooRRoooooooRLoRoooLoRRoooLLoooooooLoLooooooooRooooooooLoooRoooooooooLRoooooLoooooooooLRoRRoooooooLLoooooLoLooooooLLoooooooooooooRoRooRoooLoRLooooooooLoLooooLoooooooooooooLoLooooooooooooooooRooRooooLoRLoooRRLRooooooRoooRoRooLoooLooooLoooLooooooooLooRooooooooooooooooLLoRLooRoRoooooooooooRRRoooooLRLooooLoRoooRooRoooooooooRoRLoooooooooLooooRRoooooooRooLLoooooooooLooooLoooLooRoLoRooooLoLooooRooooLo
Output
1000

Solution language

Solution

Stub generator input