A beam runs from position 0 to position length. Beetles sit on it at the distinct whole-number
positions positions (not necessarily in order), and heading[i] is "L" or "R": the
direction beetle i starts walking. Every beetle walks at 1 unit per second. When two beetles
meet head-on (possibly halfway between whole numbers), both turn around at that instant and keep
walking at the same speed. A beetle that reaches position 0 or position length falls off.
Write beam_falls(length, positions, heading) that returns a list with one tuple
(time, end) per beetle, in the same order as positions: the whole number of seconds after
which beetle i falls off and the end it falls from ("L" for position 0, "R" for
position length). Do not change the input list.
Examples
Input: length = 10, positions = [2, 5, 8], heading = "RLL"
Output: [(5, 'L'), (8, 'L'), (8, 'R')]
Explanation: the first two beetles meet at 3.5 after 1.5 seconds and turn round, so the beetle
from 2 walks back to 0, arriving at 5 seconds.
Input: length = 6, positions = [4, 1], heading = "RR"
Output: [(2, 'R'), (5, 'R')]
Input: length = 9, positions = [1, 2, 3, 4], heading = "RRRL"
Output: [(4, 'L'), (8, 'R'), (7, 'R'), (6, 'R')]
Constraints
2 <= length <= 10**40 <= len(positions) <= 300; positions are distinct and0 < positions[i] < lengthlen(heading) == len(positions), every character is"L"or"R"
Goals
- Replace a messy collision simulation by an equivalent simpler picture
- Use the fact that the beetles never change their left-to-right order
- Match answers back to the input order through each beetle's rank